Well, it took me way longer than I wanted (I did the first 20 throughout Advent, but took six months off ), but I finally finished 2021’s Advent of Code. It definitely got sloppier as I went on, but hey, I cracked 300 stars! (I only have 48 stars that I have not done at this point)
As I did in previous years, I wrote up a little blurb on each problem, and rated them in both difficulty and how much I liked it. You can find my solutions here. My rules are to use standard library only, write everything else from scratch (no reuse from past years) and lint/mypy as much as I can.
Day 1
Type of Problem: Iteration
Difficulty: Easy
Rating: 4/5
Day 1 typically is an iteration problem, where you have to loop through some data and either aggregate the data or compare the data with its previous or next values. To solve this one efficiently, I zip together the values I want to compare and track the data I want to compare:
MVP was the ability to call the first half’s function from the second.
Measurements = list[int]
def get_number_of_increasing_measurements(measurements: Measurements) -> int:
measurement_pairs = zip(measurements, measurements[1:])
return len([p for p in measurement_pairs if p[1] > p[0]])
def get_number_of_increasing_sliding_windows(measurements: Measurements) -> int:
measurement_sums = [sum(w) for w in
zip(measurements, measurements[1:], measurements[2:])]
return get_number_of_increasing_measurements(measurement_sums)
Day 2
Type of Problem: Coordinate Systems
Difficulty: Easy
Rating: 3/5
The problems that end up dealing with figuring out where you are after a series of directions are not typically my favorite. Similar to a Mars Rover problem, it’s fairly easy to figure out, and this problem was no different. This involved tracking x and y separately, or tracking x, y , and an aim variable as you go through each move.
Day 3
Type of Problem: Binary Manipulation
Difficulty: Easy-Medium
Rating: 3/5
This involved figuring out which bits are the most common, and doing some bitwise manipulation, so nothing too bad here. However, part 2 involves filtering bitstrings based on certain criteria, which could probably trip some people up as the code bloats on them. I thought this one was okay, as it was a long problem to read for not a complex problem.
MVP goes to my part 1 solution, which zipped each bit together, joined into a new bitstring, and then used bitwise negation to figure out the power rate.
def get_power_rate(numbers: list[str]) -> int:
bitgroups = zip(*numbers)
gamma_bitstring = [get_most_common_bit(b) for b in bitgroups]
gamma_rate = int(''.join(gamma_bitstring), base=2)
# this is a bit of cheat since we know its 12 bits long
return gamma_rate * (~gamma_rate & 0xFFF)
Day 4
Type of Problem: Game Simulation
Difficulty: Easy-Medium
Rating: 3/5
This might be a bit more tedious since you are encoding a game of bingo (several, actually) so I ranked it easy-medium because some newbies might find the complexity overwhelming. When doing things like this, I like lots of small classes with useful methods to try and manage the complexity (see below for my Board class).
I also created a game class that handled figuring out which board wins, and which ones are remaining, which made simple while loops easy to write.
class Board:
def __init__(self, rows: list[Row]):
assert len(rows) == 5
self.rows: list[Row] = rows
def has_won(self) -> bool:
return (any(row.is_all_marked() for row in self.rows) or
any(self.is_column_marked(index)
for index in range(len(self.rows[0]))))
def is_column_marked(self, index: int) -> bool:
return all(row.is_marked(index) for row in self.rows)
def get_score(self) -> int:
return sum(row.get_sum() for row in self.rows)
def apply_move(self, move: int):
for row in self.rows:
try:
position = row.index(move)
row.mark(position)
except ValueError:
pass
Day 5
Type of Problem: Grid Manipulation
Difficulty: Easy
Rating: 4/5
This one involved plotting lines on a grid and finding which point overlaps the most. A simple dictionary from point to number of lines would suffice, so I of course used the collections.Counter class to do just that. Nothing too fancy here:
def get_number_of_overlapping_points_no_diagonal(
lines: list[LineSegment]) -> int:
non_diagonal = [l for l in lines if l.is_vertical() or l.get_slope() == 0]
return get_number_of_overlapping_points(non_diagonal)
def get_number_of_overlapping_points(lines: list[LineSegment]) -> int:
all_points = itertools.chain.from_iterable(
line.get_all_points() for line in lines)
overlaps = Counter(all_points)
return len([val for val, count in overlaps.items() if count >= 2])
Day 6
Type of Problem: Iteration / Data Structure
Difficulty: Easy-Medium
Rating: 5/5
These sort of problems are satisfying for me. Part 1 can typically be solved by brute force, but if you try doing that for part 2, you’re going to have a bad time. In this case, we have exponential growth of lanternfish, where a new one is created after certain conditions. You could keep a list of lanternfish, but you’ll quickly exhaust memory.
However, if you reduce the problem to just keeping count of how many lanternfish are in each stage, you just have to track roughly 7 counts. collections.Counter to the rescue again:
def get_lanternfish_after(fish: list[int], days: int) -> int:
counter = Counter(fish)
for _ in range(days):
counter = reproduce_fish(counter)
return sum(counter.values())
def reproduce_fish(counter: Counter) -> Counter:
new_counter: Counter = Counter()
for fish, number in counter.items():
if fish > 0:
new_counter[fish-1] = number
if 0 in counter:
new_counter[6] += counter[0]
new_counter[8] = counter[0]
return new_counter
Day 7
Type of Problem: Iteration
Difficulty: Easy-Medium
Rating: 3/5
As I’m writing this, I’m surprised how many pure iteration problems are here in the first week. (I define an iteration problem where you have to loop over your data, and figure out some calculation on it) This time, we’re calculating how much fuel is spent to get to an average position, and you keep moving the crabs until they are there.
Here’s my somewhat convoluted block of calculating fuel spent (whether linear or geometric consumption)
def calculate_fuel_spent(crabs: list[int], pos: int, geometric=False) -> int:
func = (lambda c: sum(range(1, abs(c - pos) + 1))) if geometric else (lambda c: abs(c - pos))
return sum(func(c) for c in crabs)
Day 8
Type of Problem: Deduction
Difficulty: Easy-Medium
Rating: 4/5
Deduction problems involve having some obscured information, and then trying to deduce the correct mappings. Typically they are all the same idea, as you create mappings to identify things you know for sure(in this case, some 7-segment display’s digits have a unique number of wires), and then you use that information to rule out other pieces of information, adding to your mapping as you go. Typically straightforward, I appreciated this one for at least having an interesting premise where we had to figure out the different numbers represented by the 7-segement displays.
Day 9
Type of Problem: Grid Manipulation
Difficulty: Medium
Rating: 5/5
This was my favorite of the early problems. I like problems that have a visual component to them (in this case, figuring out low points of a basin). Each year, I start from scratch (I don’t compete for speed, rather I just like the practice of building components up), so this was my first chance to write my grid class (which I do every year). This year, I added a get_neighbors function so that I could find the orthogonal adjacent points.
The second part was definitely tricky, as you had to find a way to merge basins. In this case, it meant that I was creating a mapping of point to basin. I started in the top-left and iterated through all points, and if you had any point above or to the left, I merged with that basin. If you had no basin to your top or left, you were a new basin, getting a unique ID. Once I mapped point to ID, I just had to use a collections.Counter (my favorite AoC collection type it seems) to count which was the biggest.
Day 10
Type of Problem: Text Parsing
Difficulty: Easy-Medium
Rating: 3/5
The infamous parentheses balancing problem :). I’ve hit this during interviews for two out of the four jobs I’ve held, and it’s a good practice problem for dealing with stacks. This is pretty much identical to code I’ve written in interviews, but I put in some hooks to be able to track corrupt and incomplete scores. This allowed me to use the core function for both parts (I try to reuse as much as I can for both parts rather than rewriting)
(Note, when reviewing this, I should be checking if the letter is in my mapping’s keys or values instead of hardcoding the opening/closing braces.
def parse(line: str,
on_corrupt: Callable[[str], None] = lambda _: None,
on_incomplete: Callable[[str], None] = lambda _: None
):
stack: list[str] = []
for letter in line:
if letter in "{[(<":
stack.append(letter)
if letter in ">]})":
closing_letter = CLOSING_LETTER[stack.pop(-1)]
if letter != closing_letter:
on_corrupt(letter)
return
if stack:
on_incomplete(''.join(stack))
Day 11
Type of Problem: Grid Manipulation
Difficulty: Easy-Medium
Rating: 4/5
I was happy to have my grid class for determining octopuses (octopodes?) interaction with their neighbors (I changed my get_neighbors function to optionally produce diagonal neighbors). In these sort of problems, it doesn’t makes sense to look at every piece of the grid, but instead checking which ones are about to “flash”. Once an octopus flashes, you just have to look at the neighbors and track flashes from them (repeating if necessary)
def flash(octopodes: Grid[Octopus]) -> int:
flashes = 0
for point in octopodes:
octopodes[point] += 1
potentials = [point for point, octopus in octopodes.items()
if octopus == 10]
while potentials:
point = potentials.pop(0)
for neighbor_point,neighbor in octopodes.get_neighbors(point, None,
diagonal=True):
if neighbor and neighbor != 10:
#update original grid point
octopodes[neighbor_point] += 1
# it's getting bumped to >9
if neighbor == 9:
potentials.append(neighbor_point)
# reset and count flashes
for point, octopus in octopodes.items():
if octopus == 10:
flashes += 1
octopodes[point] = 0
return flashes
Day 12
Type of Problem: Graph Theory
Difficulty: Medium
Rating: 4/5
I like graph theory problems, I really do. This problem was to find the number of paths through a cave, given that you can only visit a small cave at most once. At first I thought about Hamiltonian or Eulerian paths, but you can do it with just a breadth-first search, tracking which nodes you’ve seen already. The part 2 was allowing one revisit of a node, which just means we track a boolean whether we’ve hit it or not.
Day 13
Type of Problem: Grid Manipulation
Difficulty: Medium
Rating: 5/5
I like problems that deal with some sort of visualization; this one involved folding a piece of transparent paper with marks and tracking what’s visible. At the end, you have to see what the message is. Straightforward to setup, but I had a few minor issues dealing with the folding logic.
Here’s how I’m folding a group of points. I especially like the list comprehensions and the splat operator (*) to expand lists.
def make_fold(points: list[Point], fold: Fold) -> list[Point]:
if fold[0] == Direction.VERTICAL:
normal_half = [p for p in points if p[1] < fold[1]]
to_be_reversed = [p for p in points if p[1] > fold[1]]
reverse = [(x, 2*fold[1]-y)
for x,y in to_be_reversed]
else:
normal_half = [p for p in points if p[0] < fold[1]]
to_be_reversed = [p for p in points if p[0] > fold[1]]
reverse = [(2*fold[1]-x, y)
for x,y in to_be_reversed]
return list(set([*normal_half, *reverse]))
Day 14
Type of Problem: Iteration / Data structure
Difficulty: Medium
Rating: 3/5
I dreaded this one seeing it was a polymer chain (I’m still stuck on this polymer chain from 2017), but this didn’t turn out nearly as bad. Anytime you see an answer that is in the billions (or more), you know that you can’t just iterate over the problem, you have to find a more intelligent way of storing it. In this case, collection.Counter comes to the rescue again (My hero for this year). In this case, I just keep track of how many pairs I see, and add to that counter each iteration. Thus, after 40 rounds, I can get an answer lightning quick, because at most I have 16 (the number of possible pairs) counts in my counter.
Day 15
Type of Problem: Graph Theory
Difficulty: Medium
Rating: 5/5
I always like a a good Djikstra’s problem, and this was no exception. Trying to find your way through a grid isn’t too bad, as you use a heap to track your progress instead of a queue (which gives you BFS). Your lowest cost paths are at the top of the heap, and you go until you find the shortest path. I could use A*, but in most AoC problems, I haven’t found it worth the time to implement the heuristic part.
MVP is the heapq module in the standard library
def get_lowest_risk(grid: Grid[int]):
grid_side_length = int(sqrt(len(grid)))
start = (0, 0)
end = (grid_side_length-1, grid_side_length-1)
smallest_cost = 10*len(grid)*len(grid)
heap_queue: list[tuple[int, Point, set[Point]]] = [(0, start, set())]
while heap_queue:
cost, point, seen = heapq.heappop(heap_queue)
if point in seen:
continue
if cost > smallest_cost:
continue
if point == end:
smallest_cost = cost
continue
seen.add(point)
neighbors = grid.get_neighbors(point, -1) # type: ignore
for neighbor, value in neighbors:
if value != -1:
heapq.heappush(heap_queue, (cost + value, # type:ignore
neighbor, seen))
return smallest_cost
Day 16
Type of Problem: Parsing / Recursion
Difficulty: Medium
Rating: 3/5
Ah this brings me back to parsing network protocol packets at ADTRAN. This was recursive parsing of a packet, where packets may contain other packets. The trick for these sort of problems is to use an iterator rather than looping through, as keeping a stateful iterator will make it easy to recurse into a sub-problem
Here’s how I broke down the value vs operator packets, so that it was easy to recursively evaluate the packet.
FUNC_LOOKUP: dict[int, Callable] = {
0: lambda *args: reduce(operator.add, args),
1: lambda *args: reduce(operator.mul, args),
2: lambda *args: min(args),
3: lambda *args: max(args),
5: lambda t1, t2: 1 if t1 > t2 else 0,
6: lambda t1, t2: 1 if t1 < t2 else 0,
7: lambda t1, t2: 1 if t1 == t2 else 0
}
@dataclass
class LiteralValuePacket(Packet):
value: int
def get_value(self) -> int:
return self.value
@dataclass
class OperatorPacket(Packet):
func: Callable
def get_value(self) -> int:
values = [p.get_value() for p in self.subpackets]
return self.func(*values)
Day 17
Type of Problem: Simulation
Difficulty: Medium-Hard
Rating: 4/5
This is the first stumbling block of the year I had, as I didn’t finish it the first day. I had to do some math to figure out the right answers, and there was a few false starts as I tried to work out the math. Eventually, I went to a simpler solution that worked well for me. I’m not going to paste the whole solution, but I like the interplay here between itertools and zip to figure out the x-step.
def accumulator() -> Generator[tuple[int, int], None, None]:
yield from zip(itertools.count(start=1), itertools.accumulate(itertools.count(start=1)))
def get_first_x_value(target: Target) -> int:
return next(i for i,sum in accumulator() if sum >= target[0])
Day 18
Type of Problem: Recursion
Difficulty: Hard
Rating: 3/5
This was another rough one for me. I would not get the right answer, no matter how hard I tried, and had quite a few crashes along the way. I knew I had to do a depth-aware tree, but I had a lot of problems crossing nodes of the tree. I’m not going to paste any code, but it was atrocious. My advice for when you have problems like this, is liberal usage of asserts. I started asserting my preconditions and postconditions and found out where I had logic problems.
Day 19
Type of Problem: Deduction, Coordinate Systems
Difficulty: Hard
Rating: 4/5
Three hard problems in a row (at least for me), as you had to deduce three dimensional coordinates based on distances between points, almost like an inverse triangulation. I had to optimize code all over the place to get it to actually finish. I wrote 160 lines of Python to solve this, and once again, it’s atrocious code. However, I still liked this as far as its uniqueness goes.
Day 20
Type of Problem: Grid Manipulation
Difficulty: Medium
Rating: 3/5
Grid manipulation comes back to figure out how many pixels are lit. I actually read this one wrong and thought this was one of those cellular automation problems where you have to wait until the problem converges to a stable solution. However, once I looked a little closer, I ran it a finite amount times and got the answer quite quickly.
Day 21
Type of Problem: Dynamic Programming
Difficulty: Medium-Hard
Rating: 4/5
This is the problem that took me 6 months to complete. The first half was simple (using iterators) but the second half took me for a loop. I knew dynamic programming was the play, as I had optimal substructure and a recurrence relation with overlapping solutions. The problem was, I picked the wrong recurrence relation.
I thought that the # of universes won was as followed
Wins(Turn, Space, Score) = Sum(Possibilities * Wins(Turn - 1, Space - Roll, Score - Space) for Roll, Possibilities in DicePossibilities)
Where DicePossibilities are the ways you can roll 3, 4, 5, 6, 7, 8 ,9 with 3 dice (for instance, you can roll 4 in 3 different ways (1,1,2; 1,2,1; 2,1,1).
However, this missed some key points. I put in my answer and got a too high answer, which means that I’m double counting something (or overcounting), which is a typical problem of dynamic counting. I was looking for errors in my algorithm, never thinking that my reccurence relation was wrong). However, I was treating a player as independent, when in fact, you shouldn’t count any games in which the other player has already won (nor where you have already run either).
Thus, the recurrence relation is closer to:
Wins(P1Score, P1Space, P2Score, P2Space, IsPlayer1) = Sum(Possibilities * (Wins(P1Score-P1Space, P1Space - Roll, P2Score, P2Space, False) if IsPlayer1 else Wins(P1Score, P1Space, P2Score-P2Space, P2Space - Roll, True)) for Roll, Possibilities in DicePossibilities)
The max score you can get is 30 (hitting a 10 after getting 20 points) so its easy enough to get what you want.
Day 22
Type of Problem: Iteration / Data Structure
Difficulty: Hard
Rating: 5/5
This string of 5 or 6 problems were quite hard. I had to visualize this one with some cube magnets to figure out what I needed. The trick is, given a new cube instruction, you have to figure out if it intersects with any cube you’ve done so far. I processed my cubes backwards, because I knew that if I already did that cube, it would override any previous instruction. To figure out intersection, I would decompose the new cube instruction into six new cuboids, ignoring any parts that were intersecting. It led to this ugly piece of code
def get_external_cubes(self, cube: 'Cuboid',) -> list['Cuboid']:
# Assuming our dimensions are Sx, Sy, Sz
# and our sides are (SXmin, SXmax), (SYmin, SYmax), (SZmin, SZmax)
# Given the cuboid with dimensions Cx, Cy, Cz and the
# and its sides are (CXmin, CXmax), (CYmin, CYmax), (CZmin, CZmax)
# with an intercept area of
# Xmin, Xmax, Ymin, Ymax, Zmin, zmax
# if it intersects the cube, there are 6 cuboids that need to
# be prepended to the list to check
# with the following dimensions
# C1 = (Xmin, Xmax), (CYmax, Ymax), (Zmin, Zmax)
# located above the intersection with same x,z
# C2 = (Xmin, Xmax), (Ymin, CYmin), (Zmin, Zmax)
# located benath the intersection with same x,z
# C3 = (CXmin, Xmin), (CYmin, CYmax), (Zmin, Zmax)
# located to the left of intersection, with full height,
# same z
# C4 = (Xmax, CXmax), (CYmin, CYmax), (Zmin, Zmax)
# located to the right of intersection, with full height,
# same z
# C5 = (CXmin, CXmax), (CYmin, CYmax), (Zmin, CZmin)
# located in front of intersection, full height/width
# C6 = (CXmin, CXmax), (CYmin, CYmax), (CZmax, Zmax)
# located in front of intersection, full height/width
# intercept dimensions
if self.x_min <= cube.x_min <= cube.x_max <= self.x_max:
xrange = (cube.x_min, cube.x_max)
elif cube.x_min <= self.x_min <= self.x_max <= cube.x_max:
xrange = (self.x_min, self.x_max)
elif self.x_min <= cube.x_min < self.x_max < cube.x_max:
xrange = (cube.x_min, self.x_max)
elif cube.x_min < self.x_min <= cube.x_max <= self.x_max:
xrange = (self.x_min, cube.x_max)
else:
assert False, "Missing condition"
if self.z_min <= cube.z_min <= cube.z_max <= self.z_max:
zrange = (cube.z_min, cube.z_max)
elif cube.z_min <= self.z_min <= self.z_max <= cube.z_max:
zrange = (self.z_min, self.z_max)
elif self.z_min <= cube.z_min < self.z_max < cube.z_max:
zrange = (cube.z_min, self.z_max)
elif cube.z_min < self.z_min <= cube.z_max <= self.z_max:
zrange = (self.z_min, cube.z_max)
else:
assert False, "Missing z condition"
new_cubes = [
Cuboid(*xrange, self.y_max + 1, cube.y_max, *zrange),
Cuboid(*xrange, cube.y_min, self.y_min - 1, *zrange),
Cuboid(cube.x_min, self.x_min - 1, cube.y_min, cube.y_max,
*zrange),
Cuboid(self.x_max + 1, cube.x_max, cube.y_min, cube.y_max,
*zrange),
Cuboid(cube.x_min, cube.x_max, cube.y_min, cube.y_max,
cube.z_min, self.z_min - 1),
Cuboid(cube.x_min, cube.x_max, cube.y_min, cube.y_max,
self.z_max + 1, cube.z_max)
]
valid_cubes = [c for c in new_cubes if c]
assert(sum(c.get_area() for c in new_cubes if c) < cube.get_area())
return valid_cubes
Day 23
Type of Problem: Constraint Satisfaction Problem / Graph Theory
Difficulty: Medium
Rating: 5/5
This was another problem I thought was cool. At its heart, its a game, where you enumerate all the moves that can be made (keeping mind of constraints), see what’s possible, and then recurse into a subtree. Again, this is a djikstra’s algorithm through the game’s statespace and heapq makes another appearance.
I really liked the use of generators for my branch-and-pruning:
# get the solution space for possible moves
def get_possible_moves(spaces: Spaces) -> Generator[tuple[int, Spaces],
None, None]:
for index, space in enumerate(spaces):
# get hallway to room moves
if isinstance(space, str):
# start walking back and forth until you find an empty room
yield from move_to_room(spaces, index, 0, -1)
yield from move_to_room(spaces, index, len(spaces) - 1, 1)
# get room to hallway moves
if isinstance(space, Room):
yield from move_to_hallway(spaces, index, 0, -1)
yield from move_to_hallway(spaces, index, len(spaces) - 1, 1)
Day 24
Type of Problem: Computer Simulation / Reverse Engineering / Recursion
Difficulty: Hard
Rating: 4/5
This one was a puzzle. Given some assembly language, I first thought that I needed to simulate a computer. Then I realized I needed to check hundreds of billions of numbers, and said no way. I started to work out the assembly language by hand, and realized that for each digit Di, there was the same code run, with variables Xi, Yi, and Zi being the only things that changed.
I worked out that the equation looked like this:
z = z // Zi
if z%26 + Xi == Di:
z = z*26 + (Di + Yi)From this, I could set z to zero,, solve for the previous z, and start working my way back to find out all solutions that would eventually produce my result. The code took a little longer than I wanted, but it eventually found a solution, and I eagerly looked ahead to the next solution, given that this one took me about a week or two.
Day 25
Type of Problem: Grid manipulation
Difficulty: Medium
Rating: 3/5
Last puzzle of the year, woo!. This was a simple grid with rule-based movement, that you just had to loop through until the state was the same as the last turn. It took me a little longer than I wanted, because I was not operating on a copy for ‘v’ sea cucumbers. Remember, if everything moves in unison, your code should operate on a copy, so that as you mutate your data, you aren’t influencing current turns.
Pat Viafore 