 michaelfogleman.com Go back Open original

# Michael Fogleman

Python solutions to the daily coding puzzles, explained.

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as a speed contest, interview prep, company training, university coursework, practice problems, or to challenge each other.

I first participated in Advent of Code (AoC) in 2017. My co-workers at Formlabs introduced it to me. This year (2018), quite a lot of Formlabs folks are taking part and we have a nice private leaderboard going. I'm having a lot of fun with it. I've been staying up until midnight to work on the problems as soon as they're available so that I can get points on the global leaderboard. This is a frantic rush to get it done as soon as possible - the resulting code is anything but clean. But then the following day I rewrite the code to my liking. Those rewritten solutions are what you'll find on this page. I'm also explaining how the code works and leaving copious comments. I hope that some of you will find this useful.

Each code snippet is a complete, runnable program. I use the `fileinput` module to parse the input, so you run the scripts like so, where the text file contains the puzzle input:

\$ python 1.py 1.txt

You can also find all of these solutions on GitHub: fogleman/AdventOfCode2018

### Work in Progress

AoC 2018 is still happening! Also, I'm still fleshing out some of the comments and documentation. Stay tuned!

### Day 1: Chronal Calibration

For Part 1, we simply need to sum up all of the numbers. In fact, you could just copy and paste the input file into Excel.

For Part 2, we need to keep track of what frequencies we've already seen. Selecting the appropriate data structure is important. We could add the frequencies to a list, and for each new frequency check if the list contains it. But list lookups are O(n) operations. So each time a new frequency needs to be checked, the entire list has to be scanned looking for a match. Instead, a set should be used as it provides O(1) lookups thanks to hashing.

``````
import fileinput # create a list of lines (strings) from the input file
lines = list(fileinput.input()) def part1(): # int(...) ignores whitespace and properly handles + and - signs # map(int, lines) applies int(...) to each line # sum(...) adds up all of the resulting integers return sum(map(int, lines)) def part2(): # starting frequency is zero f = 0 # create a new set to track frequencies that have been seen # initialize with the current frequency (zero) seen = {f} # repeatedly loop over the lines in the file # a repeat is not guaranteed to occur on the first pass while True: for line in lines: # update the current frequency f += int(line) # check if this is a repeat if f in seen: return f # remember the current frequency seen.add(f) print(part1())
print(part2())
``````

### Day 2: Inventory Management System

For Part 1, a `collections.Counter` comes in very handy to count how many times each letter repeats. A `Counter` takes any iterable and creates a dictionary mapping items to counts.

For Part 2, we need to check all pairs of box IDs. This is as simple as a nested loop. Taking advantage of the fact that all box IDs are the same length, we can just compare the strings character by character, filtering out characters that don't match. If only one character pair is filtered, we have our result.

``````
from collections import Counter
import fileinput # take care to strip newlines from the input
lines = [x.strip() for x in fileinput.input()] def part1(): has2 = 0 has3 = 0 for line in lines: # use `Counter` to count how many times each character occurs # we only need the `.values()` to see if any character occurred # two times or three times c = Counter(line).values() # `2 in c` is True if any character occurred twice, False otherwise # bools can be treated as integers, 0 for False, 1 for True # so this will increment `has2` if 2 appears in the counter values has2 += 2 in c has3 += 3 in c return has2 * has3 def part2(): # use a nested for loop to iterate over all pairs of lines # note that this will compare lines to themselves but in that case # the off-by-one length check below will fail, so it's okay for line1 in lines: for line2 in lines: # compare line1 and line2 one character at a time using `zip` # filter out non-matching pairs with `if a == b` # join the resulting characters back into a string x = ''.join(a for a, b in zip(line1, line2) if a == b) # if the filtered string length is only one less than the original # strings, we have found our answer if len(x) == len(line1) - 1: return x print(part1())
print(part2())
``````

### Day 3: No Matter How You Slice It

You might imagine doing rectangle intersections or something for this problem, but really we just need to work with a grid of cells. It's important to get our data structures right. We need to know which cells contain multiple claims. So let's build a data structure that maps `(x, y)` points to a set of claim IDs.

Part 1 is easy once we have the appropriate data structure. We just need to count how many cells ended up with a set with more than one claim ID.

For Part 2, it's easiest to determine the lone claim by first determining which claims are NOT alone - those that appear in a set with other claims. Once we have the full set of all IDs and all invalid IDs, we can simply subtract (remove) the invalid IDs from the full set to find which ones are valid. There should be only one.

``````
from collections import defaultdict
import fileinput
import re # `ids` will map (x, y) tuples to the set of claim IDs that overlap that cell
ids = defaultdict(set)
for line in fileinput.input(): # find, parse, and unpack every number in the string id, x, y, w, h = map(int, re.findall(r'\d+', line)) # update `ids` for each cell in this claim for j in range(y, y + h): for i in range(x, x + w): ids[(i, j)].add(id) # part 1
print(sum(len(x) > 1 for x in ids.values())) # part 2
all_ids = set()
invalid_ids = set()
for x in ids.values(): all_ids |= x if len(x) > 1: invalid_ids |= x print(all_ids - invalid_ids)
``````

### Day 4: Repose Record

Fortunately we only need to consider minutes in the 0th hour!

First, we have to parse the input. I found it easiest to use regular expressions and `string in string` tests. I build up two data structures: one that maps guard IDs to the total number of minutes slept, and another that maps guard IDs to dictionaries mapping minute numbers to how many times that guard was observed sleeping on that minute.

With these data structures, solving the problem is easy. The only trick is finding the key with the maximum value in the dictionaries. This is accomplished using `itemgetter(1)` as the key to the `max` function.

``````
from collections import defaultdict
from operator import itemgetter
import fileinput
import re # `totals` will map guard IDs to how many total minutes they were observed sleeping
# `minutes` will map guard IDs to another dict mapping minute numbers (0-59) to counts
totals = defaultdict(int)
minutes = defaultdict(lambda: defaultdict(int)) # sort the lines (by timestamp)
for line in sorted(fileinput.input()): # always parse the minute minute = int(re.search(r':(\d+)', line).group(1)) if '#' in line: guard = int(re.search(r'#(\d+)', line).group(1)) elif 'asleep' in line: m0 = minute # starting minute (inclusive) elif 'wakes' in line: m1 = minute # ending minute (non-inclusive) # guard, m0, and m1 are known here; increment the data structures for m in range(m0, m1): totals[guard] += 1 minutes[guard][m] += 1 # part 1
key = itemgetter(1) # compare the value in the (key, value) pairs
guard = max(totals.items(), key=key)
minute = max(minutes[guard].items(), key=key)
print(guard * minute) # part 2
items = []
for guard in minutes: minute, count = max(minutes[guard].items(), key=key) items.append((count, guard * minute))
print(sorted(items)[-1][-1])
``````

### Day 5: Alchemical Reduction

Here we need to eliminate all adjacent pairs of characters that are the same letter but opposite case, e.g. Aa, bB, or zZ. I wrote a function that does this in a single pass, always checking the current character with the previous. Python even has a builtin `swapcase` function to make the comparison easy.

``````
import fileinput # read and strip the first line
line = next(fileinput.input()).strip() def react(x): # initialize list with an empty string result = [''] # for each character in the input string for c in x: # see if the current character matches the previous when case is swapped if c == result[-1].swapcase(): # if so, pop the previous character, and don't add the current character result.pop() else: # otherwise, add the current character result.append(c) # join the characters back into a single string return ''.join(result) # part 1
# simply `react` the input
print(len(react(line))) # part 2
# find all distinct characters in the input
cs = set(line.lower())
# for each character, fully remove all instances of it (upper and lower)
# react the results and pick the minimum length reaction
print(min(len(react(line.replace(c, '').replace(c.upper(), ''))) for c in cs))
``````

### Day 6: Chronal Coordinates

I initially thought I'd have to do some kind of recursive search or flood fill operation for this problem. Turned out it was actually simpler than that. We can just compute the Manhattan distance to every point for each cell in the grid.

