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
```

• NY can: Try adding some comments to your code so that someone would be able to figure it out just by looking at it.

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.