You know it’s true

Thanks to Cameron Barrett for the find! Tap to view at full size.

Of course, the proper comeback is: jeffy is not in the sudoers file. This incident will be reported...TO MOM!

Programming What I’m Up To

My solution to Advent of Code 2020’s Day 1 challenge, in Python


December has arrived, and so has the great programming exercise known as the Advent of Code!

Think of it as an Advent calendar, but chocolates (or cheese, or wine), you’re presented with a new programming puzzle every day between the start of December and Christmas Day, in which you try to save Santa’s mission. You can use whatever programming language you want, and you don’t need to be an expert — as the site says, “just a little programming knowledge and some problem solving skills will get you pretty far.”

Advent of Code started in 2015, and has been taking place every year ever since. The 2020 edition began on Tuesday, December 1st at 12:00 midnight Eastern time (UTC-5).

Not only do I plan on participating in this year’s Advent of Code, but I might even use a couple of the challenges in the Python class I’m currently teaching on behalf of Computer Coach.

You have to sign in to play

In order to take on Advent of Code’s challenges, you have to sign in using an account from one of these popular “federated ID” services:

  • Github
  • Google
  • Twitter
  • Reddit

This is for a couple of reasons:

  • Signing in makes it easier for the site to keep track of your progress. Advent of Code is structures so that you must successfully complete challenge n before taking on challenge (n+1).
  • While everyone has to solve the same problem, each user gets their own (presumably) unique data set.

Once you’ve signed in, you can start on the first challenge…

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 1 challenge.

The Day 1 challenge, part one

Here’s the text from part one of the challenge:

Day 1: Report Repair

After saving Christmas five years in a row, you’ve decided to take a vacation at a nice resort on a tropical island. Surely, Christmas will go on without you.

The tropical island has its own currency and is entirely cash-only. The gold coins used there have a little picture of a starfish; the locals just call them stars. None of the currency exchanges seem to have heard of them, but somehow, you’ll need to find fifty of these coins by the time you arrive so you can pay the deposit on your room.

To save your vacation, you need to get all fifty stars by December 25th.

Collect stars by solving puzzles. Two puzzles will be made available on each day in the Advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!

Before you leave, the Elves in accounting just need you to fix your expense report (your puzzle input); apparently, something isn’t quite adding up.

Specifically, they need you to find the two entries that sum to 2020 and then multiply those two numbers together.

For example, suppose your expense report contained the following:

In this list, the two entries that sum to 2020 are 1721 and 299. Multiplying them together produces 1721 * 299 = 514579, so the correct answer is 514579.

Of course, your expense report is much larger. Find the two entries that sum to 2020; what do you get if you multiply them together?

Here are the expense numbers that were provided for my account:

I decided to use a Jupyter notebook running a Python kernel solve the problem.

Importing the data

My first step was to copy the numbers above, paste them into a triple-quoted string, and assign that string to the variable raw_input:

Now that I had the data in a string, I could split the string into an array, using the newline character as the delimiter. I named the array split_input:

split_input is an array of strings which needed to be converted into integer values.

In many other languages, I’d do this by using the map function to apply a “convert a string to its integer value” function to every item in the array, creating a resulting array called expenses. Here’s the Python version of that approach:

It works, but from a Python programming point of view, it just doesn’t feel right.

The Pythonic approach would involve using a list comprehension instead of map (and then using the resulting iterator into a list). It just seems more readable:

Now that I had the expenses in a Python list (that’s Pythonese for “array”), I could work with them.

Combinations to the rescue!

Once again, the goal of the challenge was to find the two numbers in the expense report whose sum was 2020.

To solve this problem, we need a way to generate all the possible combinations of two numbers taken from the list. I could write this code, but Python’s itertools module has a combinations() method that can do just that.

Here’s a quick demo of combinations() in action. Given a list containing a small number of integers, it generates a list of the possible 2-number combinations you can get from the list, without repetition (that is, a number can’t appear more than once in any combination):

itertools also has a combinations_with_replacement() method. Rather than tell you what it does, let me show you:

With that in mind, I used combinations() to generate a list of all the possible two-number combinations in expenses, which I assigned to a variable named all_expense_pairs:

Now that we have all the possible two-number combinations from the expense report, we can try to find the one(s) whose numbers add up to 2020.

Any time you’re in a situation where you need to find values in an array that match some criteria, you should think about applying a filter() function. I did just that: I used a filter() to extract a list of only those pairs summed to 2020…

The resulting list had one tuple, (1387, 633), whose values sum to 2020. I entered the product of these two numbers — 877971 — and completed the first challenge.

The Day 1 challenge, part two

Here’s the text from part two:

The Elves in accounting are thankful for your help; one of them even offers you a starfish coin they had left over from a past vacation. They offer you a second one if you can find three numbers in your expense report that meet the same criteria.

Using the above example again, the three entries that sum to 2020 are 979366, and 675. Multiplying them together produces the answer, 241861950.

In your expense report, what is the product of the three entries that sum to 2020?

Had I solved the problem from first principles, the solution might have taken a lot of extra work. Thanks to the use of itertools.combinations(), the solution for part two took three lines of code:

Once again, the resulting list had one tuple, (867, 264, 889), and its values, added up, were 2020. I entered the product of these three numbers — 203481432 — and completed the second challenge.

Feeling simultaneously proud and soiled

Thanks to Python (and remembering that it had a library that could do combinations and permutations),  I made a personal best in solving the Day 1 puzzles. I’m pretty pleased, but at the same time, I did so little work that it feels as if I’ve cheated. I may have to try solving the problem from first principles — if I have the time.

Other days’ solutions:

Here are my solutions for other days in Advent of Code 2020: