Advent of Haskell, Part 1

//

This year is the first time that I participate in the Advent of Code. 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 again. Two days earlier I had already written the probably most imperative solution one could come up with.

$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 have 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 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.

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.

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.

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 and Hspec exists, so I’ll probably check one of them or both out soon.

See also in Advent of Haskell