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


    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!


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

    Neil Smith

    Read more posts by this author.