3
\$\begingroup\$

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 iterateMatch function 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 part2 function (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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.