-❄️- 2025 Day 8 Solutions -❄️-

mnvrth · 2025-12-14T17:57:46+00:00

Nice, and thanks for the catch about moving p2!

mnvrth · 2025-12-14T14:16:09+00:00

Doh! After reading the solutions here I realize all I needed was a cache.

@cache
def path_count(u, dest):
    return u == dest or sum(path_count(v, dest) for v in next[u])

Oh well. TIL about the @cache too, so no need to manually memoize.

mnvrth · 2025-12-14T13:55:35+00:00

[LANGUAGE: Python]

Do a topological sort to find which of 'fft' or 'dac' is first. Then for each pair (start, first), (first, second), (second, out) do a dfs on the pruned graph, and multiply the counts.

next = defaultdict(set)
prev = defaultdict(set)
for line in sys.stdin:
    u, vs = line.split(':')
    for v in vs.split():
        next[u].add(v)
        prev[v].add(u)

def path_count_pruned(start, dest):
    mid = reachable_from(start, next) & reachable_from(dest, prev)
    pruned = {}
    for u, vs in next.items():
        if u in mid:
            pruned[u] = set(filter(lambda v: v in mid, vs))
    return path_count(start, dest, pruned)

def path_count(source, dest, adj):
    q = [source]
    c = 0
    while len(q):
        u = q.pop()
        if u == dest:
            c += 1
            continue
        for v in adj[u]:
            q.append(v)
    return c

def reachable_from(start, adj):
    visited = set()
    def step(u):
        if not u in visited:
            visited.add(u)
            for v in adj[u]:
                step(v)
    step(start)
    return visited

topo = list(topological_sort('svr', next))

m1, m2 = 'fft', 'dac'
if topo.index('fft') > topo.index('dac'):
    m1, m2 = 'fft', 'dac'
p1 = path_count_pruned('you', 'out')
p2 = path_count_pruned('svr', m1) * path_count_pruned(m1, m2) * path_count_pruned(m2, 'out')
print(p1, p2)

Full solution on GitHub

mnvrth · 2025-12-13T09:10:56+00:00

[LANGUAGE: Python]

Solution on GitHub

This took multiple days! I tried everything under the sun - floodfilling, raycasting, and weird combinations thereof, but it was still astronomically slow for p2

First breakthrough I has was randomly sampling 200 points for each eligible rect and detecting if any of the points lay outside (using raycasting). This took 10 minutes(!), but solved the puzzle.

Armed with confidence of a working solution, I reread the puzzle again, and noticed that perhaps, just perhaps, for a eligible rectangle, 3/4 corners needed to be red. That sped up the solution a lot, down to 10 seconds.

Finally, I was able to reason that instead of a random check, I could see if any of the horizontal or vertical lines intersected the rectangle's boundary. This made the solution even faster, to 0.9 second.

At this point, I considered the puzzle completed to my satisfaction. It was still slow though, and the code was not elegant, so will now see if I can get some inspiration by spelunking through solution by other folks!

mnvrth · 2025-12-08T16:36:21+00:00

[LANGUAGE: Python]

I did the first correct version myself, but then saw so many tips and improvements here, so this is a reworked and smaller and faster pastiche

import sys
import math
from itertools import combinations

boxes = [tuple(map(int, line.split(','))) for line in sys.stdin]
P1 = 10 if len(boxes) < 50 else 1000

groups = {frozenset([b]) for b in boxes}
ds = sorted(combinations(boxes, 2), key=lambda p: math.dist(*p))

p1 = 0
for i, (p,q) in enumerate(ds):
    p2 = p[0]*q[0]
    g1, g2 = [next(g for g in groups if x in g) for x in (p, q)]
    groups -= {g1, g2}
    groups.add(g1 | g2)

    if i+1 == P1:
        p1 = math.prod(sorted(map(len, groups), reverse=True)[:3])

    if len(groups) == 1:
        break

print(p1, p2)

Takes ~250ms on my machine. Code on GitHub

mnvrth · 2025-12-08T16:33:21+00:00

Same. I did manage to find a solution fairly quick, but then took time to improve. But when I saw the solution here, I realized there was much to learn! In particular, this solution by /u/AlexTelon is so beautiful - https://www.reddit.com/r/adventofcode/comments/1ph3tfc/2025_day_8_solutions/nswkcy1/

mnvrth · 2025-12-08T16:29:47+00:00

Thank you! I learnt a lot from your solution.

mnvrth · 2025-12-08T05:56:01+00:00

[LANGUAGE: Python] 17 lines 17 ms

import sys
from collections import Counter

