Advent of Code Day 8 [spoilers]

Day 8's puzzle was basically just about parsing a long list of integers correctly, and writing tree-recursive functions correctly. Both are pretty easy in Haskell.

I defined the tree object like this, although the "num*" fields are technically redundant:

data Tree = Tree {
  numChildren :: Int,
  numMetadata :: Int,
  children :: [Tree],
  metadata :: [Int]
  } deriving (Show)

The parsing comes in two parts: one function to parse a tree, and a helper function to parse the correct number of child trees (as specified by the parent tree's number of children nc.) I still haven't figured out parser combinators, so this does the work "by hand" of returning the unparsed portion of the list.

parseTree :: [Int] -> (Tree, [Int])
parseTree (nc:nm:rest) =
  let subtreeParse = parseNumberOfTrees nc [] rest in
    let children = fst subtreeParse
        remaining = snd subtreeParse in
      (Tree nc nm children (take nm remaining), (drop nm remaining))

parseNumberOfTrees :: Int -> [Tree] -> [Int] -> ([Tree],[Int])
parseNumberOfTrees 0 ts is = (ts, is)
parseNumberOfTrees numTrees ts is =
  let nextTree = parseTree is in
    parseNumberOfTrees (numTrees - 1) (ts ++ [(fst nextTree)]) (snd nextTree)

I really wish it was as easy in Haskell to unpack a tuple as it is in Python. Instead of the let-expression I used here to get children and remaining I could have used a case statement to do it in... the same number of lines. I feel like I'm missing something about the best way to do multiple-returns in Haskell. (I could pass in a continuation, I guess?)

I didn't check that I had completely parsed the tree; when we're done the second return value should be the empty list:

-- FIXME: check for empty list after parsing --
realTree = fst (parseTree (map read (words input)))

Part one asks us to sum all the metadata values, that's easy to do recursively. We don't even need a base case.

sumMetadata :: Tree -> Int
sumMetadata (Tree _ _ children metadata) =
  (sum metadata) + (sum (map sumMetadata children))

Part two is a more complicated way of adding up the values, by using the metadata as pointers into the child trees. Again pretty simple; we just have to use guards to check for invalid indices.

treeValue :: Tree -> Int
treeValue (Tree 0 nm [] metadata ) = sum metadata
treeValue (Tree nc _ children metadata ) =
  sum (map (childValue nc children) metadata)

childValue :: Int -> [Tree] -> Int -> Int
childValue numTrees ts i
  | i < 1 = 0
  | i > numTrees = 0
  | otherwise = treeValue (ts !! (i - 1))

Full solution: https://github.com/mgritter/aoc2018/blob/master/day8/day8.hs

I didn't think I learned much from today. Day 9 was a beast, though, in terms of understanding Haskell's memory management so maybe that will be a more interesting writeup.

Advent of Code Day 8 [spoilers] | Ecency