Advent of Code in Haskell: T Minus 16

Posted on Nov 15, 2020

Introduction

For the past few years I’ve been trying to learn haskell in various ways but have never been able to stick to the method, let alone actually “become productive” in Haskell.

Since I’ve decided to spent more time on tinkering during the evenings, I thought it would be a nice idea to document my learning process.

The general idea is that I will do the challenges from the Advent of Code (2020 edition) and implement them in Haskell. And since there are 16 days left before “it begins”, I’ll kick off with doing some of the challenges from last year to prepare.

The documentation part will not really involve the learning of the language itself, but more on “everything ephemeral” (the plumbing?). I’ll try to elaborate on some of the “typical difficult Haskell stuff” as I encounter them (and when I deem them appropriate).

I’m convinced that Haskell in itself is quite an easy language to grasp (once you manage to get “some functional programming practices to click”), but that there are a number of barriers that prevent people from becoming productive in it.

Getting setup

During this attempt to grasp Haskell I will be working on my Windows 10 laptop under WSL2 running an Ubuntu 20.04 installation. My notes will assume that a sort of sane setup for an editor is available.

I use vim myself, with a fairly minimal vimrc (no haskell specific configuration) and the following packages:

ale/ coc.nvim/ fzf/ ultisnips/ vim-go/ vim-repeat/ vim-surround/ vim-vinegar/

To get started I installed the GHC compiler through the default Ubuntu package manager:

sudo apt-get install ghc

And then verified that installation has succeeded by running

> ghci --version
The Glorious Glasgow Haskell Compilation System, version 8.6.5
> ghc --version
The Glorious Glasgow Haskell Compilation System, version 8.6.5
> cabal --version
cabal-install version 2.4.0.0
compiled using version 2.4.0.1 of the Cabal library

This ensured that all binaries are properly available (in path) to get going.

The Advent of Code

For those who do not know, The Advent of Code (TAOC) is a yearly event in which 50 programming assignments are made available during the first 25 days of december, outlining a glorious story usually involving santa, elves, presents and the (not so) daily challenges they face.

Every day two programming challenges are presented that take a certain input (your daily input file) and require you to do StuffTM with that input to accomplish a certain task. Don’t worry, it will all become clear when you actually try this.

You can register on https://adventofcode.com.

Kicking the tires, day 1

With the environment setup I create a fresh directory for the first day:

mkdir -p taoc19/day1

and paste my input for the first challenge into taoc19/day1/input.txt

Since I’m not trying to do anything fancy right now, I create a new cabal package with the cabal init command. During the interrogation cabal gives me, I stick with the defaults, except when asked whether I’m building a package or executable, in which I choose ‘executable’.

This gives me a few files that I can use to start building.

To start the process I need to get my data from the input.txt file into a function. Since I’ve read something about Haskell before (and some quick googling) I try using the readFile function (from the stdlib/Prelude) in GHCi and voila:

let raw = readFile "input.txt"

The problem arises when I put the let raw = readFile 'input.txt' line in my main do-block. Haskell has this notorious Monad thing going on, which I do not yet fully grasp. But you don’t need to understand it to use it, so a small Google session quickly led to the insight that I need to “reverse arrow put” the result of the readFile call into a variable instead of using let. This leads to a really minimal Main.hs file

module Main where

main :: IO ()
main = do
        raw <- readFile "input.txt"
        print raw

when loadng it into GHCi and running main, it nicely outputs my input data. First win achieved!

Prelude> :l Main.hs
[1 of 1] Compiling Main             ( Main.hs, interpreted )
Ok, one module loaded.
*Main> main
<your data here>

Step two involves splitting up the input into lines and converting these lines into an array of integers.

To accomplish the first step, Haskell has a handy function lines (in the Prelude) available. The second part involves the read function (also a Prelude thing) and specifying the type of the statement. Initially I created a separate function stoi for this

stoi :: String -> Int
stoi = rread

but decided that “casting” the data inline would still be perfectly readable (and perhaps even clearer), resulting in:

module Main where

main :: IO ()
main = do
        raw <- readFile "input.txt"

        -- since lines does not take an IO <something> but a regular String
        -- we do not use the do ... <- syntax here, but put it in a variable
        -- directly.
        let ls = lines raw

        -- we want to have an [Int], so map the read function over the lines.
        let nums = map read ls :: [Int]

        print nums

Achievement 2 unlucked, I’m finally ready to do something with my data.

Part 1 of the challenge involves calculating how much fuel we need according to a certain formula, so for every input we apply a function to it, and sum the results.o

module Main where

fuelRequired :: Int -> Int
fuelRequired = id -- todo

main :: IO ()
main = do
        raw <- readFile "input.txt"

        -- since lines does not take an IO <something> but a regular String
        -- we do not use the do ... <- syntax here, but put it in a variable
        -- directly.
        let ls = lines raw

        -- we want to have an [Int], so map the read function over the lines.
        let nums = map read ls :: [Int]

        -- apply the fuelRequired function to all the inputs and sum the result
        let totalFuel = sum $ map fuelRequired nums
        print totalFuel

which if we load it into GHCi gives us the sum of all the weights.

*Main> :edit
[1 of 1] Compiling Main             ( Main.hs, interpreted )
Ok, one module loaded.
*Main> main
9961383
*Main>

The actual calculation of required fuel involves dividing the weight by 3, rounding it down and subtracting 2, giving me a really simple to implement fuelRequired function.

-- fuelRequired should be the mass x, divided by 3, minus 2
-- with a minimum of 0.
fuelRequired :: Int -> Int
fuelRequired x = max 0 $ (div x 3) - 2

Running the main file in GHCi again (after reloading the Main.hs file) gives me a number that, when entered in the answer field on AOC tells me I’m on the right track! Yay!

Day 1, part 2

Oh, surprise, physics kicks in. Turns out, fuel weighs something as well, so we’ll have to calculate the amount of fuel required to carry the fuel, which also requires fuel to carry, etc.

This looks like a typically recursive situation where fuel that requires no fuel (i.e. weighing 9 or less) serves as a perfect termination case. Let’s try to write this as a recursive function with a guard in it.

-- recursiveFuelRequired is implemented as a recursive function
-- where we terminate recursion as soon as there is no more
-- fuel required for a certain component.
recursiveFuelRequired x
        | x == 0    = 0
        | otherwise = let thisFuel = fuelRequired x in
                        thisFuel + recursiveFuelRequired thisFuel

and then calculating the actual total fuel required in the same way as before, but now with this new recursive function:

let totalFuel = sum $ map recursiveFuelRequired nums
print totalFuel

output copy-paste into solution field, press submit, and… GREAT SUCCESS!

I’ll cover my solving of the Day 2 challenges somewhere in the upcoming days.