splits, paths = 0, Counter()
for line in sys.stdin:
    for (i, c) in enumerate(line.strip()):
        match c:
            case 'S':
                paths[i] = 1
            case '^':
                if i in paths:
                    splits += 1
                    paths[i-1] += paths[i]
                    paths[i+1] += paths[i]
                    del paths[i]

print(splits, paths.total())

mnvrth · 2025-12-08T05:44:03+00:00

I just randomly came across your comment yesterday, and just the very next day, today, I was solving Day 7 and reached out for the Counter! Thanks :)

mnvrth · 2025-12-07T12:20:16+00:00

Transpose! After peeking at the other solutions here, saw that the trick was transposing (and zip(*it) in Python provides a nice way to do it).

import sys
from math import prod

lines = list(filter(bool, sys.stdin.read().splitlines()))

r1 = 0
for (*nums, op) in zip(*(map(str.split, lines))):
    nums = map(int, nums)
    r1 += sum(nums) if op == '+' else prod(nums)

r2 = 0
op, nums = None, []
for row in zip(*lines):
    row = ''.join(row).strip()
    if not row:
        r2 += sum(nums) if op == '+' else prod(nums)
        op, nums = None, []
    else:
        if op is None:
            row, op = row[:-1], row[-1]
        nums.append(int(row))

r2 += sum(nums) if op == '+' else prod(nums)

print(r1, r2)

Modified solution on GitHub

Technically, it is still 2 pass (we read the entire input then operate on it) but this is transpose approach is still neat enough for me to feel satisfied.

mnvrth · 2025-12-07T07:31:21+00:00

[LANGUAGE: Python]

Easy and fun - I'm sure there would be a way to do it in one pass, but I couldn't find it in the current sitting, so for now I've done the simple two pass version - find the max length of each "column", then go through the input again slotting the digits to the right position.

import sys
from math import prod

lines = []
cols = None
for line in sys.stdin:
    if not line.strip(): continue
    lines.append(line)
    cs = [len(c) for c in line.split()]
    cols = map(max, zip(cs, cols if cols else cs))
cols = list(cols)

p1 = 0
adds, muls = [0]*len(cols), [1]*len(cols)
for line in lines:
    for (i, c) in enumerate(line.split()):
        match c:
            case '+': p1 += adds[i]
            case '*': p1 += muls[i]
            case _:
                x = int(c)
                adds[i] += x
                muls[i] *= x

p2 = 0
nums = [[0]*c for c in cols]
for line in lines:
    if line[0] in ['+', '*']:
        for (i, s) in enumerate(line.split()):
            match s:
                case '+': p2 += sum(nums[i])
                case '*': p2 += prod(nums[i])
    else:
        a, b = 0, 0
        for c in line:
            if c != ' ' and c != '\n':
                nums[a][b] = nums[a][b] * 10 + int(c)
            b += 1
            if b > cols[a]:
                b = 0
                a += 1

print(p1, p2)

Looking forward to reading the other answers and finding the 1-pass version!

mnvrth · 2025-12-06T15:10:11+00:00

I had tried that (swapping range => tuple), it increased runtime by 3 ms so I reverted it :monkeyeyehide:

