Advent of Haskell: Trying to solve puzzles without knowing Haskell

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

Comments

[Valts Liepiņš]

Heh, I happened to do exactly the same last year. I still use Haskell and it has become my go to langusge for personal projects!

As for testing, Haskell has this QuickCheck library, that allows defining some properties for your functions and QuickCheck will test them against randomized inputs.

[Philip Weinke]

Cool. I know QuickCheck from Go and just learned that it has its origin in Haskell.