``````
from collections import defaultdict
import fileinput
import re # parse the lines into `(x, y)` tuples
points = [tuple(map(int, re.findall(r'\d+', x))) for x in fileinput.input()] # find the min / max bounds of all points
x0, x1 = min(x for x, y in points), max(x for x, y in points)
y0, y1 = min(y for x, y in points), max(y for x, y in points) # manhattan distance function
def dist(x1, y1, x2, y2): return abs(x1 - x2) + abs(y1 - y2) # part 1
counts = defaultdict(int)
infinite = set()
# iterate over all cells in the bounding box
for y in range(y0, y1 + 1): for x in range(x0, x1 + 1): # at this cell, find the distance to every point # sort the result by distance ds = sorted((dist(x, y, px, py), i) for i, (px, py) in enumerate(points)) # if the 1st and 2nd points are not the same distance # then we don't have a tie, and this cell will count if ds != ds: counts[ds] += 1 # assume points along the perimeter will extend infinitely if x == x0 or y == y0 or x == x1 or y == y1: infinite.add(ds)
for k in infinite: counts.pop(k)
# print the maximal area
print(max(counts.values())) # part 2
count = 0
# iterate over all cells in the bounding box
for y in range(y0, y1 + 1): for x in range(x0, x1 + 1): # sum up the distance to all points from this cell # increment our counter if the sum is less than 10000 if sum(dist(x, y, px, py) for px, py in points) < 10000: count += 1
print(count)
``````

### Day 7: The Sum of Its Parts

Part 1 was basically a topological sort. Part 2 was pretty tricky. We have to emulate 5 workers completing tasks in the right order, and each task takes a different number of time steps to complete.

``````
from collections import defaultdict
import fileinput
import re # tasks is a set of all task names A - Z
deps = defaultdict(set)
for line in fileinput.input(): a, b = re.findall(r' ([A-Z]) ', line) tasks |= {a, b} deps[b].add(a) # part 1
done = []
for _ in tasks: # find the minimal (lexicographically) task that is not yet done # and has all of its prerequisites satisfied; add it to the list done.append(min(x for x in tasks if x not in done and deps[x] <=>``````

### Day 8: Memory Maneuver

The tree structure can nicely be parsed in a single pass using an iterator over the input values. Then we just need a couple recursive functions to visit the nodes in the tree and accumulate the metadata sum and node value.