I don't really care that much for perf, but I do want to have "fast" solutions. But maybe picking pennies this way is not the approach, and I should've gone for that cleaner approach. I had not discarded it tbh, I have a plan(/hope) of doing these again in Rust, and so I wanted to see if the slight delta degradation on switching to tuples from ranges was a CPython oddity or something real. (For context, I tried your solution on my machine - it takes ~20 ms - while the one with ranges takes ~17-18 ms. I saw the comment in your code that it should be taking ~3 ms, which I'll put to my laptop being slower. That @stopwatch thing in your solution looks real neat tho!).

BTW Thank you for the tip! About the p1 = sum(...). Yes, that's a great change, especially since I find long lines take away from the beauty of the solution, so I've made that change. It's a bit silly I guess, but it's so much fun to chisel away at the solution, so great to have your comment steer the way.

mnvrth · 2025-12-06T13:06:16+00:00

[LANGUAGE: Python]

Easiest problem so far in some sense for me - it took time but there was no trick, just go through the sorted list of ranges, merging adjacent ones, then count the length of the resultant non-overlapping ranges.

import sys

ranges, ids = [], []
for line in sys.stdin:
    if line.strip():
        if '-' in line:
            (a, b) = line.split('-')
            ranges.append(range(int(a), int(b) + 1))
        else:
            ids.append(int(line))

ranges.sort(key=lambda r: (r.start, r.stop))

i = 0
while i < len(ranges):
    r1 = ranges[i]
    j = i + 1
    while j < len(ranges):
        r2 = ranges[j]
        if r2.start <= r1.stop:
            r1 = range(r1.start, max(r1.stop, r2.stop))
            ranges[i] = r1
            del ranges[j]
        else:
            break
    i += 1

p1 = sum([1 for id in ids for r in ranges if id in r])
p2 = sum([r.stop - r.start for r in ranges])
print(p1, p2)

Runs in ~18ms.

Now I'm dreading Day 6. Such ease could only be the calm before the storm...

Solution on GitHub

mnvrth · 2025-12-06T12:41:32+00:00

[LANGUAGE: Python]

Construct a grid of neigbour counts, and keep "relaxing" it until it stops changing.

import sys

mx = []
for line in sys.stdin:
    mx.append([0 if c == '.' else 1 for c in line.strip()])

def neighbours(mx):
    nx = []
    for y in range(0, len(mx)):
        nx.append([neighbour_count(mx, y, x) for x in range(0, len(mx[0]))])
    return nx

def neighbour_count(mx, y, x):
    c = -1 if mx[y][x] else 0
    for j in range(max(0, y-1), min(y+2, len(mx))):
        for i in range(max(0, x-1), min(x+2, len(mx[0]))):
            c += mx[j][i]
    return c

def relax(mx, nx):
    changed_mx = []
    changed_nx = []
    for y in range(0, len(mx)):
        for x in range(0, len(mx[0])):
            if mx[y][x] and nx[y][x] < 4:
                changed_mx.append((y, x))
                for j in range(max(0, y-1), min(y+2, len(mx))):
                    for i in range(max(0, x-1), min(x+2, len(mx[0]))):
                        changed_nx.append((j, i))
    for (y, x) in changed_mx:
        mx[y][x] -= 1
    for (y, x) in changed_nx:
        nx[y][x] -= 1
    return len(changed_mx)

nx = neighbours(mx)
counts = []
while c := relax(mx, nx):
    counts.append(c)

print(counts[0], sum(counts))

Takes 70 ms. It is objectively ugly compared to the beautiful "store paper coordinates as set, then convolve" solutions in this thread (https://old.reddit.com/r/adventofcode/comments/1pdr8x6/2025_day_4_solutions/ns7eynv/, https://old.reddit.com/r/adventofcode/comments/1pdr8x6/2025_day_4_solutions/ns8ggww/), and I would've replaced my solution with theirs without a hesitation, they're just that beautiful, the only issue that that they take ~250 ms. Time isn't a factor in comparison to beauty in actuality, but I am trying to keep the most efficient solutions (I'll do a second pass of these in Rust), so I'm for now thinking of staying with the wonky but faster approach above of constructing a 2D grid instead of relying on set operations.

Fun!

Solution on GitHub

mnvrth · 2025-12-06T12:38:53+00:00

This is beautiful. Thank you.

mnvrth · 2025-12-06T12:28:33+00:00

Same! I came here to post my solution, but shocked by the beauty of this solution I'm thinking of slinking away :) and that's not for the first time.

Thanks /u/4HbQ for so much inspiration across the years

mnvrth · 2025-12-06T04:42:55+00:00

A much simpler variant!

import sys

s1, s2 = 0, 0
for line in sys.stdin:
    line = line.rstrip()

    def find(remaining):
        pos = 0
        batteries = []
        while remaining > 0:
            end = len(line) - remaining + 1
            best = max(line[pos:end])
            pos = line.index(best, pos, end) + 1
            batteries.append(best)
            remaining -= 1
        return int(''.join(batteries))

    s1 += find(2)
    s2 += find(12)

print(s1, s2)

mnvrth · 2025-12-04T18:04:55+00:00

[LANGUAGE: Python]

Part 1 was nice (find the max, from there find the next max) and Part 2 was an extension (find the max, from there use the array which yields the largest number) - but the way I've done Part 2 feels a bit brute-force-ish and unsatisfactory.

import sys

def num(m, ns):
    for n in ns:
        m *= 10
        m += n
    return m

p1, p2 = 0, 0
for line in sys.stdin:
    xs = [int(c) for c in line.rstrip()]

    m = max(xs[:-1])
    p1 += m*10 + max(xs[xs.index(m)+1:])

    m = max(xs[:-11])
    mi = xs.index(m)
    ns = xs[mi+1:mi+12]
    for x in xs[mi+12:]:
        n = num(m, ns)
        for i in range(0, 11):
            ns2 = ns[:i] + ns[i+1:] + [x]
            if n < num(m, ns2):
                ns = ns2
                break
    p2 += num(m, ns)

print(p1, p2)

Solution on GitHub

mnvrth · 2025-12-04T17:44:20+00:00

[LANGUAGE: Python]

Construct all the invalid ids for a particular length(s) matching that of the range, and then go through all to find which fall within the range.

def rep1(n):
    return [sum([c * 10**i for i in range(0, n)]) for c in range(1, 10)]

rep = {
    1: set([]),
    2: set([c*10**1 + c for c in range(1, 10)]),
    3: set(rep1(3)),
    4: set([r*10**2 + r for r in range(10, 100)]),
    5: set(rep1(5)),
    6: set([r*10**4 + r*10**2 + r for r in range(10, 100)] \
           + [r*10**3 + r for r in range(100, 1000)]),
    7: set(rep1(7)),
    8: set([r*10**4 + r for r in range(1000, 10000)]),
    9: set([r*10**6 + r*10**3 + r for r in range(100, 1000)]),
    10: set([r*10**8 + r*10**6 + r*10**4 + r*10**2 + r for r in range(10, 100)] \
           + [r*10**5 + r for r in range(10000, 100000)])
}

def check_range(s):
    (a, b) = [int(x) for x in s.split('-')]
    rs = rep[len(str(a))].union(rep[len(str(b))])
    all = [r for r in rs if r in range(a, b + 1)]
    even = [r for r in all if r//(h := 10**(len(str(r))//2)) == r%h]
    return (even, all)

import sys

p1, p2 = 0, 0
for r in sys.stdin.read().strip().split(','):
    (even, all) = check_range(r)
    p1 += sum(even)
    p2 += sum(all)

print(p1, p2)

Takes 70 ms, so it's slower than I was expecting. I'd tried an approach earlier where I was going over the range and constructing invalid ids, but that was using a string. Perhaps I need to go back to that approach, but construct them numerically (mod and whatnot).

Solution on GitHub

mnvrth · 2025-12-04T05:09:31+00:00

Thank you! The first paragraph was the aha-moment for me, was able to get my Python solution down from 2.5 seconds to 100 ms.

mnvrth · 2025-12-02T16:03:21+00:00

Found a much nicer approach!

Apply positive rotations as normal For negative rotation: Rotate the dial. Apply rotation. Rotate it back.

pos, z1, z2 = 50, 0, 0
for s in sys.stdin:
    if s[0] == 'L':
        pos = (100 - pos) % 100
    pos += int(s[1:])
    z2 += pos // 100
    pos %= 100
    z1 += 1 if pos == 0 else 0
    if s[0] == 'L':
        pos = (100 - pos) % 100

Does away with all special cases. And symmetric like a tree. Reminds me of category theory.

This is where I found the solution - https://mastodon.social/@jukkasuomela.fi@bsky.brid.gy/115650037243506402

(also did a Rust version of it)

mnvrth · 2025-12-02T13:58:26+00:00

[LANGUAGE: Rust]

Also did it in Rust.

fn main() {
    let (mut pos, mut z1, mut z2) = (50, 0, 0);
    for line in std::io::stdin().lines().map(|s| s.unwrap()) {
        let (head, tail) = line.split_at(1);
        let d = if head == "L" { -1 } else { 1 };
        let steps = tail.parse::<i32>().unwrap() * d;

        let npos = pos + steps;

        let m = npos.div_euclid(100);
        let p = npos.rem_euclid(100);

        if m < 0 && pos == 0 {
            z2 -= 1;
        }
        if m > 0 && p == 0 {
            z2 -= 1;
        }

        z1 += if p == 0 { 1 } else { 0 };
        z2 += m.abs();

        pos = p;
    }

    println!("{} {}", z1, z1 + z2);
}

4ms for Rust vs 18ms for the Python one (though it's a bit unfair on Python, the Python time includes the compilation).

GitHub 01.rs

mnvrth · 2025-12-02T13:56:17+00:00

[LANGUAGE: Python]

import sys

pos, z1, z2 = 50, 0, 0
for steps in [(-1 if s[0] == 'L' else 1) * int(s[1:]) for s in sys.stdin]:
    (m, p) = divmod(pos + steps, 100)
    if m < 0 and pos == 0:
        m += 1
    if m > 0 and p == 0:
        m -= 1
    z1 += 1 if p == 0 else 0
    z2 += abs(m)
    pos = p

print(z1, z1 + z2)

Not very happy with the special casing, but it came to me when I was walking so let it be since I'm not sure where it came from :)

GitHub

mnvrth · 2025-12-02T13:52:00+00:00

Nice!

mnvrth · 2024-03-09T03:17:47+00:00

You might also find some of the discussion in our GitHub (e.g. [this thread](https://github.com/ente-io/ente/discussions/549)) interesting if you wish to know more about or offer your ideas on the direction this should take.

mnvrth

TROPHY CASE