Whilst browsing hacker news the other day, I stumbled upon this cool blog post which mentioned the advent of code. What exactly is this advent? It’s a series of programming challenges released in the countdown to Christmas. To help me get back into my machine learning scholar adventure and coding generally, I decided to take part and build momentum.
For Day 1: Report Repair, the first puzzle was to find out which two numbers in a list added together to 2020. To verify you had the right answer, you would provide the product of these two numbers. So for example, if the list of numbers was 921, 785, 459, 1079, 888, 514 the numbers would be 921 and 1079 with the product being 993759. When I first read the problem, the basic steps that came to mind were:
- Form pairs of all the numbers
- Go through each pair to see which added up to 2020
- Multiply that specific pair to get the product
Since the problem brief came with a simple example with the correct answer, I would start there. If I could get an algorithm to get the same answer as the simple example, I was confident it would work for the actual problem.
Now how was I going to form the pairs? I’d whip out python’s list comprehensions which I’d used before to generate combinations of numbers ?
With pairings secured, my journey to puzzle heaven was off to a solid start. Now, I was confronted with the next conundrum. How was I going to narrow down the numbers in this list? I could clearly see some pairings which involved repeated numbers e.g. (1721, 1721) so I chose to start cutting those down first. Why? At this point, I only wanted numbers with no duplicates in the pairing.
Great! I’d removed the duplicates but could see that another form of duplication was still present. For example, (1721, 979) and (979, 1721) were still present. I also realised that my condition was not great…what if numbers appeared twice in the list e.g. (1010, 1010) which would add to 2020. Could I do something about this? I tried googling but nothing specific/simple to implement was showing up ??♂️ Then I remembered a way to filter out a bunch of these tuples! How? By implementing my 2nd step: check which pairs added up to 2020 as the comprehension condition!
Boom! I had the same answer as given in the example! The only tuples that were left added up to 2020. Multiplying them together gave 514579 just like in the example. It seemed like my algorithm was working so it was time to read in the input numbers, apply my algorithm and solve this ting.
After tidying up my code to take in the input numbers (and doing some renaming), I executed the code and got the correct answer! However, it wasn’t over yet! My submission unlocked part two. Fortunately, it was a very similar puzzle, all I had to do was find three numbers which added to 2020. I quickly turned my current code into a function and modified it for the three number case.
After running my special_triple function, I entered my candidate answer…and solved the problem ?? Day 1 was now complete!
With both gold stars under my belt, It was time for a victory dance.
Solving this puzzle taught/reminded me that:
- It’s more efficient to sketch out what a solution could look like before coding
- Working with the simplest case helps as a check and aids understanding of the problem
- Google is a coding friend, helped me to remember some list comprehension syntax
- Using an online repl is great for fast problem solving
- Solving problems is fun!
Here’s a github repo of my solutions 🙂