Advent of Code

Advent of Code: Solving Your Puzzles With Python

by Geir Arne Hjelle Dec 01, 2021 basics testing

Advent of Code is an online Advent calendar where you’ll find new programming puzzles offered each day from December 1st to the 25th. While you can solve the puzzles at any time, the excitement when new puzzles unlock is really something special. You can participate in Advent of Code in any programming language—including Python!

This tutorial will help you get started with solving puzzles and earning your first golden stars.

In this tutorial, you’ll learn:

  • What an online Advent calendar is
  • How solving puzzles can advance your programming skills
  • How you can participate in the Advent of Code
  • How you can organize your code and tests when solving Advent of Code puzzles
  • How test-driven development can be used when solving puzzles

Advent of Code puzzles are designed to be approachable by anyone with an interest in problem-solving. You don’t need a heavy computer science background to participate. Instead, Advent of Code is a great arena for learning new skills and testing out new features of Python.

Puzzling in Programming?

Working on puzzles may seem like a waste of your available programming time. After all, it seems like you’re not really producing anything useful and you’re not advancing your current projects forward.

However, there are several advantages to taking some time off to practice with programming puzzles:

  • Programming puzzles are usually better specified and more contained than your regular job tasks. They offer you the chance to practice logical thinking on problems that are less complex than the ones you typically need to handle in your day job.

  • You can often challenge yourself with several similar puzzles. This allows you to build procedural memory, much like muscle memory, and get experience with structuring certain kinds of code.

  • Puzzles are often designed with an eye towards a solution. They allow you to learn about and apply algorithms that are tried and tested and are an important part of any programmer’s toolbox.

  • For some puzzle solutions, even the greatest supercomputers can be too slow if the algorithm is inefficient. You can analyze the performance of your solution and get experience to help you understand when a straightforward method is fast enough and when a more optimized procedure is necessary.

  • Most programming languages are well-suited for solving programming puzzles. This gives you a great opportunity to compare different programming languages for different tasks. Puzzles are also a great way for getting to know a new programming language or trying out some of the newest features of your favorite language.

On top of all of this, challenging yourself with a programming puzzle is often pretty fun! When you add it all up, setting aside some time for puzzles can be very rewarding.

Exploring Options for Solving Programming Puzzles Online

Luckily, there are many websites where you can find programming puzzles and try to solve them. There are often differences in the kinds of problems these websites present, how you submit your solutions, and what kind of feedback and community the sites can offer. You should therefore take some time to look around and find those that appeal the most to you.

In this tutorial, you’ll learn about Advent of Code, including what kind of puzzles you can find there and which tools and tricks you can employ to solve them. However, there are also other places where you can get started solving programming puzzles:

  • Exercism has learning tracks in many different programming languages. Each learning track offers small tutorials about different programming concepts, coding challenges, and mentors that give you feedback on your solutions.

  • Project Euler has been around for a long time. The site offers hundreds of puzzles, usually formulated as math problems. You can solve the problems in any programming language, and once you’ve solved a puzzle, you get access to a community thread where you can discuss your solution with others.

  • Code Wars offers tons of coding challenges, which they call katas. You can solve puzzles in many different programming languages with their built-in editor and automated tests. Afterward, you can compare your solutions to others’ and discuss strategies in the forums.

  • HackerRank has great features if you’re looking for a job. They offer certifications in many different skills, including problem-solving and Python programming, as well as a job board that lets you show off your puzzle-solving skills as part of your job applications.

There are many other sites available where you can practice your puzzle-solving skills. In the rest of this tutorial, you’ll focus on what Advent of Code has to offer.

Preparing for Advent of Code: 25 Fresh Puzzles for Christmas

It’s time for Advent of Code! It was started by Eric Wastl in 2015. Since then, a new advent calendar of twenty-five new programming puzzles has been published every December. The puzzles have gotten more and more popular over the years. More than 170,000 people have solved at least one of the puzzles from 2020.

In traditional Advent calendars, you open one door every day to reveal what’s inside. Advent of Code mimics this by letting you open one puzzle each day from December 1st to December 25th. For each puzzle you solve, you’ll earn golden stars that are yours to keep.

In this section, you’ll get more familiar with Advent of Code and see a glimpse of your first puzzle. Later, you’ll look at the details of how you can solve these puzzles and practice solving a few of the puzzles yourself.

Advent of Code Puzzles

Advent of Code is an online Advent calendar where a new puzzle is published every day from December 1st to December 25th. Each puzzle becomes available at midnight, US Eastern Time. An Advent of Code puzzle has a few typical characteristics:

  • Each puzzle consists of two parts, but the second part isn’t revealed until you finish the first part.
  • You’ll earn one golden star (⭐) for each part that you finish. This means you can earn two stars per day and fifty stars if you solve all the puzzles for one year.
  • The puzzle is the same for everyone, but you need to solve it based on personalized input that you get from the Advent of Code site. This means that your answer to a puzzle will be different from someone else’s, even if you use the same code to calculate it.

You can participate in a global race to be the first to solve each puzzle. However, this is usually pretty crowded with highly skilled, competitive programmers. Advent of Code is probably going to be more fun if you use it as practice for yourself or if you challenge your friends and coworkers to a small, friendly competition.

To get a feeling for how an Advent of Code puzzle works, consider the Day 1 puzzle of 2020:

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.

Each year, there’s a wonderfully silly backstory that binds the puzzles together. The 2020 story describes your attempts at leaving for a well-deserved vacation, now that you’ve saved Christmas several years in a row. The story usually has no effect on the puzzles, but it’s still fun to follow along.

In between the plot elements of the story, you’ll find the puzzles themselves. In this example, you’re looking for two entries in your puzzle input that sum to 2,020. After the explanation that describes the problem, you’ll usually find an example showing the calculations you’re expected to do:

For example, suppose your expense report contained the following:

1721
979
366
299
675
1456

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.

The example shows you the answer for this particular list of numbers. If you were about to jump in and start solving this puzzle, you would now start thinking about how you can find the two entries in any valid list of numbers. Before getting deeper into this puzzle, however, you’ll explore how to use the Advent of Code site.

How to Participate in Advent of Code

You’ve seen an example of an Advent of Code puzzle. Next, you’ll learn how you can submit your answer for it. You never submit any code to solve the puzzles. You just submit the answer, which is usually a number or a text string.

