import functools
import itertools
import os
import re
import string
import sys
from collections import defaultdict, deque
from pathlib import Path
from queue import PriorityQueue
import more_itertools
import numpy as np
import pandas as pd
import scipy
from IPython.display import HTML
sys.path.insert(1, os.path.join(sys.path[0], ".."))
import utils
load = utils.year_load(2018)data = load(1, "np")
data.sum()i = 0
value = 0
seen = {}
while True:
if value in seen:
break
seen[value] = 1
value += data[i % len(data)]
i += 1
valuelines = [np.array([ord(y) for y in x]) for x in load(2)]
twos = sum([2 in np.unique(list(line), return_counts=True)[1] for line in lines])
twos * sum([3 in np.unique(list(line), return_counts=True)[1] for line in lines]) for s1 in lines:
for s2 in lines:
if len(s2) != len(s1): continue
if (s2 - s1 != 0).sum() == 1:
result = ''.join(chr(x) for x in s1[np.where(s1 == s2)])
break
else:
continue
break
resultnum = re.compile(r"\d+")
data = np.array([[int(x) for x in re.findall(num, line)] for line in load(3)])
field = np.zeros([1000, 1000])
for pid, x, y, w, h in data:
field[x : x + w, y : y + h] += 1
(field > 1).sum()for pid, x, y, w, h in data:
if (field[x : x + w, y : y + h] == 1).all():
break
pidfrom time import strptime
events = [event[1:].split("] ") for event in load(4)]
date_format = "%Y-%m-%d %H:%M"
events = sorted(events, key=lambda event: strptime(event[0], date_format))
guards = {}
while events:
event = events.pop(0)
if "Guard" in event[1]:
active_guard = event[1][7:-13]
if active_guard not in guards:
guards[active_guard] = np.zeros(60)
continue
end = events.pop(0)
guards[active_guard][int(event[0][-2:]) : int(end[0][-2:])] += 1
sleepiest_guard = sorted(guards.keys(), key=lambda x: -guards[x].sum())[0]
int(sleepiest_guard) * guards[sleepiest_guard].argmax()sleepiest_guard = sorted(guards.keys(), key=lambda x: -max(guards[x]))[0]
int(sleepiest_guard) * guards[sleepiest_guard].argmax()s = load(5)[0]
def reduce(s):
l = len(s)
for char in string.ascii_lowercase:
s = s.replace(f"{char + char.swapcase()}", "")
s = s.replace(f"{char.swapcase() + char}", "")
return l if l == len(s) else reduce(s)
reduce(s)min(reduce(s.replace(c, "").replace(c.upper(), "")) for c in string.ascii_lowercase)The numbers involved are small enough that brute force is a viable approach. It’s ugly, but it works. The question is basically asking for the voronoi diagram of the initial points using the L1 metric, but I’m too slow to see an efficient way of calculating that. The approach would have to be something like determining the boundary line between each pair of points, and then intersecting all of those half planes to get the voronoi cell.
data = load(6)
coordinates = np.array([list(map(int, re.findall("\d+", line))) for line in data])
xmax, ymax = coordinates.max(axis=0)
board = np.zeros([xmax, ymax], dtype=int)
for x, y in itertools.product(range(xmax), range(ymax)):
distances = (np.abs(coordinates - np.array([x, y]))).sum(axis=1)
values, counts = np.unique(distances, return_counts=True)
board[x, y] = distances.argmin() if counts[0] == 1 else -1
infinite = functools.reduce(
lambda x, y: set(x) | set(y), [board[0], board[:, 0], board[-1], board[:, -1]]
)
max(
[
(board == seed).sum() if seed not in infinite else 0
for seed in range(len(coordinates))
]
)board = np.zeros([xmax, ymax], dtype=int)
for x, y in itertools.product(range(xmax), range(ymax)):
board[x, y] = (np.abs(coordinates - np.array([x, y]))).sum()
(board < 10000).sum()I haven’t figured out the cleanest way of solving part 1, but here’s an approach that’s slightly better than brute force. We can basically flood fill the grid, starting with the seed locations given in the input, and then expanding one step at a time. That way we end up considering the effect of at most four (and usually only one or two) seeds on each location, and we avoid having to calculate the distance from the point to every single seed.
import matplotlib.pyplot as plt
board = np.zeros([xmax + 1, ymax + 1], dtype=int)
def expand_one(cells, idx, to_paint):
new_cells = []
for neighbor in get_neighbors(cells):
if board[neighbor] == 0:
if neighbor in to_paint:
del to_paint[neighbor]
board[neighbor] = -1
else:
to_paint[neighbor] = idx + 1
new_cells.append(neighbor)
return new_cells
def get_neighbors(cells):
neighbors = []
for x, y in cells:
candidates = [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]
neighbors += [
(x, y) for x, y in candidates if (0 <= x <= xmax) and (0 <= y <= ymax)
]
return set(neighbors)We can animate the process of expanding each seed
to_paint = {tuple(x): idx + 1 for idx, x in enumerate(coordinates)}
system = [[x] for x in to_paint.keys()]
boards = []
while to_paint:
for key in to_paint:
board[key] = to_paint[key]
to_paint = {}
for idx, cells in enumerate(system):
system[idx] = expand_one(cells, idx, to_paint)
image = board.astype(float).copy()
image[image == 0] = np.nan
boards.append(image)
import matplotlib.animation as animation
s = 3.0
fig = plt.figure(figsize=(s, s * ymax / xmax))
l = len(boards)
i = 0
im = plt.imshow(boards[0], animated=True, cmap="inferno")
plt.xticks([])
plt.yticks([])
def updatefig(*args):
global i
if i < len(boards) - 1:
i += 1
else:
i = 0
im.set_array(boards[i])
return (im,)
a = animation.FuncAnimation(fig, updatefig, blit=True, frames=len(boards), interval=10)
plt.close(fig)
HTML(a.to_jshtml())How each seed expands to fill its own area
constraints = {}
lines = load(7)
for tokens in map(str.split, lines):
parent, child = tokens[1], tokens[-3]
if parent not in constraints:
constraints[parent] = ["", ""]
if child not in constraints:
constraints[child] = ["", ""]
constraints[parent][0] += child
constraints[child][1] += parent
executed = ""
available = []
def pop_node(node, ordering):
for child in ordering[node][0]:
idx = ordering[child][1].index(node)
ordering[child] = [
ordering[child][0],
ordering[child][1][:idx] + ordering[child][1][idx + 1 :],
]
del ordering[node]
part1 = constraints.copy()
while part1:
available = sorted(set(available + [key for key in part1 if not part1[key][1]]))
current = available.pop(0)
executed += current
pop_node(current, part1)
executedactive = []
n_workers = 5
part2 = constraints.copy()
time = -1
while part2:
new_active = []
for key, count in active:
if count:
new_active += [[key, count - 1]]
else:
pop_node(key, part2)
active = new_active
available = sorted(
set(key for key in part2 if not part2[key][1]) - set(x[0] for x in active)
)
while available and len(active) < n_workers:
key = available.pop(0)
active += [[key, ord(key) - ord("A") + 60]]
time += 1
timedata = load(8, "int")[0]
def parse(tree_list):
result = {"children": []}
n_children, n_metadata = tree_list[:2]
tree_list = tree_list[2:]
for _ in range(n_children):
tree_list, child = parse(tree_list)
result["children"] += [child]
result["metadata"] = tree_list[:n_metadata]
return tree_list[n_metadata:], result
def weigh(tree):
if not tree["children"]:
return sum(tree["metadata"])
return sum(tree["metadata"]) + sum(map(weigh, tree["children"]))
tree = parse(data)[1]
weigh(tree)def value(node):
children = node["children"]
if not children:
return sum(node["metadata"])
return sum(
value(children[idx - 1]) for idx in node["metadata"] if idx <= len(children)
)
value(tree)n_players = 419
n_marbles = 72164
def run(n_players, n_marbles):
scores = defaultdict(int)
circle = deque([0])
for marble in range(1, n_marbles + 1):
if marble % 23 == 0:
circle.rotate(7)
scores[marble % n_players] += marble + circle.pop()
circle.rotate(-1)
else:
circle.rotate(-1)
circle.append(marble)
return max(scores.values())
run(n_players, n_marbles)run(n_players, n_marbles * 100)array = np.array(load(10, "int"))
positions = array[:, :2].copy()
velocities = array[:, 2:]
bounding_box = np.product(positions.max(axis=0) - positions.min(axis=0))
old_bounding_box = np.inf
while bounding_box < old_bounding_box:
positions += velocities
old_bounding_box = bounding_box
bounding_box = np.product(positions.max(axis=0) - positions.min(axis=0))
positions -= velocities
board = np.zeros(positions.max(axis=0) - positions.min(axis=0) + 1)
board[
(positions[:, 0] - positions[:, 0].min(), positions[:, 1] - positions[:, 1].min())
] = 1
print("\n".join(["".join("█" if char else " " for char in line) for line in board.T]))int(((positions[0] - array[0, :2]) / velocities[0])[0])s = 8772
board = np.zeros((300, 300), dtype=int)
for row, col in itertools.product(range(300), range(300)):
score = ((row + 1 + 10) * (col + 1) + s) * (row + 1 + 10)
board[row, col] = (score // 100) % 10
board -= 5
best = 0
for row, col in itertools.product(range(300 - 2), range(300 - 2)):
total = board[row : row + 3, col : col + 3].sum()
if total > best:
best = total
result = row + 1, col + 1
print(",".join(str(x) for x in result))Brute force over all sizes is slow, but works
best = 0
for i in range(3, 301):
for row, col in itertools.product(range(301 - i), range(301 - i)):
total = board[row : row + i, col : col + i].sum()
if total > best:
best = total
result = row + 1, col + 1, i
print(",".join(str(x) for x in result))data = load(12)
lookup = {".": 0, "#": 1}
generations = 20
initial_state = [lookup[char] for char in data[0] if char in lookup]
state = np.pad(initial_state, generations)
rules = [line.split(" => ") for line in data[2:]]
alive = np.array(
[[lookup[x] for x in rule[0]] for rule in rules if lookup[rule[1]] == 1]
)
def update(cell_neighbors):
return 1 * (not abs(np.array(alive) - cell_neighbors).sum(axis=1).min())
states = [state.copy()]
for i in range(generations):
state = scipy.ndimage.generic_filter(
state, update, footprint=np.ones(5), mode="constant"
)
states.append(state.copy())
indices = np.arange(state.shape[0]) - generations
(indices * state).sum()Simulating the 50 billion generations is impossible, so something cleverer is needed. My first attempt was to see how the total number of plants changed as the generations progressed, and I noticed that after comparatively gew generations the number was constant. Looking at how the pattern of plants changed after that period made extrapolation to 50 billion generations easy. An off-by-one and an off-by-a-factor-of-ten error later, and the problem was solved.
generations = 150
state = np.pad(initial_state, generations)
states = [state.copy()]
for i in range(1, generations):
new_state = scipy.ndimage.generic_filter(
state, update, footprint=np.ones(5), mode="constant"
)
states.append(new_state.copy())
if (new_state == np.roll(state, 1)).all():
break
state = new_state
(
((np.arange(new_state.shape[0]) - generations) + (50_000_000_000 - i)) * new_state
).sum()characters = r" |-/\+><v^"
cart_labels = {">": ("-", 1), "<": ("-", -1), "v": ("|", -1j), "^": ("|", 1j)}
graph = {}
carts = []
carts_part2 = []
for y, line in enumerate(load(13)):
for x, char in enumerate(line):
position = x - 1j * y
if char in cart_labels:
char, direction = cart_labels[char]
carts.append([position, direction, itertools.cycle([1j, 1, -1j])])
carts_part2.append([position, direction, itertools.cycle([1j, 1, -1j])])
graph[position] = characters.index(char)
i = 0
while True:
for cart in carts:
new_position = cart[0] + cart[1]
if new_position in [x[0] for x in carts]:
result = int(new_position.real), -int(new_position.imag)
break
cart[0] = new_position
tile = graph[new_position]
if tile == 3:
cart[1] = cart[1].imag + 1j * cart[1].real
elif tile == 4:
cart[1] = -(cart[1].imag + 1j * cart[1].real)
elif tile == 5:
cart[1] = cart[1] * next(cart[2])
else:
i += 1
continue
break
print(result)carts = carts_part2
carts.sort(key=lambda x: (-x[0].imag, x[0].real))
while len(carts) > 1:
is_crashed = [False] * len(carts)
for idx, cart in enumerate(carts):
if is_crashed[idx]:
continue
new_position = cart[0] + cart[1]
crashes = [
i
for i, cart2 in enumerate(carts)
if new_position == cart2[0] and not is_crashed[i]
]
for crash in crashes:
is_crashed[idx] = True
is_crashed[crash] = True
continue
cart[0] = new_position
tile = graph[new_position]
if tile == 3:
cart[1] = cart[1].imag + 1j * cart[1].real
elif tile == 4:
cart[1] = -(cart[1].imag + 1j * cart[1].real)
elif tile == 5:
cart[1] = cart[1] * next(cart[2])
carts = [cart for (crash, cart) in zip(is_crashed, carts) if not crash]
carts.sort(key=lambda x: (-x[0].imag, x[0].real))
print(int(carts[0][0].real), int(-carts[0][0].imag), sep=",")def solve(n):
e1, e2 = 0, 1
recipes = [3, 7]
while len(recipes) < n + 10:
v1, v2 = recipes[e1], recipes[e2]
tens, units = divmod(v1 + v2, 10)
recipes += [tens, units] if tens else [units]
l = len(recipes)
e1, e2 = (e1 + v1 + 1) % l, (e2 + v2 + 1) % l
# print(recipes)
return functools.reduce(lambda x, y: 10 * x + y, recipes[n : n + 10])
solve(157901)def solve(n):
seq = [int(x) for x in str(n)]
s = len(seq)
e1, e2 = 0, 1
recipes = [3, 7]
while recipes[-s:] != seq and recipes[-s - 1 : -1] != seq:
v1, v2 = recipes[e1], recipes[e2]
tens, units = divmod(v1 + v2, 10)
recipes += [tens, units] if tens else [units]
l = len(recipes)
e1, e2 = (e1 + v1 + 1) % l, (e2 + v2 + 1) % l
delta = 0 if recipes[-s:] == seq else 1
return l - s - delta
solve("157901")This was a slog. Lots of small pieces to keep track of
class Unit:
def __init__(self, kind, power=3):
self.kind = kind
self.hit_points = 200
self.attack_power = power
def attack(self, other):
other.hit_points -= self.attack_power
@property
def is_dead(self):
return self.hit_points <= 0
class Board:
def __init__(self, rock, elves, goblins, elf_power=3):
self.state = {}
self.ymax = max(rock + elves + goblins, key=lambda x: x[0])[0]
self.xmax = max(rock + elves + goblins, key=lambda x: x[1])[1]
self.board = np.zeros((self.ymax + 1, self.xmax + 1), dtype=np.byte)
for coord in rock:
self.board[coord] = 1
for coord in elves:
self.state[coord] = Unit("elf", elf_power)
self.board[coord] = 2
for coord in goblins:
self.state[coord] = Unit("goblin")
self.board[coord] = 3
def __str__(self):
char_map = {0: " ", 1: "█", 2: "E", 3: "G"}
return "\n".join(
"".join(char_map[char] for char in line) for line in self.board
)
def combat(self):
n = 0
while self.any_alive("goblin") and self.any_alive("elf"):
x = self.one_round()
n += 1
return (n + x), sum(unit.hit_points for unit in self.state.values())
def any_alive(self, kind):
for unit in self.state.values():
if unit.kind == kind:
return True
return False
def count(self, kind):
return sum(x.kind == kind for x in self.state.values())
def one_round(self):
alive_count = {key: self.count(key) for key in ["elf", "goblin"]}
unit_positions = sorted(zip(*np.where(self.board > 1)))
for unit_position in unit_positions:
if any(x == 0 for x in alive_count.values()):
return -1
try:
unit = self.state[unit_position]
except KeyError: # Unit was killed earlier in the round
continue
target_position = self.find_target(unit_position)
if target_position is None:
new_position = self.find_move(unit_position)
if new_position is None:
continue
self.board[unit_position] = 0
del self.state[unit_position]
self.state[new_position] = unit
self.board[new_position] = 2 if unit.kind == "elf" else 3
target_position = self.find_target(new_position)
if target_position is None:
continue
target = self.state[target_position]
unit.attack(target)
if target.is_dead:
alive_count[target.kind] -= 1
del self.state[target_position]
self.board[target_position] = 0
return 0
def find_move(self, position):
paths = deque([(0, [], position)])
seen = set()
target_kind = 3 if (self.board[position] == 2) else 2
mask = [[0, 1, 0], [1, 0, 1], [0, 1, 0]]
target_mask = scipy.ndimage.convolve(
self.board == target_kind, mask, mode="constant"
) & (self.board == 0)
targets = sorted(zip(*np.where(target_mask)))
candidates = []
target_distance = np.inf
while paths:
distance, first_move, position = paths.popleft()
if distance > target_distance:
break
if position in seen:
continue
if position in targets:
candidates.append((position, first_move))
target_distance = distance
seen.add(position)
y, x = position
for neighbor in [(y - 1, x), (y, x - 1), (y, x + 1), (y + 1, x)]:
if self.board[neighbor] == 0 and neighbor not in seen:
move = neighbor if not first_move else first_move
paths.append((distance + 1, move, neighbor))
if not candidates:
return None
return sorted(candidates, key=lambda x: x[0])[0][1]
def find_target(self, position):
y, x = position
target_kind = 2 + (self.board[position] == 2)
targets = []
for neighbor in [(y - 1, x), (y, x - 1), (y, x + 1), (y + 1, x)]:
if self.board[neighbor] == target_kind:
targets.append((self.state[neighbor].hit_points, *neighbor))
return sorted(targets)[0][1:] if targets else None
lookup = {".": 0, "#": 1, "E": 2, "G": 3}
board = np.array([[lookup[char] for char in line] for line in load(15)])
goblins = sorted(zip(*np.where(board == 3)))
elves = sorted(zip(*np.where(board == 2)))
rock = sorted(zip(*np.where(board == 1)))
board = Board(rock, elves, goblins)
np.product(board.combat())For the longest time I missed the requirement that when two targets were equally far away, the first one in reading order should be picked, so my units weren’t targetting correctly. Annoyingly, this error didn’t show up in any of the test cases
def test(power):
board = Board(rock, elves, goblins, elf_power=power)
while board.any_alive("goblin"):
board.one_round()
if board.count("elf") != len(elves):
return False
return True
for power in range(3, 200):
if test(power):
break
board = Board(rock, elves, goblins, power)
x = board.combat()
print(np.product(x))This is fairly straightforward. We have seven different operations, with two or three different addressing modes for each. We’ll start by building a dictionary of each operation, and then one of the valid addressing modes for each operation. From that, we can get a set of all the valid tuples of (operation, addressing mode 1, addressing mode 2).
We can then scan through the header lines of the input, and for each (before, command, after) triple, we can loop over the valid tuples, and check which ones convert before to after.
import operator
from more_itertools import chunked
registers = [0, 0, 0, 0]
ops = {
"add": operator.add,
"mul": operator.mul,
"ban": operator.iand,
"bor": operator.ior,
"set": lambda a, b: a,
"gt": operator.gt,
"eq": operator.eq,
}
# 1 is register, 0 is immediate
valid_modes = defaultdict(lambda: [(1, 0), (1, 1)])
valid_modes["set"] = [(0, 0), (1, 0)]
valid_modes["gt"] = [(0, 1), (1, 0), (1, 1)]
valid_modes["eq"] = [(0, 1), (1, 0), (1, 1)]
valid_ops = {(op,) + mode for op in ops for mode in valid_modes[op]}
def get_operands(modes, operands, registers):
result = []
for mode, operand in zip(modes, operands):
result.append(registers[operand] if mode else operand)
return result
split = 3298
values = load(16, "int", footer=split)
total = 0
for state, operation, new_state in chunked(values, 3):
count = 0
operands = operation[1:-1]
result = new_state[operation[-1]]
for op, *mode in valid_ops:
a, b = get_operands(mode, operands, state)
if ops[op](a, b) == result:
count += 1
if count >= 3:
total += 1
totalWith that out of the way, we can intersect all the potentially valid assignments for each test case, and use that to figure out which opcode corresponds to what. Running the program after that is fairly straightforward.
op_ids = defaultdict(lambda: valid_ops.copy())
op_assignments = {}
for state, operation, new_state in chunked(values, 3):
op_number = operation[0]
if op_number in op_assignments:
continue
operands = operation[1:-1]
result = new_state[operation[-1]]
candidate_ops = set()
for op, *modes in valid_ops:
a, b = get_operands(modes, operands, state)
if ops[op](a, b) == result:
candidate_ops.add((op,) + tuple(modes))
op_ids[op_number] &= candidate_ops
if len(op_ids[op_number]) == 1:
assignment = op_ids[op_number].pop()
op_assignments[op_number] = assignment
for i in range(16):
op_ids[i].discard(assignment)
state = [0, 0, 0, 0]
program = load(16, "int", header=split)
i = 0
for op_id, a, b, c in program:
op, *modes = op_assignments[op_id]
a, b = get_operands(modes, (a, b), state)
state[c] = ops[op](a, b)
state[0]data = load(17, "int")
variables = [line[0] for line in load(17)]
xmin = min(line[0] if v == "x" else line[1] for v, line in zip(variables, data))
xmax = max(line[0] if v == "x" else line[2] for v, line in zip(variables, data))
ymin = min(line[0] if v == "y" else line[1] for v, line in zip(variables, data))
ymax = max(line[0] if v == "y" else line[2] for v, line in zip(variables, data))
r, a, f, s = ord("#"), ord("."), ord("|"), ord("~")
board = np.zeros((ymax - ymin + 1, xmax - xmin + 3), dtype=int) + a
for v, line in zip(variables, data):
if v == "x":
board[line[1] - ymin : line[2] - ymin + 1, line[0] - xmin + 1] = r
else:
board[line[0] - ymin, line[1] - xmin + 1 : line[2] - xmin + 2] = r
source = (-1, 500 - xmin + 1)
tips = deque([source])
while tips:
y, x = tips.popleft()
window = board[y + 1 :, x]
solid = (window == r) | (window == s)
if not solid.any():
board[y + 1 :, x] = f
else:
first_rock = solid.argmax()
board[y + 1 : y + 1 + first_rock, x] = f
y += first_rock
r_platform = ((board[y + 1, x:] != r) & (board[y + 1, x:] != s)).argmax()
l_platform = ((board[y + 1, :x] != r) & (board[y + 1, :x] != s))[::-1].argmax()
r_wall = mask.argmax() if (mask := (board[y, x:] == r)).any() else np.inf
l_wall = mask.argmax() if (mask := (board[y, :x] == r)[::-1]).any() else np.inf
fill = s
to_add = []
if l_wall > l_platform:
fill = f
to_add += [(y, x - l_platform - 1)]
left = x - l_platform - 1
else:
left = x - l_wall
if r_wall > r_platform:
fill = f
to_add += [(y, x + r_platform)]
right = x + r_platform + 1
else:
right = x + r_wall
if fill == s:
to_add += [(y - 1, x)]
if (board[y, left:right] != fill).any():
board[y, left:right] = fill
for element in to_add:
tips.append(element)
((board == f) | (board == s)).sum()This was a very weird part 2, since I basically solved it already in part 1
(board == s).sum()state_map = {".": 0, "|": 1, "#": 2}
reverse_map = {v: k for k, v in state_map.items()}
state = np.array([[state_map[char] for char in line] for line in load(18)])
weights = np.ones((3, 3))
weights[1, 1] = 0
seen = {}
for i in range(10):
seen[tuple(state.flatten())] = i
tree_nb = scipy.ndimage.convolve(1 * (state == 1), weights, mode="constant")
lumber_nb = scipy.ndimage.convolve(1 * (state == 2), weights, mode="constant")
change = (
((state == 0) & (tree_nb >= 3))
| ((state == 1) & (lumber_nb >= 3))
| ((state == 2) & ((tree_nb == 0) | (lumber_nb == 0)))
)
state = (state + change) % 3
(state == 1).sum() * (state == 2).sum()There’s no way we can run the simulation for that long. Hopefully we’ll get a repeat before then
target = 1000000000
for i in range(10, target):
if tuple(state.flatten()) in seen:
start = seen[tuple(state.flatten())]
reversed_dict = {v: k for k, v in seen.items()}
state = np.array(reversed_dict[start + (target - start) % (i - start)])
break
seen[tuple(state.flatten())] = i
tree_nb = scipy.ndimage.convolve(1 * (state == 1), weights, mode="constant")
lumber_nb = scipy.ndimage.convolve(1 * (state == 2), weights, mode="constant")
change = (
((state == 0) & (tree_nb >= 3))
| ((state == 1) & (lumber_nb >= 3))
| ((state == 2) & ((tree_nb == 0) | (lumber_nb == 0)))
)
state = (state + change) % 3
(state == 1).sum() * (state == 2).sum()basic_ops = ["add", "mul", "ban", "bor"]
name_to_op = {
basic_op + mode: (basic_op, 1, int(mode == "r"))
for basic_op in basic_ops
for mode in "ir"
}
name_to_op.update(**{"set" + mode: ("set", int(mode == "r"), 0) for mode in "ir"})
name_to_op.update(
**{
comparison
+ mode_pair: (comparison, int(mode_pair[0] == "r"), int(mode_pair[1] == "r"))
for comparison in ["gt", "eq"]
for mode_pair in ["ir", "ri", "rr"]
}
)
def interpret(op_name):
name, *modes = name_to_op[op_name]
return [ops[name], modes]
def run(program, registers, ip_register):
ip = 0
while ip < len(program):
registers[ip_register] = ip
op, modes, a, b, c = program[ip]
a, b = get_operands(modes, (a, b), registers)
registers[c] = op(a, b)
ip = registers[ip_register] + 1
return registers[0]
data = load(19)
registers = [0, 0, 0, 0, 0, 0]
ip, program = data[0], data[1:]
ip_register = int(re.findall(r"-?\d+", ip)[0])
program = [x.split() for x in program]
program = [interpret(line[0]) + [int(x) for x in line[1:]] for line in program]
run(program, registers, ip_register)This is another one of those where changing the value in the first register causes the code to go through a different path in the program, and greatly increases the runtime.
Analysing the execution path shows that the code starts off by jumping to a setup section at the end, which has the main effect of placing a value in register 5. It then jumps back to two nested loops, which go through a lot of busywork, and store their results in register 0. Finally, after a long time, it hits the exit condition of both loops, and the program ends.
Looking at the inner loop, it does the following
for x4 in range(1, x5 + 1):
if x4 * x2 == x5:
x0 += x2But thats equivalent to x0 += x2 if x5 % x2 == 0 else 0. The outer loop just runs over all values of x2 from 1 to x5. So what this code is really doing is calculating the sum of divisors function of whatever horrible mess is placed in x5 by the setup. We’ll get that by running through the code until the setup is over, and then calculate the sum of divisors:
def sum_of_divisors(n):
total = n + 1
for i in range(2, n):
if n % i == 0:
total += i
return total
registers = [1, 0, 0, 0, 0, 0]
ip = 0
while ip != 1:
registers[ip_register] = ip
op, modes, a, b, c = program[ip]
a, b = get_operands(modes, (a, b), registers)
registers[c] = op(a, b)
ip = registers[ip_register] + 1
sum_of_divisors(registers[5])The hard part of this problem is moving from the regex representation of the map to a more sensible one. A pseudo-ebnf of the grammar is:
path = direction, path | bracketed_path, path | optionsdirection = n|e|w|sbracketed_path = (, path, )options = (path, |)*, path?Based on this, we can parse the string from start to finish by tracking a list of current positions. If a direction is encountered, each of the positions is updated. Whenever an opening bracket is encountered, the matching close bracket is found, the subexpression is split into options, and each of those paths is parsed. The visited edges are tracked along the way in a global dictionary. It’s not super elegant, but it works.
s = load(20)[0][1:-1]
directions = {"N": 1j, "E": 1, "S": -1j, "W": -1}
def find_closing_paren(s):
count = 0
for idx, char in enumerate(s):
count += 1 if char == "(" else -1 if char == ")" else 0
if count == 0:
return idx
def split_into_options(s):
count = 0
result = []
current = ""
for char in s:
if char == "|" and count == 0:
result.append(current)
current = ""
else:
current += char
count += 1 if char == "(" else -1 if char == ")" else 0
result.append(current)
return result
edges = defaultdict(bool)
def endpoints(s, positions=None):
i = 0
if positions is None:
positions = {0}
else:
positions = positions.copy()
while i < len(s):
char = s[i]
if char == "(":
delta = find_closing_paren(s[i:])
substring = s[i + 1 : i + delta]
options = split_into_options(substring)
positions = {point for x in options for point in endpoints(x, positions)}
i += delta
else:
direction = directions[char]
positions = {x + direction for x in positions}
for position in positions:
edges[2 * position - direction] = True
i += 1
return positions
points = endpoints(s)
def edge_to_nodes(x):
return (
(x.real - x.real % 2 + 1j * (x.imag - x.imag % 2)) / 2,
(x.real + x.real % 2 + 1j * (x.imag + x.imag % 2)) / 2,
)
nodes = len({node for edge in edges.keys() for node in edge_to_nodes(edge)})With all that out of the way, the furthest room can be found with a BFS:
def neighbors(state):
return [
state + direction
for direction in directions.values()
if edges[2 * state + direction]
]
utils.bfs(0, None, neighbors)And finding how many rooms require at least 1000 steps can be found with the same BFS, but ending whenever we get a cost greater than 1000
end_condition = lambda cost, state: cost >= 1000
nodes - len(utils.bfs(0, end_condition, neighbors, return_visited=True))Analysing the structure of the program, we can see that the value of register 0 is only relevant in one place, namely as a comparison towards the end, where the program exits if x0 == x3. So for the first part, we just run the code until we hit that comparison the first time, and see what the value of x3 is; that must be the answer to the problem.
data = load(21)
registers = [0, 0, 0, 0, 0, 0]
ip, program = data[0], data[1:]
ip_register = int(re.findall(r"-?\d+", ip)[0])
ip = 0
program = [x.split() for x in program]
program = [interpret(line[0]) + [int(x) for x in line[1:]] for line in program]
count = 0
while True:
registers[ip_register] = ip
op, modes, a, b, c = program[ip]
a, b = get_operands(modes, (a, b), registers)
registers[c] = op(a, b)
ip = registers[ip_register] + 1
if ip == 28:
count += 1
if count == 2:
break
registers[3]For part 2, we need to do two things:
For part 1, it turns out that the code is repeatedly applying a fairly simple transformation to register 3, and then checking that against register 0. The only way that there could be a largest set of iterations is if the code eventualy produces the same value in register 3 as it did some number of iterations ago. The value we’re looking for is then the last value found in register 3 before the repeated value:
x1, x3 = 0, 0
seen = []
while x3 not in seen:
seen.append(x3)
x1 = x3 | 65536
x3 = 4921097
while x1 >= 1:
x3 = ((x3 + (x1 % 256)) * 65899) % 16777216
x1 = x1 // 256
seen[-1]d = 7863
target_x, target_y = 14, 760
base = 20183
@functools.cache
def geologic_index(x, y):
if y == 0:
return (x * 16807) % base
if x == 0:
return (y * 48271) % base
return ((geologic_index(x - 1, y) + d) * (geologic_index(x, y - 1) + d)) % base
@functools.cache
def terrain_type(x, y):
if x == target_x and y == target_y:
return 0
return ((geologic_index(x, y) + d) % base) % 3
board = np.zeros((target_x + 1, target_y + 1), dtype=int)
for i in range(target_x + 1):
for j in range(target_y + 1):
board[i, j] = terrain_type(i, j)
board.sum()This calls for a path finding algorithm. A* to the rescue! We’ll need functions that
def neighbors(state):
x, y, equipment = state
candidates = [
(x + 1, y, equipment),
(x - 1, y, equipment),
(x, y - 1, equipment),
(x, y + 1, equipment),
(x, y, (equipment + 1) % 3),
(x, y, (equipment + 2) % 3),
]
return [
candidate
for candidate in candidates
if candidate[0] >= 0
and candidate[1] >= 0
and candidate[2] != terrain_type(candidate[0], candidate[1])
]
def weights(s1, s2):
return 1 if s1[-1] == s2[-1] else 7
def heuristic(s1, s2):
return abs(s1[0] - s2[0]) + abs(s1[1] - s2[1]) + 7 * (s1[-1] != s2[-1])
initial_state = 0, 0, 1
target = target_x, target_y, 1
utils.astar(initial_state, target, neighbors, heuristic, weights)The first part is pretty simple
data = np.array(load(23, "int"))
row = data[np.argmax(data[:, -1])]
(np.abs((data - row)[:, :-1]).sum(axis=1) <= row[-1]).sum()The next part is signifcantly more tricky. Blindly iterating through every point and asking “how many are you in range of” is a non-starter, due to the sizes of the numbers involved. SImilarly, going the other way and generating all the covered points for each nanobot and adding those up runs into the same problem.
A first thing to realise is that the sets of points covered by any given nanobot is an axis-aligned octahedron, centered at the nanobot’s position. The eight faces that define the octahedron have normal vectors [±1, ±1, ±1]. We can group these faces into four pairs of parallel faces, and each octahedron can be thought of as the intersection of the infinte regions between those pairs of planes. That means we can represent an octahedron as four sets of intervals, which I will call the \((s, t, u, v)\) basis. To intersect two octahedra we can simply intersect the corresponding intervals of each octahedron.
With the above considerations in hand, we could create a list of (region, number of intersections) pairs, with initial state [(all space, 0)]. We could then loop over all the nanobots, and for each one, calculate all the intersections with the existing list, and if they are non-zero, append them to the list, with updated intersection count.
That would build up a map of all the intersections, and the desired answer would be represented by the pair with greatest intersection count. That would look something like this:
normal_vectors = np.array([[1, 1, 1], [1, 1, -1], [1, -1, 1], [1, -1, -1]])
centers = data[:, :-1] @ normal_vectors.T
radii = data[:, -1].reshape(-1, 1)
c = np.transpose(np.stack([centers - radii, centers + radii + 1]), axes=[1, 2, 0])
intersections = {}
for idx, row in enumerate(c):
current = frozenset([idx])
to_add = {current: row}
for i in intersections:
new_i = np.hstack(
[
np.maximum(intersections[i], row)[:, :1],
np.minimum(intersections[i], row)[:, 1:],
]
)
if (np.diff(new_i) > 0).all():
to_add[current.union(i)] = new_i
intersections = intersections | to_add
breakUnfortunately, the above approach has a slight flaw: It ends up explicitly creating all \(\sim2^n\) possible intersections. With 1000 nanobots, that’s just not feasible.
If we focus on just one set of planes we can quite easily find where the biggest intersection is in that direction by scanning through from \(-\infty\) to \(\infty\), adding one for every left plane we encounter, and subtracting one for every right plane.
openings = sorted(c[:, 0, 0])[::-1]
closings = sorted(c[:, 0, -1])[::-1]
current_closing, current_opening = closings.pop(), openings.pop()
total = 0
edges = {}
while openings:
if current_opening < current_closing:
total += 1
edges[current_opening] = total
current_opening = openings.pop()
else:
total -= 1
edges[current_closing] = total
current_closing = closings.pop()
max(edges.values())But extending this to all four planes is non-obvious. Analysing the inputs shows that all the points overlap, apart from very few emitters. That means we can identify these, and the relevant points are just the intersection of all the other emitters, which can easily be found in the basis we’ve chosen.
adjacency_matrix = np.zeros((len(c), len(c)))
for i, pi in enumerate(c):
for j, pj in enumerate(c):
new = np.hstack([np.maximum(pi, pj)[:, :1], np.minimum(pi, pj)[:, 1:]])
if (np.diff(new) > 0).all():
adjacency_matrix[i, j] = 1
mask = (adjacency_matrix.sum(axis = 0) >= np.median(adjacency_matrix.sum(axis = 0)) / 2)
indices = np.where(mask)[0]
c[indices, :, :].max(axis=0)[0, 0]This feels slightly like cheating, since it easily fails for other inputs.
A better approach would be to iteratively zoom in on promising areas of space. That is, starting with a bounding box containing all the points of interest, iteratively split the box into 16 sub-boxes, and for each of these boxes ask how many of the beacons it intersects with. Expanding the boxes in the order:
Means that by the time we see a box of size 1, we know that it is the optimal box, since
All we need to implement is thus a procedure for determining whether a box and a beacon intersect. But in the \((s, t, u, v)\) basis, that’s just determining whether the intervals that make up the box and the intervals that make up the beacon intersect. And it’s not too difficult to verify that two half-open intervals \(\left[ a, b\right)\) and \(\left[x, y\right)\) intersect if \(x \leq a < y\) or \(a \leq x < b\). Putting everything together gives
def score_box(corner, length, c=c):
x = c[:, :, 0]
y = c[:, :, 1]
left = (x <= corner) & (corner < y)
right = (corner <= x) & (x - length < corner)
return -(left | right).all(axis=1).sum()
l = 2 ** (int(np.ceil(np.log2(abs(c).max()))))
corner = -l, -l, -l, -l
length = 2 * l
q = PriorityQueue()
initial_state = score_box(corner, length), -length, 0, corner
q.put(initial_state)
i = 0
while q.qsize() > 0 and i < 1000:
i += 1
s, neg_length, position, corner = q.get()
l = -neg_length
if l == 1:
break
for new_corner in (
np.array(list(itertools.product([0, 1], repeat=4))) * l // 2 + corner
):
score = score_box(new_corner, l // 2)
position = 0 if l > 2 else max(abs(new_corner))
q.put((score, -l // 2, position, tuple(new_corner)))
positionThis was a bit of a slog, with a fair bit of attention needed to make sure that the requirements were implemented correctly.
class Group:
def __init__(
self,
n_units,
hit_points,
damage,
initiative,
damage_type,
weaknesses=[],
immunities=[],
):
self.n_units = n_units
self.hit_points = hit_points
self.damage = damage
self.initiative = initiative
self.damage_type = damage_type
self.weaknesses = weaknesses
self.immunities = immunities
def __repr__(self):
return (
f"Group({self.n_units}, {self.hit_points}, {self.damage}, "
f"{self.initiative}, {self.damage_type})"
)
@property
def effective_power(self):
return self.damage * self.n_units
@property
def is_alive(self):
return self.n_units > 0
def attack(self, other):
other.defend(self.calculate_damage(other))
def calculate_damage(self, other):
if self.damage_type in other.immunities:
return 0
elif self.damage_type in other.weaknesses:
return 2 * self.effective_power
return self.effective_power
def defend(self, damage):
self.n_units = self.n_units - damage // self.hit_points
self.n_units = max(self.n_units, 0)
def selection_order(self):
return (-self.effective_power, -self.initiative)
def select_target(self, others):
max_damage = (0, 0, 0)
for other in others:
damage = self.calculate_damage(other)
key = (damage, other.effective_power, other.initiative)
if key > max_damage:
max_damage = key
result = other
if max_damage[0] > 0:
return result
else:
return None
def select_targets(attackers, defenders):
targets = []
defenders = defenders.copy()
for group in sorted(attackers, key=lambda x: x.selection_order()):
target = group.select_target(defenders)
if target is not None:
targets.append((group, target))
defenders.remove(target)
return targets
def one_round(infection, immune):
matchup = select_targets(infection, immune) + select_targets(immune, infection)
for match in sorted(matchup, key=lambda x: -x[0].initiative):
match[0].attack(match[1])
return [x for x in infection if x.is_alive], [x for x in immune if x.is_alive]
data = [x.split("\n")[1:] for x in load(24, "raw")[:-1].split("\n\n")]
def parse(line):
n_units, hit_points, damage, initiative = [
int(x) for x in re.findall("-?\d+", line)
]
damage_type = re.search("(\w*) damage", line).groups()[0]
immunity_match = re.search("\((.*)\)", line)
if not immunity_match:
weaknesses, immunities = [], []
else:
weaknesses, immunities = parse_immunities(immunity_match.groups()[0])
return Group(
n_units, hit_points, damage, initiative, damage_type, weaknesses, immunities
)
def parse_immunities(exp):
weaknesses = []
immunities = []
for sequence in exp.split("; "):
first, middle, *rest = sequence.split()
if first == "weak":
kind = weaknesses
else:
kind = immunities
kind += "".join(rest).split(",")
return weaknesses, immunities
immune, infection = [[parse(line) for line in block] for block in data]
while immune and infection:
immune, infection = one_round(immune, infection)
result = immune if immune else infection
sum(x.n_units for x in result)I did a binary search for this one. The players can get stuck in a draw, so we need to take that into account.
def winner(boost):
immune, infection = [[parse(line) for line in block] for block in data]
for group in immune:
group.damage += boost
while immune and infection:
total = sum(x.n_units for x in immune + infection)
immune, infection = one_round(immune, infection)
if total == sum(x.n_units for x in immune + infection):
return 0
return sum(x.n_units for x in immune)
high = 1
while not winner(high):
high *= 2
low = high // 2
while high - low > 1:
mid = (high + low) // 2
if winner(mid):
high = mid
else:
low = mid
winner(high)I could write this by hand. Or I could realise that the problem description is perfectly suited for a union-find/disjoint set data structure:
from scipy.cluster.hierarchy import DisjointSet
points = [tuple(x) for x in load(25, "int")]
disjoint_set = DisjointSet(points)
for x in range(len(points)):
deltas = np.abs(np.array(points) - np.array(points[x])).sum(axis=1)
for y in range(x + 1, len(points)):
if deltas[y] <= 3:
disjoint_set.merge(points[x], points[y])
disjoint_set.n_subsets