*Peter Norvig*

December 2020

December 2020

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

to`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.

Notes:

- 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
`day`

functions, which all return`int`

, except`day21_2`

). - 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`b`

;`cdefg`

is 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:

```
..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
```

where each `#`

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
`valid_fields`

).

# 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`crowded`

attribute; it had been an inline literal`4`

. Also made`deltas`

an attribute, not a global constant.`next_generation`

: Changed`Layout(seats)`

to`type(self)(seats)`

.

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*, 2*d*, 3*d*, ... 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 `str`

.

# 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
`possible`

for 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?

# Day 19

A grep-like pattern matcher, where a *message* is a sequence of characters (all `'a'`

or `'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 `int`

.

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

I'll use `binding`

to temporarily redefine `next_generation`

and `cell_deltas`

to work with this problem; then call `life`

.

# 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.

# Postmortem: Timing

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: