import functools
import itertools
import os
import queue
import sys
from collections import defaultdict
from pathlib import Path
import numpy as np
import pandas as pd
sys.path.insert(1, os.path.join(sys.path[0], ".."))
import utils
load = utils.year_load(2021)
datadir = Path("../data/2021")data = load(1, "np")
(np.diff(data) > 0).sum()(pd.Series(data).rolling(3).sum().diff() > 0).sum()data = [x.split() for x in load(2)]
df = pd.DataFrame(data, columns=["instruction", "amount"])
df["amount"] = df["amount"].apply(int)
totals = df.groupby("instruction").sum()
(totals.loc["forward"] * (totals.loc["down"] - totals.loc["up"])).iat[0]state = (0, 0, 0)
ops = {
"down": lambda x, y: (x[0] + y, x[1], x[2]),
"up": lambda x, y: (x[0] - y, x[1], x[2]),
"forward": lambda x, y: (x[0], x[1] + y, x[2] + x[0] * y),
}
for row in data:
state = ops[row[0]](state, int(row[1]))
print(state[1] * state[2])df = pd.read_fwf(datadir / "3.txt", widths=[1] * 12, header=None)
def binarize(array):
return int("".join(str(x) for x in array.reshape(-1)), 2)
bits = df.median().to_numpy(dtype=int)
binarize(bits) * binarize(1 - bits)oxygen = df
co2 = df
for column in df.columns:
oxygen = oxygen[oxygen[column] == int(oxygen[column].median() + 0.5)]
if len(co2) > 1:
co2 = co2[co2[column] != int(co2[column].median() + 0.5)]
binarize(oxygen.to_numpy()) * binarize(co2.to_numpy())data = load(4, "raw").split("\n\n")
numbers = np.array([int(x) for x in data[0].strip().split(",")])
boards = np.array(
[int(x) for x in " ".join(data[1:]).replace("\n", " ").split()]
).reshape(-1, 5, 5)
def winning_array(boards):
return ((boards == -1).all(axis=2) | (boards == -1).all(axis=1)).any(axis=1)
for number in numbers:
boards[np.where(boards == number)] = -1
if winning_array(boards).any():
break
index = np.where(winning_array(boards))
np.sum(np.ma.array(boards, mask=(boards == -1))[index]) * numberFigure out which board will win last. Once it wins, what would its final score be?
for number in numbers:
boards[np.where(boards == number)] = -1
wins = winning_array(boards)
if wins.sum() == len(boards) - 1:
index = np.where(~wins)[0]
if wins.all():
break
np.sum(np.ma.array(boards, mask=(boards == -1))[index]) * numberdata = pd.read_csv(datadir / "5.txt", names=["x1", "middle", "y2"])
data[["y1", "x2"]] = data["middle"].apply(
lambda x: pd.Series(x.split("->")).astype("int")
)
grid = np.zeros((1000, 1000))
def endpoints_to_line(x1, x2, y1, y2):
steps = max(abs(x1 - x2), abs(y1 - y2))
delta = np.array([np.sign(x2 - x1), np.sign(y2 - y1)])
points = [np.array([x1, y1]) + delta * n for n in range(steps + 1)]
return tuple(np.array(points).T.tolist())
on_axis = data[(data["x1"] == data["x2"]) | (data["y1"] == data["y2"])]
for row in on_axis.itertuples():
grid[endpoints_to_line(row.x1, row.x2, row.y1, row.y2)] += 1
(grid > 1).sum()skewed = data[(data["x1"] != data["x2"]) & (data["y1"] != data["y2"])]
for row in skewed.itertuples():
grid[endpoints_to_line(row.x1, row.x2, row.y1, row.y2)] += 1
(grid > 1).sum()data = load(6, "np")
population, _ = np.histogram(data, range(10))
transition_matrix = np.roll(np.eye(9, dtype=int), 1, axis=1)
transition_matrix[6, 0] = 1
(np.linalg.matrix_power(transition_matrix, 80) @ population).sum()(np.linalg.matrix_power(transition_matrix, 256) @ population).sum()data = load(7, "np")
np.abs(data - np.median(data)).sum()def cost(position):
delta = np.abs(data - position)
return ((delta) * (delta + 1) / 2).sum()
options = [cost(int(data.mean())), cost(int(data.mean() + 0.5))]
min(options)segments = [line.split("|")[1].split() for line in load(8)]
mylen = np.vectorize(len)
np.isin(mylen(segments), [2, 3, 4, 7]).sum()This is an obvious task for constraint programming. It feels a bit like cheating, so I’ll see if I can come up with a home-grown approach at a later stage. I’ll start by describing the segment pattern of each digit. I’m deliberately using numbers for the segment positions and letters for the segment names so that I don’t get confused.
We can do part 2 by exploiting the structure in our data.
We know that every digit occurs before the pipe for every row in our input.
Using that, we can immediately identify segment 1, segments {36} segments {24} and segments {57}.
The three five segment numbers let us disambiguate {147}, {25}, {36}. 147 occur in every group, 25 in only 1 and 36 in two
The three six segment numbers let us disambiguate {1267}, {345}.
1 is the segment present in 3 but not in 2.
2 is the segment present in 4, not present in 2, and present in every 6
3 is the segment present in 2 which is not present in every 6
4 is the segment present in 4, not present in 2, and not present in every 6
5 is the segment not present in 4 which only occurs once in 5
6 is the segment which is present in 2 and is present in every 6
7 is the segment present in every 5, not present in every 6, not present in 4
It’s not super elegant, and I kind of prefer just using the generalised constraints programming.
data = pd.read_fwf(datadir / "9.txt", widths=[1] * 100, header=None).to_numpy()
data = np.pad(data, pad_width=1, mode="constant", constant_values=9)
mask = (
(data < np.roll(data, -1, axis=0))
& (data < np.roll(data, 1, axis=0))
& (data < np.roll(data, -1))
& (data < np.roll(data, 1))
)
np.ma.array(data + 1, mask=~mask).sum()def up(x, y):
return x, y + 1
def down(x, y):
return x, y - 1
def left(x, y):
return x - 1, y
def right(x, y):
return x + 1, y
moves = [up, down, left, right]
def basin(x, y):
visited = np.zeros(data.shape, dtype=bool)
neighbors = [(x, y)]
result = 0
while neighbors:
x, y = neighbors.pop()
if data[x, y] == 9 or visited[x, y]:
continue
result += 1
visited[x, y] = True
for move in moves:
new_x, new_y = move(x, y)
if not visited[new_x, new_y]:
neighbors.append((new_x, new_y))
return result
low_points = zip(*np.where(mask))
sizes = list(map(lambda x: basin(*x), low_points))
print(np.product(sorted(sizes)[-3:]))lines = load(10)
pairs = ["[]", "()", "<>", "{}"]
def normalize(string):
old_string = string
while True:
for pair in pairs:
string = string.replace(pair, "")
if string == old_string:
break
old_string = string
return string
scores = {")": 3, "]": 57, "}": 1197, ">": 25137}
total = 0
for line in lines:
normalized = normalize(line)
indices = np.array([normalized.find(pair[1]) for pair in pairs])
if (indices == -1).all():
continue
index = min(index for index in indices if index != -1)
total += scores[normalized[index]]
print(total)delimiters = " ([{<"
scores = []
for line in lines:
normalized = normalize(line)
indices = np.array([normalized.find(pair[1]) for pair in pairs])
if (indices != -1).any():
continue
scores.append(
functools.reduce(lambda x, y: 5 * x + delimiters.find(y), normalized[::-1], 0)
)
int(np.median(scores))def find_neighbors(x, y):
return (
(x - 1, x - 1, x - 1, x, x, x + 1, x + 1, x + 1),
(y - 1, y, y + 1, y - 1, y + 1, y - 1, y, y + 1),
)
def step(board):
board += 1
flashed = np.zeros(board.shape, dtype=bool)
indices = list(zip(*np.where(board > 9)))
while indices:
x, y = indices.pop()
if flashed[x, y]:
continue
flashed[x, y] = True
neighbors = find_neighbors(x, y)
board[neighbors] += 1
for neighbor in zip(*neighbors):
if board[neighbor] > 9:
indices.append(neighbor)
board[np.where(flashed)] = 0
return flashed.sum()
result = 0
data = pd.read_fwf(datadir / "11.txt", widths=[1] * 10, header=None).to_numpy(
dtype=float
)
data = np.pad(data, pad_width=1, mode="constant", constant_values=-np.inf)
arr = data.copy()
for i in range(100):
result += step(arr)
print(result)count = 0
arr = data.copy()
while arr[1:-1, 1:-1].sum() > 0:
step(arr)
count += 1
countdef flatten(mylist):
return (element for sublist in mylist for element in sublist)
def edges_to_tree(edges, repeat_visits=0):
tree = defaultdict(set)
for e1, e2 in edges:
tree[e1].add(e2)
tree[e2].add(e1)
return tree
def remove_node(tree, node):
tree = tree.copy()
neighbors = tree[node]
del tree[node]
for neighbor in neighbors:
tree[neighbor] = tree[neighbor] - set([node])
return tree
def paths(tree, node, end):
if node == end:
return [(end,)]
if not tree[node]:
return []
new_tree = tree if node == node.upper() else remove_node(tree, node)
return [
(node,) + x
for x in flatten([paths(new_tree, neighbor, end) for neighbor in tree[node]])
]
edges = [line.split("-") for line in load(12)]
tree = edges_to_tree(edges)
len(paths(tree, "start", "end"))def paths(tree):
def inner(subtree, node, end, state):
if node == end:
return [(end,)]
if not subtree[node]:
return []
new_tree = subtree if node == node.upper() else remove_node(subtree, node)
tail = [inner(new_tree, neighbor, end, state) for neighbor in subtree[node]]
if state == 1 and node != "start":
tail += [inner(subtree, neighbor, end, 0) for neighbor in subtree[node]]
return [(node,) + x for x in flatten(tail)]
return inner(tree, "start", "end", 1)
len(set(paths(tree)))start = load(13, "np")
arr = np.zeros(start.max(axis=0) + 1, dtype=bool)
arr[start[:, 0], start[:, 1]] = 1
top = arr[:655]
bottom = arr[656:]
bottom = np.pad(bottom, ((0, top.shape[0] - bottom.shape[0]), (0, 0)))
print((top | np.flip(bottom, 0)).sum())replacement = np.vectorize(lambda x: "█" if x else " ")
instructions = [
"x=655",
"y=447",
"x=327",
"y=223",
"x=163",
"y=111",
"x=81",
"y=55",
"x=40",
"y=27",
"y=13",
"y=6",
]
for instruction in instructions:
direction, position = instruction.split("=")
position = int(position)
arr = arr.T if direction == "y" else arr
top = arr[:position]
bottom = arr[position + 1 :]
if top.shape[0] < bottom.shape[0]:
top = np.pad(top, ((bottom.shape[0] - top.shape[0], 0), (0, 0)))
else:
bottom = np.pad(bottom, ((0, top.shape[0] - bottom.shape[0]), (0, 0)))
arr = np.flip(bottom, 0) | top
arr = arr.T if direction == "y" else arr
for row in replacement(arr.T):
print("".join(row))Here’s another puzzle that seems tailor made for a transition matrix based approach. We are given an initial state, and a set of rules for producing the next state from the current state. The rules are all phrased in terms of pairs, so we should work in the basis of pairs of elements.
A rule like CH -> B should be interpreted as state “CH” produces states “CB” and “BH” in the next generation.
state_string = "VCOPVNKPFOOVPVSBKCOF"
data = load(14)
transition_elements = "".join(line.replace(" -> ", "") for line in data)
elements = sorted(set(state_string + transition_elements))
n = len(elements)
def encode(pair):
return elements.index(pair[0]) * n + elements.index(pair[1])
initial_pairs = [encode(state_string[i : i + 2]) for i in range(len(state_string) - 1)]
initial_state = np.zeros(n**2, dtype=np.int64)
for pair in initial_pairs:
initial_state[pair] += 1
transition_matrix = np.zeros((n**2, n**2), dtype=np.int64)
for line in data:
source, target = line.split(" -> ")
transition_matrix[encode(source), encode(source[0] + target)] = 1
transition_matrix[encode(source), encode(target + source[1])] = 1
def count(state):
result = defaultdict(int)
result[state_string[0]] += 1
result[state_string[-1]] += 1
for index, number in enumerate(state):
result[elements[int(index % n)]] += number
result[elements[int(index // n)]] += number
return {k: int(v / 2) for k, v in result.items()}
totals = count(initial_state.T @ (np.linalg.matrix_power(transition_matrix, 10)))
pd.Series(totals).max() - pd.Series(totals).min()totals = count(initial_state.T @ (np.linalg.matrix_power(transition_matrix, 40)))
pd.Series(totals).max() - pd.Series(totals).min()This is a shortest path search, where we’ll use a priority queue to store the items and their cost. Reusing my A* implementation then gives
data = pd.read_fwf(datadir / "15.txt", widths=[1] * 100, header=None).to_numpy(
dtype=int
)
def neighbors(state, data=None):
x, y = state
if data is None:
return []
xmax, ymax = data.shape
candidates = [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]
return [c for c in candidates if 0 <= c[0] < xmax and 0 <= c[1] < ymax]
def cost(state, neighbor, data=None):
return 1 if data is None else 0 if state == neighbor else data[neighbor]
def heuristic(node, end):
return abs(node[0] - end[0]) + abs(node[1] - end[1])
utils.astar((0, 0), (99, 99), neighbors, heuristic, cost, data=data)x, y = data.shape
arr = np.zeros([5 * x, 5 * y], dtype=int)
for i in range(5):
for j in range(5):
arr[i * x : (i + 1) * x, j * y : (j + 1) * y] = data + i + j
arr = ((arr - 1) % 9) + 1
utils.astar((0, 0), (499, 499), neighbors, heuristic, cost, data=arr)nybbles = {hex(i)[2:]: bin(i)[2:].rjust(4, "0") for i in range(16)}
def parse(bitstring):
if len(bitstring) == 0 or set(bitstring) == set("0"):
return 0, 0
version = int(bitstring[:3], 2)
offset = 3
type_id = int(bitstring[offset : offset + 3], 2)
offset += 3
if type_id == 4:
while True:
chunk = bitstring[offset : offset + 5]
offset += 5
if chunk[0] != "1":
break
return version, offset
kind = bitstring[offset]
offset += 1
if kind == "0":
length = int(bitstring[offset : offset + 15], 2)
offset += 15
target = offset + length
while offset != target:
dv, do = parse(bitstring[offset:])
version += dv
offset += do
return version, target
if kind == "1":
n_operators = int(bitstring[offset : offset + 11], 2)
offset += 11
for i in range(n_operators):
dv, do = parse(bitstring[offset:])
version += dv
offset += do
return version, offset
data = load(16)[0]
bits = "".join(nybbles[x.lower()] for x in data)
parse(bits)For part 2, we have to completely ignore the version number and actually do something with the data associated with each packet. Actually moving through the packet happens in the same way, but what we have to do at each level is sufficiently different that it’s not worth it to try and reuse the parsing function.
def evaluate_one_packet(bitstring):
offset = 3
type_id = int(bitstring[offset : offset + 3], 2)
offset += 3
if type_id == 4:
result = ""
while True:
chunk = bitstring[offset : offset + 5]
result += chunk[1:]
offset += 5
if chunk[0] == "0":
break
return int(result, 2), offset
kind = bitstring[offset]
offset += 1
operands = []
if kind == "0":
length = int(bitstring[offset : offset + 15], 2)
offset += 15
target = offset + length
while offset < target:
operand, do = evaluate_one_packet(bitstring[offset:])
operands.append(operand)
offset += do
elif kind == "1":
n_operators = int(bitstring[offset : offset + 11], 2)
offset += 11
for i in range(n_operators):
operand, do = evaluate_one_packet(bitstring[offset:])
operands.append(operand)
offset += do
operators = [
sum,
np.product,
min,
max,
None,
lambda x: x[0] > x[1],
lambda x: x[0] < x[1],
lambda x: x[0] == x[1],
]
return operators[type_id](operands), offset
print(evaluate_one_packet(bits)[0])First pen and paper solution for this year.
Things to note:
xmin, xmax = 217, 240
ymin, ymax = -126, -69
parabola = lambda v, t: (t * v - int(t * (t - 1) / 2))
time_map = defaultdict(list)
for vy in range(ymin, -ymin):
for time in [
t for t in range(1, 3 - 2 * ymin) if parabola(vy, t) in range(ymin, ymax + 1)
]:
time_map[time].append(vy)
def x_times(vx):
times = [t for t in range(1, vx) if parabola(vx, t) in range(xmin, xmax + 1)]
if vx - 1 in times:
times += list(range(max(times) + 1, max(time_map.keys()) + 1))
return times
result = []
for vx in range(int(0.5 + np.sqrt(0.25 + 2 * xmin)), xmax + 1):
times = x_times(vx)
for time in times:
for vy in time_map[time]:
result.append((vx, vy))
print(len(set(result)))def to_node(thing, depth):
if isinstance(thing, int):
return thing
elif isinstance(thing, Pair):
for node in thing.traverse():
node.depth += 1
return thing
else:
return Pair(thing[0], thing[1], depth + 1)
class Pair:
def __init__(self, left, right, depth=0):
self.depth = depth
self.left = to_node(left, depth)
self.right = to_node(right, depth)
def leftmost(self):
return self if isinstance(self.left, int) else self.left.leftmost()
def rightmost(self):
return self if isinstance(self.right, int) else self.right.rightmost()
def sum(self):
left = self.left if isinstance(self.left, int) else self.left.sum()
right = self.right if isinstance(self.right, int) else self.right.sum()
return 3 * left + 2 * right
def traverse(self):
left = [] if isinstance(self.left, int) else self.left.traverse()
right = [] if isinstance(self.right, int) else self.right.traverse()
return left + [self] + right
def reduce(self):
while True:
altered = False
altered = self.explode()
if not altered:
altered = self.split()
if not altered:
return self
def split(self):
for node in self.traverse():
for d in ["left", "right"]:
val = getattr(node, d)
if isinstance(val, int) and val >= 10:
setattr(node, d, Pair(val // 2, val // 2 + val % 2, node.depth + 1))
return True
return False
def explode(self):
traversal = self.traverse()
for idx, node in enumerate(traversal):
if node.depth == 4:
if idx == len(traversal) - 1:
parent = traversal[idx - 1]
direction = "right"
elif traversal[idx + 1].left == node:
parent = traversal[idx + 1]
direction = "left"
else:
parent = traversal[idx - 1]
direction = "right"
setattr(parent, direction, 0)
if idx != 0:
if isinstance(traversal[idx - 1].left, int):
traversal[idx - 1].left += node.left
else:
left_neighbor = traversal[idx - 1].left.rightmost()
left_neighbor.right += node.left
if idx != len(traversal) - 1:
if isinstance(traversal[idx + 1].right, int):
traversal[idx + 1].right += node.right
else:
right_neighbor = traversal[idx + 1].right.leftmost()
right_neighbor.left += node.right
return True
return False
snumbers = [eval(line) for line in load(18)]
result = Pair(*snumbers[0])
for snumber in snumbers[1:]:
result = Pair(result, Pair(*snumber)).reduce()
print(result.sum())maxval = 0
for left, right in itertools.permutations(snumbers, 2):
total = (Pair(left, right).reduce()).sum()
maxval = total if total > maxval else maxval
maxvalWe’ll start by generating the 24 rotation matrices. There are six possible ways of permuting the axes, and eight possible sign conventions. Half of the sign conventions will be left-handed, so we discard them
rotations = []
for permutation in itertools.permutations([0, 1, 2], 3):
arr = np.zeros((3, 3), dtype=int)
arr[np.array([0, 1, 2]), permutation] = 1
for sign in itertools.product([-1, 1], repeat=3):
rotation = arr.copy() * sign
if np.linalg.det(rotation) > 0:
rotations.append(rotation)Then we find overlapping scanners in the input and populate a map (x, y) with the matrices to convert from y coordinates to x coordinates
from scipy.spatial.distance import pdist, squareform
foo = load(19, "raw")[:-1]
scanners = foo.split("\n\n")
scanners = [
np.array(
[list(map(int, line.split(","))) for line in scanner.split("\n")[1:]], dtype=int
)
for scanner in scanners
]
distances = [squareform(pdist(scanner)) for scanner in scanners]
mapping = {}
for a, b in itertools.combinations(range(len(scanners)), 2):
pairs = []
d0 = distances[a]
d1 = distances[b]
for i in range(len(d0)):
for j in range(len(d1)):
if len(np.intersect1d(d1[j], d0[i])) >= 12:
pairs.append((i, j))
pairs = np.array(pairs)
if len(pairs) < 12:
continue
x0 = scanners[a][pairs[:, 0]]
y0 = scanners[b][pairs[:, 1]]
for rotation in rotations:
c = x0[0] - y0[0] @ rotation
if (x0[1:] == (y0[1:] @ rotation + c)).all():
mapping[(a, b)] = [rotation, c]
mapping[(b, a)] = [rotation.T, -c @ rotation.T]
breakWe do some linear algebra to extend this map to all the scanners
while True:
done = True
for x in range(len(scanners)):
columns = [pair[1] for pair in mapping.keys() if pair[0] == x]
for y, z in itertools.combinations(columns, 2):
if (y, z) not in mapping:
done = False
Q1, a1 = mapping[(x, y)]
Q2, a2 = mapping[(x, z)]
mapping[(z, y)] = [Q1 @ Q2.T, (a1 - a2) @ Q2.T]
mapping[(y, z)] = [Q2 @ Q1.T, (a2 - a1) @ Q1.T]
if done:
breakAnd then we convert all the initial coordinates to one representation and find its length
coords = [tuple(x) for x in scanners[0]]
for idx in range(1, len(scanners)):
Q, a = mapping[0, idx]
coords += [tuple(x) for x in (np.array(scanners[idx]) @ Q + a)]
print(len(set(coords)))What is the largest Manhattan distance between any two scanners?
maxval = 0
for i, j in itertools.combinations(range(len(scanners)), 2):
total = sum(abs(mapping[(i, j)][1]))
if total > maxval:
maxval = total
maxvaldata = load(20, "raw")
pixel_map = {".": 0, "#": 1}
key, array = data.split("\n\n")
key = np.array([pixel_map[x] for x in key.strip()], dtype=bool)
new = np.array(
[[pixel_map[x] for x in line.strip()] for line in array.split("\n")[:-1]]
)
for n in range(1, 51):
old = np.pad(new, 2, constant_values=(n % 2 == 0))
new = old.copy()
for i in range(1, len(old) - 1):
for j in range(1, len(old) - 1):
index = sum(
(2 ** np.arange(9)) * old[i - 1 : i + 2, j - 1 : j + 2].ravel()[::-1]
)
new[i, j] = key[index]
new = new[1:-1, 1:-1]
if n == 2 or n == 50:
print(new.sum())positions, scores, count = [4, 6], [0, 0], 0
def step_one(position, score, count):
position = (position + 3 * count + 5) % 10 + 1
return position, score + position, count + 3
i = 0
while max(scores) < 1000:
positions[i], scores[i % 2], count = step_one(
positions[i % 2], scores[i % 2], count
)
i = 1 - i
count * min(scores)states = {((4, 0), (6, 0)): 1}
wins = [0, 0]
# The frequency table for the 3x3 dice
rolls = [0, 0, 0, 1, 3, 6, 7, 6, 3, 1]
def step_one(states, player):
new_states = defaultdict(int)
for state in states:
for step in range(3, 10):
new_position = ((state[player][0] + step) - 1) % 10 + 1
new_score = state[player][1] + new_position
if new_score >= 21:
wins[player] += states[state] * rolls[step]
else:
new_state = list(state)
new_state[player] = (new_position, new_score)
new_states[tuple(new_state)] += states[state] * rolls[step]
return new_states, wins
i = 0
while states:
states, wins = step_one(states, i)
i = 1 - i
max(wins)The first part can be solved trivially by using numpy’s indexing
offset = 50
board = np.zeros((101, 101, 101), dtype=int)
def parse_line(line):
command, line = line.split(" ")
indices = [x.split("..") for x in line.split(",")]
return command, [[int(x[0][2:]), int(x[1]) + 1] for x in indices]
commands = [parse_line(line) for line in load(22)]
values = {"on": 1, "off": 0}
maxval = 0
for command, indices in commands:
idx = np.ravel(indices) + offset
if max(abs(idx)) > maxval:
maxval = max(abs(idx))
if (idx < 0).any() or (idx > 100).any():
continue
board[idx[0] : idx[1], idx[2] : idx[3], idx[4] : idx[5]] = values[command]
board.sum()The above approach doesn’t work for part two since the field of play is too large; we have ~ 100k elements in each direction, which give ~10**15 elements in total; far too much to keep in memory.
The first step is to realise that the vast majority of the empty space is never touched – so there’s no reason to store all those zeros.
What we can do instead is to store a set containing only the coordinates which are turned on. Turning on more coordinates corresponds to making the union with the new coordinate, while turning off coordinates is a set difference. This automatically accounts for not lighting coordinates which are already lit, and not turning off coordinates which are already off.
Unfortunately, this is still too memory intensive – from the example solution, we see that at the end of the process, 2,758,514,936,282,235 coordinates are on, which is way too many to store individually.
We need an approach that only looks at corners of cuboids, and doesn’t need to store the individual coordinates at all.
If there were only “on” instructions, we could use the inclusion-exclusion principle, along with the fact that the intersection of two cuboids is always another cuboid, or empty.
That is, the volume lit by one “on” instruction is just the volume of the cuboid it represents. The volume lit by two is the sum of the volumes of each, minus the volume of their intersection. The volume lit by three is:
And this extends to the general case. The volume lit after the nth instruction, N, is:
The volume lit after the (n-1)th instruction plus the volume of N, minus the sum of the volumes of the pairwise intersection of N with all previous instructions, plus the sum of the volumes of intersection of N with all previously calculated pairs, and so on.
Turning a cuboid off is equivalent to removing the intersection between it and all the other cuboids from the sum, and then accounting for the double counting by adding back the triple intersections etc. But that’s the same as we’re doing for the positive cuboid, except for the off cuboid we never add the volume of the individual cuboid
We’re going to need a way of calculating the intersection of two cuboids. But that’s just the intersection of 3 pairs of lines, since the cuboids are axis-aligned. And we can intersect two line segments and hence two cuboids as follows
def intersect_segments(x1, x2):
pair = [max(x1[0], x2[0]), min(x1[1], x2[1])]
return pair if pair[1] > pair[0] else False
def intersect_cuboids(c1, c2):
result = [intersect_segments(*pair) for pair in zip(c1, c2)]
return result if all(result) else FalseThe segments were originally given as closed intervals, but the parsing converted them to open intervals. The length of each is thus the endpoint minus the starting point. The volume of a cuboid is just the product the three lengths:
def cuboid_volume(cuboid):
return np.product([[line[1] - line[0]] for line in cuboid])The approach we’ll take is to process the list of instructions sequentially, calculating the various intersections as we go. They’ll go in a list where the first element represents the positive terms, and the second represents the negative terms. The final score is then just the sum of the positive values minus the sum of the negative values
Putting it all together gives the following. For each instruction, we intersect with all previous cuboids, and swap the signs. If it’s an “on” instruction, we also add the whole region to the list of positive volumes.
def reboot(instructions):
state = [[], []]
for instruction, region in instructions:
extra = [region] if instruction == "on" else []
clipped_state = [
[c for cuboid in s if (c := intersect_cuboids(cuboid, region))]
for s in state
]
state = [state[0] + clipped_state[1] + extra, state[1] + clipped_state[0]]
return sum(map(cuboid_volume, state[0])) - sum(map(cuboid_volume, state[1]))
reboot(commands)This is definitely not pretty, and takes a bunch of time to run as well, but it works. This is a pathfinding problem: Given some initial state, our goal is to move to the final state with as small a cost as possible.
The tricky thing is to find the neighboring positions that can be reached from a given position with a valid move. There are only two types of moves
The third type (room straight to final room) is just the composition of the above two moves.
Once we have a method for finding neighbors, actually running the pathfinding is comparatively simple. This could probably be improved by including a heuristic for how far away a given state is from the finish, but getting finding and calculating a suitable heuristic is fiddly.
value_to_letter = {0: " ", 1: "A", 10: "B", 100: "C", 1000: "D"}
letter_to_value = {v: k for k, v in value_to_letter.items()}
number_to_room = {10**i: i for i in range(4)}
room_to_number = {v: k for k, v in number_to_room.items()}
def find_blockers(room, n):
top_row = list(range(4 * n, 4 * n + 7))
distances = [1, 2, 2, 2, 2, 2, 1]
left = top_row[: room + 2][::-1], np.cumsum(distances[: room + 2][::-1])
right = top_row[room + 2 :], np.cumsum(distances[room + 2 :])
return left, right
def find_moves(position, n=2):
position = np.array(position)
def is_endgame(room):
return set(position[n * room : n * (room + 1)]) <= set(
[0, room_to_number[room]]
)
possible_moves = []
for i in [idx + 4 * n for idx, val in enumerate(position[4 * n :]) if val != 0]:
room = number_to_room[position[i]]
if not is_endgame(room):
continue
left, right = find_blockers(room, n)
moves, costs = left if i in left[0] else right
index = moves.index(i)
if (position[moves[:index]] != 0).any():
continue
offset = np.argwhere(position[n * room : n * (room + 1)] == 0)[0][0]
new_position = n * room + offset
cost = costs[index] + n - 1 - offset
possible_moves.append((i, new_position, cost))
for room in range(4):
target = room * n
if is_endgame(room):
continue
offset = np.argwhere(position[target : target + n])[-1][-1]
moves, costs = [], []
for block, steps in find_blockers(room, n):
free = np.maximum.accumulate(position[block]) == 0
if not free.any():
continue
n_free = np.argwhere(free)[-1][-1] + 1
moves += block[:n_free]
costs += list(steps[:n_free] + n - offset - 1)
possible_moves += [
(target + offset, move, cost) for move, cost in zip(moves, costs)
]
return possible_moves
def navigate(source, destination):
n = (len(source) - 7) // 4
q = queue.PriorityQueue()
q.put((0, source))
seen = set()
while q:
cost, position = q.get()
if position == destination:
return cost
if position in seen:
continue
seen.add(tuple(position))
for source_index, target_index, distance in find_moves(position, n):
new_position = list(position)
value = position[source_index]
new_position[source_index] = 0
new_position[target_index] = value
q.put((cost + value * distance, tuple(new_position)))
return np.infWith all of that out of the way, actually solving the puzzle is just a question of calling the navigate function. First for part 1
source = tuple(letter_to_value[x] for x in "CDCABABD ")
destination = tuple(letter_to_value[x] for x in "AABBCCDD ")
navigate(source, destination)And then for part 2
s = tuple(letter_to_value[x] for x in "CDDDCBCABABABCAD ")
d = tuple(letter_to_value[x] for x in "AAAABBBBCCCCDDDD ")
navigate(s, d)Rarely in AOC have I had a worse ratio of thinking employed to code written - this code looks way simpler than for day 23, but getting there was a real challenge.
I think this is the intended approach, since it uses the realisation that if we multiply z by 26 6 times, then to get back below zero, we need to divide 7 times. So each time there’s a divide, the value of w is fixed.
data = load(24, "raw")
chunks = [[y.split() for y in x.split("\n") if y] for x in data.split("inp w\n")][1:]
indices = [3, 4, 14]
table = [[chunk[index][2] for index in indices] for chunk in chunks]
triples = [[int(n) for n in row] for row in table]
def run(triple, z, w):
a, b, c = triple
if w == z % 26 + b:
return z // a
return (z // a) * 26 + w + c
zs = [[0, 0]]
for triple in triples:
new_zs = []
for prefix, z in zs:
if triple[0] == 26:
w = z % 26 + triple[1]
ws = [w] if 1 <= w < 10 else []
else:
ws = range(1, 10)
new_zs += [(10 * prefix + w, run(triple, z, w)) for w in ws]
zs = new_zs
max(x[0] for x in zs)We can be slightly smarter with pen and paper. The test is always z % 26 + something, which means that we always get out wn + cn for some n, since (z // a) * 26 % 26 = 0. Keeping track of the order in which the a = 1 and a = 26 instructions arrive, we can match each of the 14 instructions to exactly one other, giving a series of relationships like w1 = w14 + 8. Then it’s just a question of forcing the early digit of each pair to the highest possible allowed value.
After all that, luckily part 2 is trivial
min(int(x[0]) for x in zs)🎄
lookup = {".": 0, ">": 1, "v": -1}
reverse = {v: k for k, v in lookup.items()}
array = np.array([[lookup[char] for char in line] for line in load(25)], dtype=int)
def move_one(array, direction=1):
critter = 2 * direction - 1
critters = np.where(array == critter)
filtered = np.roll(array, -1, axis=direction)[critters] == 0
old_positions = (critters[0][filtered], critters[1][filtered])
new_positions = [x.copy() for x in old_positions]
new_positions[direction] = (new_positions[direction] + 1) % array.shape[direction]
array[old_positions] = 0
array[tuple(new_positions)] = critter
return not filtered.any()
def to_string(array):
return "\n".join(["".join([reverse[value] for value in line]) for line in array])
i = 0
while True:
m1 = move_one(array, 1)
m2 = move_one(array, 0)
i += 1
if m1 and m2:
break
i