Quantum encryption isn’t something quantum computers can even do. It’s not just transforming bits into other bits, it’s about building entirely new security properties based on physical properties of matter.
So, even if it is interesting for end users, they would need dedicated hardware anyway.
We used to drive bicycles when we were children. Then we started driving cars. Bicycles have two wheels, cars have four. Eight wheels seems to be the logical next step, why don’t we drive eight-wheel vehicles?
This seems to be an encrypted file: https://stackoverflow.com/questions/47712102/sd-card-files-with-encrypted-data-console-text-in-it-how-to-get-my-files-bac
I would try magick identify from imagemagick. If that doesn’t work, I would try strings just to see if it has any metadata at all. Cameras usually store their model name somewhere.
The “15 to 17” part is worded somewhat confusingly, but it’s not wrong.
The number of bits contained in a double is equivalent to ~15.95 decimal digits. If you want to store exactly a decimal number with a fixed number of significant digits, floor(15.95) = 15 digits is the most you can hope for. However, if you want to store exactly a double by writing it out as a decimal number, you need 17 digits.
I’m surprised no one mentioned it. Hellblade (full title: Hellblade: Senua’s Sacrifice) had me in literal tears. Not only it’s a decent game, it’s also an essay on heavy topics like mental health and the story of viking invasions.
import networkx as nx
from .solver import Solver
class Day25(Solver):
def __init__(self):
super().__init__(25)
def presolve(self, input: str):
self.graph = nx.Graph()
for line in input.splitlines():
from_, to_line = line.split(': ')
for to in to_line.split(' '):
self.graph.add_edge(from_, to)
def solve_first_star(self) -> int | str:
cut_value, partition = nx.algorithms.stoer_wagner(self.graph)
return len(partition[0]) * len(partition[1])
import numpy as np
import z3
from aoc23.util import assert_full_match
from .solver import Solver
class Day24(Solver):
def __init__(self):
super().__init__(24)
self.test_area = [200000000000000, 400000000000000]
def presolve(self, input: str):
self.stones = []
for line in input.splitlines():
(x, y, z, vx, vy, vz) = assert_full_match(
r'([0-9-]+), +([0-9-]+), +([0-9-]+) +@ +([0-9-]+), +([0-9-]+), +([0-9-]+)', line).groups()
self.stones.append((int(x), int(y), int(z), int(vx), int(vy), int(vz)))
def solve_first_star(self) -> int | str:
count = 0
for i, stone_a in enumerate(self.stones):
for stone_b in self.stones[i+1:]:
matrix = np.array([[stone_a[3], -stone_b[3]],
[stone_a[4], -stone_b[4]],])
rhs = np.array([[stone_b[0] - stone_a[0]], [stone_b[1] - stone_a[1]]])
try:
x = np.linalg.solve(matrix, rhs)
if not (x > 0).all():
continue
intersection_x = stone_a[0] + stone_a[3] * x[0, 0]
intersection_y = stone_a[1] + stone_a[4] * x[0, 0]
if (self.test_area[0] <= intersection_x <= self.test_area[1]
and self.test_area[0] <= intersection_y <= self.test_area[1]):
count += 1
except np.linalg.LinAlgError:
continue
return count
def solve_second_star(self) -> int | str:
x0 = z3.Int('x0')
y0 = z3.Int('y0')
z0 = z3.Int('z0')
vx0 = z3.Int('vx0')
vy0 = z3.Int('vy0')
vz0 = z3.Int('vz0')
t1 = z3.Int('t1')
t2 = z3.Int('t2')
t3 = z3.Int('t3')
solver = z3.Solver()
solver.add(x0 + vx0 * t1 == self.stones[0][0] + self.stones[0][3] * t1)
solver.add(y0 + vy0 * t1 == self.stones[0][1] + self.stones[0][4] * t1)
solver.add(z0 + vz0 * t1 == self.stones[0][2] + self.stones[0][5] * t1)
solver.add(x0 + vx0 * t2 == self.stones[1][0] + self.stones[1][3] * t2)
solver.add(y0 + vy0 * t2 == self.stones[1][1] + self.stones[1][4] * t2)
solver.add(z0 + vz0 * t2 == self.stones[1][2] + self.stones[1][5] * t2)
solver.add(x0 + vx0 * t3 == self.stones[2][0] + self.stones[2][3] * t3)
solver.add(y0 + vy0 * t3 == self.stones[2][1] + self.stones[2][4] * t3)
solver.add(z0 + vz0 * t3 == self.stones[2][2] + self.stones[2][5] * t3)
assert solver.check() == z3.sat
model = solver.model()
return sum([model[x0].as_long(), model[y0].as_long(), model[z0].as_long()])
from .solver import Solver
def _directions_from(char: str) -> list[tuple[int, int]]:
if char == '.':
return [(0, 1), (0, -1), (1, 0), (-1, 0)]
if char == 'v':
return [(1, 0)]
if char == '^':
return [(-1, 0)]
if char == '<':
return [(0, -1)]
if char == '>':
return [(0, 1)]
raise ValueError(f'unknown char: {char}')
class Day23(Solver):
lines: list[str]
def __init__(self):
super().__init__(23)
def presolve(self, input: str):
self.lines = input.splitlines()
def _find_longest(self, current: tuple[int, int], visited: set[tuple[int, int]]) -> int|None:
i, j = current
if i == len(self.lines) - 1:
return 0
visited.add(current)
options = []
for di, dj in _directions_from(self.lines[i][j]):
ni, nj = i + di, j + dj
if ni < 0 or ni >= len(self.lines) or nj < 0 or nj >= len(self.lines[0]):
continue
if self.lines[ni][nj] == '#':
continue
if (ni, nj) in visited:
continue
result = self._find_longest((ni, nj), visited)
if result is not None:
options.append(result)
visited.remove(current)
if options:
return max(options) + 1
return None
def solve_first_star(self) -> int:
start_i = 0
start_j = self.lines[0].find('.')
result = self._find_longest((start_i, start_j), set())
assert result
return result
def _find_longest_2(self, current: tuple[int, int],
connections: dict[tuple[int, int], list[tuple[int, int, int]]],
visited: set[tuple[int, int]]) -> int|None:
i, j = current
if i == len(self.lines) - 1:
return 0
visited.add(current)
options = []
for ni, nj, length in connections[(i, j)]:
if (ni, nj) in visited:
continue
result = self._find_longest_2((ni, nj), connections, visited)
if result is not None:
options.append(result + length)
visited.remove(current)
if options:
return max(options)
return None
def solve_second_star(self) -> int:
start_i = 0
start_j = self.lines[0].find('.')
stack = [(start_i, start_j)]
connections = {}
visited = set()
while stack:
edge_i, edge_j = stack.pop()
i, j = edge_i, edge_j
path_length = 0
options = []
connections[(edge_i, edge_j)] = []
while True:
options = []
path_length += 1
visited.add((i, j))
for di, dj in ((0, 1), (0, -1), (1, 0), (-1, 0)):
ni, nj = i + di, j + dj
if ni < 0 or ni >= len(self.lines) or nj < 0 or nj >= len(self.lines[0]):
continue
if self.lines[ni][nj] == '#':
continue
if (ni, nj) in visited:
continue
options.append((ni, nj))
if len(options) == 1:
i, j = options[0]
else:
connections[(edge_i, edge_j)].append((i, j, path_length - 1))
break
connections[(i, j)] = [(ni, nj, 1) for ni, nj in options]
stack.extend(options)
connections_pairs = list(connections.items())
for (i, j), connected_nodes in connections_pairs:
for (ni, nj, d) in connected_nodes:
if (ni, nj) not in connections:
connections[(ni, nj)] = [(i, j, d)]
elif (i, j, d) not in connections[(ni, nj)]:
connections[(ni, nj)].append((i, j, d))
result = self._find_longest_2((start_i, start_j), connections, set())
assert result
return result
Max Payne 1/2 dream sequences.
I actually like the underground, but it does have a couple of annoyingly obtuse puzzles.
assert_full_match is basically re.full_match, if you want to run it, you can grab my code from Github.
10.578 line-seconds.
import collections
from aoc23.util import assert_full_match
from .solver import Solver
def _trace_brick(x0, y0, x1, y1):
if x0 == x1:
y0, y1 = min(y0, y1), max(y0, y1)
for y in range(y0, y1 + 1):
yield (x0, y)
elif y0 == y1:
x0, x1 = min(x0, x1), max(x0, x1)
for x in range(x0, x1 + 1):
yield (x, y0)
else:
raise ValueError(f'not a brick: {x0}, {y0}, {x1}, {y1}')
class Day22(Solver):
can_be_deleted: set[int]
support_map: dict[int, list[int]]
brick_count: int
def __init__(self):
super().__init__(22)
def presolve(self, input: str):
lines = input.splitlines()
bricks = []
for line in lines:
x0, y0, z0, x1, y1, z1 = assert_full_match(r'(\d+),(\d+),(\d+)~(\d+),(\d+),(\d+)', line).groups()
bricks.append(((int(x0), int(y0), int(z0)), (int(x1), int(y1), int(z1))))
self.brick_count = len(bricks)
bricks.sort(key=lambda brick: min(brick[0][2], brick[1][2]))
self.can_be_deleted = set()
topmost_brick_per_position: dict[tuple[int, int], tuple[int, int]] = {}
self.support_map = {}
for brick_id, ((x0, y0, z0), (x1, y1, z1)) in enumerate(bricks):
support_brick_ids = set()
support_brick_z = 0
for (x, y) in _trace_brick(x0, y0, x1, y1):
potential_support = topmost_brick_per_position.get((x, y))
if not potential_support:
continue
if potential_support[0] > support_brick_z:
support_brick_z = potential_support[0]
support_brick_ids = {potential_support[1]}
elif potential_support[0] == support_brick_z:
support_brick_ids.add(potential_support[1])
self.support_map[brick_id] = list(support_brick_ids)
if len(support_brick_ids) == 1:
self.can_be_deleted.discard(support_brick_ids.pop())
for (x, y) in _trace_brick(x0, y0, x1, y1):
topmost_brick_per_position[(x, y)] = (support_brick_z + 1 + z1 - z0, brick_id)
self.can_be_deleted.add(brick_id)
def solve_first_star(self) -> int:
return len(self.can_be_deleted)
def solve_second_star(self) -> int:
reverse_support_map = collections.defaultdict(set)
for brick_id, support_brick_ids in self.support_map.items():
for support_brick_id in support_brick_ids:
reverse_support_map[support_brick_id].add(brick_id)
total = 0
for brick_id in range(self.brick_count):
all_destroyed_bricks = set()
queue = [brick_id]
while queue:
destroy_brick_id = queue.pop(0)
for potential_destroyed_brick in reverse_support_map[destroy_brick_id]:
if potential_destroyed_brick in all_destroyed_bricks:
continue
remaining_supports = set(self.support_map[potential_destroyed_brick])
remaining_supports -= (all_destroyed_bricks | {destroy_brick_id})
if not remaining_supports:
queue.append(potential_destroyed_brick)
all_destroyed_bricks.add(destroy_brick_id)
total += len(all_destroyed_bricks) - 1
return total
The data today has a special property, which allows for a fast solution. This won’t work on other data, including the example data in the problem description.
1645 line-seconds.
import collections
import math
from .solver import Solver
class Day21(Solver):
first_star_steps: int
second_star_steps: int
lines: list[str]
def __init__(self):
super().__init__(21)
self.first_star_steps = 64
self.second_star_steps = 26501365
def presolve(self, input: str):
self.lines = input.splitlines()
def solve_first_star(self) -> int | str:
positions = {(i, j) for i, line in enumerate(self.lines) for j, c in enumerate(line) if c == 'S'}
for _ in range(self.first_star_steps):
next_positions = set()
for i, j in positions:
for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
if not 0 <= i + di < len(self.lines):
continue
if not 0 <= j + dj < len(self.lines[i]):
continue
if self.lines[i + di][j + dj] == '#':
continue
next_positions.add((i + di, j + dj))
positions = next_positions
return len(positions)
def solve_second_star(self) -> int:
positions = {(i, j) for i, line in enumerate(self.lines) for j, c in enumerate(line) if c == 'S'}
modulus = self.second_star_steps % len(self.lines)
points_to_extrapolate = (modulus, modulus + len(self.lines), modulus + len(self.lines) * 2)
values = []
for step_count in range(modulus + len(self.lines) * 2 + 1):
if step_count in points_to_extrapolate:
values.append(len(positions))
next_positions = set()
for i, j in positions:
for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
ni = i + di
nj = j + dj
if self.lines[ni % len(self.lines)][nj % len(self.lines)] == '#':
continue
next_positions.add((ni, nj))
positions = next_positions
a = (values[2] - values[1] *2 + values[0]) // 2
b = values[1] - values[0] - 3 * a
c = values[0] - b - a
cycles = math.ceil(self.second_star_steps / len(self.lines))
return a * cycles * cycles + b * cycles + c
Also on Github
import collections
import math
import re
from .solver import Solver
class Day20(Solver):
modules: dict[str, tuple[str, list[str]]]
conjunction_inputs: dict[str, set[str]]
def __init__(self):
super().__init__(20)
def presolve(self, input: str):
self.modules = {}
self.conjunction_inputs = collections.defaultdict(set)
for line in input.splitlines():
m = re.fullmatch(r'(\W?)(\w+) -> (.*)', line)
assert m
kind, name, destinations = m.groups()
self.modules[name] = (kind, destinations.split(', '))
for source, (_, destinations) in self.modules.items():
for destination, (kind, _) in ((d, self.modules[d]) for d in destinations if d in self.modules):
if kind == '&':
self.conjunction_inputs[destination].add(source)
def _press_button(self, flip_flops_on: set[str],
conjunction_high_pulses: dict[str, set[str]]) -> tuple[list[str], list[str]]:
low_pulses: list[str] = []
high_pulses: list[str] = []
pulse: list[tuple[str, str, int]] = [('', 'broadcaster', 0)]
while pulse:
origin, source, value = pulse.pop(0)
if value == 0:
low_pulses.append(source)
else:
high_pulses.append(source)
if source not in self.modules:
continue
kind, destinations = self.modules[source]
if source == 'broadcaster':
for d in destinations:
pulse.append((source, d, value))
elif kind == '%' and value == 0:
if source in flip_flops_on:
flip_flops_on.remove(source)
for d in destinations:
pulse.append((source, d, 0))
else:
flip_flops_on.add(source)
for d in destinations:
pulse.append((source, d, 1))
elif kind == '&':
if value:
conjunction_high_pulses[source].add(origin)
elif origin in conjunction_high_pulses[source]:
conjunction_high_pulses[source].remove(origin)
if conjunction_high_pulses[source] == self.conjunction_inputs[source]:
for d in destinations:
pulse.append((source, d, 0))
else:
for d in destinations:
pulse.append((source, d, 1))
return low_pulses, high_pulses
def solve_first_star(self) -> int:
flip_flops_on = set()
conjunction_high_pulses = collections.defaultdict(set)
low_pulse_count = 0
high_pulse_count = 0
for _ in range(1000):
low, high = self._press_button(flip_flops_on, conjunction_high_pulses)
low_pulse_count += len(low)
high_pulse_count += len(high)
return low_pulse_count* high_pulse_count
def solve_second_star(self) -> int:
flip_flops_on = set()
conjunction_high_pulses = collections.defaultdict(set)
button_count = 0
rx_upstream = [module for module, (_, destinations) in self.modules.items() if 'rx' in destinations]
if len(rx_upstream) != 1:
rx_upstream = []
else:
rx_upstream = [module for module, (_, destinations) in self.modules.items() if rx_upstream[0] in destinations]
rx_upstream_periods = [None] * len(rx_upstream)
low_pulses = []
while 'rx' not in low_pulses and (not rx_upstream or not all(rx_upstream_periods)):
button_count += 1
low_pulses, _ = self._press_button(flip_flops_on, conjunction_high_pulses)
for module, periods in zip(rx_upstream, rx_upstream_periods, strict=True):
if periods is not None:
continue
if module in low_pulses:
rx_upstream_periods[rx_upstream.index(module)] = button_count
if 'rx' in low_pulses:
return button_count
return math.lcm(*rx_upstream_periods)
Also on Github
0.09 line-seconds (third simplest after days 6 and 2).
from .solver import Solver
class Day18(Solver):
def __init__(self):
super().__init__(18)
def presolve(self, input: str):
self.lines = input.splitlines()
def solve_first_star(self):
commands = []
for line in self.lines:
direction, distance, *_ = line.split(' ')
commands.append((direction, int(distance)))
return self._solve(commands)
def solve_second_star(self):
commands = []
for line in self.lines:
_, _, command = line.split(' ')
distance = int(command[2:-2], 16)
direction = ('R', 'D', 'L', 'U')[int(command[-2])]
commands.append((direction, distance))
return self._solve(commands)
def _solve(self, commands: list[tuple[str, int]]):
points: list[tuple[int, int]] = [(0, 0)]
perimeter_integer_points = 1
x, y = 0, 0
for direction, distance in commands:
dx, dy = {'R': (1, 0), 'L': (-1, 0), 'U': (0, -1), 'D': (0, 1)}[direction]
x, y = x + dx * distance, y + dy * distance
perimeter_integer_points += distance
points.append((x, y))
last_x, last_y = points[-1]
perimeter_integer_points += abs(last_x) + abs(last_y) - 1
area_x2 = sum((points[i][1] + points[(i+1) % len(points)][1]) *
(points[i][0] - points[(i+1) % len(points)][0])
for i in range(len(points)))
interior_integer_points = (area_x2 - perimeter_integer_points) // 2 + 1
return interior_integer_points + perimeter_integer_points
I did a different heuristic for A*: I ran a Dijkstra backwards from the bottom right corner and computed the heat losses for each block if there were no movement restrictions whatsoever. Maybe that’ll help shave more milliseconds :)
Also on Github
749 line-seconds
import collections
import dataclasses
import heapq
import numpy as np
from .solver import Solver
@dataclasses.dataclass(order=True)
class QueueEntry:
price: int
x: int
y: int
momentum_x: int
momentum_y: int
deleted: bool
class Day17(Solver):
lines: list[str]
sx: int
sy: int
lower_bounds: np.ndarray
def __init__(self):
super().__init__(17)
def presolve(self, input: str):
self.lines = input.splitlines()
self.sx = len(self.lines[0])
self.sy = len(self.lines)
start = (self.sx - 1, self.sy - 1)
self.lower_bounds = np.zeros((self.sx, self.sy)) + np.inf
self.lower_bounds[start] = 0
queue: list[QueueEntry] = [QueueEntry(0, self.sx - 1, self.sy - 1, 0, 0, False)]
queue_entries: dict[tuple[int, int], QueueEntry] = {start: queue[0]}
while queue:
cur_price, x, y, _, _, deleted = dataclasses.astuple(heapq.heappop(queue))
if deleted:
continue
del queue_entries[(x, y)]
self.lower_bounds[x, y] = cur_price
price = cur_price + int(self.lines[y][x])
for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
nx, ny = x + dx, y + dy
if not (0 <= nx < self.sx) or not (0 <= ny < self.sy):
continue
if price < self.lower_bounds[nx, ny]:
self.lower_bounds[nx, ny] = price
if (nx, ny) in queue_entries:
queue_entries[(nx, ny)].deleted = True
queue_entries[(nx, ny)] = QueueEntry(price, nx, ny, 0, 0, False)
heapq.heappush(queue, queue_entries[(nx, ny)])
def _solve(self, maximum_run: int, minimum_run_to_turn: int):
came_from: dict[tuple[int, int, int, int], tuple[int, int, int, int]] = {}
start = (0, 0, 0, 0)
queue: list[QueueEntry] = [QueueEntry(self.lower_bounds[0, 0], *start, False)]
queue_entries: dict[tuple[int, int, int, int], QueueEntry] = {start: queue[0]}
route: list[tuple[int, int]] = []
prices: dict[tuple[int, int, int, int], float] = collections.defaultdict(lambda: np.inf)
prices[start] = 0
while queue:
_, current_x, current_y, momentum_x, momentum_y, deleted = dataclasses.astuple(heapq.heappop(queue))
cur_price = prices[(current_x, current_y, momentum_x, momentum_y)]
if deleted:
continue
if ((current_x, current_y) == (self.sx - 1, self.sy - 1) and
(momentum_x >= minimum_run_to_turn or momentum_y >= minimum_run_to_turn)):
previous = came_from.get((current_x, current_y, momentum_x, momentum_y))
route.append((current_x, current_y))
while previous:
x, y, *_ = previous
if x != 0 or y != 0:
route.append((x, y))
previous = came_from.get(previous)
break
for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
dot_product = dx * momentum_x + dy * momentum_y
if dot_product < 0 or dot_product >= maximum_run:
continue
if ((momentum_x or momentum_y) and dot_product == 0 and
abs(momentum_x) < minimum_run_to_turn and abs(momentum_y) < minimum_run_to_turn):
continue
new_x, new_y = current_x + dx, current_y + dy
if not (0 <= new_x < self.sx) or not (0 <= new_y < self.sy):
continue
new_momentum_x, new_momentum_y = (dx, dy) if dot_product == 0 else (momentum_x + dx, momentum_y + dy)
new_position = (new_x, new_y, new_momentum_x, new_momentum_y)
potential_new_price = cur_price + int(self.lines[new_y][new_x])
if potential_new_price < prices[new_position]:
queue_entry = queue_entries.get(new_position)
if queue_entry:
queue_entry.deleted = True
queue_entries[new_position] = QueueEntry(potential_new_price + self.lower_bounds[new_x, new_y],
*new_position, False)
came_from[new_position] = (current_x, current_y, momentum_x, momentum_y)
prices[new_position] = potential_new_price
heapq.heappush(queue, queue_entries[new_position])
return sum(int(self.lines[y][x]) for x, y in route)
def solve_first_star(self) -> int:
return self._solve(3, 0)
def solve_second_star(self) -> int:
return self._solve(10, 4)
Also on Github
53.059 line-seconds (ranks third hardest after days 8 and 12 so far).
from .solver import Solver
def _trace_beam(data, initial_beam_head):
wx = len(data[0])
wy = len(data)
beam_heads = [initial_beam_head]
seen_beam_heads = set()
while beam_heads:
next_beam_heads = []
for x, y, dx, dy in beam_heads:
seen_beam_heads.add((x, y, dx, dy))
nx, ny = (x + dx), (y + dy)
if nx < 0 or nx >= wx or ny < 0 or ny >= wy:
continue
obj = data[ny][nx]
if obj == '|' and dx != 0:
next_beam_heads.append((nx, ny, 0, 1))
next_beam_heads.append((nx, ny, 0, -1))
elif obj == '-' and dy != 0:
next_beam_heads.append((nx, ny, 1, 0))
next_beam_heads.append((nx, ny, -1, 0))
elif obj == '/':
next_beam_heads.append((nx, ny, -dy, -dx))
elif obj == '\\':
next_beam_heads.append((nx, ny, dy, dx))
else:
next_beam_heads.append((nx, ny, dx, dy))
beam_heads = [x for x in next_beam_heads if x not in seen_beam_heads]
energized = {(x, y) for x, y, _, _ in seen_beam_heads}
return len(energized) - 1
class Day16(Solver):
def __init__(self):
super().__init__(16)
def presolve(self, input: str):
data = input.splitlines()
self.possible_energized_cells = (
[_trace_beam(data, (-1, y, 1, 0)) for y in range(len(data))] +
[_trace_beam(data, (x, -1, 0, 1)) for x in range(len(data[0]))] +
[_trace_beam(data, (len(data[0]), y, -1, 0)) for y in range(len(data))] +
[_trace_beam(data, (x, len(data), 0, -1)) for x in range(len(data[0]))])
def solve_first_star(self) -> int:
return self.possible_energized_cells[0]
def solve_second_star(self) -> int:
return max(self.possible_energized_cells)
I’m not sure what a “music jukebox” is, and how it’s different from a music player, but I would recommend to try mpd. It should work with your collection, although I don’t have personal experience with collections of this size. Some clients might also not have been designed to work with such collections, so probably you’d have to try several.