This is a working solution to today's Advent of Code puzzle, written in Haskell. However, I feel like this solution is not optimal.
module BinaryDiagnostic (parseInput, part1, part2) where import Control.Monad (liftM2) import Data.List (group, maximumBy, sort, transpose) import Data.Ord (comparing) bin2dec :: String -> Integer bin2dec = foldl (\acc x -> acc * 2 + read [x]) 0 mostCommonElems :: (Ord a) => [[a]] -> [a] mostCommonElems = map (head . maximumBy (comparing length) . group . sort) . transpose bitNot :: String -> String bitNot = map (\bit -> if bit == '0' then '1' else '0') iterateMatch :: Eq a => ([[a]] -> [a]) -> [[a]] -> [a] iterateMatch criterion = head . snd . until ((== 1) . length . snd) iterator . (,) 0 where iterator (n, xs) = (n + 1, filter ((criterion xs !! n ==) . (!! n)) xs) part1 :: [String] -> String part1 = show . liftM2 (*) bin2dec (bin2dec . bitNot) . mostCommonElems part2 :: [String] -> String part2 xs = show $ bin2dec (iterateMatch mostCommonElems xs) * bin2dec (iterateMatch (bitNot . mostCommonElems) xs) parseInput :: String -> [String] parseInput = lines You can test this solution by running
part1 $ parseInput "00100\n11110\n10110\n10111\n10101\n01111\n00111\n11100\n10000\n11001\n00010\n01010" -- should return "198" part2 $ parseInput "00100\n11110\n10110\n10111\n10101\n01111\n00111\n11100\n10000\n11001\n00010\n01010" -- should return "230" I am particularly looking for improvement suggestions regarding the following:
- How can I make the code more readable in general? (especially the
iterateMatchfunction looks a bit hard to understand) - Can I use existing functions from common packages to simplify some operations?
- How can I remove the redundancy in the
part2function (and can it be pointfree)? Both operands of*do a very similar thing. - Are there any parts that could be significantly optimized in terms of runtime performance?
Just very briefly, below is the task. The complete puzzle is linked above.
The input is a line-separated list of binary numbers of fixed width, e. g.
00100 11110 10110 10111 10101 01111 00111 11100 10000 11001 00010 01010 For part 1, for each bit position (0 to 4), we need to find the most common bit (either 0 or 1). The most common bit for each of the 5 positions give us a new binary number γ. We do the same thing for the least common bits and get a binary number ε. For the example above, γ is 10110 and ε ist 01001. Their product (in decimal) is the solution for part 1, in this case 10110 (22) times 01001 (9) is 198.
For part 2, we again find the most common bit for each position. However, after every step, we eliminate the binary numbers that have the opposite bit at that position. We repeat that process until only one binary number is left (10111 in the example). The same thing for the least common bits give us another binary number (01010 in the example). Again, their product is the solution for part 2, in this case 10111 (23) times 01010 (10) is 230.
