# 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 =
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