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
coFilter. That was easy because of the details of how to break ties in both cases.
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!