# Post-Christmas Advent of Code In Haskell - Day 1

07 Jan 2019This year, for the first time, I tried to follow the annual Advent of Code coding challenge series. In case you haven’t heard about it, here is an excerpt from its about page:

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as a speed contest, interview prep, company training, university coursework, practice problems, or to challenge each other.

It began with nice little tasks that I could solve with relatively little effort. After some days however the challenges got more and more involved and i was unable to find the time to work on them. Each day there is a new challenge so the unsolved ones started to pile up which I found a bit demotivating.

Now that *Advent Of Code 2018* is over I decided to return to the challenges but instead
of just solving them I will try to also explain *how* I am solving them in Haskell. Hopefully
some people will find this useful.

### A Short Note On Nix

I ♥ Nix - so I also use its wonderful Haskell integration. This isn’t really relevant in the context of this series but I wanted to briefly mention it anyway. You can have a look at the relevant default.nix. Some notes:

- It picks
`ghc863`

as compiler. - It declares a little ghcid script.
- It uses callCabal2nix for creating a nix derivation from a cabal file.
- It uses shellFor to provide a shell environment with everything we need (including the ghcid script).

There is also a shell.nix which just refers to the
shell from the `default.nix`

file and is automatically picked up from `nix-shell`

calls.

**TL;DR**: If you have nix installed you can just run `nix-shell`

to get a working development environment.

### Day 1 / Part 1

Go here for the full description of the challenge. Looking at the following examples should suffice to understand what we need to do though:

```
+1, +1, +1 results in 3
+1, +1, -2 results in 0
-1, -2, -3 results in -6
```

Our input is a sequence of numbers that we have to “combine” to a single number (is it me or does it suddenly smell very monoidal in here?). First things first though: Let us start with reading in the input.

#### Reading the input

Reading the input data is of course just a matter of calling readFile.
Unfortunately all the numbers are prefixed with either `-`

or `+`

. If we want to use read we’ll get into trouble:

```
Prelude> read "3" :: Integer
3
Prelude> read "-3" :: Integer
-3
Prelude> read "+3" :: Integer
*** Exception: Prelude.read: no parse
```

We need to skip the `+`

signs. We can just peek at the start of the string to check if it is
a `+`

or not and then act accordingly:

```
toNum :: String -> Integer
toNum str@(s:ss) = if s == '+' then read ss else read str
```

#### Combining the input

Now that we know how to read the file and parse the numbers we can think about how to perform the actual calculation. All we really need to do is to sum up all the numbers. For this we can use a combination of foldMap and Sum:

```
calibrate :: String -> Integer
calibrate = getSum
. foldMap (Sum . toNum)
. lines
```

This is a neat little composition. Let’s go over it step by step (starting at the end because composition goes right to left):

`lines :: String -> [String]`

: the numbers in the input data file are`\n`

separated to lets split them up`foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m`

: We fold over our list of strings (`t a`

) using`(Sum . toNum)`

(`a -> m`

), and get back`Sum Integer`

(`m`

).`getSum :: Sum a -> a`

: unwraps our Integer from the Sum.

#### Solution To Part 1

Putting it all together we can write a module like the following:

```
module Day1 where
import Data.Monoid
toNum :: String -> Integer
toNum str@(s:ss) = if s == '+' then read ss else read str
calibrate :: String -> Integer
calibrate = getSum
. foldMap (Sum . toNum)
. lines
solvePart1 :: FilePath -> IO Integer
solvePart1 file = calibrate <$> readFile file
```

We can use the `solvePart1`

function to get our answer:

```
Day1> solvePart1 "./day1.input"
477
```

### Day 1 / Part 2

The second part of the challenge is about finding the first value that occurs twice when continuously adding up values from the input stream. If we reach the end of the input before finding a repetition we have to wrap around and continue from the start of the list:

```
<input> → <steps> → <result>
+1, -1 → [0 , 1, 0] → 0
+3, +3, +4, -2, -4 → [0, 3, 6, 10, 8, 4, 7, 10] → 10
-6, +3, +8, +5, -6 → [0,-6,-3,5,10,4,-2,1,9,14,8,2,5] → 5
+7, +7, -2, -7, -4 → [0,7,14,12,5,1,8,15,13,6,2,9,16,14] → 14
```

So let’s think about this for a moment:

- Obviously we want to read the file contents and convert number strings using
`toNum`

again. - We have to work on a repeated sequence of the input since we don’t know how soon the repetition will occur (→ repeat).
- We need to operate on all intermediate results of adding up values from the input (→ scanl).
- Going through the data we need to keep track of whether or not a value has already occurred (→ Set from the
`containers`

package).

#### Constructing The Input Sequence

Given the same input data we want to obtain a sequence that contains all intermediate addition results:

```
buildSequence :: String -> [Integer]
buildSequence = scanl (+) 0
. join
. repeat
. (fmap toNum)
. lines
```

Again we are only composing functions to reach our goal:

`lines :: String -> [String]`

: split the`\n`

separated string.`(fmap toNum) :: [String] -> [Integer]`

: Turn the strings into numbers.`repeat :: [Integer] -> [[Integer]]`

: Create an infinite repetition of the list.`join :: [[Integer]] -> [Integer]`

: Collapse the list of lists to a list.`scanl (+) 0 :: [Integer] -> [Integer]`

: Fold the list using addition while keeping all successive reduced values.

We now have an *infinite* list that contains the intermediate results of adding up cycles of
the input data into all eternity. We can use this to find the first value that occurs twice.

#### Looking For Repetition

As mentioned before we are going to use a `Set`

to keep track of values that have
already occurred while going through our list. When a value is not already in the Set
we add the value to the Set and carry on with the remainder of the list. If the value is in our Set we have found the first repetition and are done:

```
findRep :: String -> Maybe Integer
findRep xs = go (buildSequence xs) (Set.fromList [])
where
go :: [Integer] -> Set.Set Integer -> Maybe Integer
go [] _ = Nothing
go (x:xs) s = if x `Set.member` s
then (Just x)
else go xs (Set.insert x s)
```

### Solution To Part 2

All in all we can add the following code to our existing module to solve the second part of this challenge:

```
import Control.Monad (join)
import qualified Data.Set as Set
buildSequence :: String -> [Integer]
buildSequence = scanl (+) 0
. join
. repeat
. (fmap toNum)
. lines
findRep :: String -> Maybe Integer
findRep xs = go (buildSequence xs) (Set.fromList [])
where
go :: [Integer] -> Set.Set Integer -> Maybe Integer
go [] _ = Nothing
go (x:xs) s = if x `Set.member` s
then Just x
else go xs (Set.insert x s)
```

Thanks to lazy evaluation we can just operate on the infinite list
that we create in `buildSequence`

. The manual recursion in `findRep`

determines how much of the list needs to be evaluated – which is
as many elements as it takes to hit the first repetition.

## That’s All Folks!

This concludes my first post on this blog and in this series. I hope it might be useful for people who are new to Haskell and are looking for more than just a GitHub repository containing solutions.

That being said there are a lot of great Haskell developers out there who published all of their solutions so don’t hesitate to look at them and learn from them.

*PS: The repository containing all the code is here.*