``````
import fileinput def parse(it): # read the number of children and number of metadata num_children, num_metadata = next(it), next(it) # recursively parse children nodes children = [parse(it) for _ in range(num_children)] # read the metadata metadata = [next(it) for _ in range(num_metadata)] return (metadata, children) root = parse(map(int, next(fileinput.input()).split())) # part 1
def node_value(node): metadata, children = node if children: return sum(node_value(children[i-1]) for i in metadata if 1 <=>``````

### Day 9: Marble Mania

A linked list is appropriate for this problem, and is especially necessary on Part 2 to get an answer in a reasonable amount of time. I actually wrote this one in Go for Part 2 on the night of. Props to my coworker János for pointing out `deque.rotate` which is perfect for this problem!

``````
from collections import deque
import fileinput
import re num_players, num_marbles = map(int, re.findall(r'\d+', next(fileinput.input()))) def solve(num_players, num_marbles): # initialize a double-ended queue with zero d = deque() # track score for each player scores =  * num_players for m in range(1, num_marbles + 1): if m % 23 == 0: d.rotate(7) scores[m % num_players] += m + d.pop() d.rotate(-1) else: d.rotate(-1) d.append(m) return max(scores) print(solve(num_players, num_marbles))
print(solve(num_players, num_marbles * 100))
``````

### Day 10: The Stars Align

The main idea here is that when the stars align, the bounding box of the stars will be at a minimum. So the code assumes that the bounding box will initially decrease in size, hit a minimum, and then increase in size.

``````
from itertools import count
import fileinput
import re # parse points into (x, y, vx, vy) tuples
points = [tuple(map(int, re.findall(r'[-\d]+', x))) for x in fileinput.input()] # return (x, y) positions for the stars at time t
def state(points, t): return [(x + vx * t, y + vy * t) for x, y, vx, vy in points] # return the bounding box of the provided points
def bounds(points): x0, x1 = min(p for p in points), max(p for p in points) y0, y1 = min(p for p in points), max(p for p in points) return (x0, y0, x1, y1) # return the bounding box area of the provided points
def area(points): x0, y0, x1, y1 = bounds(points) return (x1 - x0 + 1) * (y1 - y0 + 1) # find the time when bounding area is minimal
# bounding area will decrease, hit a minimum, and then increase
# find when it first increases and return the previous, minimal time value
def min_area_t(points): prev = area(points) for t in count(): a = area(state(points, t)) if a > prev: return t - 1 prev = a # construct a string to display the stars
def display(points): x0, y0, x1, y1 = bounds(points) points = set(points) rows = [] for y in range(y0, y1 + 1): row = [] for x in range(x0, x1 + 1): row.append('*' if (x, y) in points else ' ') rows.append(''.join(row)) return '\n'.join(rows) # find the proper time
t = min_area_t(points) # part 1: print the stars at time t (no OCR here)
print(display(state(points, t))) # part 2: print the time
print(t)
``````

### Day 11: Chronal Charge

This problem was fun because there's an efficient algorithm that can be used to compute sums of arbitrary sub-regions quickly. The trick is to use a summed-area table! Props to my coworker Matt for pointing this out.

``````
from collections import defaultdict
import fileinput def summed_area_table(n): t = defaultdict(int) for y in range(1, 301): for x in range(1, 301): # compute the value of this cell using the specified formula r = x + 10 p = (((r * y + n) * r) // 100) % 10 - 5 # store the result in summed-area form t[(x, y)] = p + t[(x, y - 1)] + t[(x - 1, y)] - t[(x - 1, y - 1)] return t # derive the sum of this region by checking four corners in the summed-area table
def region_sum(t, s, x, y): x0, y0, x1, y1 = x - 1, y - 1, x + s - 1, y + s - 1 return t[(x0, y0)] + t[(x1, y1)] - t[(x1, y0)] - t[(x0, y1)] # using the summed-area table `t` and a region size `s` find the sub region with a maximal sum
def best(t, s): rs = [] for y in range(1, 301 - s + 1): for x in range(1, 301 - s + 1): r = region_sum(t, s, x, y) rs.append((r, x, y)) return max(rs) # build the summed area table
t = summed_area_table(int(next(fileinput.input()))) # find the best 3x3 region
print('%d,%d' % best(t, 3)[1:]) # find the best region of any size
print('%d,%d,%d' % max(best(t, s) + (s,) for s in range(1, 301))[1:])
``````

### Day 12: Subterranean Sustainability

This problem was basically an Elementary Cellular Automaton with a window size of 5. We need to keep track of indexes, so one nice approach is to just model the state as a set of indexes that are "on." (as opposed to a string or list of all cells)

Part 2 was obviously not meant to be computed via simulation (based on the 50 billion number), so I set out looking for a pattern in the output. It turned out that the automaton reaches a kind of equilibrium where each new iteration adds a constant number of activated cells. The code below just assumes that this equilibrium is reached within 1000 cycles.

``````
import fileinput lines = list(fileinput.input()) # set of indexes that are initially active
initial_state = set(i for i, x in enumerate(lines.split()[-1]) if x == '#') # rules map a window of 5 cells to a new cell state
# (the central cell and two neighbors in each direction)
rules = dict(line.split()[::2] for line in lines[2:]) def step(state): result = set() # check all indexes in "view" of any active cells for i in range(min(state) - 2, max(state) + 3): # construct a window string like '#.##.' w = ''.join('#' if j in state else '.' for j in range(i - 2, i + 3)) # check the rule for this window if rules[w] == '#': result.add(i) return result # part 1
s = initial_state
# run 20 iterations
for i in range(20): s = step(s)
# simply sum the active indexes
print(sum(s)) # part 2
s = initial_state
p = n = 0
# run enough iterations, tracking current and previous sums
for i in range(1000): p = n s = step(s) n = sum(s)
# extrapolate to 50 billion
print(p + (n - p) * (50000000000 - i))
``````

### Day 13: Mine Cart Madness

This was a fun simulation problem with mine carts zipping around on tracks. The tracks intersect and the carts can turn at intersections. We need to figure out where collisions occur and which cart lasts the longest without crashing into another cart.

In my initial haste, I assumed that the carts would move simultaneously. (I still believe this would've been more sensible.) But it's turn-based, and collisions are checked for after each individual cart moves.

I first defined the four cardinal directions as tuples of `(dx, dy)`. Then I defined several dictionaries mapping current direction to new direction for different scenarios. This was the first problem where I defined a class!

``````
import fileinput # define up, down, left, right directions
U, D, L, R = (0, -1), (0, 1), (-1, 0), (1, 0) # map input characters to directions
directions = {'^': U, 'v': D, '<':>': R} # map directions to new directions for various scenarios
straight = {U: U, D: D, L: L, R: R}
left_turn = {U: L, D: R, L: D, R: U}
right_turn = {U: R, D: L, L: U, R: D}
forward_slash_turn = {U: R, D: L, L: D, R: U}
back_slash_turn = {U: L, D: R, L: U, R: D} class Cart: def __init__(self, p, d): self.p = p # position self.d = d # direction self.i = 0 # turn index self.ok = True # ok is set to False after a collision def step(self, grid): # make one step in the current direction self.p = (self.p + self.d, self.p + self.d) # lookup the grid character at the new position c = grid[self.p] if c == '+': # intersection; make a turn based on the current index turn = [left_turn, straight, right_turn][self.i % 3] self.d = turn[self.d] self.i += 1 elif c == '/': self.d = forward_slash_turn[self.d] elif c == '\\': self.d = back_slash_turn[self.d] def hits(self, other): # return True if this cart hits the other return self != other and self.ok and other.ok and self.p == other.p grid = {} # grid maps (x, y) positions to characters from the input
carts = [] # carts is a list of Cart instances
for y, line in enumerate(fileinput.input()): for x, c in enumerate(line): grid[(x, y)] = c if c in directions: carts.append(Cart((x, y), directions[c])) part1 = part2 = None
while True: # for each new tick, sort the carts by Y and then X carts = sorted(carts, key=lambda x: (x.p, x.p)) for cart in carts: # update this cart cart.step(grid) # check for collisions for other in carts: if cart.hits(other): cart.ok = other.ok = False # first collision is our part 1 result part1 = part1 or cart.p # remove carts that crashed carts = [x for x in carts if x.ok] # if only one cart is left, part 2 is done if len(carts) == 1: part2 = carts.p break print(part1)
print(part2)
``````

### Day 14: Chocolate Charts

I found this problem to be a bit contrived and not very clearly explained. Once I figured out exactly what needed to be done, the code was pretty straight-forward.

``````
import fileinput n = int(next(fileinput.input())) def step(scores, i, j): # sum the current scores s = scores[i] + scores[j] # the sum will be at most 9 + 9 = 18, so we can just check for a leading 1 if s >= 10: scores.append(1) scores.append(s % 10) # move the elves to their new positions i = (i + scores[i] + 1) % len(scores) j = (j + scores[j] + 1) % len(scores) return (i, j) # part 1
scores, i, j = [3, 7], 0, 1 # initial condition
# loop until we've scored enough recipes
while len(scores) < n + 10: i, j = step(scores, i, j)
# print the 10 scores of interest
print(''.join(map(str, scores[n:n+10]))) # part 2
scores, i, j = [3, 7], 0, 1 # initial condition
# extract the individual digits from our input
digits = list(map(int, str(n)))
while True: i, j = step(scores, i, j) # check if the last N digits match our input # we need to check both the ultimate and penultimate index # since we might have added two new recipes in the most recent step if scores[-len(digits)-1:-1] == digits: print(len(scores) - len(digits) - 1) break if scores[-len(digits):] == digits: print(len(scores) - len(digits)) break
``````

### Day 15: Beverage Bandits

OK, the problems are getting hard now! It took almost 2.5 hours for the Top 100 leaderboard to fill up on this one. Unfortunately, I didn't make it. I had it basically working at the 1.5 hour mark, but apparently had a bug. I ended up completely rewriting my code the next day!

At least this one had an interesting premise -- basically a turn-based game, Elves versus Goblins, all starting with 200 hit points. By far the hardest part is getting their motion right, particularly correctly implementing the tie-breaking rules when there are multiple shortest paths.

``````
from itertools import count
import fileinput
import heapq # return the shortest path from source to any of the targets
# in the case of a tie, return all shortest paths
def shortest_paths(source, targets, occupied): result = [] best = None visited = set(occupied) queue = [(0, [source])] while queue: distance, path = heapq.heappop(queue) if best and len(path) > best: return result node = path[-1] if node in targets: result.append(path) best = len(path) continue if node in visited: continue visited.add(node) for neighbor in adjacent({node}): if neighbor in visited: continue heapq.heappush(queue, (distance + 1, path + [neighbor])) return result # compute the manhattan distance between points
def manhattan_distance(a, b): return abs(a - b) + abs(a - b) # adjacent returns all cells that are adjacent to all of the provided positions
def adjacent(positions): return set((y + dy, x + dx) for y, x in positions for dy, dx in [(-1, 0), (0, -1), (0, 1), (1, 0)]) # choose_target determines which target square a unit at `position` should
# move toward, given the specified target units
def choose_target(position, targets, occupied): if not targets: return None if position in targets: return position paths = shortest_paths(position, targets, occupied) ends = [x[-1] for x in paths] return min(ends) if ends else None # choose_move determines the immediate up/down/left/right move to make
# given the source and target squares
def choose_move(position, target, occupied): if position == target: return position paths = shortest_paths(position, {target}, occupied) starts = [x for x in paths] return min(starts) if starts else None # a Unit is an elf or a goblin
# team is E or G, position is a (y, x) tuple, hp is remaining hit points
class Unit: def __init__(self, team, position): self.team = team self.position = position self.hp = 200 # Model tracks the state of the game, including walls, units, # of rounds, etc.
class Model: def __init__(self, lines, elf_attack=None): self.elf_attack = elf_attack self.walls = set() self.units = [] self.rounds = 0 for y, line in enumerate(lines): for x, c in enumerate(line.strip()): if c == '#': self.walls.add((y, x)) elif c in 'EG': self.units.append(Unit(c, (y, x))) # total_hp returns the total hit points for all remaining (alive) units def total_hp(self): return sum(x.hp for x in self.units if x.hp > 0) # occupied returns a set of occupied squares (walls or other units) # the provided unit is omitted, as a unit cannot block itself def occupied(self, unit=None): units = set(x.position for x in self.units if x != unit and x.hp > 0) return self.walls | units # get_move returns the new position for the unit on its turn def get_move(self, unit): occupied = self.occupied(unit) targets = set(x.position for x in self.units if x.team != unit.team and x.hp > 0) if not targets: return None in_range = adjacent(targets) - occupied target = choose_target(unit.position, in_range, occupied) if target is None: return unit.position move = choose_move(unit.position, target, occupied) return move # get_attack return which unit to attack given the specified attacker def get_attack(self, unit): units = [(x.hp, x.position, x) for x in self.units if x.team != unit.team and x.hp > 0 and manhattan_distance(unit.position, x.position) == 1] return min(units)[-1] if units else None # step executes one round - a single turn for each remaining unit def step(self): units = sorted(self.units, key=lambda x: x.position) for unit in units: if unit.hp <=>``````

### Day 16: Chronal Classification

This was an interesting twist on similar problems from last year. We have to reverse engineer the opcode numbers for each function, given observed register values when running instructions on a virtual CPU with four registers. It requires some repeated deduction, sort of like Sudoku.

``````
import fileinput
import re # the instructions: r is a set of registers
def addr(r, a, b, c): r[c] = r[a] + r[b]
def addi(r, a, b, c): r[c] = r[a] + b
def mulr(r, a, b, c): r[c] = r[a] * r[b]
def muli(r, a, b, c): r[c] = r[a] * b
def banr(r, a, b, c): r[c] = r[a] & r[b]
def bani(r, a, b, c): r[c] = r[a] & b
def borr(r, a, b, c): r[c] = r[a] | r[b]
def bori(r, a, b, c): r[c] = r[a] | b
def setr(r, a, b, c): r[c] = r[a]
def seti(r, a, b, c): r[c] = a
def gtir(r, a, b, c): r[c] = int(a > r[b])
def gtri(r, a, b, c): r[c] = int(r[a] > b)
def gtrr(r, a, b, c): r[c] = int(r[a] > r[b])
def eqir(r, a, b, c): r[c] = int(a == r[b])
def eqri(r, a, b, c): r[c] = int(r[a] == b)
def eqrr(r, a, b, c): r[c] = int(r[a] == r[b]) functions = [ addr, addi, mulr, muli, banr, bani, borr, bori, setr, seti, gtir, gtri, gtrr, eqir, eqri, eqrr,
] # parse pulls out `opcode, A, B, C`, all integers
def parse(line): return list(map(int, re.findall(r'\d+', line))) # behaves_like indicates how many functions match the observed behavior
# in the before and after registers when running the provided instruction
def behaves_like(instruction, before, after): count = 0 for f in functions: r = list(before) f(r, *instruction[1:]) if r == after: count += 1 return count # remove_candidates discards functions that do not match the observed behavior
def remove_candidates(instruction, before, after, candidates): for f in functions: r = list(before) f(r, *instruction[1:]) if r != after: candidates[instruction].discard(f) lines = list(fileinput.input()) # part 1
count = 0
for line in lines: if 'Before' in line: before = parse(line) elif 'After' in line: after = parse(line) # count how many examples behave like 3 or more functions if behaves_like(instruction, before, after) >= 3: count += 1 else: instruction = parse(line)
print(count) # part 2A - determine which opcodes map to which functions
opcodes = {}
known = set()
# loop until we've identified all opcodes
while len(known) < len(functions): # remaining candidates are the set of all functions # minus the set of known functions candidates = {} for i in range(len(functions)): candidates[i] = set(functions) - set(known) for line in lines: if 'Before' in line: before = parse(line) elif 'After' in line: after = parse(line) remove_candidates(instruction, before, after, candidates) else: instruction = parse(line) # look for opcodes that only have one candidate function # add them to the `known` set for i in range(len(functions)): if len(candidates[i]) == 1: f = candidates[i].pop() opcodes[i] = f known.add(f) # part 2B - execute the stored program
r =  * 4
i = max(i for i, x in enumerate(lines) if not x.strip()) + 1
for line in lines[i:]: op, a, b, c = parse(line) f = opcodes[op] f(r, a, b, c)
print(r)
``````

### Day 17: Reservoir Research

This was a fun water flow simulation. It's pretty tricky getting the "physics" right. I basically separated it into two actions: water falling (fall) and water spreading horizontally (scan). The bottom of a fall triggers a scan, and the uncapped edges of a scan trigger a fall.

``````
import fileinput
import re class Model: def __init__(self, lines): self.clay = set() # (x, y) clay positions self.still = set() # (x, y) still water positions self.flowing = set() # (x, y) flowing water positions # parse the clay positions for line in lines: a, b0, b1 = map(int, re.findall(r'\d+', line)) for b in range(b0, b1 + 1): self.clay.add((a, b) if line == 'x' else (b, a)) # determine bounds of all the clay self.x0 = min(x for x, y in self.clay) self.x1 = max(x for x, y in self.clay) self.y0 = min(y for x, y in self.clay) self.y1 = max(y for x, y in self.clay) self.queue = [] def run(self, x, y): # queue items are (func, *args) # queue is initially seeded with a fall at the (500, 0) starting point self.queue.append((self.fall, x, y)) while self.queue: func, *args = self.queue.pop() func(*args) # count_all returns how many in-bounds cells have still or flowing water def count_all(self): return sum(1 for x, y in self.still | self.flowing if y >= self.y0 and y <=>= self.y0 and y <=>``````

### Day 18: Settlers of The North Pole

I immediately recognized this as a cellular automaton, similar to Conway's Game of Life.

Part 2 required finding a cycle. On the night of, I found it manually by examining the numbers printed to the console. The code shown below finds it automatically.

``````
from collections import Counter
from itertools import count
import fileinput lines = [line.strip() for line in fileinput.input()] # parse the grid into a dict mapping (x, y) tuples to characters:
# . = open, | = trees, # = lumberyard
def make_grid(lines): grid = {} w, h = len(lines), len(lines) for y, line in enumerate(lines): for x, c in enumerate(line): grid[(x, y)] = c return w, h, grid # step performs one timestep, returning a new grid
def step(w, h, grid): # note that we do not alter the original grid but create a new copy # we don't want partial updates affecting our calculations result = {} for y in range(h): for x in range(w): # the current character c = grid[(x, y)] # list of eight neighboring characters neighbors = [grid.get((x + dx, y + dy), '') for dy in range(-1, 2) for dx in range(-1, 2) if dy or dx] # how many times each cell type occurs in `neighbors` counts = Counter(neighbors) if c == '.': # An open acre will become filled with trees if three or more # adjacent acres contained trees. Otherwise, nothing happens. if counts['|'] >= 3: c = '|' elif c == '|': # An acre filled with trees will become a lumberyard if three # or more adjacent acres were lumberyards. Otherwise, nothing # happens. if counts['#'] >= 3: c = '#' elif c == '#': # An acre containing a lumberyard will remain a lumberyard if # it was adjacent to at least one other lumberyard and at least # one acre containing trees. Otherwise, it becomes open. if counts['#'] == 0 or counts['|'] == 0: c = '.' result[(x, y)] = c return result def resource_value(grid): counts = Counter(grid.values()) return counts['|'] * counts['#'] # part 1
w, h, grid = make_grid(lines)
for i in range(10): grid = step(w, h, grid)
print(resource_value(grid)) # part 2
w, h, grid = make_grid(lines)
seen = {}
prev = 0
for i in count(1): grid = step(w, h, grid) v = resource_value(grid) cycle = i - seen.get(v, 0) if cycle == prev: if 1000000000 % cycle == i % cycle: print(resource_value(grid)) break seen[v] = i prev = cycle
``````