Advent of Code 2018 Solutions December 2018
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!
Table of Contents
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)[0]
minute = max(minutes[guard].items(), key=key)[0]
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[0][0] != ds[1][0]:
counts[ds[0][1]] += 1
# assume points along the perimeter will extend infinitely
if x == x0 or y == y0 or x == x1 or y == y1:
infinite.add(ds[0][1])
# discard all infinite regions
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
tasks = set()
# deps maps tasks to a set of prerequisite tasks
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] <= set(done)))
print(''.join(done))
# part 2
done = set()
seconds = 0 # total seconds elapsed
counts = [0] * 5 # seconds remaining for worker `i` to finish its current task
work = [''] * 5 # which task worker `i` is performing
while True:
# decrement each workers remaining time
# if a worker finishes, mark its task as completed
for i, count in enumerate(counts):
if count == 1:
done.add(work[i])
counts[i] = max(0, count - 1)
# while there is an idle worker
while 0 in counts:
# find the idle worker
i = counts.index(0)
# find a task that has all of its prerequisites satisfied
candidates = [x for x in tasks if deps[x] <= done]
if not candidates:
break
task = min(candidates)
tasks.remove(task)
# have the worker start the selected task
counts[i] = ord(task) - ord('A') + 61
work[i] = task
# if all workers are idle at this point, we are done
if sum(counts) == 0:
break
seconds += 1
print(seconds)
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 sum_metadata(node):
metadata, children = node
return sum(metadata) + sum(sum_metadata(x) for x in children)
print(sum_metadata(root))
# part 2
def node_value(node):
metadata, children = node
if children:
return sum(node_value(children[i-1]) for i in metadata if 1 <= i <= len(children))
return sum(metadata)
print(node_value(root))
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([0])
# track score for each player
scores = [0] * 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[0] for p in points), max(p[0] for p in points)
y0, y1 = min(p[1] for p in points), max(p[1] 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[0].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, '<': L, '>': 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[0] + self.d[0], self.p[1] + self.d[1])
# 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[1], x.p[0]))
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[0].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[0] - b[0]) + abs(a[1] - b[1])
# 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[1] 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 <= 0:
continue
move = self.get_move(unit)
if move is None:
return False
unit.position = move
attack = self.get_attack(unit)
if attack:
if self.elf_attack:
if unit.team == 'G':
attack.hp -= 3
if attack.hp <= 0:
raise Exception
else:
attack.hp -= self.elf_attack
else:
attack.hp -= 3
self.rounds += 1
return True
# run executes the game until one of the teams has lost
# it returns the number of complete rounds executed and the total hp
# of all remaining units
def run(self):
while True:
if not self.step():
return self.rounds, self.total_hp()
lines = list(fileinput.input())
# part 1
rounds, hp = Model(lines).run()
print(rounds * hp)
# part 2
for elf_attack in count(4):
try:
rounds, hp = Model(lines, elf_attack).run()
print(rounds * hp)
break
except Exception:
pass
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[0]].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 = [0] * 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[0])
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[0] == '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.y1)
# count_still returns how many in-bounds cells have still water
def count_still(self):
return sum(1 for x, y in self.still
if y >= self.y0 and y <= self.y1)
# stop returns true if (x, y) has clay (horizontal scan stops here)
def stop(self, x, y):
return (x, y) in self.clay
# pile returns true if (x, y) is clay or still water (water can pile up here)
def pile(self, x, y):
return (x, y) in self.clay or (x, y) in self.still
# fall scans downward until it hits clay or still water
def fall(self, x, y):
while y <= self.y1 and not self.pile(x, y + 1):
self.flowing.add((x, y))
y += 1
if y <= self.y1:
self.flowing.add((x, y))
self.queue.append((self.scan, x, y))
# scan looks left and right until it hits clay or falls off an edge
def scan(self, x, y):
x0 = x
while self.pile(x0, y + 1) and not self.stop(x0 - 1, y):
x0 -= 1
x1 = x
while self.pile(x1, y + 1) and not self.stop(x1 + 1, y):
x1 += 1
stop0 = self.stop(x0 - 1, y)
stop1 = self.stop(x1 + 1, y)
if stop0 and stop1:
for i in range(x0, x1 + 1):
self.still.add((i, y))
self.queue.append((self.scan, x, y - 1))
else:
for i in range(x0, x1 + 1):
self.flowing.add((i, y))
if not stop0:
self.queue.append((self.fall, x0, y))
if not stop1:
self.queue.append((self.fall, x1, y))
model = Model(fileinput.input())
model.run(500, 0)
print(model.count_all())
print(model.count_still())
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[0]), 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
Day 19: Go With The Flow
This was a continuation of Day 16, which I somewhat anticipated happening. This time we add flow control but in a unique way - the instruction pointer is bound to one of the registers. Then we have to figure out the result of a very long-running program. The best way is by analyzing the assembly manually and figuring out what's happening. I also had the code print out the state of the registers whenever register zero changed (rarely). Turns out the program computes a large number, then sums all integer divisors of that number. Once you figure that out, you can compute that sum directly. In this code, we just run 1000 cycles, grab the maximum register value and assume that's the number to be factored.
import fileinput
import re
instructions = {
'addr': lambda r, a, b: r[a] + r[b],
'addi': lambda r, a, b: r[a] + b,
'mulr': lambda r, a, b: r[a] * r[b],
'muli': lambda r, a, b: r[a] * b,
'banr': lambda r, a, b: r[a] & r[b],
'bani': lambda r, a, b: r[a] & b,
'borr': lambda r, a, b: r[a] | r[b],
'bori': lambda r, a, b: r[a] | b,
'setr': lambda r, a, b: r[a],
'seti': lambda r, a, b: a,
'gtir': lambda r, a, b: int(a > r[b]),
'gtri': lambda r, a, b: int(r[a] > b),
'gtrr': lambda r, a, b: int(r[a] > r[b]),
'eqir': lambda r, a, b: int(a == r[b]),
'eqri': lambda r, a, b: int(r[a] == b),
'eqrr': lambda r, a, b: int(r[a] == r[b]),
}
def load_program(lines):
program = []
for line in lines:
if line.startswith('#ip'):
ip_register = int(line.split()[-1])
continue
f = instructions[line.split()[0]]
a, b, c = map(int, re.findall(r'\d+', line))
program.append((f, a, b, c))
return ip_register, program
def run_program(ip_register, program, registers, max_cycles=0):
ip = 0
cycles = 0
# if the instruction pointer goes out of bounds, the program halts
while ip >= 0 and ip < len(program):
# update ip register
registers[ip_register] = ip
# execute the next instruction
f, a, b, c = program[ip]
registers[c] = f(registers, a, b)
# increment the instruction pointer
ip = registers[ip_register] + 1
# exit early if max_cycles is reached
cycles += 1
if max_cycles and cycles >= max_cycles:
break
return registers
ip_register, program = load_program(fileinput.input())
# part 1
# start with all zero registers
registers = [0, 0, 0, 0, 0, 0]
# print register zero after program halts
print(run_program(ip_register, program, registers)[0])
# part 2
# start with register zero equal to one
registers = [1, 0, 0, 0, 0, 0]
# get max register value after 1000 cycles
n = max(run_program(ip_register, program, registers, 1000))
# compute the answer directly
total = 0
for i in range(1, n + 1):
if n % i == 0:
total += i
print(total)
Day 20: A Regular Map
I really like the idea behind this problem. Unfortunately, there seems to have been a loophole that made it a lot easier than it would have been in the generic case. I decided not to take advantage of the loophole, but to solve the problem for any valid regex. Furthermore, I decided to use a full-blown lexer and parser (using the awesome ply library). Fun!
import fileinput
import ply.lex as lex
import ply.yacc as yacc
dirs = {'N': (0, -1), 'S': (0, 1), 'E': (1, 0), 'W': (-1, 0)}
# lexer rules
tokens = ['LPAREN', 'RPAREN', 'OR', 'DIR']
t_LPAREN = r'\('
t_RPAREN = r'\)'
t_OR = r'\|'
t_DIR = r'[NESW]+'
# parser rules
def p_pattern(t):
'pattern : concat'
t[0] = t[1]
def p_pattern_or(t):
'pattern : pattern OR concat'
t[0] = ('or', t[1], t[3])
def p_concat(t):
'concat : term'
t[0] = t[1]
def p_concat_term(t):
'concat : concat term'
t[0] = ('concat', t[1], t[2])
def p_term(t):
'term : DIR'
t[0] = ('dir', t[1])
def p_term_empty(t):
'term :'
t[0] = ('dir', '')
def p_term_paren(t):
'term : LPAREN pattern RPAREN'
t[0] = t[2]
# build lexer and parser given above rules
lexer = lex.lex(errorlog=lex.NullLogger())
parser = yacc.yacc(debug=False, write_tables=False, errorlog=yacc.NullLogger())
def parse(text):
text = text.strip().replace('^', '').replace('$', '')
return parser.parse(text, lexer=lexer)
def visit(node, doors, points):
if node[0] == 'concat':
points = visit(node[1], doors, points)
points = visit(node[2], doors, points)
return points
elif node[0] == 'or':
a = visit(node[1], doors, points)
b = visit(node[2], doors, points)
return list(set(a) | set(b))
else: # dir
for d in node[1]:
dx, dy = dirs[d]
doors |= set((x, y, x + dx, y + dy) for x, y in points)
doors |= set((x + dx, y + dy, x, y) for x, y in points)
points = [(x + dx, y + dy) for x, y in points]
return points
def locate_doors(text):
doors = set()
visit(parse(text), doors, [(0, 0)])
return doors
def search(doors):
distances = {}
queue = [(0, 0, 0)]
while queue:
x, y, d = queue.pop()
if (x, y) in distances and distances.get((x, y)) <= d:
continue
distances[(x, y)] = d
for dx, dy in dirs.values():
if (x, y, x + dx, y + dy) in doors:
queue.append((x + dx, y + dy, d + 1))
return distances
doors = locate_doors(next(fileinput.input()))
distances = search(doors)
print(max(distances.values()))
print(sum(x >= 1000 for x in distances.values()))