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

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

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

Zeta · Accepted Answer · 2022-04-04 17:39:53Z

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.

Stack Exchange Network

AdventofCode 2021: Day 3 Solution

1 Answer 1

Use types and functions from `base`

Prefer higher order functions over explicit recursion

Add to front and reverse all later

You must log in to answer this question.

Hot Network Questions

AdventofCode 2021: Day 3 Solution

1 Answer 1

Use types and functions from base

Prefer higher order functions over explicit recursion

Add to front and reverse all later

You must log in to answer this question.

Related

Hot Network Questions

Use types and functions from `base`