Table of Contents
- Puzzling in Programming?
- Exploring Options for Solving Programming Puzzles Online
- Preparing for Advent of Code: 25 Fresh Puzzles for Christmas
- Advent of Code Puzzles
- How to Participate in Advent of Code
- Solving Advent of Code With Python
- The Anatomy of a Puzzle
- The Structure of a Solution
- A Starting Template
- Solution Strategies
- Practicing Advent of Code: Day 1, 2019
- Part 1: Puzzle Description
- Part 1: Solution
- Part 1: Solution Using Templates
- Part 2: Puzzle Description
- Part 2: Solution
- Practicing Advent of Code: Day 5, 2020
- Part 1: Puzzle Description
- Part 1: Solution
- Part 2: Puzzle Description
- Part 2: Solution
- Practicing Advent of Code: Day 5, 2021
- Part 1: Puzzle Description
- Part 1: Input Parsing
- Part 1: Solution
- Part 2: Puzzle Description
- Part 2: Solution
- Conclusion
Remove ads
Watch Now This tutorial has a related video course created by the Real Python team. Watch it together with the written tutorial to deepen your understanding: Advent of Code: Solving Puzzles With Python
Advent of Code is an online Advent calendar where you’ll find new programming puzzles offered each day from December 1 to 25. 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!
With the help of this tutorial, you’ll be ready to start solving puzzles and earning your first gold 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 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.
Source Code: Click here to download the free source code that shows you how to solve Advent of Code puzzles with 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 of 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.
Remove ads
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 coding challenges, small tutorials about different programming concepts, and mentors who 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 235,000 people have solved at least one of the puzzles from 2021.
Note: Traditionally, an Advent calendar is a calendar used to count the days of Advent while waiting for Christmas. Over the years, Advent calendars have become more commercial and have lost some of their Christian connection.
Most Advent calendars start on December 1 and end on December 24, Christmas Eve, or December 25, Christmas Day. Nowadays, there are all kinds of Advent calendars available, including LEGO calendars, tea calendars, and cosmetics calendars.
In traditional Advent calendars, you open one door every day to reveal what’s inside. Advent of Code mimics this by giving you access to one new puzzle each day from December 1 to December 25. For each puzzle you solve, you’ll earn gold 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 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:
17219793662996751456
In this list, the two entries that sum to
2020
are1721
and299
. Multiplying them together produces1721 * 299 = 514579
, so the correct answer is514579
.
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.
Remove ads
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:
Log in on the Advent of Code website. You do this by using your credentials from another service like GitHub, Google, Twitter, or Reddit.
Read the puzzle text and pay special attention to the given example. You should make sure you understand the solution for the example data.
Download your personalized input for the puzzle. You’ll need this input to find your unique answer to the problem.
Code up your solution. This is the fun part, which you’ll get a lot of practice for in the rest of this tutorial.
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.
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.
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.
Note: There’s a leaderboard for Advent of Code. In general, you should ignore this leaderboard! It only shows who submitted the first 100 solutions after a puzzle opened up. To have a shot at joining the leaderboard, you need a lot of preparation, dedication, and experience with competitive programming.
Instead, you should look at the private leaderboards. These become available after you’ve logged in, and they give you a chance to invite your friends and colleagues to a more relaxed community. You can choose to score your private leaderboard either based on when puzzles were solved or simply based on the number of puzzles people have solved.
You can also link your name in the private leaderboards to your GitHub account, which allows you to share your solutions with your friends. You set this up by clicking Settings in the menu on the Advent of Code site after you’ve logged in.
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.
Solving Advent of Code With Python
The Advent of Code has become an annual highlight for many coders around the world. In 2021, more than 235,000 people submitted their solutions. Since Advent of Code started in 2015, programmers have collected more than ten million stars. Many participants 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 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.
Note: As mentioned earlier, your puzzle input is personalized. This means that if you discuss solutions with other people, their final answers will likely be different from yours.
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:
Shell
$ 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:
Python
>>> 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.
Note: Test-driven development (TDD) is a process where you write tests before implementing your code. Because Advent of Code provides you with expected answers to small examples, it gives you a great opportunity to try out test-driven development on your own.
You’ll learn more about TDD later when you try to solve some puzzles by yourself.
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.
Remove ads
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:
Python
>>> numbers = [1721, 979, 366, 299, 675, 1456]
The following script shows one way to solve this first part of the Day 1, 2020, puzzle:
Python
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.
Note: There are more efficient ways of calculating this answer than trying all possibilities. However, it’s usually a good idea to start with a basic approach. Joe Armstrong is quoted as saying:
Make it work, then make it beautiful, then if you really, really have to, make it fast. 90 percent of the time, if you make it beautiful, it will already be fast. So really, just make it beautiful! (Source)
— Joe Armstrong
Now that you’ve seen a working solution for this puzzle, can you make it beautiful?
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:
Python
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()] 910def 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 * num21617if __name__ == "__main__":18 for path in sys.argv[1:]:19 print(f"\n{path}:")20 puzzle_input = pathlib.Path(path).read_text().strip()2122 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:
Shell
$ python aoc202001.py example.txt input.txtexample.txt:514579input.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!
Remove ads
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:
Python
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."""1112def part2(data):13 """Solve part 2."""1415def solve(puzzle_input):16 """Solve the puzzle for the given input."""17 data = parse(puzzle_input)18 solution1 = part1(data)19 solution2 = part2(data)2021 return solution1, solution22223if __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.
Note: As you learned earlier, the example data are useful for creating tests, as they represents known data with corresponding 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()
:
Python
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.fixture10def example1():11 puzzle_input = (PUZZLE_DIR / "example1.txt").read_text().strip()12 return aoc.parse(puzzle_input)1314@pytest.fixture15def example2():16 puzzle_input = (PUZZLE_DIR / "example2.txt").read_text().strip()17 return aoc.parse(puzzle_input)1819@pytest.mark.skip(reason="Not implemented")20def test_parse_example1(example1):21 """Test that input is parsed properly."""22 assert example1 == ...2324@pytest.mark.skip(reason="Not implemented")25def test_part1_example1(example1):26 """Test part 1 on example input."""27 assert aoc.part1(example1) == ...2829@pytest.mark.skip(reason="Not implemented")30def test_part2_example1(example1):31 """Test part 2 on example input."""32 assert aoc.part2(example1) == ...3334@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 atest_
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
andexample2.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:
Text
17219793662996751456
Next, you’d remove the skip marks for the first two tests and implement them as follows:
Python
# test_aoc202001.pydef 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
:
Python
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:
Shell
$ pytest====================== test session starts =====================collected 4 itemstest_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:
Shell
$ 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.
Remove ads
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:
Python
>>> 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:
Python
1# aoc_state_machine.py 2 3from dataclasses import dataclass 4 5@dataclass 6class StateMachine: 7 memory: dict[str, int] 8 program: list[str] 910 def run(self):11 """Run the program."""12 current_line = 013 while current_line < len(self.program):14 instruction = self.program[current_line]1516 # Set a register to a value17 if instruction.startswith("set "):18 register, value = instruction[4], int(instruction[6:])19 self.memory[register] = value2021 # Increase the value in a register by 122 elif instruction.startswith("inc "):23 register = instruction[4]24 self.memory[register] += 12526 # Move the line pointer27 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:
Python
>>> 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:
Python
# aoc_grid.pyimport numpy as npfrom colorama import Cursorgrid = 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.shapefor 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:
Shell
$ 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.
Remove ads
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 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 get4
, then subtract 2 to get2
.- For a mass of
14
, dividing by 3 and rounding down still yields4
, so the fuel required is also2
.- For a mass of
1969
, the fuel required is654
.- For a mass of
100756
, the fuel required is33583
.
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:
- A short discussion of integer division and how that can help.
- 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 that 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:
Python
>>> mass = 14>>> mass / 34.666666666666667>>> int(mass / 3)4>>> int(mass / 3) - 22
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:
Python
>>> mass = 14>>> mass // 34>>> mass // 3 - 22
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:
Python
>>> masses = [12, 14, 1969, 100756]>>> total_fuel = 0>>> for mass in masses:... total_fuel += mass // 3 - 2...>>> total_fuel34241
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:
Python
>>> 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:
Text
12141969100756
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:
Python
1# test_aoc201901.py 2 3import pathlib 4import pytest 5import aoc201901 as aoc 6 7PUZZLE_DIR = pathlib.Path(__file__).parent 8 9@pytest.fixture10def example1():11 puzzle_input = (PUZZLE_DIR / "example1.txt").read_text().strip()12 return aoc.parse(puzzle_input)1314@pytest.fixture15def example2():16 puzzle_input = (PUZZLE_DIR / "example2.txt").read_text().strip()17 return aoc.parse(puzzle_input)1819def test_parse_example1(example1):20 """Test that input is parsed properly."""21 assert example1 == [12, 14, 1969, 100756]2223def test_part1_example1(example1):24 """Test part 1 on example input."""25 assert aoc.part1(example1) == 2 + 2 + 654 + 335832627@pytest.mark.skip(reason="Not implemented")28def test_part2_example1(example1):29 """Test part 2 on example input."""30 assert aoc.part2(example1) == ...3132@pytest.mark.skip(reason="Not implemented")33def test_part2_example2(example2):34 """Test part 2 on example input."""35 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:
Python
1# aoc201901.py 2 3import pathlib 4import sys 5 6def parse(puzzle_input): 7 """Parse input.""" 8 9def part1(data):10 """Solve part 1."""1112def part2(data):13 """Solve part 2."""1415def solve(puzzle_input):16 """Solve the puzzle for the given input."""17 data = parse(puzzle_input)18 solution1 = part1(data)19 solution2 = part2(data)2021 return solution1, solution22223if __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:
Shell
$ pytesttest_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 ===================
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’re delivered to parse()
as a text string of numbers separated by newlines (\n
) and should be converted into a list of integers:
Python
# aoc201901.py# ...def parse(puzzle_input): """Parse input.""" return [int(line) for line in puzzle_input.split("\n")]
The list comprehension assembles the lines 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:
Python
# aoc201901.py# ...def part1(module_masses): """Solve part 1.""" return sum(mass // 3 - 2 for mass in module_masses)
You’re solving part one by using sum()
as discussed in the previous section. You can also change the name of the parameter for the general data
to something more specific for the puzzle. As the data describe the mass of each rocket module, you call the parameter module_masses
.
Confirm that your solution is correct by running pytest
one more time:
Shell
$ pytesttest_aoc201901.py ..ss [100%]================== 2 passed, 2 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
:
Shell
$ python aoc201901.py input.txtinput.txt:3550236None
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
requires2
fuel. This fuel requires no further fuel (2 divided by 3 and rounded down is0
, which would call for a negative fuel), so the total fuel required is still just2
.- At first, a module of mass
1969
requires654
fuel. Then, this fuel requires216
more fuel (654 / 3 - 2
).216
then requires70
more fuel, which requires21
fuel, which requires5
fuel, which requires no further fuel. So, the total fuel required for a module of mass1969
is654 + 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’ll be 2
by using the same calculation as for the module with mass 14
. The question that 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?
Remove ads
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 and the test_part2_example2()
test from your test code. Next, remove the skip mark and implement test_part2_example1()
:
Python
# test_aoc201901.py# ...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.
Note: pytest
has a nice option, -k
, that you can use to only run a subset of your tests. With -k
, you can filter on the test names. For example, to only run the tests related to part two, you can use pytest -k part2
. This is also a nice incentive to use consistent and descriptive test names.
Next, it’s time for the actual implementation. Because you’re asked for repeated calculations of fuel, you’ll probably want to reach for 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.
As your solutions become more complicated, it’s a good idea to use helper functions. For example, you can add a function that calculates all the fuel needed for one module. One benefit of helper functions is that you can test these independently of the puzzle solution.
Add the following as a new function in your aoc201901.py
solution file:
Python
# aoc201901.py# ...def all_fuel(mass): """Calculate fuel while taking mass of the fuel into account. ## Example: >>> all_fuel(1969) 966 """
You’ve added a doctest inside the docstring. You can tell pytest
to run doctests by adding the --doctest-modules
flag:
Shell
$ pytest --doctest-modulesaoc201901.py F [ 20%]test_aoc201901.py ..F [100%]___________________ [doctest] aoc201901.all_fuel __________________023 Calculate fuel while taking mass of the fuel into account.024025 ## Example:026027 >>> all_fuel(1969)Expected: 966Got nothing
As part of the output from pytest
, you’ll see a note that the all_fuel()
doctest failed. Adding doctests is a great way to ensure that your helper functions do what you expect. Note that this test doesn’t rely on any input files. Instead, you directly check one of the examples given above.
Next, implement the fuel calculation:
Python
1# aoc201901.py 2 3# ... 4 5def all_fuel(mass): 6 """Calculate fuel while taking mass of the fuel into account. 7 8 ## Example: 910 >>> all_fuel(1969)11 96612 """13 fuel = mass // 3 - 214 if fuel <= 0:15 return 016 else:17 return fuel + all_fuel(mass=fuel)
Line 14 implements the stopping condition, while line 17 does the recursive call. You can run your tests to check that the calculation works as expected.
Before moving on to solve the whole puzzle, note that you can use the walrus operator (:=
) to write the function more concisely:
Python
# 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)
While the code is shorter, it’s also denser. Whether you find the end result 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 the modules together:
Python
# aoc201901.py# ...def part2(module_masses): """Solve part 2.""" return sum(all_fuel(mass) for mass in module_masses)
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:
Shell
$ python aoc201901.py input.txtinput.txt:35502365322455
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:
Python
# 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
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 that 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
, whereF
means “front”,B
means “back”,L
means “left”, andR
means “right”.The first 7 characters will either be
F
orB
; these specify exactly one of the 128 rows on the plane (numbered0
through127
). 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
through63
) or the back (64
through127
). 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
through127
.F
means to take the lower half, keeping rows0
through63
.B
means to take the upper half, keeping rows32
through63
.F
means to take the lower half, keeping rows32
through47
.B
means to take the upper half, keeping rows40
through47
.B
keeps rows44
through47
.F
keeps rows44
through45
.- The final
F
keeps the lower of the two, row44
.The last three characters will be either
L
orR
; these specify exactly one of the 8 columns of seats on the plane (numbered0
through7
). The same process as above proceeds again, this time with only three steps.L
means to keep the lower half, whileR
means to keep the upper half.For example, consider just the last 3 characters of
FBFBBFFRLR
:
- Start by considering the whole range, columns
0
through7
.R
means to take the upper half, keeping columns4
through7
.L
means to take the lower half, keeping columns4
through5
.- The final
R
keeps the upper of the two, column5
.So, decoding
FBFBBFFRLR
reveals that it is the seat at row44
, column5
.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
: row70
, column7
, seat ID567
.FFFBBBFRRR
: row14
, column7
, seat ID119
.BBFFBBFRLL
: row102
, column4
, seat ID820
.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 that you could solve the puzzle:
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:
Python
# 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
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:
Python
>>> 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:
Python
>>> 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:
Python
>>> 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:
- Convert boarding pass specifications to binary numbers.
- Calculate the decimal value of the binary numbers to get the seat IDs.
- 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:
Text
FBFBBFFRLRBFFFBBFRRRFFFBBBFRRRBBFFBBFRLL
Next, you’re going to 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:
Python
# 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
As usual, run pytest
to confirm that your tests are failing. Then it’s time to start implementing your solution. Start with the parsing:
Python
# 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") ]
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:
Python
# aoc202005.py# ...def part1(seat_ids): """Solve part 1.""" return max(seat_ids)
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.
Remove ads
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 rather than only one like the puzzle text specifies. You’re better off creating a small test manually. Here’s one way you can do it:
Python
# 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
The list [3, 9, 4, 8, 5, 10, 7, 11]
contains all seat IDs from 3 to 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:
Python
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()
On line 7, you create all the valid seat IDs. These are the numbers between the smallest seat ID and the 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.
Great, you’ve finished another puzzle! To round things out, try your hand at one of the puzzles from 2021.
Practicing Advent of Code: Day 5, 2021
As a third example of an Advent of Code puzzle, you’ll look closely at Day 5, 2021. The puzzle is called Hydrothermal Venture and will take you on a deep-sea adventure. The solution will be a bit more involved than the previous two puzzles. Check out the puzzle description.
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
Copied!0,9 -> 5,98,0 -> 0,89,4 -> 3,42,2 -> 2,17,0 -> 7,46,4 -> 2,00,9 -> 2,93,4 -> 1,40,0 -> 8,85,5 -> 8,2
Each line of vents is given as a line segment in the format
x1,y1 -> x2,y2
wherex1
,y1
are the coordinates of one end the line segment andx2
,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 points1,1
,1,2
, and1,3
.- An entry like
9,7 -> 7,7
covers points9,7
,8,7
, and7,7
.For now, only consider horizontal and vertical lines: lines where either
x1 = x2
ory1 = 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.
Note: There’s some additional information in the full puzzle description. In particular, there’s a diagram that shows all the lines drawn on a grid.
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:
Your task is to calculate how many points are covered by two or more lines. The most straightforward approach is probably the following:
- Convert each line in question to the set of points that make up the line.
- Count the number of times each point appears among all the lines.
- Count the number of points that appear two or more times.
Before you can start coding, you should think about how to represent the points and lines. This might be a good use case for using dedicated Point
and Line
classes, implemented with the help of data classes.
However, in this solution, you’ll opt for a basic representation using a 2-tuple of integers for each point and a 4-tuple of integers for each line. For example, (0, 9)
represents the point 0,9
and (0, 9, 5, 9)
represents the line 0,9 -> 5,9
.
It’s often good to start with simple data structures while being ready to move to more complex solutions if it can simplify calculations. Your first task is to parse the input data. Once you’ve set up your template, you should add some example data.
You can use the given example data, but it might be easier to create an even simpler dataset to start with. Add the following to example1.txt
:
Text
2,0 -> 0,20,2 -> 2,20,0 -> 0,20,0 -> 2,2
These data represent four lines: two diagonal ones, one horizontal line, and one vertical line. For completeness, you may also add the example data given in the puzzle description to example2.txt
. Next, you’ll manually spell out how you want to represent the four lines in your test file:
Python
# 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), ]
As usual, you should run pytest
to confirm that your test fails. There are several ways to parse the input as you want to extract four numbers from each line. You could, for example, use a regular expression. Here, you’ll use the string .split()
method repeatedly:
Python
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 ]
This is certainly a mouthful. To understand how the parsing works, start with line 13. This sets up the main loop which looks at each line by splitting the puzzle input on newlines.
Next, the tuple comprehension on lines 8 to 12 is applied to each line. It first splits each line on the arrow symbol (->
) and then splits each resulting pair of numbers on comma (,
). Finally, each number is converted from a string to an integer with int()
.
Run your tests to confirm that parse()
parses your input as expected.
Even though your code works, you may want to avoid the heavily nested comprehensions. You can, for example, rewrite it as follows:
Python
# 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
In this version, you’re explicitly building the list of lines. For each line, you first split the string into two points and then each point into individual x- and y-coordinates.
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:
The main challenge in this puzzle is to convert each line from its current representation to a list of individual points. You’ll tackle that next. Start by adding the signature of a function that can convert a line into a list of points, including a doctest documenting the expected output:
Python
# 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)] """
You want the function to return a list of points that you can count later. For now, you need to consider horizontal and vertical lines. You’ve added tests for both cases.
The puzzle description hints at how you can identify horizontal and vertical lines as those where one of the coordinates is constant. You can use an if
test to find these. However, you can also use the occasion to practice using the match
… case
statement introduced in Python 3.10:
Python
1# aoc202105.py 2 3# ... 4 5def points(line): 6 """List all points making up a line. 7 8 ## Examples: 910 >>> points((0, 3, 3, 3)) # Horizontal line11 [(0, 3), (1, 3), (2, 3), (3, 3)]12 >>> points((3, 4, 3, 0)) # Vertical line13 [(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)]
The match
… case
construct is very expressive, but can feel a bit magical if you haven’t worked with it before.
Each case
tries to match the structure of line
. So in line 16, you’re looking for a 4-tuple. Furthermore, you unpack the values of the 4-tuple into the variables x1
, y1
, x2
, and y2
, respectively. Finally, you guard the match by requiring that x1
and x2
have to be equal. In practice, this represents a vertical line.
Similarly, the case
statement on line 18 picks out the horizontal lines. For each line, you use range() to list each point, taking care to include the endpoint.
Now, run your tests. If you include the doctests, then you’ll notice that something isn’t quite right:
Shell
$ 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 lineExpected: [(3, 4), (3, 3), (3, 2), (3, 1), (3, 0)]Got: []
The vertical line example returns an empty list. As you investigate, you realize that this example calls range(4, 1)
, which is an empty range because 1
is less than 4
and you’re using the default step of 1
. To solve this, you can introduce a more complicated range()
expression.
To avoid putting more logic into points()
, you decide to create a new helper function that takes care of the necessary range()
logic:
Python
# 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)
If start
is bigger than stop
, then you make sure to use a step of -1
. You can now update points()
to use the new function:
Python
# 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)]
By replacing range()
with coords()
, you should be able to handle all horizontal and vertical lines. Run your tests to confirm that your code now works properly.
You can now convert lines into individual points. The next step in your plan is to count how many lines each point is part of. You could loop through all points and count them explicitly, but Python has many power tools in its standard library. In this case, you can use Counter from the collections
module:
Python
1# aoc202105.py 2 3import collections 4 5# ... 6 7def count_overlaps(lines): 8 """Count overlapping points between a list of lines. 910 ## Example:1112 >>> count_overlaps(13 ... [(3, 3, 3, 5), (3, 3, 6, 3), (6, 6, 6, 3), (4, 5, 6, 5)]14 ... )15 316 """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())
On line 16, you loop over each point in each line and pass all the points to Counter
. The resulting counter is essentially a dictionary whose values indicate how many times each key appeared.
To find the number of points where two or more lines overlap, you look at how many points in your counter were seen two or more times.
You’re almost done with part 1. You only need to connect the puzzle input with count_overlaps()
and make sure that you do as asked—only “consider horizontal and vertical lines.”
You can filter all the lines by employing a few more comprehensions:
Python
# 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)
You’re only passing those lines where either the x
or the y
coordinates are constant. Run your code on your personal input to calculate your solution and submit it to earn your next star.
Phew! You’ve finished the first part of the puzzle. Time to look at what part 2 has in store for you.
Remove ads
Part 2: Puzzle Description
Expand the section below to read the second part of the puzzle for Day 5, 2021:
You might have suspected that you couldn’t ignore those diagonal lines forever:
Unfortunately, considering only horizontal and vertical lines doesn’t give you the full picture; you need to also consider diagonal lines.
Because of the limits of the hydrothermal vent mapping system, the lines in your list will only ever be horizontal, vertical, or a diagonal line at exactly 45 degrees. In other words:
- An entry like
1,1 -> 3,3
covers points1,1
,2,2
, and3,3
.- An entry like
9,7 -> 7,9
covers points9,7
,8,8
, and7,9
.You still need to determine the number of points where at least two lines overlap. In the above example, this is […] now a total of
12
points.Consider all of the lines. At how many points do at least two lines overlap?
You can probably reuse a lot of the work you did for part 1. How can you take those diagonal lines into account, though?
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:
The change in the second part is that you need to take diagonal lines into account. The problem still asks you to count the number of points that are part of two or more lines. In other words, you can still use count_overlaps()
in part two, but you need to expand points()
so that it can handle diagonals.
Luckily, all diagonal lines will be exactly 45 degrees. The practical consequence of this is that the coordinates of the points in these lines will still have consecutive integer coordinates.
For example, 5,5 -> 8,2
covers points 5,5
, 6,4
, 7,3
, and 8,2
. Note that the x-coordinates are 5
, 6
, 7
, and 8
, while the y-coordinates are 5
, 4
, 3
, and 2
. You can draw the line by hand on a grid as follows:
Text
123456789 x1 .........2 .......#.3 ......#..4 .....#...5 ....#....6 .........y
Here the numbers on top represent the x-coordinates while the numbers in the left-hand margin are y-coordinates. The dots (.
) represent the grid, and the points of the line are marked with hash symbols (#
).
To finish your solution, you need to make two adjustments to your current code:
- Change
points()
so that it can convert diagonal lines as well. - Call
count_overlaps()
with the full list of lines.
Start with adapting points()
. A good first change is to update the doctest to include an example of a diagonal line:
Python
# 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)] """ # ...
You’ve added the line 1,2 -> 3,4
, which covers points 1,2
, 2,3
, and 3,4
. Run your tests to confirm that the diagonal line isn’t handled yet.
You need to add a new case to your match
… case
statement. The case
statements are checked one at a time from the top. If you add your new code below the existing statements, then you’ll know that you’re dealing with diagonal lines. Therefore, you don’t need a guard:
Python
# 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))]
The third case
statement handles diagonal lines by changing the x- and y-coordinates at the same time. Here, you’re also reaping some reward from creating coords()
, as using range()
directly for diagonal lines would’ve been even more complicated than for horizontal and vertical ones.
Now that you can convert diagonal lines to individual points, the only task that remains is to count the number of overlaps. Since count_overlaps()
delegates to points()
, it’ll now be able to handle diagonal lines as well. You can implement the solution to the second part in one line of code:
Python
# aoc202105.py# ...def part2(lines): """Solve part 2.""" return count_overlaps(lines)
You should run your tests to make sure everything works as expected. Then calculate your answer to part two and submit it on the Advent of Code website.
Congratulations! By now, you’ve solved at least three 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. You can hear even more about Advent of Code in the following episode of the Real Python Podcast: Solving Advent of Code Puzzles With Python.
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’ve 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.
Source Code: Click here to download the free source code that shows you how to solve Advent of Code puzzles with Python.
Watch Now This tutorial has a related video course created by the Real Python team. Watch it together with the written tutorial to deepen your understanding: Advent of Code: Solving Puzzles With Python