AOC2021 D1-D3 in Haskell

Haskell

Haskell is a great functional programming language and it’s not my first time coding with it.

About ten years ago when I just started college, a senior classmate @overmind, who is a genius in PLT area, intruduced it to me with a great passion. He gave me several Haskell tutorials and I also finished the book Learn you a Haskell for great good.

But unfortunatelly, as a guy who just started learning C in his undergraduate courses, Haskell is too damn hard for me to handle at that time.

Now after ten years, I gradually feel that Haskell seems not to be that hard. So I decided to pick it up again with some exercises since the aoc this year shows up just in time.

Get Started

My learing material is basically the combination of the following three notes:

stanford cs 240h

learn you a Haskell for great good

Haskell wiki

They solve my know how, know what and know why problems mutually.

At beginning the first problem I met is setting up the development toolchain, which is not quite friendly to Manjaro, the os I’m using, which is based on the Arch Linux.

I do feel confused about how I could install a single package at first. It seems that the Haskell + Arch = Hell on Earth.

Here is the story:

1. Arch only supports dynamic linking when compiling Haskell, I don’t know the reason, maybe it matches Arch philosophy better. (also it means if a package depends on haskell reated stuff, what added to your system is dymamic Haskell things)
2. So if I do not use any of the package manager, I can install libraries naming haskell-* from AUR but I can only use them by ghc -dynamic when compiling, which is not user-friendly for myself. I do need the static linking.
3. Good news is, though no stuff like haskell-static-*, there is a static AUR package called ghc-static which provides an alternative static global package database, though limited. So if I want to use a package not contained in the ghc-static, I still need to figure out a way.

Then, to solve the package install issue, I need to set up a package manager.

Stack, a Haskell package manager who follows the philosophy of Nix, is great, but works too hard for my case. My toy code doesn’t need a sandbox toolchain that is designed to host big Haskell projects. The most important thing stack want to deal with is the reproducible building, which I do not care currently. There is no need to setup a yaml file with tons of other configs for my ~10 lines of code.

(btw, I still installed stack to use Hakyll, the framework of this blog.

Cabal looks better to do globally setup and the AUR also provides a cabal-static do deal with static linking stuffs.

So my plan looks simple: using stack for large projects by providing isolated dependecies while cabal for my toy codes which needs global package configuration.

However, the current cabal-static package isn’t compatible with ghc 9.0.1, which means I have to install cabal-install instead and use dynamic linking, during which you have to tell cabal to use dynamic linking by -ghc-options=-dynamic.

Therefore, I currently have to choose one of the following way to install a new Haskell package:

• cabal install --ghc-options=-dynamic -lib <package>, then compile by cabal -dynamic <file.hs>

or

• stack install --global <package>, then compile then compile by stack ghc <file.hs>

The second may have a better way after modifying global stack configure, but haven’t figured it out yet.

Day1

The Problem

1. Part1: Given a list of numbers, count how many times the latter number is bigger than the previous number.
2. Part2: Same input and same counting problem, but three numbers as a group to do the comparison.

The Code

import System.IO
import Control.Monad

c :: [String] -> [Int]
c = map read

f a = calc 0 a
    where calc sum (a':b':xs)
            | null xs == True = if b'>a' then sum +1 else sum
            | b' > a' = calc (sum+1) (b':xs)
            | otherwise = calc sum (b':xs)

fn a = calc 0 a
    where calc sum (a':b':c':d':xs)
            | null xs == True = if b'+c'+d'>a'+b'+c' then sum +1 else sum
            | b'+c'+d'>a'+b'+c' = calc (sum+1) (b':c':d':xs)
            | otherwise = calc sum (b':c':d':xs)
main = do
    handle <- openFile "./day1.input" ReadMode
    contents <- hGetContents handle
    print $ f $ c $ words contents
    print $ fn $ c $ words contents

    hClose handle

Walk Through

1. words::String -> [String]

   whitespace characters are treated as separator

2. map read n :: [String] -> [Int]

   map a [b] means for all b, do a $ b

3. calc::[Int] -> Int

   tail recursion function, recursive until the last run

To Improve

1. the base case of recursion looks still massy, try remove the if/elif/else and merge them into the recursion logic.
2. try convert function c into a anonymous function.

Day2

The Problem

1. Part1: Given input as a group of turble (“up/down/forward”, distance), calculate the final moving distance.
2. Part2: Same input as previous, but the “up/down” only influences the moving rate when “forward”.

The Code

import System.IO
import Control.Monad

f a = calc 0 0 a
    where calc forward up (a':b':xs)
            | null xs == True = (forward + read b') * up
            | a' == "forward" = calc (forward + read b') up xs
            | a' == "up" =  calc forward (up - read b') xs
            | a' == "down" =  calc forward (up + read b') xs

fn a = calc 0 0 0 a
    where calc forward up aim (a':b':xs)
            | null xs == True = (forward + read b') * (up + aim * read b')
            | a' == "forward" = calc (forward + read b') (up + aim * read b') aim xs
            | a' == "up" = calc forward up (aim - read b') xs
            | a' == "down" = calc forward up (aim + read b') xs

main = do
    handle <- openFile "./day2.input" ReadMode
    contents <- hGetContents handle
    print $ f $ words contents
    print $ fn $ words contents

    hClose handle

Walk Through

Same strategy as Day1 with tail recursion.

I simplify the base case becase I checked the input data and find the last input is always “forward” so there is no need to if/elif/else in the last case, which is a tricky.

To Improve

Same as Day1

Day3

Problem

1. Given an 1000x12 array filled by either 0 or 1, find out the most common used and most least common used number per column.
2. Same input but a little complicated: find the most common used number in the first column, remove all rows doesn’t satisfiy, then do the same thing to the next column until only one number left. Also one more time using least common strategy.

The Code

import System.IO
import Control.Monad
import Data.List
import Data.Maybe

c :: [String] -> [Int]
c = map read

digits :: Int -> [Int]
digits n = map (\x -> read [x] :: Int) (show n)

repeatNTimes :: Int -> a -> [a]
repeatNTimes 0 _ = []
repeatNTimes n x = x : repeatNTimes (n - 1) x

makeup n | length n == 12 = n
          | otherwise = repeatNTimes (12 - length n) 0 ++ n

mostFrequent :: [Int] -> Int
mostFrequent ns =
  snd (maximum [ (length ks, head ks) | ks <- group (sort ns) ])

leastFrequent :: [Int] -> Int
leastFrequent ns =
  snd (minimum [ (length ks, head ks) | ks <- group (sort ns) ])

convert :: [Int] -> Int
convert n = calc 0 n
    where calc r' (n':xs)
                | null xs == True = r' * 2 + n'
                | otherwise = calc (r' * 2 + n') xs

