## DEV Community is a community of 601,801 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Discussion on: Advent of Code 2020 Solution Megathread - Day 7: Handy Haversacks

flwidmer

I start to like parsing these kind of rules in Haskell, it's very intuitive to me.
The association list was a nice fit for this problem; had I done it in Java, I would have used a Map with Lists as a value. Even though it's not the most time efficient approach, it was allright for this size problem.

``````solve1 :: String -> Int
solve1 input =
let assocList = createInvertedMap \$ map parseRule \$ lines input
recursion = recurse1 assocList "shinygold"
in length \$ nub recursion

recurse1 :: [(String, String)] -> String -> [String]
recurse1 assocList search  =
let current = lookupAll assocList search
next = concatMap (recurse1 assocList) current
in current ++ next

solve2 :: String -> Int
solve2 input =
let assocList = map parseRule \$ lines input
recursion = recurse2 assocList "shinygold"
in recursion

recurse2 :: [(String, [(String, Int)])] -> String -> Int
recurse2 assocList search  =
let current = concat \$ lookupAll assocList search
next = sum \$ map recurseValue current
in sum (map snd current) + next
where recurseValue (bag, multiplier) = multiplier * recurse2 assocList bag

-- parse one line into an association list
parseRule :: String -> (String, [(String, Int)])
parseRule a =
let keyValue = splitOn " contain " a
key = concat \$ take 2 \$ words \$ head keyValue
value =map parseContains \$ splitOn "," \$ keyValue !! 1
in (key , value)

-- "contain 2 shiny gold bags." -> ("shinygold", 2)
parseContains :: String -> (String, Int)
parseContains "no other bags." = ("none", 0)
parseContains a =
let removePeriod = filter (/= '.') a
noBags = filter (\x -> x /="bags" && x /= "bag") \$ words removePeriod