AdventofCode 2021: Day 3 Solution

Question

I am beginner to Haskell. Here is my solution to Advent of Code 2021 Day 3. Let me know what you think. I was looking at the transpose function and decided not to use head & tail function.

Given the data

00100 11110 10110 10111 10101 01111 00111 11100 10000 11001 00010 01010 

Problem 1 create a new binary number with most common bit in each column. Create a second binary number with least common bit in each column. The binary number with most common bit is 10110 & least common bit is 01001. Convert them to integer and multiply 22 * 9 = 198

Problem 2: It's similar to problem 1. Find the most common bit in 1st position. Assume it is 1. Discard the list with least common bit i.e. 0, then find the most common bit in second position maybe it is 0 discard the list with 1 in second position. So eventually the new list would have 10111. i.e. 23

Using the above method find the least common bit at every position discarding the list with most common bit at that position. 01010b can be converted to 10 multiply the 2 and answer is 230.

{-# OPTIONS_GHC -Wno-incomplete-patterns #-} module Main where import qualified Data.Array as A import Text.Printf (printf) import qualified Data.Foldable as Foldable import qualified Data.List as List solve ::[[Char]] -> Int solve [] = 0 solve x = datafind $ solve' $ List.transpose x --- solve' is a helper function which would call find function solve' :: [[Char]] -> [(Int, Int)] solve' [] = [] solve' (x:xs) = (find (0, 0) x : solve' xs) --- find method calculates the total number of 1 & 0's in column. and add to the tuples find:: (Int, Int) -> [Char] -> (Int, Int) find x [] = x find (a, b) ('1':xs) = find (a + 1, b) xs find (a, b) (_: xs) = find (a, b+1) xs --- Creates the binary array of most common and least common number in column datafind :: [(Int, Int)] -> Int datafind arr = datafind' [] [] arr where datafind'::[Int] -> [Int] ->[(Int, Int)] -> Int datafind' a b [] = binaryToDecimal2 a * binaryToDecimal2 b datafind' a b ((g, e):xss) | g >= e = datafind' (a ++ [1]) (b ++ [0]) xss | otherwise = datafind' (a ++ [0]) (b ++ [1]) xss --- converts binary to Integer binaryToDecimal2 ::[Int] -> Int binaryToDecimal2 x = sum $ List.zipWith (\x y -> (2 ^ x) * y ) [0..] $ reverse x ------- Solve 2 solve2 ::[[Int]] -> Int solve2 arg0 = (binaryToDecimal2 $ oxygen [] arg0) * (binaryToDecimal2 $ co2 [] arg0) --- Carbon emission function co2 ::[Int] -> [[Int]] -> [Int] co2 acc [] = acc co2 acc [x] = acc ++ x --- if has last element add to the binary list co2 acc arg0 =solveco2 acc arg0 (findpopular unpopular arg0) --- Oxygen emission function oxygen :: [Int] -> [[Int]] -> [Int] oxygen acc [] = acc oxygen acc [x] = acc ++ x --- if has last element add to the binary list oxygen acc arg0 = solveoxy acc arg0 (findpopular popular arg0) --- --- get oxygen emission 1st parameter is accumulator and second is the data and the third is the most common bit that needs to be filtered solveoxy ::[Int] -> [[Int]] -> Int -> [Int] solveoxy acc [] _ = acc solveoxy acc arg0 arg1 = oxygen (acc ++ [arg1]) (solve220 arg1 arg0 ) --- get carbon emission 1st parameter is accumulator and second is the data and the third is the least common bit that needs to be filtered solveco2::[Int] -> [[Int]] -> Int -> [Int] solveco2 acc [] _ = acc solveco2 acc arg0 arg1 = co2 (acc ++ [arg1]) (solve220 arg1 arg0 ) --- the functions filters the list on prefix and removes the empty list solve220 :: Int -> [[Int]] -> [[Int]] solve220 arg00 arg01= filter (not.null) . map solve221 $ filter (\x -> List.isPrefixOf [arg00] x) arg01 solve221 ::[Int] -> [Int] solve221 [] = [] solve221 (_:xs) = xs --- Gets the most common bit & least common bit in the column from head --- get the first column and find the most common & least common bit findpopular :: ((Int, Int) -> [Int] -> Int) -> [[Int]]-> Int findpopular f arg0 = f (0, 0) (mytranspose arg0) where mytranspose::[[Int]] -> [Int] mytranspose arg00 = mytranspose' $ List.transpose arg00 mytranspose'::[[Int]] -> [Int] mytranspose' [] = [] mytranspose' (x:xs) = x --- get most common bit in the column popular ::(Int, Int) -> [Int] -> Int popular (a, b) [] | a >= b = 1 | otherwise = 0 popular (a, b) (1: xs) = popular (a + 1, b) xs popular (a, b) (_: xs) = popular (a, b+ 1) xs --- gets the least common bit in the column unpopular ::(Int, Int) -> [Int] -> Int unpopular (a, b) [] | b > a = 1 | otherwise = 0 unpopular (a, b) (1: xs) = unpopular (a + 1, b) xs unpopular (a, b) (_: xs) = unpopular (a, b+ 1) xs readInput :: FilePath -> IO[[Int]] readInput = fmap (map readNum .lines ) .readFile readNum ::[Char] -> [Int] readNum = map (\x -> if x == '0' then 0 else 1 ) main::IO() main = do arr <- lines <$> readFile "input01.txt" printf "hello world" 

The solution can be run by copying the puzzle to a file and running

----- solution 1 x <- lines <$> readFile "filename" solve x ----- solution 2 x <- readInput "filename" solve2 x ```

Answer 1

Great work on adding type signatures to all functions. Type signatures make reviewing your code a lot easier. So let's get to it!

Use types and functions from base

String is an alias to [Char], so lets use that one to reduce the amount of [brackets].

Next, we can see that solve' is map (find (0, 0)). Many trivial recursive have some building block in base, e.g. map, foldr, foldl, zip. So, before we change solve', let us have a look at find

Prefer higher order functions over explicit recursion

The find function is slightly unfortunate: it forces the external caller to use (0, 0) for the first argument. The caller always needs to use the correct argument. That's error prone.

So, the first change we should take here is to use an internal helper and change find's type:

find:: String -> (Int, Int) find = go (0, 0) where go x [] = x go (a, b) ('1':xs) = go (a + 1, b) xs go (a, b) (_: xs) = go (a, b + 1) xs 

Now we see that this is a reducing function: a list gets reduced to a single value. The first tool in our box for this is usually foldr:

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b 

With foldr, we get

find:: String -> (Int, Int) find = foldr go (0, 0) where go '1' (a, b) = (a + 1, b ) go _ (a, b) = (a , b + 1) 

That's a lot shorter. Also, some special rules on foldr . map will improve our code's performance a lot.

With these, our initial section ends up as

solve :: String -> Int solve [] = 0 solve x = datafind . solve' . List.transpose $ x where solve' = map find find = foldr go (0, 0) go '1' (a, b) = (a + 1, b ) go _ (a, b) = (a , b + 1) 

Add to front and reverse all later

Appending to a list is \$\mathcal O(n)\$. So building a list by appending to the end repeatedly is \$\mathcal O(n^2)\$. Instead, try to either cons (:) the new value and work with the reversed list, or reverse the list after building it. If the order is required throughout the algorithm, you might want to use another data structure.