Advent of Code 2021 day 3

This one had lots of fiddling around, quite a bit of which was trying to persuade Cabal to use the version of ghc installed by ghcup.

As for the problem, the data structures here are a bit of a mess. We're given a set of strings, we need to find sets of total, and then use a predicate to convert them to sets of booleans.

Yes, bits and bytes are built-in data types, but I don't think using them would be an advantage.

The first step is to use digitToInt to convert the input strings into lists of numbers.

main :: IO ()
main = 
  do  numStrs <- readFile "data/advent03.txt"
      let bits = map (map digitToInt) $ lines numStrs
      print $ part1 bits
      print $ part2 bits

For the example in the problem text, bits will be a list of 13 elements, each being a list of 5 numbers.

Next is to find, for each column, which bit is the majority. I answer a slightly more precise question: "which columns have at least as many '1's as '0's?" I do that by adding up all the columns, finding how many are needed to be "half or more" and seeing which columns meet that criterion.

I can add two lists of numbers with zipWith (+), so zipWith (+) [1, 2, 3] [3, 4, 5] becomes [4, 6, 8]. Adding all the bits becomes a foldr1. There's a bit of fiddling to find the threshold number for determining what's "half", but identifying the columns is mapping a predicate over the totals.

findMajorities :: [[Int]] -> [Bool]
findMajorities allBits = map (>= threshold) columnSums
  where addBits = zipWith (+)
        columnSums = foldr1 addBits allBits
        (t, m) = (length allBits) `divMod` 2
        threshold = if m == 1 then t + 1 else t

I use that to find gamma and epsilon.

part1 :: [[Int]] -> Int
part1 allBits = gamma * epsilon
  where majorities = findMajorities allBits
        gamma = bitsToNum majorities
        epsilon = bitsToNum $ map not majorities

bitsToNum :: [Bool] -> Int
bitsToNum bits = foldl' includeBit 0 bits
  where includeBit n True  = n * 2 + 1
        includeBit n False = n * 2   

For part 2, I started by writing oxygenFilter directly, then generalising it into partFilter that could be called by both oxygenFilter and coFilter. That was easy because of the details of how to break ties in both cases.

The partFilter is given the current set of numbers to examine, and the current index of interest. The function finds the majorities in each column and then the value of bit I'm interested in at that position. I then filter the numbers based on whether they have the desired bit. (It's a fiddly task description, so a fiddly explanation, but it ends up with some simple code.)

oxygenFilter :: [[Int]] -> Int -> [Bool]
oxygenFilter = partFilter id

coFilter :: [[Int]] -> Int -> [Bool]
coFilter = partFilter not

partFilter :: (Bool -> Bool) -> [[Int]] -> Int -> [Bool]
partFilter filterFunc allBits n 
  | length allBits == 1 = majorities
  | otherwise = partFilter filterFunc filteredBits (n + 1)
  where majorities = findMajorities allBits
        filterValue = if (filterFunc $ majorities !! n) then 1 else 0
        filteredBits = filter (\bs -> bs !! n == filterValue) allBits

Comments

This could have been an error-prone problem. It wasn't because Advent of Code team did a good job of making a problem that was easy to solve, because of a difficult-to-write description, and very clear and useful examples. Well done, team!

Code

You can get the code from my locally-hosed Git repo, or from Gitlab.