In general, you’ll follow a series of steps to solve a puzzle on the site:

  1. Log in on the Advent of Code website. You do this by using your credentials from another service like GitHub, Google, Twitter, or Reddit.

  2. Read the puzzle text and pay special attention to the given example. You should make sure you understand the solution for the example data.

  3. Download your personalized input for the puzzle. You’ll need this input in order to find your unique answer to the problem.

  4. Code up your solution. This is the fun part, which you’ll get a lot of practice for in the rest of this tutorial.

  5. Enter your answer to the puzzle on the puzzle page. If your answer is correct, then you earn a golden star and part two of the puzzle is opened up.

  6. Repeat steps 2 to 4 for part two of the puzzle. This second part is similar to the first, but it usually adds some twist requiring you to adapt your code.

  7. Enter your second answer on the puzzle page in order to earn your second star and finish the puzzle.

Remember, you don’t submit any code—only your puzzle answers. This means that Advent of Code puzzles can be solved in any programming language. Many people use Advent of Code to practice and learn a new programming language. Eric Wastl, the creator of Advent of Code, gave a talk in 2019 where he talked about the diverse background and motivation of the people participating, among other things.

Advent of Code is completely free to use, but there are still a few different ways you can support the project:

  • You can share information about Advent of Code on your social media to get the word out.
  • You can help others by taking part in the r/adventofcode subreddit or other forums.
  • You can invite your friends to take part in Advent of Code, sharing your results on a private leaderboard.
  • You can donate to Advent of Code. If you do, then you’ll get an AoC++ badge next to your name on the site.

In the next sections, you’ll see some suggestions on how you can prepare for solving Advent of Code with Python. There’s also an awesome list you can check out that links to many different resources related to Advent of Code, including many other people’s solutions.

Solving Advent of Code With Python

The Advent of Code has become an annual highlight for many coders around the world. In 2020, more than 170,000 people submitted their solutions. Since Advent of Code was started in 2015, more than 380,000 programmers have participated. Many of them use Python to solve the puzzles.

Well, now it’s your turn! Head over to the Advent of Code website and have a look at the latest puzzles. Then, come back to this tutorial to get some tips and help to start solving Advent of Code puzzles with Python.

The Anatomy of a Puzzle

In this section, you’ll explore the typical anatomy of an Advent of Code puzzle. Additionally, you’ll learn about some tools you can use to interact with it.

Each Advent of Code puzzle is split into two parts. When you start working on a puzzle, you only see the first part. The second part unlocks once you’ve submitted the correct answer to the first part. This is often a twist on the problem you solved in the first part. Sometimes, you’ll find it necessary to refactor your solution from part one, while other times you can solve the second part quickly based on the work you’ve already done.

Both parts always use the same puzzle input. You can download your puzzle input from the puzzle page for that day. You’ll find a link after the puzzle description.

Everything you need to do in order to submit your puzzle solutions—except actually solving the puzzle—you can do from the Advent of Code website. You should use it to submit your first solutions so that you can get familiar with the flow.

Later, there are several tools you can use to organize your Advent of Code setup and work more efficiently. For example, you can use the advent-of-code-data package to download data. It’s a Python package that you can install with pip:

$ python -m pip install advent-of-code-data

You can use advent-of-code-data to download a particular puzzle input set on the command line with its aocd tool. Another fun possibility is automatically downloading and caching your personalized puzzle input within your Python code:

>>>
>>> from aocd.models import Puzzle
>>> puzzle = Puzzle(year=2020, day=1)

>>> # Personal input data. Your data will be different.
>>> puzzle.input_data[:20]
'1753\n1858\n1860\n1978\n'

You need to set your session ID in either an environment variable or a file before you can download your personalized data with advent-of-code-data. You’ll find an explanation for this in the documentation. If you’re interested, then you can also use advent-of-code-data or aocd to submit your solutions and review your earlier answers.

As part of the puzzle text, you’ll also find one or several examples typically calculated based on smaller data than your personalized input data. You should read these examples carefully and make sure you understand what you’re asked to do before you start coding.

You can use the examples to set up tests for your code. One way is to manually run your solution on the example data and confirm that you’re getting the expected answer. Alternatively, you can use a tool like pytest to automate the process.

You can solve all Advent of Code puzzles using just plain Python and the standard library. However, there are a few packages that can aid you as you’re putting together your solutions:

  • advent-of-code-data can download your input data and submit your solutions.
  • pytest can check your solution on the example data automatically.
  • parse can parse strings with a simpler syntax than regular expressions.
  • numpy can effectively compute with arrays of numbers.
  • colorama can animate your solutions in the terminal.

If you create a virtual environment and install those packages, then you’ll have a very solid toolbox for your Advent of Code adventures. Later, you’ll see examples of how you can use parse, numpy, and colorama to solve puzzles.

The Structure of a Solution

In the last section, you got familiar with how to read and understand Advent of Code puzzles. In this section, you’ll learn how you can solve them. You don’t need to do a lot of setup before you solve the Advent of Code puzzles.

Have you thought about how you’d solve the puzzle that you saw earlier? Recall that you’re looking for the product of the two numbers in a list that sum to 2,020. Before moving on, think about—and maybe code up—how you’d find which two entries of the following list sum to 2,020:

numbers = [1721, 979, 366, 299, 675, 1456]

The following script shows one way to solve this first part of the Day 1, 2020 puzzle:

 1for num1 in numbers:
 2    for num2 in numbers:
 3        if num1 < num2 and num1 + num2 == 2020:
 4            print(num1 * num2)

The nested for loop finds all combinations of two numbers from the list. The test on line 3 is actually slightly more complicated than it needs to be: you only need to test that the numbers sum to 2,020. However, by adding the condition that num1 should be smaller than num2, you avoid solutions being found twice.

In this example, one solution looks like num1 = 1721 and num2 = 299, but since you can add numbers in any order, that means that also num1 = 299 and num2 = 1721 form a solution. With the extra check, only the latter combination is reported.

Once you have this solution in place, you can copy your personalized input data into the numbers list and calculate your answer to the puzzle.

As you’re working through more puzzles, you might start feeling that copying your data into your code and rewriting it into valid Python gets tiresome. Similarly, adding a few functions to your code gives you more flexibility later. You could use them to add tests to your code, for example.

