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.