Advent of Haskell: Trying to solve puzzles without knowing Haskell
Tags: adventofcode, haskell, functional
Published: 2020-12-05 15:10:10

This year is the first time that I participate in the [Advent of Code](https://adventofcode.com/). What I learned right on the first day was that some people would finish the whole puzzle while I was still sipping on my morning coffee reading the assignment. I like challenges but I don't know whether I can compete with what's going on in the leaderboard. So, I thought it might be a good idea to add a personal challenge to keep it fun. Functional programming is an area where I have quite a few knowledge gaps so that seemed like a perfect fit. When I think of functional programming, Haskell is always one of the first things that comes to my mind. That made the language choice easy: I'm learning Haskell.

## Let's go

Here's my starting position:

- I haven't written a single line of Haskell before.
- I haven't even read much Haskell or any other purely functional code before.
- I do know some FP concepts and I'm also trying to incorporate them into my work. But after all, I'm just an OOP guy.

I went back to solve the [first puzzle](https://adventofcode.com/2020/day/1) again. Two days earlier I had already written the probably most imperative solution one could come up with.

```php
$input = array_map(
    fn(string $input) => (int)$input,
    explode("\n", file_get_contents('input'))
);

for ($i = 0; $i < count($input); $i++) {
    for ($j = $i + 1; $j < count($input); $j++) {
        if ($input[$i] + $input[$j] === 2020) {
            printf("%d\n", $input[$i] * $input[$j]);
            break;
        }
    }
}

for ($i = 0; $i < count($input); $i++) {
    for ($j = $i + 1; $j < count($input); $j++) {
        for ($k = $j + 1; $k < count($input); $k++) {
            if ($input[$i] + $input[$j] + $input[$k] === 2020) {
                printf("%d\n", $input[$i] * $input[$j] * $input[$k]);
                break;
            }
        }
    }
}
```

The thing is: As inelegant as this code may be, I didn't had to think about it. I read the assignment and it just came out like it was some mechanical reflex. With Haskell, however, there was no way **for me** to solve it without thinking.

With a rough idea of "something with recursion" I skimmed through a few sections of [Learn You a Haskell](http://learnyouahaskell.com/) and jumped into the REPL to play around. After a bit of warming up I made a plan: Build a list of tuples that contain the sum and product of all possible combinations and filter for the right answer. That sounded like something I could get done. In the REPL, I was able to get some working single bits I needed to solve the whole thing. So, I started plugging it together.

For some reason, I tried to get the type signatures for all functions right when I switched from the REPL to the editor. I don't even know why. It turned out to be a bad idea. I spent a ridiculous amount of time messing around, getting errors that were precise and confusing at the same time. At some point I simply dropped all the type signatures and one half of the errors just went away. The other half was actually an error because I was mixing integers and tuples in one part. After fixing it and cleaning up a bit, I eventually ended with the following solution. A little bit proud that I made it, I committed the code and went to bed.

```haskell
module Main where

toTuple x = (x, x)

listToTuple x = map toTuple x

combine a b = (fst a + fst b, snd a * snd b)

combineTwo [] = []
combineTwo (x:xs) = (map (combine x) xs) ++ combineTwo xs

combineThree [] = []
combineThree (x:xs) = (map (combine x) (combineTwo xs)) ++ combineThree xs

withSum x y = map snd (filter ((==x).fst) y)

main = do
  input <- getContents

  let numbers = map read (lines input) :: [Integer]

  print (withSum 2020 (combineTwo (listToTuple numbers)))
  print (withSum 2020 (combineThree (listToTuple numbers)))
```

## Couldn't I do better?
The proudness only lasted until the next evening. Was this really the best I could come up with? I tried to simplify the code by eliminating all the tuple stuff and it worked well for the first part of the puzzle.

```haskell
module Main where

value a b = if a + b == 2020 then a * b else 0

combineTwo [] = []
combineTwo (x:xs) = filter (/=0) (map (value x) xs) ++ combineTwo xs

main = do
  input <- getContents

  let numbers = map read (lines input) :: [Integer]

  print (combineTwo numbers)
```

But I couldn't wrap my head around how to get it done with a combination of three. I figured that I wanted to be able to build combinations of `n` of a given list, but I was unable to express it with my Haskell rookie knowledge. Obviously I couldn't do better (yet), so I gave up, searched the net and found [a solution](https://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n/8626006#8626006).

```haskell
module Main where

import Data.List

combinations 0 lst = [[]]
combinations n lst = do
    (x:xs) <- tails lst
    rest   <- combinations (n-1) xs
    return $ x : rest

value x = if sum x == 2020 then product x else 0

findValue lst = filter (/=0) (map value lst)

main = do
  input <- getContents

  let numbers = map read (lines input) :: [Integer]

  print (findValue (combinations 2 numbers))
  print (findValue (combinations 3 numbers))
```

I like the result, although I have a feeling that there is still some room for improvement. But I've already spent hours on the first puzzle, so it's time to move on.

## What's next?

I purposely started this adventure without studying any material before just to see how it goes. It went okay but I definitely noticed that I am lacking a proper foundation. Before moving on to the next puzzle, I'll spend at least some time actually reading - not just skimming - some introductory material.

As someone who does TDD all the time, it also feels weird to have no tests in place. I know that [HUnit](https://hackage.haskell.org/package/HUnit) and [Hspec](https://hspec.github.io/) exists, so I'll probably check one of them or both out soon.