Python has many powerful features for parsing strings. In the long run, you’ll be better off leaving the input data just as you downloaded them and let Python parse them into a usable data structure. In fact, dividing your code into two functions is often beneficial. One function will parse the string input and the other will solve the puzzle. Based on these principles, you can rewrite your code:

 1# aoc202001.py
 2
 3import pathlib
 4import sys
 5
 6def parse(puzzle_input):
 7    """Parse input"""
 8    return [int(line) for line in puzzle_input.split()]
 9
10def part1(numbers):
11    """Solve part 1"""
12    for num1 in numbers:
13        for num2 in numbers:
14            if num1 < num2 and num1 + num2 == 2020:
15                return num1 * num2
16
17if __name__ == "__main__":
18    for path in sys.argv[1:]:
19        print(f"\n{path}:")
20        puzzle_input = pathlib.Path(path).read_text().strip()
21
22        numbers = parse(puzzle_input)
23        print(part1(numbers))

On lines 12 to 15, you’ll recognize your solution from earlier. First of all, you’ve wrapped it in a function. This makes it easier to add automatic tests to your code later. You’ve also added a parse() function that can convert lines of strings into a list of numbers.

On line 20, you use pathlib to read the contents of a file as text and strip off any blank lines at the end. Looping through sys.argv gives you all the filenames entered at the command line.

These changes give you more flexibility as you’re working on your solution. Say that you’ve stored the example data in a file called example.txt and your personalized input data in a file named input.txt. You can then run your solution on any one of them, or even both, by supplying their names on the command line:

$ python aoc202001.py example.txt input.txt
example.txt:
514579

input.txt:
744475

514579 is indeed the answer to the problem when using the example input data. Remember, the solution for your personalized input data will be different from the one shown above.

Now it’s time to give the Advent of Code website a spin! Go to the 2020 Advent of Code calendar and find the puzzle for Day 1. If you haven’t already, download your input data and calculate your solution to the puzzle. Then, enter your solution on the website and click Submit.

Congratulations! You’ve just earned your first star!

A Starting Template

As you’ve seen above, Advent of Code puzzles follow a set structure. Therefore, it makes sense to create a template for yourself that you can use as a starting point when you start to code up a solution. Exactly how much structure you want in such a template is a matter of personal taste. To get started, you’ll explore one example of a template that’s based on the principles you saw in the previous section:

 1# aoc_template.py
 2
 3import pathlib
 4import sys
 5
 6def parse(puzzle_input):
 7    """Parse input"""
 8
 9def part1(data):
10    """Solve part 1"""
11
12def part2(data):
13    """Solve part 2"""
14
15def solve(puzzle_input):
16    """Solve the puzzle for the given input"""
17    data = parse(puzzle_input)
18    solution1 = part1(data)
19    solution2 = part2(data)
20
21    return solution1, solution2
22
23if __name__ == "__main__":
24    for path in sys.argv[1:]:
25        print(f"{path}:")
26        puzzle_input = pathlib.Path(path).read_text().strip()
27        solutions = solve(puzzle_input)
28        print("\n".join(str(solution) for solution in solutions))

The template has separate functions for parsing the input as well as for solving both parts of a puzzle. You don’t need to touch lines 15 to 27 at all. They take care of reading text from an input file, calling parse(), part1(), and part2(), and then report the solutions to the console.

You can create a similar template for testing your solutions.

The following template uses pytest as a test runner. It’s prepared for three different tests, one each for the functions parse(), part1(), and part2():

 1# test_aoc_template.py
 2
 3import pathlib
 4import pytest
 5import aoc_template as aoc
 6
 7PUZZLE_DIR = pathlib.Path(__file__).parent
 8
 9@pytest.fixture
10def example1():
11    puzzle_input = (PUZZLE_DIR / "example1.txt").read_text().strip()
12    return aoc.parse(puzzle_input)
13
14@pytest.fixture
15def example2():
16    puzzle_input = (PUZZLE_DIR / "example2.txt").read_text().strip()
17    return aoc.parse(puzzle_input)
18
19@pytest.mark.skip(reason="Not implemented")
20def test_parse_example1(example1):
21    """Test that input is parsed properly"""
22    assert example1 == ...
23
24@pytest.mark.skip(reason="Not implemented")
25def test_part1_example1(example1):
26    """Test part 1 on example input"""
27    assert aoc.part1(example1) == ...
28
29@pytest.mark.skip(reason="Not implemented")
30def test_part2_example2(example2):
31    """Test part 2 on example input"""
32    assert aoc.part2(example2) == ...

You’ll see an example of how you can use this template later. Until then, there are a few things you should note:

  • As indicated on line 1, you should name your pytest files with a test_ prefix.
  • Similarly, each test is implemented in a function named with a test_ prefix. You can see examples of these on lines 20, 25, and 30.
  • You should change the import on line 5 to import your solution code.
  • The template assumes that the example data are stored in files named example1.txt and example2.txt.
  • You should remove the skip marks on lines 19, 24, and 29 when you’re ready to start testing.
  • You’ll need to fill in the ellipses (...) on lines 22, 27, and 32 according to the example data and the corresponding solutions.

For example, if you were to adapt this template to the rewritten solution of the first part of the Day 1, 2020 puzzle from the previous section, then you’d need to create a file example1.txt with the following contents:

1721
979
366
299
675
1456

Next, you’d remove the skip marks for the first two tests and implement them as follows:

def test_parse_example1(example1):
    """Test that input is parsed properly"""
    assert example1 == [1721, 979, 366, 299, 675, 1456]

def test_part1_example1(example1):
    """Test part 1 on example input"""
    assert aoc.part1(example1) == 514579

Finally, you’d need to make sure that you’re importing your solution. If you used the filename aoc202001.py, then you should change line 5 to import aoc202001:

 5import aoc202001 as aoc

You would then run pytest to check your solution. If you implemented your solution correctly, then you’d see something like this:

$ pytest
====================== test session starts =====================
collected 3 items

test_aoc202001.py ..s                                     [100%]
================= 2 passed, 1 skipped in 0.02s =================

Note the two dots (..) in front of the s. They represent two tests that passed. If the tests had failed, you’d see F instead of each dot, along with a detailed explanation of what went wrong.

Tools like Cookiecutter and Copier make it easier to work with templates like these. If you install Copier, then you can use a template similar to the one you’ve seen here by running the following command:

