Advent of Code 2020
This year I return to Advent of Code, as I did in 2016, 17, and 18. Thank you, Eric Wastl! You'll have to look at the Advent of Code website if you want the full description of each puzzle; this notebook gives only a brief summary.
For each day from 1 to 25, I'll write four pieces of code, each in a separate notebook cell. For example, on day 3:
in3: List[str] = data(3): the day's input data, parsed into an appropriate form (here, a list of string lines). Most days the data comes from a file, read via the function
data(which has optional arguments to say how to split the data into sections/records and how to parse each one), but some days the data is so small I just copy and paste it.
def day3_1(nums): ...: a function that takes the day's data as input and returns the answer for Part 1.
def day3_2(nums): ...: a function that takes the day's data as input and returns the answer for Part 2.
do(3): executes the call
day3_1(in3). I'll then use the result to hopefully unlock part 2 and define
day3_2, which also gets run when I call
do(3)again. Once I verify both answers, I'll change
do(3, 167, 736527114)to serve as a unit test.
Day 0: Imports and Utility Functions
Preparations prior to Day 1:
- Some imports.
- A way to read the day's data file and to print/check the output.
- Some utilities that are likely to be useful.
- Since I'm not even attempting to compete to be among the first 100 people to find a solution, I'll take the time to write docstrings; to use reasonable variable names (not single-letter names); and to give type annotations for most functions (but not the
dayfunctions, which all return
- Traditionally, a lot of AoC problems are solved by one of the following two forms:
quantify(inputs, P): How many of your input items have property P?
sum(map(F, inputs)): What is the sum of the result of applying F to each input item?
- Some days I will re-use code that was defined on a previous day.
- I will give a few tests using
assert, but far fewer test cases than if I was programming seriously.
Day 1: Report Repair
- Find the two entries in your expense report (a file of integers) that sum to 2020; what do you get if you multiply them together?
- In your expense report, what is the product of the three entries that sum to 2020?
Day 2: Password Philosophy
- A password policy is of the form "
1-3 b: cdefg" meaning that the password must contain 1 to 3 instances of
cdefgis invalid under this policy. How many passwords in your input file are valid according to their policies?
- JK! The policy actually means that exactly one of positions 1 and 3 (1-based) must contain the letter
b. How many passwords are valid according to the new interpretation of the policies?
Day 3: Toboggan Trajectory
The input file is a map of a field that looks like this:
..##....... #...#...#.. .#....#..#. ..#.#...#.# .#...##..#.
# is a tree and the pattern in each row implicitly repeats to the right. We'll call a list of row-strings a picture.
- Starting at the top-left corner of your map and following a slope of down 1 and right 3, how many trees would you encounter?
- What do you get if you multiply together the number of trees encountered on each of the slopes 1/1, 1/3, 1/5, 1/7, 2/1?
Day 4: Passport Processing
The input is a file of passport data that looks like this (each passport is a series of field:value pairs separated from the next passport by a blank line):
ecl:gry pid:860033327 eyr:2020 hcl:#fffffd byr:1937 iyr:2017 cid:147 hgt:183cm hcl:#ae17e1 iyr:2013 eyr:2024 ecl:brn pid:760753108 byr:1931 hgt:179cm
- Count the number of valid passports — those that have all seven required fields (
byr, ecl, eyr, hcl, hgt, iyr, pid).
- Count the number of valid passports — those that have valid values for all required fields (see the rules in
Day 5: Binary Boarding
The input is a list of boarding passes, such as
'FBFBBFFRLR'. Each boarding pass corrsponds to a seat ID using an encoding where B and F stand for the back and front half of the remaining part of the plane; R and L stand for right and left half of a row. (The encoding is the same as substituting 0 for F or L, and 1 for B or R, and treating the result as a binary number.)
- What is the highest seat ID on a boarding pass?
- What is the one missing seat ID, between the minimum and maximum IDs, that is not on the list of boarding passes?
Day 6: Custom Customs
Each passenger fills out a customs form; passengers are arranged in groups. The "yes" answer are recorded; each person on one line, each group separated by a blank line. E.g.:
abc ab ac
- For each group, count the number of questions to which anyone answered "yes". What is the sum of those counts?
- For each group, count the number of questions to which everyone answered "yes". What is the sum of those counts?
Day 7: Handy Haversacks
There are strict luggage processing rules for what color bags must contain what other bags. For example:
light red bags contain 1 bright white bag, 2 muted yellow bags. dark orange bags contain 3 bright white bags, 4 muted yellow bags.
- How many bag colors must eventually contain at least one shiny gold bag?
- How many individual bags must be inside your single shiny gold bag?
I wasn't quite sure, but it turns out that "light red" and "dark red" are different colors.
Day 8: Handheld Halting
The puzzle input is a program in an assembly language with three instructions:
jmp, acc, nop. Since there is no conditional branch instruction, a program that executes any instruction twice will infinite loop; terminating programs will execute each instruction at most once.
- Immediately before any instruction is executed a second time, what value is in the accumulator register?
- Fix the program so that it terminates normally by changing exactly one jmp to nop or nop to jmp. What is the value of the accumulator register after the program terminates?
I had to think about what to do for Part 2. Do I need to make a flow graph of where the loops are? That sounds hard. But I soon realized that I can just use brute force—try every alteration of an instruction (there are only 638 instructions and at most one way to alter each instruction), and run each altered program to see if it terminates (that too takes no more than 638 steps each).
Day 9: Encoding Error
Given a list of numbers:
- Find the first number in the list (after the preamble of 25 numbers) which is not the sum of two of the 25 numbers before it.
- Find a contiguous subsequence of numbers in your list which sum to the number from step 1; add the smallest and largest numbers in this subsequence.
I could do this efficiently in $O(n)$ as in Day 1, but $n$ is so small I'll just use brute force.
Day 10: Adapter Array
You are given a bunch of joltage adapters, each with a listed joltage output; each can take an input source that is 1, 2, or 3 jolts lower than the output. There is a charging outlet rated 0 jolts, and you want to chargwe a device that is 3 jolts higher than the maximum adapter.
- Find a chain that uses all of your adapters to connect the charging outlet to your device's built-in adapter and count the joltage differences between the charging outlet, the adapters, and your device. What is the number of 1-jolt differences multiplied by the number of 3-jolt differences?
- What is the total number of distinct ways you can arrange the adapters to connect the charging outlet to your device?
Note: at first I thought this was a search problem. But then I realized that the only possibility is to increase joltage from source to adapter, so that means the adapters must appear in sorted order. For part 2, some adapters can be left out.
Day 11: Seating System
This is a version of Conway's Life, except that:
- The world is bounded, not infinite.
- Cells (seats) have three states, not two: floor as well as the traditional occupied and empty.
The rules for what changes between occupied and empty in the next generation are different:
- If a seat is empty (
L) and there are no occupied seats adjacent to it, the seat becomes occupied.
- If a seat is occupied (
#) and four or more seats adjacent to it are also occupied, the seat becomes empty.
Otherwise, the seat's state does not change.
- If a seat is empty (
- Simulate your seating area by applying the seating rules repeatedly until no seats change state. How many seats end up occupied?
- Same problem, but with two rule changes:
- When considering adjacency, if there is a floor cell in some direction, skip over that to the next visible seat in that direction.
- A seat becomes empty only when there are 5 occupied neighbors, not 4.
I have to confess that I "cheated" here: after seeing the problem description for Part 2, I went back and refactored the code for Part 1 in two places:
Layout: Introduced the
crowdedattribute; it had been an inline literal
4. Also made
deltasan attribute, not a global constant.
There was more refactoring and less reuse in Part 2 than I would have liked, but I don't feel like I made bad choices in Part 1.
Day 12: Rain Risk
Another problem involving interpreting a kind of assembly language, with navigation instructions for a ship.
- Figure out where the navigation instructions lead. What is the Manhattan distance between that location and the ship's starting position?
- Figure out where the navigation instructions actually lead, with the updated interpretation. What is the Manhattan distance between that location and the ship's starting position?
The difference between Part 1 and Part 2 comes down to the initial value of the heading/waypoint, and whether the N/E/W/S commands alter the location or the waypoint. Everything else is the same between the two parts.
Day 13: Shuttle Search
A bus with ID d leaves the terminal at times 0, d, 2d, 3d, ... You are given bus IDs and an earliest time you can leave. 1. What is the ID of the earliest bus you can take, multiplied by the number of minutes you'll need to wait for that bus? 2. What is the earliest timestamp such that all of the listed bus IDs depart at offsets matching their positions in the list?
Here's a brute-force solution for Part 2 that works for the simple test cases:
However, it is clear this will be too slow for the real input data. Instead of looking at every multiple of the first number, I'll incrementally update the
step as we go through the numbers. Out of all the puzzles so far, this is the one I had to think most carefully about. For each bus id, we want to find a time where we get that id right, then step the time by a multiple of all the ids encountered so far:
Day 14: Docking Data
Another "interpret assembly code" puzzle, with two different versions of the instructions (which I won't describe here).
- Execute the initialization program. What is the sum of all values left in memory after it completes?
- Execute the initialization program using an emulator for a version 2 decoder chip. What is the sum of all values left in memory after it completes?
A mask is a bit string but with three possible values at each position,
01X. I could make it into two bitstrings, but I choose to leave it as a
Day 15: Rambunctious Recitation
This puzzle involves a game where players speak a new number each turn, based on previous numbers.
- Given your starting numbers, what will be the 2020th number spoken?
- Given your starting numbers, what will be the 30,000,000th number spoken?
Part 2 involves no changes, but asks for the 30 millionth number. If it had been 3 million, I'd think "no problem!" If it had been 30 billion, I'd think "I need a more efficient solution!" As it is, I'll run it and see how long it takes:
That's reasonable; I won't bother trying to find a more efficient approach.
Day 16: Ticket Translation
The input to this puzzle has three parts: some rules for valid fields; your ticket; and a set of nearby tickets. The puzzle is to figure out what field number corresponds to what field name (class, row, seat, etc.). The input looks like:
class: 1-3 or 5-7 row: 6-11 or 33-44 your ticket: 7,1,14 nearby tickets: 7,3,47 40,4,50
- Consider the validity of the nearby tickets you scanned. What is the sum of the values that are are not valid for any field?
- Discard invalid tickets. Use the remaining valid tickets to determine which field is which. Look for the six fields on your ticket that start with the word departure. What do you get if you multiply those six values together?
First parse the input file, introducing the class
TicketData to hold the three parts of the input file (the fields, your ticket, and nearby tickets), and the class
Sets for a tuple of ranges or other set-like objects, so that we can easily test a number is an element of any one of a number of possibilities. For Part 1, just go through the ticket values and see which values are not in any range.
For part 2, we're playing a simplified variant of Sudoku:
- First find the valid tickets.
- Then start with the assumption that any field name is
possiblefor any index number in the tickets.
- Determine what field names are invalid for what ticket index numbers.
- Remove the field name from the possibilities for that index, and
- If there is only one possible field name left, then remove it from all other index positions.
Day 17: Conway Cubes
Now we are explicitly playing Life, but in three dimensions, not two. I've coded this before; I'll adapt my old version to three dimensions (actually, make it
d dimensions in general). My implementation represents a generation as the set of active cell coordinates.
- Starting with your given initial configuration, simulate six cycles. How many cubes are left in the active state after the sixth cycle?
- Simulate six cycles in a 4-dimensional space. How many cubes are left in the active state after the sixth cycle?
Day 18: Operation Order
At first I thought I could just apply
eval to each line, but alas, the operation order is non-standard.
- All operations are done left-to-right. Evaluate the expression on each line of the homework; what is the sum of the resulting values?
- Addition is done before multiplication. What do you get if you add up the results of evaluating the homework problems using these new rules?
A grep-like pattern matcher, where a message is a sequence of characters (all
'b') and a pattern I will represent as a list of items, where each item can be a character, a rule number (which is associated with a pattern), or a choice of two or more patterns. The input has two sections: first "rule number: pattern" lines, then messages, one per line.
I will define
match to return the remaining string in the message if part or all of the message is matched, or
None if it fails.
- How many messages completely match rule 0?
- Two of the rules are wrong. After updating rules 8 and 11, how many messages completely match rule 0?
For part 2, I coded the two changed rules by hand, taking care to avoid infinite left-recursion:
Day 20: Jurassic Jigsaw
You are given a bunch of picture tiles, which can be put together to form a larger picture, where the edges of tiles match their neighbors.
- Assemble the tiles into an image. What do you get if you multiply together the IDs of the four corner tiles?
- In the assembled image, how many
#pixels are not part of a sea monster (which is a specific shape)?
For Part 1, I can find the corners without knowing where all the other tiles go. It is guaranteed that "the outermost edges won't line up with any other tiles," but all the inside edges will. We'll define
edge_count to count how many times an edge appears on any tile (using a
canonical orientation, because tiles might be flipped). Then the corner tiles are ones that have two edges that have an edge count of 1.
Family holiday preparations kept me from doing Part 2 on the night it was released, and unfortunately I didn't feel like coming back to it later: it seemed too tedious for too little reward. I thought it was inelegant that a solid block of
# pixels would be considered a sea monster with waves.
Day 21: Allergen Assessment
This is another Sudoku-like problem, similar to Day 16, involving ingredients and allergens. Crucially, each allergen is found in exactly one ingredient, but a food may not list every allergen. I can reuse the function
eliminate_others, but the rest I need to define here.
day21_2 is the only
day function that does not return an
- Determine which ingredients cannot possibly contain any of the allergens in your list. How many times do any of those ingredients appear?
- What is your canonical dangerous ingredient list?
Day 22: Crab Combat
Part 1 is the card game War (here called Combat) with no ties. Part 2 is a more complex recursive version of the game.
- Play a game of Combat using the two decks you just dealt. What is the winning player's score?
- Play a game of Recursive Combat. What is the winning player's score?
Each player holds a deal of cards, which I will represent as a
deque so I can deal from the top and add cards to the bottom.
Day 23: Crab Cups
A game involving moving around some cups that are labelled with positive integers.
- Using your labeling, simulate 100 moves. What are the labels on the cups after cup 1?
- With 1 million cups and 10 million moves, determine which two cups will end up immediately clockwise of cup 1. What do you get if you multiply their labels together?
For Part 1, I aimed to be very explicit in my code, and the solution works fine for 9 cups and 100 moves (although it did end up being more lines of code than I wanted/expected). However, my approach would not be efficient enough to do Part 2; thus it was a poor choice. For now I'll skip Part 2; maybe I'll come back to it later. I had an idea for a representation where each entry in
cups is either a
list or a
range of cups; that way we are only breaking up and/or shifting small lists, not million-element lists.
Day 24: Lobby Layout
This puzzle involves a hexagonal grid. The input is a list of directions to follow to identify a destination hex tile that should be flipped from white to black. I recall that Amit Patel of Red Blob Games has covered hex grids topic thoroughly; I followed his recommendation to use a (pointy) axial coordinate system.
- Go through the renovation crew's list and determine which tiles they need to flip. After all of the instructions have been followed, how many tiles are left with the black side up?
- Another version of Life, but on a hex grid, where a tile is live (black) if it was white and has two black neighbors, or it was black and has 1 or 2 black neighbors. How many tiles will be black after 100 days (generations)?
binding to temporarily redefine
cell_deltas to work with this problem; then call
Day 25: Combo Breaker
This puzzle involves breaking a cryptographic protocol (whose details I won't describe here).
- What encryption key is the handshake trying to establish?
- The last rule of AoC: there is no Part 2 for Day 25.
Advent of Code suggests that each day's puzzle should run in 15 seconds or less. I met that goal, with days 11 and 15 taking about 8 seconds each, days 22 and 25 about 2 seconds, and the average under a second per day. (However, I skipped Part 2 on days 20 and 23.)
Here's a report, with stars in the first column indicating run times on a log scale: 0 stars for under 1/100 seconds up to 4 stars for over 10 seconds: