Advent of Code: Solving Your Puzzles With Python

Advent of Code Puzzles

Advent of Code is an online Advent calendar where a new puzzle is published every day from December 1 to December 25. 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 gold 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 that 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 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 gold star, and part two of the puzzle opens up.

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

7. Enter your second answer on the puzzle page 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:

• Share information about Advent of Code on your social media to get the word out.
• Help others by taking part in the r/adventofcode subreddit or other forums.
• Invite your friends to take part in Advent of Code, sharing your results on a private leaderboard.
• 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 several other people’s solutions.

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 that 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 that 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.
• advent-of-code-ocr can convert the ASCII art solutions of some puzzles to strings.
• 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.
• rich can render your terminal output more visually appealing.

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:

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

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 num1 = 299 and num2 = 1721 also 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 letting 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 28 at all. They take care of reading text from an input file, calling parse(), part1(), and part2(), and then reporting 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 several different tests, testing each of 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_example1(example1):
31    """Test part 2 on example input."""
32    assert aoc.part2(example1) == ...
33
34@pytest.mark.skip(reason="Not implemented")
35def test_part2_example2(example2):
36    """Test part 2 on example input."""
37    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, 30, and 35.
• 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, 29, and 34 when you’re ready to start testing.
• You’ll need to fill in the ellipses (...) on lines 22, 27, 32, and 37 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:

# test_aoc202001.py

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:

 1# test_aoc202001.py
 2
 3import pathlib
 4import pytest
 5import aoc202001 as aoc
 6
 7# ...

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 4 items

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

Note the two dots (..) in front of ss. 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:

• Reread 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 that 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
>>> PATTERN = parse.compile(
...     "{outer_color} bags contain {num:d} {inner_color} bags."
... )

>>> match = PATTERN.search("shiny gold bags contain 2 dark red bags.")
>>> 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 and behavior together. In Python, data classes are great for quickly setting up a state machine. In the following example, you implement a small state machine that can handle two different instructions:

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

The two instructions set and inc are parsed and handled within .run(). Note that the type hints on lines 7 and 8 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:

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

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

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:

# aoc_grid.py

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:

$ python aoc_grid.py
*****
*   *
*** *
*  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 three puzzles from earlier years.

Part 1: Puzzle Description

In the 2019 story line, 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:

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

>>> int(mass / 3)
4

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

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

>>> mass // 3 - 2
2

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

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

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

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:

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

12
14
1969
100756

 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_example1(example1):
29    """Test part 2 on example input."""
30    assert aoc.part2(example1) == ...
31
32@pytest.mark.skip(reason="Not implemented")
33def test_part2_example2(example2):
34    """Test part 2 on example input."""
35    assert aoc.part2(example2) == ...

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