$ copier gh:gahjelle/template-aoc-python advent_of_code

This will set up the template for one particular puzzle in a subdirectory of the advent_of_code directory on your computer.

Solution Strategies

Advent of Code puzzles are very diverse. As you advance through the calendar, you’ll solve many different problems and discover many different strategies for approaching them.

Some of these strategies are quite general and can be applied to any puzzle. If you find that you’re stuck on a puzzle, here are some things you can try to get unstuck:

  • Re-read the description. Advent of Code puzzles are typically very well specified, but some of them can be quite information heavy. Make sure you’re not missing a vital part of the puzzle.
  • Use the example data actively. Make sure you understand how those results are achieved, and check that your code is able to reproduce those examples.
  • Some puzzles may get a bit involved. Break the problem into smaller steps, and implement and test each step individually.
  • If your code works for the example data but not for your personalized input data, then you can build additional test cases based on numbers you’re able to calculate by hand to see whether your code covers all corner cases.
  • If you’re still stuck, then reach out to your friends and other puzzle solvers on some of the forums dedicated to Advent of Code and ask for hints about how they’ve solved the puzzle.

As you do more and more puzzles, you’ll start to recognize some general kinds of puzzles that come up again and again.

Some puzzles deal with text and passwords. Python has several powerful tools for manipulating text strings, including many string methods. To read and parse strings, it’s helpful to know the basics of regular expressions. However, you can often get very far with the third-party parse library as well.

For example, say that you have the string "shiny gold bags contain 2 dark red bags." and want to parse the relevant information from it. You can use parse and its pattern syntax:

>>>
>>> import parse
>>> string = "shiny gold bags contain 2 dark red bags."
>>> pattern = "{outer_color} bags contain {num:d} {inner_color} bags."
>>> match = parse.search(pattern, string)
>>> match.named
{'outer_color': 'shiny gold', 'num': 2, 'inner_color': 'dark red'}

In the background, parse builds a regular expression, but you use a simpler syntax similar to the one that f-strings use.

In some of these text problems, you’re explicitly asked to work with code and parsers, often building a small custom assembly language. After parsing the code, you often need to run the given program. In practice, this means that you build a small state machine that can track its current state, including the contents of its memory.

You can use classes to keep state together with behavior. In Python, data classes are great for quickly setting up a state machine. The following example shows the implementation of a small state machine that can handle two different instructions:

 1from dataclasses import dataclass
 2
 3@dataclass
 4class StateMachine:
 5    memory: dict[str, int]
 6    program: list[str]
 7
 8    def run(self):
 9        """Run the program"""
10        current_line = 0
11        while current_line < len(self.program):
12            instruction = self.program[current_line]
13
14            # Set a register to a value
15            if instruction.startswith("set "):
16                register, value = instruction[4], int(instruction[6:])
17                self.memory[register] = value
18
19            # Increase the value in a register by 1
20            elif instruction.startswith("inc "):
21                register = instruction[4]
22                self.memory[register] += 1
23
24            # Move the line pointer
25            current_line += 1

The two instructions set and inc are parsed and handled within .run(). Note that the type hints on lines 5 and 6 use a newer syntax that only works on Python 3.9 and later versions. If you’re using an older version of Python, then you can import Dict and List from typing instead.

To run your state machine, you first initialize it with an initial memory and load the program into the machine. Next, you call .run(). When the program is done, you can inspect .memory to see the new state of your machine:

>>>
>>> state_machine = StateMachine(
...     memory={"g": 0}, program=["set g 44", "inc g"]
... )
>>> state_machine.run()
>>> state_machine.memory
{'g': 45}

This program first set g to the value of 44, then increased it, leaving it at its final value of 45.

Some fun puzzles involve grids and labyrinths. If your grid has a fixed size, then you can use NumPy to get an effective representation of it. Labyrinths are often useful to visualize. You can use Colorama to draw directly in your terminal:

import numpy as np
from colorama import Cursor

grid = np.array(
    [
        [1, 1, 1, 1, 1],
        [1, 0, 0, 0, 1],
        [1, 1, 1, 0, 1],
        [1, 0, 0, 2, 1],
        [1, 1, 1, 1, 1],
    ]
)

num_rows, num_cols = grid.shape
for row in range(num_rows):
    for col in range(num_cols):
        symbol = " #o"[grid[row, col]]
        print(f"{Cursor.POS(col + 1, row + 2)}{symbol}")

This script shows an example of storing a grid using a NumPy array and then using Cursor.POS from Colorama to position the cursor in the terminal to print out the grid. When you run this script, you’ll see an output like the following:

#####
#   #
### #
#  o#
#####

Visualizing your code as it runs can be fun and also give you some good insights. It can also be an invaluable help when you’re debugging and don’t quite understand what’s happening.

So far in the tutorial, you’ve gotten some general tips on how you can work with Advent of Code puzzles. In the next sections, you’ll get more explicit and solve two puzzles from earlier years.

Practicing Advent of Code: Day 1, 2019

The first puzzle you’ll attempt to solve on your own is Day 1, 2019, called The Tyranny of the Rocket Equation. This is a typical Day 1 puzzle in that the solution isn’t very involved. It’s a great exercise to get used to how Advent of Code works and to check that your environment is properly set up.

Part 1: Puzzle Description

In the 2019 storyline, you’re rescuing Santa, who’s become stranded at the edge of the solar system. In the first puzzle, you’re getting your rocket ready for launch:

The Elves quickly load you into a spacecraft and prepare to launch.

At the first Go / No Go poll, every Elf is Go until the Fuel Counter-Upper. They haven’t determined the amount of fuel required yet.

Fuel required to launch a given module is based on its mass. Specifically, to find the fuel required for a module, take its mass, divide by three, round down, and subtract 2.

The example data look like this:

  • For a mass of 12, divide by 3 and round down to get 4, then subtract 2 to get 2.
  • For a mass of 14, dividing by 3 and rounding down still yields 4, so the fuel required is also 2.
  • For a mass of 1969, the fuel required is 654.
  • For a mass of 100756, the fuel required is 33583.

You need to calculate the total fuel requirements for your spacecraft:

The Fuel Counter-Upper needs to know the total fuel requirement. To find it, individually calculate the fuel needed for the mass of each module (your puzzle input), then add together all the fuel values.

