Advent of Code 2024

Today is Haskell day. Haskell is a lazily-evaluated, purely functional language with automatic currying.

Lazy evaluation means that everything is computed when we ask for it. Among other things, that makes it fine to define a list like ones = 1:ones (: conses a head onto a linked list), and then you can use it like take 5 ones. take 5 only evaluates the first 5 heads and then returns them, so it doesn't matter that the list never actually ends.

Automatic currying means that there essentially aren't functions with more than 1 parameter. take has type Int -> [a] -> [a] (a is a type variable); take 5 has type [a] -> [a], and take 5 ones has type [Int].

Haskell also leans very hard into strict type-checking, enough so that a surprising amount of incorrect code simply does not compile. Weeding through type errors can sometimes be challenging, but once you do, it gives vastly more confidence in the program than it does in most statically typed languages.

Haskell is an absolutely gorgeous language. Its biggest flaw in my opinion is just how much the community tends to prefer very short, and often punctuation-only, names for functions and variables.

Part 1

The first task is to read in a file where each line is of the form k: x y z ..., and return the sum of all ks that can be computed from combining their x y z .... The values are combined by going through each number left-to-right and either adding it to the running total, or multiplying it with the running total. For example, 9: 1 2 3 is valid, because 1 + 2 * 3 (when evaluated left-to-right, without BEDMAS) equals 9.

We can begin by defining a type for each line. This will allow us to represent lines like Operation 9 [1, 2, 3]:

data Operation = Operation Int [Int]

Now we can use that type in our main function. Haskell separates side effects at the type-level, so any function that does IO has to return a value in the IO monad. I won't really explain this right now because it's difficult to explain, and we don't have to get into it very much, but just know that main returns IO () (like a void function in C), parseFile returns an IO [Operation] (a list of Operations in the IO monad, and using do at the start of main lets us write operations <- parseFile "..." to have operations be just an [Operation] inside main. Don't worry about it too much.

We also use the & function, which is commonly known as a pipeline operator, and is spelt |> or -> in other languages. x & f & g is the same as g (f x)). This works especially well with Haskell's lazy evaluation: we can process a list with successive functions that all evaluate elements as needed, so we aren't doing successive runs over the entire list.

main :: IO ()
main = do
  operations <- parseFile "2024/input/day-07.txt"
  operations
    & filter isValid
    & map (\(Operation target _) -> target)
    & sum
    & print

So, we read operations with parseFile and unpack it from the IO monad, then filter out the elements whose values can't be made to combine into their target, then extract just the targets, sum them, and print the result.

The file parsing isn't too bad:

parseFile :: FilePath -> IO [Operation]
parseFile filePath = do
  content <- readFile filePath
  let linesOfFile = lines content
  pure $ map parseLine linesOfFile

We read the file content, unpack it from the IO monad, call lines to get a list of lines (we have to unpack it first because lines' first argument is a String, not an IO String), and then parse each line. Because parsing the lines only gives us an [Operation], we need to use pure to lift the value into the IO monad. $ here just saves us from typing brackets around the call to map.

parseLine is a pure function that doesn't do any IO; it just takes a String and returns an Operation. We use splitOn to split the line on a colon and extract the before and after parts, use words to split the values by spaces, and use read to read integers from the strings:

parseLine :: String -> Operation
parseLine line =
  let (targetPart : valuePart : _) = splitOn ":" line
      target = read targetPart
      values = map read (words valuePart)
   in Operation target values

With that out of the way, we can move onto isValid. We'll take the straightforward approach and just generate options for combining the values with a generateOperations function, then check if evaluating any of those options equals the target with an evaluate function. Here, we use where, which is like let, except that we place the definitions after:

isValid :: Operation -> Bool
isValid (Operation target values) = any (evalsTo target) options
  where evalsTo x ops = x == evaluate ops
        options = generateOperations $ reverse values

When you think of injecting operators between successive elements of a list to combine them, you should be thinking of fold, AKA reduce, since that's what it does: reduce(+, [1,2,3]) means 1 + 2 + 3. We'll use this approach and represent our combinations as lists of (Int, Operator) pairs, where Operator is a type we'll define to hold the possible operations, Add, Multiply, and an additional Id that will just be used for the first element so that it starts the accumulator off with itself. In generateOperations, we use a list comprehension to generate the possibilities:

data Operator = Id | Add | Multiply

generateOperations :: [Int] -> [[(Int, Operator)]]
generateOperations [] = []
generateOperations [x] = [[(x, Id)]]
generateOperations (x:xs) =
  [((x, op) : rest) | rest <- generateOperations xs, op <- [Add, Multiply]]

evaluate :: [(Int, Operator)] -> Int
evaluate = foldr calculate 0
  where
    calculate (x, Id)       _   = x
    calculate (x, Add)      acc = acc + x
    calculate (x, Multiply) acc = acc * x

Part 2

For the second puzzle, we only need to add support for a 3rd kind of operator we can insert: a concatenation operator that combines its arguments like strings, eg concat(12, 34) is 1234. The obvious thing to do is very inefficient, but it's such a simple change, I can't resist. All we need to do to get it working is add the new operator to the Operator type:

data Operator = Id | Add | Multiply | Concat

Include it in the list of operations to pull from in generateOperations:

generateOperations (x:xs) =
  [((x, op) : rest) | rest <- generateOperations xs, op <- [Add, Multiply, Concat]]

And add one more calculate clause inside evaluate:

calculate (x, Concat) acc = read (show acc ++ show x)