f n  = gammaRate * epsilonRate where
    orderedNum = transpose $ map makeup $ map digits $ c n
    gammaRate = convert $ map mostFrequent orderedNum
    epsilonRate = convert $ map leastFrequent orderedNum

---

rm x v p = if x!!p == v then Nothing else Just x

rmByIndex :: [[Int]] -> Int -> Int ->[[Int]]
rmByIndex n v p = mapMaybe (\x -> rm x v p) n

findMcbRef n = map mostFrequent $ transpose n

findLcbRef n = map leastFrequent $ transpose n

rmLoopByMcb n index | length n == 1 = n
  | otherwise = rmLoopByMcb (rmByIndex n (ref!!index) index) (index + 1) where ref = findMcbRef n

rmLoopByLcb n index | length n == 1 = n
  | otherwise = rmLoopByLcb (rmByIndex n (ref!!index) index) (index + 1) where ref = findLcbRef n

fn n = o2Rate * co2Rate where
    orderedNum = map makeup $ map digits $ c n
    o2Rate = convert $ head $ rmLoopByMcb orderedNum 0
    co2Rate = convert $ head $ rmLoopByLcb orderedNum 0


main = do
    handle <- openFile "./day3.input" ReadMode
    contents <- hGetContents handle

    print $ f $ words contents
    print $ fn $ words contents

    hClose handle

Walk Through

1. digits :: Int -> [Int]

   1. map an Int means operate its digits one by one,
   2. the show will convert current digits into a String, but when there is one Char in a String, it becomes Char.
   3. to covert it back to Int, we need read :: String ->Int who only accepts String as input, therefore we change Char into [Char], then it becomes a String (i.e. Char array) but just for solving the paramter type issue (from my understanding).

2. For a 2D array, the best way to handle column data is to convert it into row data by matrix transposition after padding enough ’0’s at beginning.

3. The second part is also tail recursion. Keep ‘count -> compare -> remove -> next digit’ until only one number left.

To Improve

Too many repeated methods, should be organized into better functions, DRY.

Conclusion

The functional programming really makes you dealing with things more concisely and usually the functional way is more scalable.

But it is difficult to come up with the best design at first, you need to change your mind from the step into the monad.

Personally, I do enjoy the process of figuring it out and it’s better to keep coding while studying the concepts and theories.