Day 1 - Rusty at start

by Elmar Wachtmeester |

Haskell is my language of choice for the annual Advent of Code event. Most people probably don't know what I'm talking about. Within the developer community, it might be known a bit more, but even there a lot of people might not know it. So let me explain, Advent of Code is an annual competition held for the sixth time this year. It is a coding competition held over a period of 25 days. One assignment each day, hence the name Advent of Code, named after the Advent calendar. Well, actually each daily assignment consists of two parts, with each part you can earn a star. So in total 50 stars can be earned. The theme for all assignments is of course Christmas. Something in the line of the elves making all sorts of devices to help Santa Claus save Christmas, this year we are helping Santa to get a well deserved holiday.

Why should you (as a developer) also enter this contest? Well to win of course.... Or maybe there are other reasons why you could join. Let me start with a fair warning, if you are in for the win you have a big challenge, the people in the top are very fast, for the first few days people will have solved the challenge in the time it would take me to only read through the problem statement. For example day 1 (part 1) of last year's competition has about as much text in the explanation as there is text in this article so far, the fastest time it was solved was in 23 seconds. But you can have your own private leaderboards in which you can still compete, I personally have my goal set to be in the top 5 of ING's leaderboard (the company I work for.) Other reasons include:

  • Learning a new language. Some people say you should at least learn a new language each year, so why not with the Advent of Code
  • Find out how good (or bad) you are in comparison to your peers
  • Learn about new algorithms
  • Get out of your day to day routine work

It could also be a mixture of some of the reasons above like it is for me. My plan is to write a series about my experience with this year's challenge. I will try to go over how I solved the problem, what pitfalls I got in solving the problem or while learning the language. Explains some of the interesting parts of the language that are worth sharing. Also after the solve, I like to see how I could have written my code better. Since this is a series, please let me know what you think about it. How I can improve, what should I leave out, what should I add, etcetera.

Learning a new language is the main reason for doing the competition, last year I started with Rust, this year it is Haskell for me. A big difference with last year is that the language is not completely new to me like Rust was. I had already written a few pet projects in Elm, which has its roots in Haskell, so that got me interested in Haskell. So halfway through this year, I had already decided about Haskell being my language for this year's Advent, and I have already played around with it for some time a few months back. Last few months I hadn't gotten around to put the time into it. So today when I started with the challenge quite cold again I really noticed that I had already forgotten about the basics, and although I did figure out how to solve it, it was really hard to put it in code. Ok, but after quite a long intro for this series, let's dive into it.....

Day 1

Santa wants to go on holiday but needs to have 50 stars to do so. On day 1 you can earn a star for each part. For part 1 you have to find two numbers from a list of numbers that add up to 2020. If you find these two numbers you have two multiply them and that would be your answer. Usually, there is some small example input to explain the problem, which could be used to run a test of your code. The actual input for the challenge can be found via a download link, this will get a much larger set of data, which is personalized for you. The list of test numbers is 1721, 979, 366, 299, 675, 1456. Adding up the first with the fourth number will give you 2020. So the final answer will be 514579 (1721 times 299.)

To solve this I would start with the first number and check that against all the other numbers in the remainder of the list to see if they add up to 2020. If that doesn't work out, I would drop the first number and start the process over again. In Java, the language I use in my job, this could easily be solved with two loops. In Haskell, an idiomatic way to solve this is with the use of recursion.

In my first attempt, I created two functions, one to loop over the array and separate the first number from the remainder of the list. The second function to check if they add up.

The solve function takes an array as input, which is split up by pattern matching into the first element x and the remainder of the list. We call our second function to check if the first number meets our criteria against one of the other numbers in the list. We check with an if-statement whether the check function returns a positive number, which would be our answer, so we would return that answer by calling the function again. This was going to be optimized later, but I couldn't remember the correct way to do it. If the number is not positive we call the solve function with the remainder of the list (by use of the tail function.)

solve (x:xs) = if ((check x xs) > 0) then check x xs else solve (tail xs)

check n (y:ys) = if n+y == 2020 then n*y else check n ys

The check function takes two arguments, the first (n) is the number we are going to check. The second argument is the remainder of the numbers, which are again split into the first number of the remainder (y) and the remainder of the remainder (ys). With the if-statement, we check if the sum is 2020 and if so return n times y, which is our answer, otherwise we recurse into the other elements of the list to check them against n.

There is more code to it than I just described, but I will not go into that, since the main part happens in these functions. Let us give it a try (against the example input)

*main> main
Part 1: 514576

That's looking promising, that's the answer we expect for the example input. Let us run it with the actual input

*main> main
Part 1: *** Exception: aoc2020-1:6:1-56: Non-exaustive pattern in function check