What is the sum of the fuel requirements for all of the modules on your spacecraft?

Now it’s time to try to solve the puzzle on your own! It’s probably the most fun to download your personalized input data and check your solution on Advent of Code so that you can earn your stars. However, feel free to solve the puzzle based on the example data provided above if you’re not ready to sign in to Advent of Code yet.

Part 1: Solution

Once you’re done with the puzzle and you’ve earned your star, you can expand the collapsed block to see a discussion of the puzzle solution:

This solution discussion is a bit more involved than what’s necessary for the puzzle. The goal is that you’ll explore some extra detail in this first solution so that you’ll be even better prepared for the next puzzles.

This section is split into two parts:

  1. A short discussion of integer division and how that can help.
  2. A straightforward solution to the puzzle.

Then, in the next section, you’ll see another solution that uses the templates for solutions and tests that you’ve seen earlier.

To return to the current puzzle, take a second look at the calculation you’re asked to perform:

[To] find the fuel required for a module, take its mass, divide by three, round down, and subtract 2.

You can carry out these steps one after another:

>>>
>>> mass = 14
>>> mass / 3
4.666666666666667

>>> int(mass / 3)
4

>>> int(mass / 3) - 2
2

For positive numbers, you can use int() to round down. If your numbers may be negative, then you should use math.floor() instead.

