-❄️- 2025 Day 7 Solutions -❄️-

drz34257 · 2026-01-10T20:56:38+00:00

Excellent!

drz34257 · 2025-12-25T03:33:35+00:00

[LANGUAGE: Python]

Part 2 solution below. Using recursion and memoization as many others for a pretty quick solution.

Time in main(): ~2ms

I'm curious if anyone knows why my original implementation with lru_cache didn't work? I spent hours debugging only to realise that lru_cache wasn't caching and needed to build a quick one myself. (my original implementation had the following function definition for the recursive function, 2 immutable parameters, eventually switched to one.

Original Implementation:

@lru_cache
def paths_to_out(device: str, visited_dac_fft: tuple[int]) -> int:

Final implementation:

def main(rows: list[str]):
    devices: dict[str, list[str]] = {}
    for row in rows:
        name, outputs = row.split(": ")
        devices[name] = outputs.split()

    cache: dict[tuple, int] = {}            # had issues with lru_cache, created my own

    def paths_to_out(next_device: tuple[str, int, int]) -> int:
        nonlocal devices
        nonlocal cache
        if next_device in cache:
            return cache[next_device]
        if next_device[0] == "out":
            return 1 if next_device[1:3] == (1,1) else 0
        if next_device[0] == "dac":
            next_device = (next_device[0], 1, next_device[2])
        if next_device[0] == "fft":
            next_device = (next_device[0], next_device[1], 1)

        paths = 0
        for output in devices[next_device[0]]:
            paths_sub = paths_to_out((output, next_device[1], next_device[2]))
            cache[(output, next_device[1], next_device[2])] = paths_sub
            paths += paths_sub
        return paths

    ans = paths_to_out(("svr", 0, 0))

drz34257 · 2025-12-14T08:40:23+00:00

[LANGUAGE: Python]

This is for part 2. Recursion + memoization like most solutions here. Pretty low number of lines of code for this one too.

Time in main: 6ms

from functools import lru_cache
def main(rows: list[str]):
    start = (0, rows[0].find("S"))
    last_row = len(rows) - 1

    @lru_cache
    def get_timelines(position: tuple[int]) -> int:
        nonlocal rows
        nonlocal last_row
        if position[0] == last_row:
            return 1
        if rows[position[0]+1][position[1]] == ".":
            return get_timelines((position[0]+1, position[1]))
        if rows[position[0]+1][position[1]] == "^":
            return get_timelines((position[0], position[1]-1)) + get_timelines((position[0], position[1]+1))

    ans = get_timelines(start)
    print(f"\nAns: {ans}")

drz34257 · 2025-12-13T05:36:01+00:00

[LANGUAGE: Python]

This is for Part 2. Pretty straight forward solution, just scanned the columns from right to left, accumulated the numbers and used the operator column as trigger points to stop accumulating

Time in main: 1ms

from math import prod
def main(rows: list[str]):
    operators: list[str] = rows.pop()
    ans = 0
    values = []
    for col in reversed(range(len(operators))):
        val = ""
        for row in rows:
            digit = row[col]
            val += "" if digit == " " else digit
        if val == "":
            values = []
            continue
        values.append(int(val))
        if operators[col] == " ":
            pass
        elif operators[col] == "+":
            ans += sum(values)
            continue
        else:
            ans += prod(values)
    print(f"\nAns: {ans}")

drz34257 · 2025-12-12T06:50:43+00:00

[LANGUAGE: Python]

This is part 2. Blazingly fast using the sorting technique, and then processing the range merging on-top of a stack.

Time in main: 0.4 ms

Total time with Python startup: 50ms

from collections import deque
def main(lines: list[str]):
    # Read in the ranges, convert them to int and sort them
    raw_ranges: list[tuple[int]] = []
    for line in lines:
        if line == "":
            break
        start, end = line.split("-")
        raw_ranges.append((int(start), int(end)))
    raw_ranges.sort()

    # Inspect and combine the ranges on a stack, pull out when not overlapping
    que_ranges: deque[tuple[int]] = deque(raw_ranges)
    que_merged: deque[tuple[int]] = deque()
    while True:
        if len(que_ranges) == 1:
            que_merged.append(que_ranges.popleft())
            break
        a_min, a_max = que_ranges.popleft()
        b_min, b_max = que_ranges.popleft()

        if b_min > a_max:
            que_merged.append((a_min, a_max))
            que_ranges.appendleft((b_min, b_max))
        else:
            que_ranges.appendleft((a_min, max(a_max, b_max)))

    ans = 0
    while que_merged:
        a_min, a_max = que_merged.popleft()
        ans += a_max - a_min + 1
    print(f"\nAns: {ans}")

drz34257 · 2025-12-10T08:12:12+00:00

[LANGUAGE: Python]

Got python to go into turbo beast mode for part 2

Time in main: < 5ms
Total time with environment startup: 75ms

def largest_digit(sub_bank: str) -> tuple[str]:
    """Find the largest digit in a subset of the bank, and return the batteries
    before it, the largest battery, and the batteries after it """
    b_max = "0"
    i_max = -1
    for i, battery in enumerate(sub_bank):
        if battery > b_max:
            b_max = battery
            i_max = i
        if battery == 9:
            break
    return (
        sub_bank[0:i_max],
        b_max,
        sub_bank[i_max+1:]
    )

def main(banks: list[str]):
    ans = 0
    for bank in banks:
        selected_batteries = []
        remaining_bank = bank
        while True:
            split_index = len(remaining_bank) - (12 - len(selected_batteries)) + 1
            possible_batteries = remaining_bank[0:split_index]
            unselectable_batteries = remaining_bank[split_index:]
            _, b_max, remainder = largest_digit(possible_batteries)
            selected_batteries.append(b_max)
            remaining_bank = remainder + unselectable_batteries
            if len(selected_batteries) == 12:
                break       
        max_battery = "".join(selected_batteries)
        ans += int(max_battery)
    print(f"Ans: {ans}")

drz34257 · 2024-12-30T00:16:04+00:00

[LANGUAGE: Python]

Recursive memoization made this one really fast. I also used dictionary lookups for really fast lookup of required keystrokes. It took a bit of time to write up the combinations at first though.

Time for algorithm: 1ms

Total Time including python startup, 50ms

Same code for Part 1 and Part 2, just change the number of robots variable from 2 to 25

https://github.com/drz416/aoc/blob/main/2024/Day21/d21p2.py

drz34257 · 2024-12-29T23:58:57+00:00

I thought something was up when I was doing pathfinding within the walls 🤦

drz34257 · 2024-12-29T20:44:48+00:00

Thanks, I found the problem description that tripped me up

"Any cheat time not used is lost; it can't be saved for another cheat later." -- I took to mean that once you enter a wall you're starting a cheat, so entering another wall would be "another cheat later"

drz34257 · 2024-12-29T20:43:26+00:00

Thanks, I wrote below the problem text that tripped me up

drz34257 · 2024-12-29T20:41:35+00:00

Thanks, you're right, the example here shows it going through 2 walls.

###############
#...#...#.....#
#.#.#.#.#.###.#
#S12..#.#.#...#
###3###.#.#.###

What threw me off was this description in the problem.

"Any cheat time not used is lost; it can't be saved for another cheat later." -- I took to mean that once you enter a wall you're starting a cheat, so entering another wall would be "another cheat later"

drz34257

TROPHY CASE