$ pytest
test_aoc201901.py FFss                                       [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, 2 skipped in 0.09s ===================

# aoc201901.py

# ...

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

# aoc201901.py

# ...

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

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

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

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

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:

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:

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:

# test_aoc201901.py

# ...

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

# aoc201901.py

# ...

def all_fuel(mass):
    """Calculate fuel while taking mass of the fuel into account.

    ## Example:

    >>> all_fuel(1969)
    966
    """

$ pytest --doctest-modules
aoc201901.py F                                               [ 20%]
test_aoc201901.py ..F                                        [100%]
___________________ [doctest] aoc201901.all_fuel __________________
023 Calculate fuel while taking mass of the fuel into account.
024
025     ## Example:
026
027     >>> all_fuel(1969)
Expected:
    966
Got nothing

 1# aoc201901.py
 2
 3# ...
 4
 5def all_fuel(mass):
 6    """Calculate fuel while taking mass of the fuel into account.
 7
 8    ## Example:
 9
10    >>> all_fuel(1969)
11    966
12    """
13    fuel = mass // 3 - 2
14    if fuel <= 0:
15        return 0
16    else:
17        return fuel + all_fuel(mass=fuel)

# aoc201901.py

# ...

def all_fuel(mass):
    """Calculate fuel while taking mass of the fuel into account.

    ## Example:

    >>> all_fuel(1969)
    966
    """
    return 0 if (fuel := mass // 3 - 2) < 0 else fuel + all_fuel(fuel)

# aoc201901.py

# ...

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

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

# aoc201901.py

# ...

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

    return total_fuel

Congratulations! You’ve now solved an entire Advent of Code puzzle. Are you ready for a more challenging 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:

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 that you could solve the puzzle:

# aoc202005.py

# ...

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

>>> decode("FBFBBFF")
44

>>> decode("RLR")
5

>>> decode("FBFBBFFRLR")
357

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

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

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

FBFBBFFRLR
BFFFBBFRRR
FFFBBBFRRR
BBFFBBFRLL

# test_aoc202005.py

# ...

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

# aoc202005.py

# ...

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")
    ]

# aoc202005.py

# ...

def part1(seat_ids):
    """Solve part 1."""
    return max(seat_ids)

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:

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:

# test_aoc202005.py

# ...

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

 1# aoc202005.py
 2
 3# ...
 4
 5def part2(seat_ids):
 6    """Solve part 2."""
 7    all_ids = set(range(min(seat_ids), max(seat_ids) + 1))
 8    return (all_ids - set(seat_ids)).pop()

Great, you’ve finished another puzzle! To round things out, try your hand at one of the puzzles from 2021.

Part 1: Puzzle Description

The story line in 2021 starts with the Elves carelessly dropping the keys to Santa’s sleigh into the ocean. You end up in a submarine searching for them in order to save Christmas. On day 5, you come across a field of hydrothermal vents on the ocean floor.

It turns out that these vents are harmful to your submarine and you need to map out the field to avoid the most dangerous areas:

They tend to form in lines; the submarine helpfully produces a list of nearby lines of vents (your puzzle input) for you to review. For example:

Text

0,9 -> 5,9
8,0 -> 0,8
9,4 -> 3,4
2,2 -> 2,1
7,0 -> 7,4
6,4 -> 2,0
0,9 -> 2,9
3,4 -> 1,4
0,0 -> 8,8
5,5 -> 8,2

Each line of vents is given as a line segment in the format x1,y1 -> x2,y2 where x1,y1 are the coordinates of one end the line segment and x2,y2 are the coordinates of the other end. These line segments include the points at both ends. In other words:

• An entry like 1,1 -> 1,3 covers points 1,1, 1,2, and 1,3.
• An entry like 9,7 -> 7,7 covers points 9,7, 8,7, and 7,7.

For now, only consider horizontal and vertical lines: lines where either x1 = x2 or y1 = y2.

The example shows how the puzzle input describes lines at given coordinates. Your job is to find where these lines overlap:

To avoid the most dangerous areas, you need to determine the number of points where at least two lines overlap. In the above example, this is […] a total of 5 points.

Consider only horizontal and vertical lines. At how many points do at least two lines overlap?

As in the previous puzzle, there’s a lot of information in the puzzle text. The information mostly pertains to how you should interpret your puzzle input.

Try to solve the puzzle for yourself. When you’re done, move on to the next sections to see one possible solution.

Part 1: Input Parsing

There are many ways to implement a solution to this puzzle. Expand the block below to start working with the input data:

2,0 -> 0,2
0,2 -> 2,2
0,0 -> 0,2
0,0 -> 2,2

# test_aoc202105.py

# ...

def test_parse_example1(example1):
    """Test that input is parsed properly."""
    assert example1 == [
        (2, 0, 0, 2),
        (0, 2, 2, 2),
        (0, 0, 0, 2),
        (0, 0, 2, 2),
    ]

 1# aoc202105.py
 2
 3# ...
 4
 5def parse(puzzle_input):
 6    """Parse input."""
 7    return [
 8        tuple(
 9            int(xy)
10            for points in line.split(" -> ")
11            for xy in points.split(",")
12        )
13        for line in puzzle_input.split("\n")
14    ]

# aoc202105.py

# ...

def parse(puzzle_input):
    """Parse input."""
    lines = []
    for line in puzzle_input.split("\n"):
        point1, point2 = line.split(" -> ")
        x1, y1 = point1.split(",")
        x2, y2 = point2.split(",")
        lines.append((int(x1), int(y1), int(x2), int(y2)))
    return lines

Once you’ve represented the data in a structure that you can work with, then you can move on to solving the puzzle itself.

Part 1: Solution

You’ll continue working on part 1 of the puzzle. The following solution takes advantage of the structural pattern matching feature introduced in Python 3.10. Expand the collapsed section to read the details:

# aoc202105.py

# ...

def points(line):
    """List all points making up a line.

    ## Examples:

    >>> points((0, 3, 3, 3))  # Horizontal line
    [(0, 3), (1, 3), (2, 3), (3, 3)]
    >>> points((3, 4, 3, 0))  # Vertical line
    [(3, 4), (3, 3), (3, 2), (3, 1), (3, 0)]
    """

 1# aoc202105.py
 2
 3# ...
 4
 5def points(line):
 6    """List all points making up a line.
 7
 8    ## Examples:
 9
10    >>> points((0, 3, 3, 3))  # Horizontal line
11    [(0, 3), (1, 3), (2, 3), (3, 3)]
12    >>> points((3, 4, 3, 0))  # Vertical line
13    [(3, 4), (3, 3), (3, 2), (3, 1), (3, 0)]
14    """
15    match line:
16        case (x1, y1, x2, y2) if x1 == x2:
17            return [(x1, y) for y in range(y1, y2 + 1)]
18        case (x1, y1, x2, y2) if y1 == y2:
19            return [(x, y1) for x in range(x1, x2 + 1)]

$ pytest --doctest-modules
___________________ [doctest] aoc202105.points ___________________
List all points making up a line

    ## Examples:

    >>> points((0, 3, 3, 3))  # Horizontal line
    [(0, 3), (1, 3), (2, 3), (3, 3)]
    >>> points((3, 4, 3, 0))  # Vertical line
Expected:
    [(3, 4), (3, 3), (3, 2), (3, 1), (3, 0)]
Got:
    []

# aoc202105.py

# ...

def coords(start, stop):
    """List coordinates between start and stop, inclusive."""
    step = 1 if start <= stop else -1
    return range(start, stop + step, step)

# aoc202105.py

# ...

def points(line):
    """List all points making up a line.

    ## Examples:

    >>> points((0, 3, 3, 3))  # Horizontal line
    [(0, 3), (1, 3), (2, 3), (3, 3)]
    >>> points((3, 4, 3, 0))  # Vertical line
    [(3, 4), (3, 3), (3, 2), (3, 1), (3, 0)]
    """
    match line:
        case (x1, y1, x2, y2) if x1 == x2:
            return [(x1, y) for y in coords(y1, y2)]
        case (x1, y1, x2, y2) if y1 == y2:
            return [(x, y1) for x in coords(x1, x2)]

 1# aoc202105.py
 2
 3import collections
 4
 5# ...
 6
 7def count_overlaps(lines):
 8    """Count overlapping points between a list of lines.
 9
10    ## Example:
11
12    >>> count_overlaps(
13    ...     [(3, 3, 3, 5), (3, 3, 6, 3), (6, 6, 6, 3), (4, 5, 6, 5)]
14    ... )
15    3
16    """
17    overlaps = collections.Counter(
18        point for line in lines for point in points(line)
19    )
20    return sum(num_points >= 2 for num_points in overlaps.values())

# aoc202105.py

# ...

def part1(lines):
    """Solve part 1."""
    vertical = [(x1, y1, x2, y2) for x1, y1, x2, y2 in lines if x1 == x2]
    horizontal = [(x1, y1, x2, y2) for x1, y1, x2, y2 in lines if y1 == y2]
    return count_overlaps(vertical + horizontal)

Phew! You’ve finished the first part of the puzzle. Time to look at what part 2 has in store for you.

Part 2: Puzzle Description

Expand the section below to read the second part of the puzzle for Day 5, 2021:

Play around with the second part and try to solve it yourself. Once you’re done, have a look in the next section for a possible solution.

Part 2: Solution

Click to reveal the solution below when you’re ready to have a look at a solution and compare it with your own:

  123456789 x
1 .........
2 .......#.
3 ......#..
4 .....#...
5 ....#....
6 .........
y

# aoc202105.py

# ...

def points(line):
    """List all points making up a line.

    ## Examples:

    >>> points((0, 3, 3, 3))  # Horizontal line
    [(0, 3), (1, 3), (2, 3), (3, 3)]
    >>> points((3, 4, 3, 0))  # Vertical line
    [(3, 4), (3, 3), (3, 2), (3, 1), (3, 0)]
    >>> points((1, 2, 3, 4))  # Diagonal line
    [(1, 2), (2, 3), (3, 4)]
    """
    # ...

# aoc202105.py

# ...

def points(line):
    """List all points making up a line.

    ## Examples:

    >>> points((0, 3, 3, 3))  # Horizontal line
    [(0, 3), (1, 3), (2, 3), (3, 3)]
    >>> points((3, 4, 3, 0))  # Vertical line
    [(3, 4), (3, 3), (3, 2), (3, 1), (3, 0)]
    >>> points((1, 2, 3, 4))  # Diagonal line
    [(1, 2), (2, 3), (3, 4)]
    """
    match line:
        case (x1, y1, x2, y2) if x1 == x2:
            return [(x1, y) for y in coords(y1, y2)]
        case (x1, y1, x2, y2) if y1 == y2:
            return [(x, y1) for x in coords(x1, x2)]
        case (x1, y1, x2, y2):
            return [(x, y) for x, y in zip(coords(x1, x2), coords(y1, y2))]

# aoc202105.py

# ...

def part2(lines):
    """Solve part 2."""
    return count_overlaps(lines)

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