Python, and many other programming languages, have support for dividing and rounding down in one step. This is called integer division and is done with the integer division operator (//). You can then rewrite your previous calculation:

>>>
>>> mass = 14
>>> mass // 3
4

>>> mass // 3 - 2
2

Using mass // 3 divides by three and rounds down in one step. You can now calculate the fuel for each mass and add them together to solve the puzzle:

>>>
>>> masses = [12, 14, 1969, 100756]
>>> total_fuel = 0

>>> for mass in masses:
...     total_fuel += mass // 3 - 2
...
>>> total_fuel
34241

The four example modules need a total of 34241 fuel units. In the puzzle description, they’re listed as requiring 2, 2, 654, and 33583 fuel units, respectively. Adding these up, you get 34241, which confirms your calculations. You can replace the numbers in the masses list with your personalized input data to get your own answer to the puzzle.

If you’re familiar with comprehensions and generator expressions, then you can use sum() to shorten your code:

>>>
>>> masses = [12, 14, 1969, 100756]
>>> sum(mass // 3 - 2 for mass in masses)
34241

With sum(), you don’t need to manually add up each fuel requirement. Instead, you can solve the current puzzle in one line of code.

You’ve now solved the first part of the puzzle. However, before moving on to the second part of the puzzle, the next section shows how you can use the templates you saw earlier when solving this problem.

Part 1: Solution Using Templates

Expand the collapsed block below to see another solution to the first part of the Advent of Code puzzle for Day 1, 2019—this time using the templates you saw earlier to organize your code and simplify testing:

If you’re going to do several Advent of Code puzzles, then it’s a good idea to organize your solutions into folders. This allows you to keep all the files related to a puzzle together. One nice way of keeping things tidy is to have one folder for each year of Advent of Code and to have folders for each day within each year’s folder.

For this puzzle, you might set up something like this:

advent_of_code/
│
└── 2019/
    └── 01_the_tyranny_of_the_rocket_equation/
        ├── aoc201901.py
        ├── input.txt
        ├── example1.txt
        └── test_aoc201901.py

You store your personalized input data in input.txt, while example1.txt contains the example data from the puzzle description:

12
14
1969
100756

You can then use these data to set up your first tests. Start with the test template from earlier, and fill in tests for parsing input and for solving part one:

 1# test_aoc201901.py
 2
 3import pathlib
 4import pytest
 5import aoc201901 as aoc
 6
 7PUZZLE_DIR = pathlib.Path(__file__).parent
 8
 9@pytest.fixture
10def example1():
11    puzzle_input = (PUZZLE_DIR / "example1.txt").read_text().strip()
12    return aoc.parse(puzzle_input)
13
14@pytest.fixture
15def example2():
16    puzzle_input = (PUZZLE_DIR / "example2.txt").read_text().strip()
17    return aoc.parse(puzzle_input)
18
19def test_parse_example1(example1):
20    """Test that input is parsed properly"""
21    assert example1 == [12, 14, 1969, 100756]
22
23def test_part1_example1(example1):
24    """Test part 1 on example input"""
25    assert aoc.part1(example1) == 2 + 2 + 654 + 33583
26
27@pytest.mark.skip(reason="Not implemented")
28def test_part2_example2(example2):
29    """Test part 2 on example input"""
30    assert aoc.part2(example2) == ...

You want the parser to read the text file and convert each line to a number in a list. You specify this on line 21 as the expected value in test_parse_example1(). The expected value for test_part1_example1() is the sum of the four fuel requirements mentioned in the text.

Finally, add aoc201901.py based on the solution template:

 1# aoc201901.py
 2
 3import pathlib
 4import sys
 5
 6def parse(puzzle_input):
 7    """Parse input"""
 8
 9def part1(data):
10    """Solve part 1"""
11
12def part2(data):
13    """Solve part 2"""
14
15def solve(puzzle_input):
16    """Solve the puzzle for the given input"""
17    data = parse(puzzle_input)
18    solution1 = part1(data)
19    solution2 = part2(data)
20
21    return solution1, solution2
22
23if __name__ == "__main__":
24    for path in sys.argv[1:]:
25        print(f"{path}:")
26        puzzle_input = pathlib.Path(path).read_text().strip()
27        solutions = solve(puzzle_input)
28        print("\n".join(str(solution) for solution in solutions))

Before you start adding your solution to the template, take a minute to run pytest to confirm that the tests are indeed failing. In between a lot of details, you should get something like this:

$ pytest
test_aoc201901.py FFs                                        [100%]

===================== short test summary info =====================
FAILED test_parse_example1 - assert None == [12, 14, 1969, 100756]
FAILED test_part1_example1 - assert None == (((2 + 2) + 654) + 33583)
================== 2 failed, 1 skipped in 0.09s ===================

Note that you have two tests that are failing—just as expected. This way of working is known as test-driven development (TDD). You first write your tests and make sure they fail. Afterward, you implement the code necessary to make them pass. This may seem like overkill for this puzzle but can be a very useful habit for more challenging problems.

It’s time to add your solution to aoc201901.py. First, parse the input data. They are delivered to parse() as a text string of numbers separated by newlines (\n) and should be converted into a list of integers:

def parse(puzzle_input):
    """Parse input"""
    return [int(line) for line in puzzle_input.split("\n")]

The list comprehension assembles each line into a list and converts them to integers. Run pytest again and confirm that your first test, test_parse_example1(), no longer fails.

Next, add your solution to the puzzle:

def part1(data):
    """Solve part 1"""
    return sum(mass // 3 - 2 for mass in data)

You’re solving part one by using sum() as discussed in the previous section. Confirm that your solution is correct by running pytest one more time:

$ pytest
test_aoc201901.py ..s                                        [100%]

================== 2 passed, 1 skipped in 0.01s ===================

With the tests passing, you can solve the puzzle for your personalized input data by running the program against input.txt:

$ python aoc201901.py input.txt
input.txt:
3550236
None

Your own answer will be different from what’s shown here, 3550236. The None output at the bottom represents the solution to the second part, which you haven’t implemented yet. Now might be a good time to look at part two!

You can now move on to the second part of the puzzle. Are you ready for the twist?

Part 2: Puzzle Description

Every Advent of Code puzzle consists of two parts, where the second part is revealed only after you solve the first part. The second part is always related to the first and will use the same input data. However, you may often need to rethink your approach to the first half of the puzzle in order to account for the second half.

Expand the collapsed block below to have a look at the second part of the Advent of Code puzzle for Day 1, 2019:

Your quest to get the rocket off the ground continues:

During the second Go / No Go poll, the Elf in charge of the Rocket Equation Double-Checker stops the launch sequence. Apparently, you forgot to include additional fuel for the fuel you just added.

Fuel itself requires fuel just like a module - take its mass, divide by three, round down, and subtract 2. However, that fuel also requires fuel, and that fuel requires fuel, and so on. Any mass that would require negative fuel should instead be treated as if it requires zero fuel; the remaining mass, if any, is instead handled by wishing really hard, which has no mass and is outside the scope of this calculation.

Of course, adding all that fuel to your spacecraft has made it heavier. You need to add more fuel to account for the added weight, but that fuel will also need to be accounted for. To see how this works in practice, have a look at the examples:

So, for each module mass, calculate its fuel and add it to the total. Then, treat the fuel amount you just calculated as the input mass and repeat the process, continuing until a fuel requirement is zero or negative. For example:

  • A module of mass 14 requires 2 fuel. This fuel requires no further fuel (2 divided by 3 and rounded down is 0, which would call for a negative fuel), so the total fuel required is still just 2.
  • At first, a module of mass 1969 requires 654 fuel. Then, this fuel requires 216 more fuel (654 / 3 - 2). 216 then requires 70 more fuel, which requires 21 fuel, which requires 5 fuel, which requires no further fuel. So, the total fuel required for a module of mass 1969 is 654 + 216 + 70 + 21 + 5 = 966.
  • The fuel required by a module of mass 100756 and its fuel is: 33583 + 11192 + 3728 + 1240 + 411 + 135 + 43 + 12 + 2 = 50346.

The examples are still using the same numbers as for part one. The fuel needed for the module with mass 12 isn’t specified, but you can calculate that it will be 2 using the same calculation as for the module with mass 14. The question you need to answer remains the same:

What is the sum of the fuel requirements for all of the modules on your spacecraft when also taking into account the mass of the added fuel? (Calculate the fuel requirements for each module separately, then add them all up at the end.)

Have a go at solving this part as well. Can you earn your second star?

You’ll see a possible solution to part two in the next section. However, try to solve the puzzle for yourself first. If you need a hint to get started, then expand the box below:

Repeated calculations like the ones in this part of the puzzle often lend themselves well to recursion.

How did you do? Is your rocket ready for launch?

Part 2: Solution

This section shows how you can solve part two, continuing with the template you saw above:

Continuing with the test-driven development workflow, start with adding the new examples to your test file. The examples are using the same numbers as part one, so you can use the same example1.txt file. You can therefore remove the example2() fixture from your test code. Next, remove the skip mark and then rename and implement test_part2_example1():

def test_part2_example1(example1):
    """Test part 2 on example input"""
    assert aoc.part2(example1) == 2 + 2 + 966 + 50346

As before, run pytest to confirm that your test is failing.

Next, it’s time for the actual implementation. Repeated calculations of fuel like you’re asked for here can be handled well using recursion.

A recursive function is a function that calls itself. When implementing a recursive function, you should be conscious of including a stopping condition: When should the function stop calling itself? In this example, the stopping condition is mentioned quite explicitly in the puzzle description. You should stop when the fuel becomes zero or negative.

Add the following as a new function in your aoc201901.py solution file:

 1def all_fuel(mass):
 2    """Calculate fuel while taking mass of the fuel into account"""
 3    fuel = mass // 3 - 2
 4    if fuel <= 0:
 5        return 0
 6    else:
 7        return fuel + all_fuel(mass=fuel)

Line 4 implements the stopping condition, while line 7 does the recursive call. You can add a test to check that the calculation works as expected. Note that if you’d been doing pure test-driven development, then you’d have added the test first. Add this function to your test file:

def test_all_fuel():
    """Test that fuel can be calculated recursively"""
    assert aoc.all_fuel(1969) == 966

In this test, you don’t use the input files. Instead, you check directly one of the examples given above. Before moving on to solve the whole puzzle, note that you can use the walrus operator to write the function more concisely:

def all_fuel(mass):
    """Calculate fuel while taking mass of the fuel into account"""
    return 0 if (fuel := mass // 3 - 2) < 0 else fuel + all_fuel(fuel)

While the code is shorter, it’s also denser. Whether you find that the end result is more readable or not is a matter of taste and experience.

To finish off the puzzle, you also need to implement part2(). Your all_fuel() function calculates the fuel needed for each module, so what’s left is adding the fuel for all modules together:

def part2(data):
    """Solve part 2"""
    return sum(all_fuel(mass) for mass in data)

The implementation of part2() ends up being quite similar to part1(). You only need to change the fuel calculation for each mass.

To finish up, run pytest to confirm that everything works. Then run your program on your input to get your final puzzle answer:

$ python aoc201901.py input.txt
input.txt:
3550236
5322455

Back at the Advent of Code website, enter your own answer, which will be different from the one above. Your second star is waiting!

Before leaving this puzzle completely, note that it’s possible to solve the second part without using recursion. You could do the same calculations using loops instead. Here’s one possible implementation:

def part2(data):
    """Solve part 2"""
    total_fuel = 0
    for mass in data:
        while (mass := mass // 3 - 2) > 0:
            total_fuel += mass

    return total_fuel

For each mass, the while loop calculates all the fuel needed and adds it to the running total fuel count.

One of the fun things about challenging yourself with programming puzzles is that they give you a great opportunity to try out different solutions to problems and compare them.

Congratulations! You’ve now solved an entire Advent of Code puzzle. Are you ready for a more challenging one?

Practicing Advent of Code: Day 5, 2020

The second puzzle you’ll attempt to solve is the one for Day 5, 2020, called Binary Boarding. This puzzle is a bit more challenging than the previous one, but the final solution won’t require a lot of code. Start by having a look at the puzzle description for part one.

Part 1: Puzzle Description

In 2020, you’re trying hard to get to your well-deserved vacation spot. On Day 5, you’re about to board your plane when trouble ensues:

You board your plane only to discover a new problem: you dropped your boarding pass! You aren’t sure which seat is yours, and all of the flight attendants are busy with the flood of people that suddenly made it through passport control.

You write a quick program to use your phone’s camera to scan all of the nearby boarding passes (your puzzle input); perhaps you can find your seat through process of elimination.

Instead of zones or groups, this airline uses binary space partitioning to seat people. A seat might be specified like FBFBBFFRLR, where F means “front”, B means “back”, L means “left”, and R means “right”.

The first 7 characters will either be F or B; these specify exactly one of the 128 rows on the plane (numbered 0 through 127). Each letter tells you which half of a region the given seat is in.

Start with the whole list of rows; the first letter indicates whether the seat is in the front (0 through 63) or the back (64 through 127). The next letter indicates which half of that region the seat is in, and so on until you’re left with exactly one row.

For example, consider just the first seven characters of FBFBBFFRLR:

  • Start by considering the whole range, rows 0 through 127.
  • F means to take the lower half, keeping rows 0 through 63.
  • B means to take the upper half, keeping rows 32 through 63.
  • F means to take the lower half, keeping rows 32 through 47.
  • B means to take the upper half, keeping rows 40 through 47.
  • B keeps rows 44 through 47.
  • F keeps rows 44 through 45.
  • The final F keeps the lower of the two, row 44.

The last three characters will be either L or R; these specify exactly one of the 8 columns of seats on the plane (numbered 0 through 7). The same process as above proceeds again, this time with only three steps. L means to keep the lower half, while R means to keep the upper half.

For example, consider just the last 3 characters of FBFBBFFRLR:

  • Start by considering the whole range, columns 0 through 7.
  • R means to take the upper half, keeping columns 4 through 7.
  • L means to take the lower half, keeping columns 4 through 5.
  • The final R keeps the upper of the two, column 5.

So, decoding FBFBBFFRLR reveals that it is the seat at row 44, column 5.

Every seat also has a unique seat ID: multiply the row by 8, then add the column. In this example, the seat has ID 44 * 8 + 5 = 357.

Here are some other boarding passes:

  • BFFFBBFRRR: row 70, column 7, seat ID 567.
  • FFFBBBFRRR: row 14, column 7, seat ID 119.
  • BBFFBBFRLL: row 102, column 4, seat ID 820.

As a sanity check, look through your list of boarding passes. What is the highest seat ID on a boarding pass?

There’s a lot of information in this puzzle description! However, most of it concerns how binary space partitioning works for this particular airline.

Now, try to solve the puzzle for yourself! Keep in mind that if you consider it from the right perspective, the conversion from a boarding pass specification to a seat ID isn’t as complicated as it might seem at first. If you find that you’re struggling with that part, then expand the box below to see a hint on how you can get started.

The boarding pass specifications are based on the binary system, just camouflaged with different characters. Can you translate the boarding passes into binary numbers?

When you’re done with your solution, have a look in the next section to see a discussion about the puzzle.

Part 1: Solution

Now that you’ve given it a shot yourself, you can go ahead and expand the following block to see one way the puzzle can be solved:

You can implement the calculation of the seat IDs based on the description in the text. The following function takes the same steps as the example:

def decode(string):
    """Decode a boarding pass string into a number"""
    start, end = 0, 2 ** len(string)
    for char in string:
        if char in {"F", "L"}:
            end -= (end - start) // 2
        elif char in {"B", "R"}:
            start += (end - start) // 2

    return start

You limit the range of possible rows or columns by start and end. While start is included in the range, end is not. This makes the math easier as it keeps the difference of end - start divisible by two throughout the calculation. You lower the upper limit for each F or L, and you increase start, the lower limit, for each B or R. You can check that the function gives the same results as the examples:

>>>
>>> decode("FBFBBFF")
44

>>> decode("RLR")
5

>>> decode("FBFBBFFRLR")
357

Using decode(), you can calculate the row, the column, and the seat ID for a boarding pass. However, Python already has built-in tools to carry out the same calculation for you.

The name of the puzzle, Binary Boarding, and the mention of binary space partitioning are meant to start you thinking about (or reading about) the binary system. Binary is a number system composed of two digits, 0 and 1, instead of the traditional ten digits.

In the puzzle, the boarding pass specifications are really binary numbers. The difference is that they use F or L in place of 0, and B and R in place of 1. For example, FBFBBFFRLR can be translated to the binary number 01011001012. You can use Python to convert this to a regular decimal number:

>>>
>>> int("0101100101", base=2)
357

Do you recognize that answer? 357 is indeed the seat ID of FBFBBFFRLR. In other words, in order to calculate seat IDs, you need to translate F, L, B, R into their respective binary digits. There are several ways you can do this, but str.translate() in Python’s standard library is probably the most convenient. Here’s how it works:

>>>
>>> mapping = str.maketrans({"F": "0", "L": "0", "B": "1", "R": "1"})
>>> "FBFBBFFRLR".translate(mapping)
'0101100101'

The .translate() method uses character codes like 70 instead of strings like "F". You can set up the translation based on strings, though, with the convenience function str.maketrans(). You can now use these tools to solve the puzzle in three steps:

  1. Convert boarding pass specifications to binary numbers.
  2. Calculate the decimal value of the binary numbers to get the seat IDs.
  3. Find the maximal seat ID.

Set up your templates for the new puzzle, with input.txt containing your personalized puzzle input:

advent_of_code/
│
└── 2020/
    └── 05_binary_boarding/
        ├── aoc202005.py
        ├── input.txt
        ├── example1.txt
        └── test_aoc202005.py

You can add the worked examples to example1.txt as usual:

FBFBBFFRLR
BFFFBBFRRR
FFFBBBFRRR
BBFFBBFRLL

Next, you’re gonna prepare the tests for the first part. Before doing so, you should think about how you want to parse the puzzle input.

One option is to parse the input file into a list of strings. However, you can also think about the conversion from boarding pass specification to seat ID as part of the parsing process. One consideration to take into account is whether you think you’ll need the original boarding pass strings later—that is, in part two.

You decide to take the chance, and you parse the seat IDs immediately. If the boarding pass strings are needed in part two, then you can always go back and refactor your code. Add the following tests to your test file:

def test_parse_example1(example1):
    """Test that input is parsed properly"""
    assert example1 == [357, 567, 119, 820]

def test_part1_example1(example1):
    """Test part 1 on example input"""
    assert aoc.part1(example1) == 820

As usual, run pytest to confirm that your tests are failing. Then it’s time to start implementing your solution. Start with the parsing:

BP2BINARY = str.maketrans({"F": "0", "B": "1", "L": "0", "R": "1"})

def parse(puzzle_input):
    """Parse input"""
    return [
        int(bp.translate(BP2BINARY), base=2)
        for bp in puzzle_input.split("\n")
    ]

You set up the translation table between boarding pass strings and binary numbers. Then you use .translate() to translate each boarding pass in your input to a binary number and int() to convert the binary number to a seat ID.

Finding the highest seat ID is now straightforward:

def part1(data):
    """Solve part 1"""
    return max(data)

Python’s built-in max() finds the highest value in a list. You can now run your tests to confirm that your solution works and then run your code against your personalized input to get your answer to the puzzle.

Time to move on to the second part of the puzzle. Will you be able to board the plane?

Part 2: Puzzle Description

Expand the section below when you’re ready for the second part of the puzzle:

Compared to the first part, the description of part two is quite short and concise:

Ding! The “fasten seat belt” signs have turned on. Time to find your seat.

It’s a completely full flight, so your seat should be the only missing boarding pass in your list. However, there’s a catch: some of the seats at the very front and back of the plane don’t exist on this aircraft, so they’ll be missing from your list as well.

Your seat wasn’t at the very front or back, though; the seats with IDs +1 and -1 from yours will be in your list.

What is the ID of your seat?

Can you find your seat?

Take your time and work on your solution to this second part.

Part 2: Solution

Open the box below when you’re ready to compare your solution to another one:

In this second part of the puzzle, you’re looking for one missing number in a list of numbers.

There are several ways you can approach this. You can, for example, sort all the numbers and compare consecutive items in your sorted list. Another option is to use Python’s powerful sets. You can first create the full set of valid seat IDs. Then you can calculate the set difference between this full set and the set of seat IDs on your list.

Before you start on the implementation, though, you should add a test for it. In this case, the example data are actually not good to use for a test. They have many seat IDs missing and not only one like the puzzle text specifies. You’re better off creating a small test manually. Here’s one way you can do it:

def test_part2():
    """Test part 2 on example input"""
    data = [3, 9, 4, 8, 5, 10, 7, 11]
    assert aoc.part2(data) == 6

The list [3, 9, 4, 8, 5, 10, 7, 11] contains all seat IDs from 3 and 11 with the exception of 6. This smaller example fulfills the conditions of the puzzle. Your solution should therefore be able to pick out the missing seat ID.

In this implementation, you’ll use the set() approach:

 1def part2(data):
 2    """Solve part 2"""
 3    all_ids = set(range(min(data), max(data) + 1))
 4    return (all_ids - set(data)).pop()

On line 3, you create all the valid seat IDs. These are the numbers between the smallest seat ID and highest seat ID in your dataset, inclusive. To find your seat ID, you convert your list of seat IDs to a set, compare it to the set of all IDs, and pop out the one remaining seat ID.

Congratulations! By now, you’ve solved at least two Advent of Code puzzles. Luckily, there are hundreds more waiting for you!

Conclusion

Advent of Code is a great resource of fun programming puzzles! You can use it to practice your problem-solving skills and challenge your friends to a fun competition and common learning experience. If you haven’t already done so, then head over to the Advent of Code website and try out some of the new puzzles.

In this tutorial, you learned:

  • How solving puzzles can advance your programming skills
  • How you can participate in Advent of Code
  • How you can approach different kinds of puzzles
  • How you can organize your code and tests when solving Advent of Code puzzles
  • How test-driven development can be used when solving puzzles

Real Python hosts a private leaderboard and a community forum about Advent of Code. Become a Real Python member and join the #advent-of-code Slack channel to access it.

🐍 Python Tricks 💌

Get a short & sweet Python Trick delivered to your inbox every couple of days. No spam ever. Unsubscribe any time. Curated by the Real Python team.

Python Tricks Dictionary Merge

About Geir Arne Hjelle

Geir Arne Hjelle Geir Arne Hjelle

Geir Arne is an avid Pythonista and a member of the Real Python tutorial team.

» More about Geir Arne

Each tutorial at Real Python is created by a team of developers so that it meets our high quality standards. The team members who worked on this tutorial are:

Master Real-World Python Skills With Unlimited Access to Real Python

Join us and get access to hundreds of tutorials, hands-on video courses, and a community of expert Pythonistas:

Level Up Your Python Skills »

Master Real-World Python Skills
With Unlimited Access to Real Python

Join us and get access to hundreds of tutorials, hands-on video courses, and a community of expert Pythonistas:

Level Up Your Python Skills »

What Do You Think?

Real Python Comment Policy: The most useful comments are those written with the goal of learning from or helping out other readers—after reading the whole article and all the earlier comments. Complaints and insults generally won’t make the cut here.

What’s your #1 takeaway or favorite thing you learned? How are you going to put your newfound skills to use? Leave a comment below and let us know.

Keep Learning

Related Tutorial Categories: basics testing