Advent of Code 2024 day 7

I was expecting day 7 to be a challenge (being the first proper puzzle on a weekend) and … it wasn't.

I didn't bother making a new data type for the calibrations, and parsing was simple.

type Calibration = (Int, [Int])

calibrationsP = calibrationP `sepBy` endOfLine
calibrationP = (,) <$> decimal <* ": " <*> (decimal `sepBy` " ")

Extending and checking

Checking each calibration is a combination of a fold and concatMap. It's easier to think about what's happening if we imagine we're part-way through the process of checking a calibration.

I'm working left-t0-right across the list of terms in the calibration, building up a list of running totals as I go. Consider the calibration 292: 11 6 16 20: after I've handled the first three terms, there are four partial totals:

• 11 + 6 + 16 = 33
• 11 + 6 * 16 = 272
• 11 * 6 + 16 = 82
• 11 * 6 * 16 = 1056

For each of those, I need to produce two new running totals: the total + 20, and the total * 20. That's a map over the running totals, but I want to flatten the results into a list, rather than a list of lists; that makes it concatMap.

extendOne partials next = concatMap go partials
  where go p = [p + next, p * next]

The fold over the terms is a basic foldl', but I take the first term and turn it into a singleton list.

extend  (x:xs) = foldl' extendOne  [x] xs

A calibration is valid if the target is one of the extensions.

isValid  (target, factors) = target `elem` extend factors

Part 2

Part 2 introduced another operator, concatenation. That meant a change to extendOne:

extendOneC partials next = concatMap go partials
  where go p = [ p + next
               , p * next
               , read (show p ++ show next)
               ]

I could have done something complicated with typeclasses and polymorphism to avoid code duplication, but it's only two lines to duplicate!

isValidC (target, factors) = target `elem` extendC factors
extendC (x:xs) = foldl' extendOneC [x] xs

This takes a bit longer to execute, but still not long. I could optimise it by removing duplicate partial solutions in extendOne, and removing partial solutions that are already larger than the target. I could also spread the checking over multiple cores. But this version is quick enough and I can't be bothered.

Code

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