That doesn't look good. It tells me that one of the patterns cannot be matched. Remembering how this worked, the pattern matching on (x:xs) or (y:ys) needs at least one element in the list to make the split. It will split in the one element in y and an empty array in ys. This is recursively going to call itself with an empty array, which can't be split by the current pattern. We need to add a second pattern to match the empty array case.

check n (y:ys) = if n+y == 2020 then n*y else check n ys
check _ [] = 0

The first argument is replaced by _ since it is not needed in the implementation. The second argument is the empty array. So in the case where we call our check function with an empty array, the second definition will match and return 0. Let's see what happens.

*main> main
Part 1: *** Exception: aoc2020-1:4:1-73: Non-exaustive pattern in function solve

We have seen that before, still the same error. Or maybe it isn't... it now is on our solve function. So I tried different things from here, got different errors, but was not able to get a working solution. So I took a step back to look at my problem again, what was I trying to solve. We need to find a pair of two numbers that add up to 2020. Wait a minute, I've create a helper function for creating a list of all the pairs in a list while working on Haskell a few months back. We'll try to use that.

solve = check . pairsHalf

check ((x , y): xs) = if x + y == 2020 then x * y else check xs

Two functions again, solve which calls our helper function and feeds that into our check function. The name pairsHalf might seem a bit weird, but it comes from all the combinations in a half competition. The check function uses an if to see if our sum condition is met and returns the answer, otherwise it recuses into the remainder of the list. I'm using an if here instead of guards, which might be the more idiomatic way because I couldn't remember how to do it. Running this code against our example gives the correct result again. So lets test it on our competition input.

*Main> main
Part 1: 751776

Feeding this answer into the website of Advent of Code gives us a congratulations message, yes!! Let's continue with part 2 of the day. Now instead of finding two numbers we hava to find three numbers that add up to 2020. The final answer will be the product of these three numbers. In the example, the three numbers that add up to 2020 would be 979, 366, 675 which would give the product 241861950. To get to that solution we have to make a new version of the pairsHalf function that would create triplets of all possible combinations in a list. The implementation of the pairs functions looks like this

pairsHalf :: [a] -> [(a, a)]
pairsHalf xs = [(x,y) | (x:ys) <- tails xs, y <- ys]

Cool (or not), it uses list comprehension, which is a very powerful tool, but something I don't use every day, so I'm not very familiar with (yet). To enhance this into an extended version I first have to understand it (again), so let's break this down a little bit:

  • (x,y) - the output function of the list comprehension. It creates a tuple of x and y.
  • (x:ys) <- tails xs - a generator function, which loops over the result of the tails function with the input xs as parameter. Each element is assigned to the pattern (x:ys) which breaks the list into the first element and the remainder.
  • y <- ys - the second generator function which loops over every element of ys, but will do this for every element produced by the first generator.

To clarify this explaination a little bit, lets go over a simple example:

xs = [1,2,3,4]
tails xs = [[1,2,3,4],[2,3,4],[3,4],[4]]
Generator 1 iteration 1: x = 1, ys = [2,3,4]
  Generator 2 iteration 1: y = 2, (x,y) = (1,2)
  Generator 2 iteration 2: y = 3, (x,y) = (1,3)
  Generator 2 iteration 3: y = 4, (x,y) = (1,4)
Generator 1 iteration 2: x = 2, ys = [3,4]
  Generator 2 iteration 1: y = 3, (x,y) = (2,3)
  Generator 2 iteration 2: y = 4, (x,y) = (2,4)
Generator 1 iteration 3: x = 3, ys = [4]
  Generator 2 iteration 1: y = 4, (x,y) = (3,4)
Generator 1 iteration 34 x = 4, ys = [] no input for the 2nd generator,   no output.
The final output will be [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]

To extend this into a triplet version, we should add a third variable z, and extend this with a third generator.

triplesHalf :: [a] -> [(a, a, a)]
triplesHalf xs = [(x,y) | (x:ys) <- tails xs, (y:zs) <- tails ys, z <- zs]

Using this instead of our pairsHalf function (and some small modifications in the addition and multiplication) gives us the expected result of 241861950. So let's put this the test on the input set.

*Main> main
Part 1: 751776
Part 2: 42275090

Checking this on the website gives us our much desired second star!!! So curious as how I'm doing on our ING leaderboard. 8th place, not too bad considering how Rusty I was on putting everything together, but not in line with my goal of being in the top 5, but plenty of days to fix that. A weird thing happened, looking at the leaderboard later that morning showed no scores at all... They had been removed because the server of Advent of Code had been down, which I had already noticed while trying to download the input set. I had ignored it, but and just started coding and downloaded it later. But they did have a point that it didn't give a fair chance to everyone. At first, I was kind of bummed that my score was gone but later realized that it would give me a new chance for getting in the top 5 on the next day.

Thanks for reading along with my Advent adventures, please share your thoughts on the article, so I can improve along with the series. And if you code yourself, consider joining the competition yourself. See you tomorrow on the next day of Advent of Code