advent of code, haskell

Advent of Code 2024 day 3

Day 3 required a data structure, some parsing, and a fold to handle when things should and shouldn't be included.

Data structure and parsing

I had a suspicion that the "junk" in the input might be useful, so I decided to keep it around. The input is either a mul term or a string of junk, so that was my initial data structure for terms.

data Term = Mul Int Int
          | Junk String
          deriving (Eq, Show)

I can parse that with Attoparsec and the parsers:

junkP = Junk <$> many1 anyChar
mulP = Mul <$> ("mul(" *> decimal <* ",") <*> decimal <* ")"

termsP = (++) <$> (many' junkP) <*> (mulP `sepBy` junkP)

Unfortunately, that doesn't work! The junkP parser will read any number of characters, including any following mul terms. To read the input, I needed to slow down junkP to read just one character at a time.

That gave the revised data structure of:

data Term = Mul Int Int
          | Junk Char
          deriving (Eq, Show)

and this parser:

junkP = Junk <$> anyChar
mulP = Mul <$> ("mul(" *> decimal <* ",") <*> decimal <* ")"

termsP = many' (mulP <|> junkP)

This parser tries to read a mul term; if it can't, it consumes just one character and tries again. That reads the input properly, returning a list of Mul or Junk.

Evaluating

Evaluating the parse input is simple: Mul terms get calculated, Junk terms become zero, and the whole lot is added together.

part1 :: [Term] -> In
part1 = sum . fmap evalTerm

evalTerm :: Term -> Int
evalTerm (Mul a b) = a * b
evalTerm _ = 0

Dos and Don'ts

Part 2 includes do and don't terms. Those need to be added to the data structure and parser.

data Term = Mul Int Int
          | Junk Char
          | DoTerm
          | DontTerm
          deriving (Eq, Show)

junkP = Junk <$> anyChar
doP = DoTerm <$ "do()"
dontP = DontTerm <$ "don't()"
mulP = Mul <$> ("mul(" *> decimal <* ",") <*> decimal <* ")"

termsP = many' (choice [mulP, doP, dontP, junkP])

Note that choice tries parsers in order, so the real terms are tried before we resort to calling a character junk.

Given all the Mul, Do, and Dont terms, I need to switch off the correct Mul terms. That's a foldl' over the list of terms, keeping track of both whether to include Mul and the set of Mul terms included so far. It has to be a left fold, as the order (left to right) of the terms matters.

There are four cases:

  1. Including Mul terms and I've found one: add it to the list of found Muls.
  2. Reached a DontTerm: turn off including future Muls.
  3. Reached a DoTerm: turn on including future Muls.
  4. Anything else: leave the state unchanged.
enabledMuls :: [Term] -> [Term]
enabledMuls terms = snd $ foldl' go (True, []) terms
  where go (True, ts) (Mul a b) = (True, Mul a b : ts)
        go (_, ts) DontTerm = (False, ts)
        go (_, ts) DoTerm = (True, ts)
        go (c, ts) _ = (c, ts)

This returns the enabled Mul terms in reverse order, but as I'm only summing them it doesn't matter.

part2 = sum . fmap evalTerm . enabledMuls

Code

You can get the code from my locally-hosted Git repo, or from Codeberg.