Max Payne 1/2 dream sequences.
hades
joined 1 year ago
I actually like the underground, but it does have a couple of annoyingly obtuse puzzles.
Python
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
Python
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
Python
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)
Python
6.528 line-seconds (ranks 8th hardest after days 17, 8, 12, 16, 14, 11 and 10).
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)
Python
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 :)
Python
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)
Python
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.
Python