![](https://feddit.uk/pictrs/image/d9975ee2-1817-4b02-9e8a-a90a7e5fffa6.png)
My personal favourite is "blithering idiot".
My personal favourite is "blithering idiot".
Fantastic, thanks!
Very nice! Could you tweak the colours a bit so they work in dark mode?
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
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)
6.528 line-seconds (ranks 8th hardest after days 17, 8, 12, 16, 14, 11 and 10).
Also on Github
import functools
import operator
import re
import portion as P # noqa: N812
from .solver import Solver
def isize(i: P.Interval):
return sum(i_part.upper - i_part.lower - int(i_part.left == P.OPEN) + int(i_part.right == P.CLOSED)
for i_part in i)
class Day19(Solver):
workflows: dict[str, list[str|tuple[str, str, int, str]]]
parts: list[dict[str, int]]
def __init__(self):
super().__init__(19)
def presolve(self, input: str):
lines = input.splitlines()
self.workflows = {}
while lines:
line = lines.pop(0)
if not line:
break
name, program = line.split('{')
instructions = program[:-1].split(',')
self.workflows[name] = []
for item in instructions:
match_condition = re.fullmatch(r'(\w+)([<>])(\d+):(\w+)', item)
if match_condition:
category, op, threshold, goto = match_condition.groups()
self.workflows[name].append((category, op, int(threshold), goto))
else:
self.workflows[name].append(item)
self.parts = []
while lines:
items = lines.pop(0)[1:-1].split(',')
part = {}
for category, value in (i.split('=') for i in items):
part[category] = int(value)
self.parts.append(part)
def solve_first_star(self):
return sum(sum(part.values()) for part in self.parts if
self._count_options('in', 0, {c: P.singleton(v) for c, v in part.items()}) > 0)
def solve_second_star(self):
return self._count_options('in', 0, {c: P.closed(1, 4000) for c in self.parts[0].keys()})
def _count_options(self, workflow_name: str, workflow_index: int, ranges: dict[str, P.Interval]) -> int:
if workflow_name == 'A':
return functools.reduce(operator.mul, (isize(r) for r in ranges.values()), 1)
if workflow_name == 'R':
return 0
if any(isize(r) == 0 for r in ranges.values()):
return 0
match self.workflows[workflow_name][workflow_index]:
case (category, '>', threshold, goto):
new_ranges_true = {c: r & P.open(threshold, P.inf) if c == category else r for c, r in ranges.items()}
new_ranges_false = {c: r & P.openclosed(-P.inf, threshold) if c == category else r for c, r in ranges.items()}
return (self._count_options(goto, 0, new_ranges_true) +
self._count_options(workflow_name, workflow_index + 1, new_ranges_false))
case (category, '<', threshold, goto):
new_ranges_true = {c: r & P.open(-P.inf, threshold) if c == category else r for c, r in ranges.items()}
new_ranges_false = {c: r & P.closedopen(threshold, P.inf) if c == category else r for c, r in ranges.items()}
return (self._count_options(goto, 0, new_ranges_true) +
self._count_options(workflow_name, workflow_index + 1, new_ranges_false))
case next_workflow:
return self._count_options(next_workflow, 0, ranges)
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
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)
Very nice! I was wondering what the movements of the blocks looked like.
0.248 line-seconds (sixth simplest so far after days 6, 2, 1, 4 and 9).
Also on Github
import collections
import re
from .solver import Solver
def _hash(string: str) -> int:
result = 0
for c in string:
result = (result + ord(c)) * 17 % 256
return result
def _assert_full_match(pattern: str, string: str):
m = re.fullmatch(pattern, string)
if not m:
raise RuntimeError(f'pattern {pattern} does not match {string}')
return m
class Day15(Solver):
input: list[str]
def __init__(self):
super().__init__(15)
def presolve(self, input: str):
self.input = input.rstrip().split(',')
def solve_first_star(self) -> int:
return sum(_hash(string) for string in self.input)
def solve_second_star(self) -> int:
boxes = [collections.OrderedDict() for _ in range(256)]
for instruction in self.input:
label, op, value = _assert_full_match(r'([a-z]+)([=-])(\d*)', instruction).groups()
box = boxes[_hash(label)]
match op:
case '-':
if label in box:
del box[label]
case '=':
box[label] = value
return sum((1 + box_idx) * (1 + lens_idx) * int(value)
for box_idx, box in enumerate(boxes)
for lens_idx, (_, value) in enumerate(box.items()))
Oh yeah, great idea, thanks!
Also on Github
import numpy as np
from .solver import Solver
def _tilt(row: list[int], reverse: bool = False) -> list[int]:
res = row[::-1] if reverse else row[:]
rock_x = 0
for x, item in enumerate(res):
if item == 1:
rock_x = x + 1
if item == 2:
if rock_x < x:
res[rock_x] = 2
res[x] = 0
rock_x += 1
return res[::-1] if reverse else res
class Day14(Solver):
data: np.ndarray
def __init__(self):
super().__init__(14)
def presolve(self, input: str):
lines = input.splitlines()
self.data = np.zeros((len(lines), len(lines[0])), dtype=np.int8)
for x, line in enumerate(lines):
for y, char in enumerate(line):
if char == '#':
self.data[x, y] = 1
elif char == 'O':
self.data[x, y] = 2
def solve_first_star(self) -> int:
for y in range(self.data.shape[1]):
self.data[:, y] = _tilt(self.data[:, y].tolist())
return sum((self.data.shape[0] - x) * (self.data[x] == 2).sum() for x in range(self.data.shape[0]))
def solve_second_star(self) -> int:
seen = {}
order = []
for i in range(1_000_000_000):
order += [self.data.copy()]
s = self.data.tobytes()
if s in seen:
loop_size = i - seen[s]
remainder = (1_000_000_000 - i) % loop_size
self.data = order[seen[s] + remainder]
break
seen[s] = i
for y in range(self.data.shape[1]):
self.data[:, y] = _tilt(self.data[:, y].tolist())
for x in range(self.data.shape[0]):
self.data[x, :] = _tilt(self.data[x, :].tolist())
for y in range(self.data.shape[1]):
self.data[:, y] = _tilt(self.data[:, y].tolist(), reverse=True)
for x in range(self.data.shape[0]):
self.data[x, :] = _tilt(self.data[x, :].tolist(), reverse=True)
return sum((self.data.shape[0] - x) * (self.data[x] == 2).sum() for x in range(self.data.shape[0]))
33.938 line-seconds (ranks 3rd hardest after days 8 and 12 so far).
Lines of code can be arbitrarily reduced, and seconds to solve depends to a large extent on how good my hardware is. So both metrics are useless, and multiplying them makes a useless-squared metric.
I love it!
Here are my stats for the solutions so far (with no optimisation beyond the initial solution):
+-----+-----------+-------+---------------+
| Day | Time (s) | Lines | line-seconds |
+-----+-----------+-------+---------------+
| 1 | 0.003 | 35 | 0.098 |
| 2 | 0.001 | 47 | 0.042 |
| 3 | 0.006 | 60 | 0.348 |
| 4 | 0.003 | 41 | 0.115 |
| 5 | 0.077 | 74 | 5.708 |
| 6 | 0.000 | 45 | 0.001 |
| 7 | 0.005 | 87 | 0.395 |
| 8 | 10.175 | 60 | 610.476 |
| 9 | 0.004 | 31 | 0.128 |
| 10 | 0.084 | 103 | 8.634 |
| 11 | 0.240 | 49 | 11.771 |
| 12 | 2.448 | 93 | 227.633 |
| 13 | 0.009 | 83 | 0.707 |
+-----+-----------+-------+---------------+
Also on Github
from .solver import Solver
def is_mirrored_x(pattern: set[tuple[int, int]], max_x: int, max_y: int,
x_mirror: int, desired_errors: int = 0) -> bool:
min_x = max(0, 2 * x_mirror - max_x)
max_x = min(max_x, 2 * x_mirror)
errors = 0
for y in range(max_y):
for x in range(min_x, x_mirror):
mirrored = 2 * x_mirror - x - 1
if (x, y) in pattern and (mirrored, y) not in pattern:
errors += 1
if (x, y) not in pattern and (mirrored, y) in pattern:
errors += 1
if errors > desired_errors:
return False
return errors == desired_errors
def is_mirrored_y(pattern: set[tuple[int, int]], max_x: int, max_y: int,
y_mirror: int, desired_errors: int = 0) -> bool:
min_y = max(0, 2 * y_mirror - max_y)
max_y = min(max_y, 2 * y_mirror)
errors = 0
for x in range(max_x):
for y in range(min_y, y_mirror):
mirrored = 2 * y_mirror - y - 1
if (x, y) in pattern and (x, mirrored) not in pattern:
errors += 1
if (x, y) not in pattern and (x, mirrored) in pattern:
errors += 1
if errors > desired_errors:
return False
return errors == desired_errors
def find_mirror_axis(pattern: set[tuple[int, int]], max_x: int, max_y: int,
desired_errors: int = 0) -> tuple[None, int]|tuple[int, None]:
for possible_x_mirror in range(1, max_x):
if is_mirrored_x(pattern, max_x, max_y, possible_x_mirror, desired_errors):
return possible_x_mirror, None
for possible_y_mirror in range(1, max_y):
if is_mirrored_y(pattern, max_x, max_y, possible_y_mirror, desired_errors):
return None, possible_y_mirror
raise RuntimeError('No mirror axis found')
class Day13(Solver):
def __init__(self):
super().__init__(13)
self.patterns: list[set[tuple[int, int]]] = []
self.dimensions: list[tuple[int, int]] = []
def presolve(self, input: str):
patterns = input.rstrip().split('\n\n')
for pattern in patterns:
lines = pattern.splitlines()
points: set[tuple[int, int]] = set()
max_x = 0
max_y = 0
for y, line in enumerate(lines):
max_y = max(max_y, y)
for x, char in enumerate(line):
max_x = max(max_x, x)
if char == '#':
points.add((x, y))
self.patterns.append(points)
self.dimensions.append((max_x + 1, max_y + 1))
def solve_first_star(self) -> int:
sum = 0
for pattern, (max_x, max_y) in zip(self.patterns, self.dimensions, strict=True):
mirror_x, mirror_y = find_mirror_axis(pattern, max_x, max_y)
sum += (mirror_x or 0) + (mirror_y or 0) * 100
return sum
def solve_second_star(self) -> int:
sum = 0
for pattern, (max_x, max_y) in zip(self.patterns, self.dimensions, strict=True):
mirror_x, mirror_y = find_mirror_axis(pattern, max_x, max_y, 1)
sum += (mirror_x or 0) + (mirror_y or 0) * 100
return sum
Fake as in not from the sky, but made on the ground with one of those machines. They consume around 20 GWh of power per year in every large alpine ski area[1].
[1] https://praxistipps.chip.de/stromverbrauch-schneekanone-so-viel-strom-verbrauchen-kuenstliche-schneeerzeuger_153343