# AdventofCode 2021: Day 3 Solution

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

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
solve2 x
$$$$

• Try adding some comments to your code so that someone would be able to figure it out just by looking at it. Commented Jan 16, 2022 at 0:53

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.