Skip to content

Instantly share code, notes, and snippets.

@maxfire2008

maxfire2008/aoc-2025-05.py

Created December 5, 2025 13:12
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save maxfire2008/f5eb09ab01a088f8c07b0bff99d9aecf to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save maxfire2008/f5eb09ab01a088f8c07b0bff99d9aecf to your computer and use it in GitHub Desktop.
Download ZIP
Advent of Code 2025 Day 05 solution
Raw
aoc-2025-05.py
import random
import sys
import traceback
import typing
import pathlib
import llist
import copy
class Input:
def __init__(self, d=""):
self.ranges = []
self.ingredients = []
mode = "ranges"
for line in d.splitlines():
if line == "":
mode = "ingredients"
elif mode == "ranges":
ls = line.split("-")
self.ranges.append([int(i) for i in ls])
elif mode == "ingredients":
self.ingredients.append(int(line))
def __str__(self):
return f"ranges: {self.ranges}, ingredients: {self.ingredients}"
def copy(self):
c = Input()
c.ranges = copy.deepcopy(self.ranges)
c.ingredients = copy.deepcopy(self.ingredients)
return c
def part1(data: Input) -> int:
fresh = 0
for i in data.ingredients:
for r in data.ranges:
if r[0] <= i <= r[1]:
fresh += 1
break
return fresh
class FillableLine:
def __init__(self):
# self._filled: list[int] = []
self._filled: llist.dllist = llist.dllist()
def fill(self, r: list[int, int]):
"""
Pre-condition: the self._filled value is a linked list
with only consecutive and non-overlapping ranges within it
Post-condition: the provided range `r` is inserted into
self._filled by altering ranges or inserting them
"""
rmin = r[0]
rmax = r[1]
if len(self._filled) == 0:
self._filled.appendright(r)
return 0
for node in self._filled.iternodes():
# NNNNNNNN
# RRR
if node.value[0] <= rmin and rmax <= node.value[1]:
return 10
# (PPP) NNN (nnn)
# RRRRRRRRRR
if (
(node.prev is None or node.prev.value[1] < rmin)
and rmin <= node.value[0]
and node.value[1] <= rmax
and (node.next is None or rmax < node.next.value[0])
):
node.value[0] = rmin
node.value[1] = rmax
# # NNN (nnnnn)
# # RRRRRR
# if node.value[0] <= rmin <= node.value[1] and (
# node.next is None or rmax < node.next.value[0]
# ):
# node.value[1] = rmax
# return 20
# (PPP) NNN (nnn)
# RRR(RRRRRR)
if (
(node.prev is None or node.prev.value[1] < rmin)
and rmin <= node.value[0]
and node.value[0] <= rmax
):
node.value[0] = rmin
# --NNN (ttt) (ttt) (nnn)
# RRRRRRRRRRRRRRRR
if node.next is not None and node.next.value[0] <= rmax:
t = node.next
while t.next is not None and t.next.value[0] <= rmax:
t = t.next
node.value[1] = max(t.value[1], rmax)
# delete nodes up to t.next
delc = node.next
# print("deleting to", t.next.value)
while delc is not None and delc.value != t.value:
delcn = delc.next
# print("deleting", delc.value)
self._filled.remove(delc)
delc = delcn
self._filled.remove(delc)
return 30
elif node.value[1] < rmax:
node.value[1] = rmax
return 31
return 32
# > (PPP) NNN
# RRR
# e.g., at start of list
if (node.prev is None or node.prev.value[1] < rmin) and rmax <= node.value[
0
]:
self._filled.insertbefore(r, node)
return 40
# NNN nnn nnn nnn
# RRRRRR(RRRRRRRR)
if (
node.value[0] <= rmin <= node.value[1]
): # and node.next.value[0] <= rmax:
# NNN ttt ttt ttt
# RRRRRR(RRRRRRRR)
if node.next is not None and node.next.value[0] <= rmax:
t = node.next
while t.next is not None and t.next.value[0] <= rmax:
# print(f"{t.next.value}[0] < {rmax}")
t = t.next
# print(t.value[1], rmax)
node.value[1] = max(t.value[1], rmax)
# delete nodes up to t.next
delc = node.next
while delc is not None and delc.value != t.value:
delcn = delc.next
self._filled.remove(delc)
delc = delcn
self._filled.remove(delc)
return 50
elif node.value[1] < rmax:
node.value[1] = rmax
return 51
else:
return 52
# NNN (nnn)
# RRR
if node.value[1] < rmin and (
node.next is None or rmax < node.next.value[0]
):
self._filled.insertafter(r, node)
return 60
raise ValueError
def filled(self):
filled = 0
for r in self._filled:
filled += r[1] - r[0] + 1
return filled
def __repr__(self):
return "FillableLine<" + str(list(self._filled)) + ">"
def part2(data: Input, check_naive: bool = True) -> int:
naive_values = []
fresh_ranges = FillableLine()
print(fresh_ranges)
for i, r in enumerate(data.ranges):
print(i, "/", len(data.ranges))
if check_naive:
for v in range(r[0], r[1] + 1):
if v not in naive_values:
naive_values.append(v)
s = fresh_ranges.fill(r)
print(fresh_ranges)
print(r)
print(s)
if check_naive:
frl = fresh_ranges.filled()
vl = len(naive_values)
if frl != vl:
print("naive mismatch!", "frl:", frl, "vl:", vl)
# print(fresh_ranges)
return fresh_ranges.filled()
def naive_part2(data: Input) -> int:
values = []
for i, r in enumerate(data.ranges):
# print(i, "/", len(data.ranges))
for v in range(r[0], r[1] + 1):
if v not in values:
values.append(v)
return len(values)
def fuzz_part2():
data = Input()
for _ in range(100):
v = random.randint(100, 5000)
vr = random.randint(0, 100)
if random.randint(0, 10) == 0:
vr //= 50
r = [v - vr, v + vr]
data.ranges.append(r)
p2 = part2(data.copy(), check_naive=False)
nvp2 = naive_part2(data.copy())
if p2 != nvp2:
print("FUZZ INCONSISTENT:", p2, nvp2, data)
else:
print("FUZZ CONSISTENT")
def main() -> None:
if sys.argv[1] == "_fz2":
for i in range(500):
print(i, "/", 500)
fuzz_part2()
return
data: Input = Input(
open(pathlib.Path(__file__).parent / sys.argv[1], encoding="UTF-8")
.read()
.strip()
)
print("DATA:")
print(data)
print("=" * 20)
answer1: typing.Optional[int] = None
answer2: typing.Optional[int] = None
print("ANSWER1 WORKING:")
try:
answer1 = part1(data.copy())
except Exception as error:
traceback.print_exception(error)
print("=" * 20)
print("ANSWER2 WORKING:")
try:
answer2 = part2(data.copy(), check_naive=False)
except Exception as error:
traceback.print_exception(error)
print("=" * 20)
print("ANSWER1:", answer1)
print("=" * 20)
print("ANSWER2:", answer2)
# print("NAIVE 2:", naive_part2(data.copy()))
if __name__ == "__main__":
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment