Solving Advent of Code 2025

I took the Solve It with Code course from answer.ai, and Advent of Code is used as practice.

I always thought my Python skills were quite mediocre; I always used to in a “just get things done” style, so this is also a chance to improve my Python. For this reason I want to mostly stick with the standard packages and pythonic styles, and only use extra packages when it’s too cumbersome otherwise.

The way AOC works, we have one new puzzle each day, which has two parts: part 1 is often simpler, and can be tackled with brute force; but part 2 would need some more structured thinking, and better algorithmic design.

Accompanying each day’s input there is also a smaller example input, which is worked out to explain the problem, understand the data and show the expected solution patterns. It’s very helpful as a stepstone to solving the real problem. But it can also be a double edged sword, because there might be patterns or complexities that are present in the real data but not in the example data, so we might be led astray if we rely completely on the example data to construct the solutions.

house keeping

The SolveIt method has 4 steps:

1. understand the problem
2. make a plan
3. carry out the plan
4. review, reflect, refactor

The key is to think clearly, go slowly, stop and reflect constantly.

We use the aocd package to interact with Advent of Code programmatically.

1
2
3

import os
session = os.getenv('AOC_SESSION')
from aocd import get_data, submit, models

1

current_day is only available in December (EST)

01 rotating dials at the entrance

1. We are at the entrance, and there we have a circular dial;
2. its range is 0 to 99;
3. we can turn left (L) or right (R);
4. keep turning right after 99 we arrive at 0, and keep turning left after 0 we arrive at 99;
5. we start at 50, and the input is a series of records for turning left or right;
6. for part 1 we count the total number of times we arrive at 0, after turning the dial;
7. for part 2 we count the total number of times we pass across 0, after turning the dial.

1
2
3
4
5
6
7
8

def parse_2501(data: str) -> list[int]:
    """Parse rotations: L becomes negative, R becomes positive."""
    return [-int(line[1:]) if line[0] == 'L' else int(line[1:])
            for line in data.split('\n')]

D01 = models.Puzzle(year=2025, day=1)
rotations = parse_2501(D01.input_data)
print(len(rotations), rotations[:5])

1

4042 [29, -3, -46, -25, -38]

One of my goals for AOC is to use, as much as possible, only the standard libraries. I felt that there are a lot I can learn in the standard libraries, and my experience with AOC has proven that I was quite right. For part 1, Python’s modulo operator elegantly handles the circular arithmetic—even for negative numbers. (50 - 68) % 100 gives 82, and (-5) % 100 gives 95. This means we don’t need to manually handle wrap-around; just track cumulative position modulo 100 and count zeros.

Since the landing position can be calculated by accumulatively adding the new turns to the starting position, we can use itertools.accumulate. The function apply a binary function (default to sum) accumulatively to a function, then return a generator of the sequence of results.

1
2

from itertools import accumulate
print(list(accumulate([1, 2, 3, 4], initial=0)))

1

[0, 1, 3, 6, 10]

After the accumulative sum we do modulo to see if it lands on zeros.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def solve_250101(data: str) -> int:
    """Part 1: Count positions landing exactly on 0.

    Uses accumulate with initial=50, then applies %100 to get dial positions.
    O(n) time, O(n) space.
    """
    rotations = parse_2501(data)
    positions = [p % 100 for p in accumulate(rotations, initial=50)][1:]
    return sum(1 for p in positions if p == 0)

print(solve_250101(D01.input_data))

1

969

For part 2, we need to count every time the dial crosses 0 during a rotation, not just when it lands there. My initial idea was to add a large offset (1e6) to convert circular to linear arithmetic, then count “hundred boundaries” crossed. However this turned out to be unnecessary. However we have to be careful to avoid double counting landing positions for a previous turn and the starting position for the next.

After quite some trial and error it turns out, for a move from s to e, the number of zeros crossed depends only on direction:

• Going right (positive turn): e//100 - s//100
• Going left (negative turn): (s-1)//100 - (e-1)//100

The -1 adjustment for leftward moves ensures we count correctly at boundaries: moving left from 10000 to 9999 shouldn’t count as crossing (we started at the boundary), but moving right from 9999 to 10000 should. The logic seems simple in retrospect, but I got stuck here for quite a while!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def solve_250102(data: str) -> int:
    """Part 2: Count all zero-crossings during rotations.

    Adds offset to linearize circular dial, then counts hundred-boundaries
    crossed using integer division. Direction matters for boundary handling.
    O(n) time, O(n) space.
    """
    rotations = parse_2501(data)
    ends = list(accumulate(rotations, initial=50))

    total = 0
    s = ends[0]
    for t, e in zip(rotations, ends[1:]):
        if t > 0: # right turn, count as usual
            total += e // 100 - s // 100
        else: # left turn, -1 to avoid double counting
            total += (s - 1) // 100 - (e - 1) // 100
        s = e
    return total

print(solve_250102(D01.input_data))

1

5887

02 invalid product IDs in the gift shop

1. We are in the gift shop, and we are given a list of product ID ranges;
2. some IDs in those ranges are considered invalid;
3. for part 1 it’s IDs with double repetitions, e.g. 55, 6464, 321321, etc.
4. for part 2 it’s IDs with any number of repetitions, e.g. 55, 555, 64646464, etc.
5. we need to find and sum up all the invalid IDS.

When I started doing AOC, data parsing was a huge effort, because I had to sharpen my list comprehension and looping skills. But this got easier as I worked through more puzzles. Come to think about it, perhaps the only thing that computers can do better than humans, are fast iterations? As such it should be a central focus in computer programming. As Alan Perlis would say, “a program without a loop and a structured variable isn’t worth writing.” (Still working on the later!)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import numpy as np

def parse_2502(data: str) -> list[tuple[str, str]]:
    """Parse input into list of (start, end) string tuples.
    Keep as strings to preserve digit length information."""
    return [tuple(rng.split('-')) for rng in data.split(',')]

D02 = models.Puzzle(year=2025, day=2)
data = D02.input_data
ranges = parse_2502(data)
print(len(ranges),sum(int(e) - int(s) + 1 for s, e in ranges))

1

38 2178105

For part 1, since we are filtering for double repetitions, only even-length IDs can be invalid, so I filtered the ranges to even-length ranges, and then used integer division/modulo to compare halves. The filtering was made easy by the fact that the maximum length difference between start and end is only 1. This upfront filtering is perhaps unnecessary; I did it mainly to reduce the cognitive load for solving the problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def solve_250201(data: str) -> int:
    """Part 1: Sum all double-repetition IDs in ranges.

    Approach: expand ranges to arrays, use vectorized arithmetic
    to check if first_half == second_half via division and modulo.

    O(n) where n = total numbers across all ranges.
    """
    ranges = parse_2502(data)

    def filter_range(start: str, end: str) -> tuple[str, str] | None:
        """Filter to even-length numbers only."""
        len_s, len_e = len(start), len(end)
        s_even, e_even = len_s % 2 == 0, len_e % 2 == 0

        if s_even and e_even: return (start, end)
        elif s_even and not e_even: return (start, '9' * len_s)
        elif not s_even and e_even: return ('1' + '0' * (len_e - 1), end)
        else: return None

    filtered = [r for r in map(lambda x: filter_range(*x), ranges) if r]

    total = 0
    for start, end in filtered:
        a = np.arange(int(start), int(end) + 1)
        divider = 10 ** (len(start) // 2)
        mask = a // divider == a % divider
        total += a[mask].sum()
    return total

print(solve_250201(D02.input_data))

1

30608905813

For part 2 any length can be invalid as long as the digits are a repetition of a shorter base (at least two repeats), so we cannot filter out any number and have to check them all. The approach I settled on, is to build up all possible repetition patterns for all number lengths, and then check whether each pattern is found in each range. That’s a huge amount of loops!

1. get all the lengths for all ranges.
2. for all lengths, get all their factors. We need to exclude the lengths themselves, since repeating once doesn’t count.
3. for all factor lengths, build up all repetition bases.
4. for all length bases, build up all repetitions that match the target length.
5. since all above work only involves the lengths of the numbers, not the ranges themselves, they can be done upfront.
6. check whether the repets are in any of our ranges.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

from sympy import divisors

def solve_250202(data: str) -> int:
    """Part 2: Sum all repeated-pattern IDs (≥2 reps) in ranges.

    Approach: generate all possible repeated-pattern numbers,
    then filter to those within any range. Much faster than
    checking every number when candidates are sparse.

    O(c * r) where c = candidates, r = ranges.
    """
    ranges = parse_2502(data)

    # Collect all digit lengths and their proper divisors
    all_lens = set(len(x) for rng in ranges for x in rng)
    all_divs = set()
    for l in all_lens:
        all_divs.update(divisors(l)[:-1])  # exclude self

    # Build bases for each divisor length
    bases = {}
    for f in all_divs:
        if f == 1: bases[f] = list(range(1, 10))
        else: bases[f] = list(range(10**(f-1), 10**f))

    # Generate all candidate repeated-pattern numbers
    candidates = set()
    for div in all_divs:
        for base in bases[div]:
            for target_len in all_lens:
                if target_len % div == 0 and target_len > div:
                    candidates.add(int(str(base) * (target_len // div)))

    # Sum candidates that fall in any range
    total = 0
    for start, end in ranges:
        s, e = int(start), int(end)
        for c in candidates:
            if s <= c <= e:
                total += c
    return total

print(solve_250202(D02.input_data))

1

31898925685

I think my solution is quite complicated. I’m not versed in regular expressions, this is one of my weak points. In retrospect, since we are literally just finding patterns in a string, regex seems to be the natural choice. I plan to come back for a regex solution later.

03 maximum joltages of the lobby escalator

1. we need to get the escalator working by setting it to a maximum power level;
2. we have a list of battery “banks”,
3. each bank in turn is another long list of labelled batteries, we can only choose a certain number of them;
4. the power that each bank supplies is given by concatenating the chosen numbers, e.g. choosing 5 and 6 from 45623 gives us 56;
5. for part 1 we choose 2 of them, for part 2 we choose 12.

First parse the data into lists of integers.

1
2
3
4
5
6

def parse_2503(data: str) -> list[list[int]]:
    return [[int(c) for c in l] for l in data.splitlines()]

D03 = models.Puzzle(year=2025, day=3)
banks = parse_2503(D03.input_data)
print(len(banks), len(banks[0]), len(banks[-1]))

1

200 100 100

Part 1 looks quite simple: pick the best possible tens digit while leaving one digit for units, then after choosing the tens, choose the largest units digit to its right. It’s all about indexing.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def solve_250301(data: str) -> int:
    """Part 1: sum of maximum 2-digit joltage per bank."""
    banks = parse_2503(data)
    total = 0
    for line in banks:
        tens = max(line[:-1])
        tens_idx = line.index(tens)
        units = max(line[tens_idx+1:])
        total += int(str(tens) + str(units))
    return total

print(solve_250301(D03.input_data))

1

17155

line.index(val) only finds the first index for val, which happens to be exactly what we want.

Part 2 is the same logic, but with 12 digits, we have to be more careful with the indexing. This is a typical case where the data being processed is changing as the loop progresses, so the most important issue is to keep the target data correctly updated. In this case, since the updated allowed data is a slice of the original list, we only have to keep updating the start and end of the indexing. The key is to always leaving enough room the the rest of the digits.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def solve_250302(data: str) -> int:
    """Part 2: sum of maximum 12-digit joltage per bank."""
    banks = parse_2503(data)
    total = 0
    for line in banks: # loop through each bank
        start, end = 0, -12+1 # allowed indexing range
        picks = []
        for _ in range(12): # loop through the digits
            if end == 0: # the last digit requires separate slicing syntax
                l = line[start:]
                m = max(l)
            else: # all digits except the last
                l = line[start:end]
                m = max(l)
                idx = l.index(m)
                start += idx + 1
                end += 1
            picks.append(m)
        total += int(''.join(map(str, picks)))
    return total

print(solve_250302(D03.input_data))

1

169685670469164

All in all this one is fairly simple, but correctly updating the indices can be tricky if we kept it all in head. I found my current indexing approach rather ugly, especially the -12+1 part, and the fact that I have to use a different indexing syntax for the last digit. Finding each digit is actually indexing a slice of the original list, so we have to accumulate the indices correctly. I had to draw some schematics on paper to get the indexing logic right. I intend to find a better indexing logic once I got the time.

04 accessible paper rolls in the print shop

1. we have paper rolls in the print shop, arranged on a 2D grid;
2. rolls are denoted by @, empty spaces by .;
3. each roll has up to 8 neighbors (the 3x3 grid around it);
4. a roll is accessible if it has fewer than 4 neighboring rolls;
5. in part 1 we count all accessible rolls in the initial grid;
6. in part 2 we repeatedly remove all accessible rolls, and count how many are removed in total.

Parsing the data into a 2D grid.

1
2
3
4
5
6
7

def parse_2504(data: str) -> list[list[int]]:
    """Parse grid: @ -> 1, . -> 0."""
    return [[1 if c == '@' else 0 for c in line] for line in data.splitlines()]

D04 = models.Puzzle(year=2025, day=4)
grid = parse_2504(D04.input_data)
print(len(grid), len(grid[0]))

1

135 135

Initially I thought about using a tuple of indices for the data, but apparently using a 2D Numpy array would be much simpler. The key is the 3x3 kernel with a zero in the center.

This problem is quite similar to the convolution operation in computer vision, so I turned to scipy.ndimage.convolve. But actually the convolution used in computer vision packages, such as PyTorch, is not convolution, but correlation, since mathematically convolution involves flipping the input data first. So the right operation is actually scipy.ndimage.correlate, and padding all borders with 0 is natively supported with the constant mode, and the constant value being set to 0.

And then finding the targets satisfying the creterion is just filtering the results for paper rolls with less than 4 neighbors.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

import numpy as np
from scipy.ndimage import correlate

def solve_250401(data: str) -> int:
    """Part 1: count rolls with <4 neighbors.

    Uses 8-neighbor correlation with a 3x3 kernel.
    O(H*W) time, O(H*W) space.
    """
    grid = parse_2504(data)
    arr = np.array(grid, dtype=int)
    kernel = np.array([[1, 1, 1],
                       [1, 0, 1],
                       [1, 1, 1]], dtype=int)
    neighbor_counts = correlate(arr, kernel, mode='constant', cval=0)
    return int(((arr == 1) & (neighbor_counts < 4)).sum())

print(solve_250401(D04.input_data))

1

1437

Part 2 is the same neighbor test, but applied repeatedly. Each pass removes the rolls that are currently accessible; we keep looping until no more rolls qualify.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def solve_250402(data: str) -> int:
    """Part 2: iteratively remove accessible rolls and count total removed.

    Each iteration is O(H*W); the number of iterations depends on structure.
    """
    grid = parse_2504(data)
    arr = np.array(grid, dtype=int)
    kernel = np.array([[1, 1, 1],
                       [1, 0, 1],
                       [1, 1, 1]], dtype=int)
    total = 0
    while True:
        neighbor_counts = correlate(arr, kernel, mode='constant', cval=0)
        mask = (arr == 1) & (neighbor_counts < 4)
        count = int(mask.sum())
        if count == 0:
            break
        total += count
        arr[mask] = 0
    return int(total)

print(solve_250402(D04.input_data))

1

8765

I intend to implement the indexing solution later, without NumPy. In retrospect the problem is quite easy, once we connected it to image processing in computer vision. But this doesn’t come up right away; I only thought of it after spending quite some effort considering how to pad the grid. This shows that I still need practice on some of the basic algorithms.

05 fresh items in the cafeteria

1. we are in the cafeteria, which keeps a LARGE inventory (large enough to feed a nation!)
2. we have two lists, the first is ranges of possible fresh items, possibly overlapping;
3. the second is the individual items that are currently actually in inventory, some fresh, some probably rotten;
4. for part 1 we need to find all the fresh items in inventory, and count them;
5. for part 2 we need to count how many items are actually in the overlapping fresh item ranges.

My original plan was quite simplistic, just turn the lists of ranges into one big set with all the elements, which perfectly solves the partially overlapping problem; then part 1 is simply checking set membership, while part 2 is checking the size of the set. But set is atomic, which means that every element in it has to be independently initiated, and this requires a huge amount of memory: I tried and exhausted the memory before finishing the set initialization.

The cleanest practical solution should be deduplicating and merging the overlapping ranges, after ordering them one after another, and then for part 1 we can find the range corresponding to a certain item and check its membership, for part 2 just sum up the range lengths.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def parse_2505(data: str) -> tuple[list[tuple[int, int]], list[int]]:
    """Parse input into (ranges, ids). Ranges are inclusive (lo, hi) tuples."""
    ranges, ids = [part.split('\n') for part in data.split('\n\n')]
    ranges = [tuple(map(int, rng.split('-'))) for rng in ranges]
    ids = list(map(int, ids))
    return ranges, ids

D05 = models.Puzzle(year=2025, day=5)
ranges, ids = parse_2505(D05.input_data)
print(len(ranges), len(ids))

1

189 1000

However for part 1, since we only have 1000 items, and 189 ranges to check, we might just check them one by one using brute force. Nonetheless, note that an item is fresh if it’s in any range, so we could stop checking for that item once an enclosing range is found. And any() with a generator expression is quite neat for readable short-circuit membership testing.

1
2
3
4
5
6
7
8
9

def solve_250501(data: str) -> int:
    """Part 1: Count IDs that fall within any range.

    O(n*m) where n=IDs, m=ranges.
    """
    ranges, ids = parse_2505(data)
    return sum(any(lo <= inv <= hi for lo, hi in ranges) for inv in ids)

print(solve_250501(D05.input_data))

1

840

Once data parsed to the correct format, the solution is just a one-liner. Using generators avoids keeping all the items in memory, and using any we can early stop the membership check once a match is found.

For part 2, saying that we need to deduplicate the ranges is neither clear on what the desired result should be like, nor how we could get there. We first need to sort them by starting value, which can be easily dealt with with sorted. Then starting with the first range, we can merge the remaining ranges to it, one by one. The merged result can be a single range, e.g. merging (1, 3) to (1,2) gives simply (1, 3), or a number of disjoint ranges, e.g. merging (4,6) to (1,3) gives [(1,3), (4,6)]. For this reason the starting object must be a list with only one element, not the element itself, i.e. [(1,2),] not (1,2).

My initial impression of reduce is largely limited to summary statistics, min, max, argmin, etc. But reduce is actually a general procedure that applies a function of two arguments cumulatively to the items of a sequence or iterable, from left to right, so as to reduce the iterable to a single value. So it’s a perfect fit for what we are trying to achieve.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

from functools import reduce
def solve_250502(data: str) -> int:
    """Part 2: Count total unique IDs covered by union of all ranges.

    Classic interval merging algorithm:
    1. Sort ranges by start
    2. Merge overlapping/adjacent ranges via reduce
    3. Sum lengths (+1 for inclusive bounds)
    """
    ranges, _ = parse_2505(data)
    sorted_ranges = sorted(ranges)

    def merge_step(acc, rng):
        last_start, last_end = acc[-1]
        next_start, next_end = rng
        if last_end < next_start:  # no overlap
            acc.append(rng)
        else:  # overlap: extend current range
            acc[-1] = (last_start, max(last_end, next_end))
        return acc

    merged = reduce(merge_step, sorted_ranges[1:], sorted_ranges[:1])
    return sum(hi - lo + 1 for lo, hi in merged)

print(solve_250502(D05.input_data))

1

359913027576322

The use of reduce in this puzzle is inspirational to me. More and more I’m convinced that programming is simply about iteration, once we have the object to be iterated over, and the target to be produced correctly configured (that is, the data structure properly laied out.) All other procedural programs are boilerplates. So again, “a program without a loop and a structured variable is not worth writing”.

06 cephalopod math in the trash compactor

1. we are given a set of arithmetic problems laid out in a wide grid;
2. the last row has the operators, the rows above are digits for operands;
3. problems are separated by full columns of spaces;
4. part 1 reads numbers by rows (split on whitespace), part 2 reads numbers by columns (trimming the leading or ending whitespaces);
5. once parsed, each problem is just a sum or a product, then we add all results.

This is the first time where the difficulty of solving the puzzle lays in parsing the data, rather than solving the problems. There are only 2 operators, multiplication and addition, which should not pose any problem in any modern programming language. In fact, after parsing the data correctly the solution for both parts should be identical.

For part 1 the key problem is to split the numbers into groups of problems. This seemingly simple problem is complicated by the fact that all data processing functions I know of (in Python) all process data row by row, while the numbers for each problem are arranged by columns. However this is made easy by a combination of zip(*numbers), which is effectively the transpose function in standard Python. The operator row gives the operator for each problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def parse_250601(data: str) -> tuple[list[tuple[int, ...]], list[str]]:
    """Part 1 parse: split each row on whitespace, then zip into problems."""
    *number_rows, operator_row = data.splitlines()
    numbers = [list(map(int, row.split())) for row in number_rows]
    problems = list(zip(*numbers))
    operators = operator_row.split()
    return problems, operators

D06 = models.Puzzle(year=2025, day=6)
problems, operators = parse_250601(D06.examples[0].input_data)
print(len(problems), problems[0], operators[0])

1

4 (123, 45, 6) *

After parsing the data all that’s left is to compute each problem using its operator and sum everything. Since this exact logic can be used in both parts, I’ve refactored the solver function so that in addition to the data, it also accepts a parser argument.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from math import prod

def solve_2506(data: str, parser) -> int:
    """Shared solver: apply the operator to each problem, then sum."""
    problems, operators = parser(data)
    return sum(
        prod(nums) if op == '*' else sum(nums)
        for nums, op in zip(problems, operators)
    )

print(solve_2506(D06.input_data, parse_250601))

1

6957525317641

Actually we can understand this solution as another parser: parsing the * and + symbols into Python prod and sum functions. But this is rather simple. I plan to study some similar use cases but with more complexity later (Norvig’s lisp interpreters).

The parsing logic for part 2 is a bit more convoluted. The problems in part 1 are stored in different columns, and we have to process them into rows (thus the need for transpose), because that’s what our computer is accustomed to process. In part 2, apart from the problems being separated in columns, the operands for each problem are also in columns, so this creates an extra layer of complexity. We can see that most of the difficulty in this puzzle arises because of the fact that we are only accustomed to processing information in a certain fashion, i.e. one row after another. It’s curious that we are so used to processing information row by row, from left to right, and almost all our computer tools are built around this procedure. It’s quite possible that some other civilizations might invent some other procedures that work differently. Classic Chinese, for example, reads column by column, and from right to left.

Back to the problem, the key is to transpose the character grid, then group contiguous non-blank columns into problems.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

from itertools import groupby

def parse_250602(data: str) -> tuple[list[tuple[int, ...]], list[str]]:
    """Part 2 parse: read numbers by columns (character-wise)."""
    *number_rows, operator_row = data.splitlines()
    columns = [''.join(chars) for chars in zip(*number_rows)]
    groups = [
        list(group)
        for is_digit, group in groupby(columns, key=lambda col: col.strip() != '')
        if is_digit
    ]
    problems = [tuple(int(col.strip()) for col in group) for group in groups]
    operators = operator_row.split()
    return problems, operators

problems, operators = parse_250602(D06.examples[0].input_data)
print(len(problems), problems[0], operators[0])

1

4 (1, 24, 356) *

The main novelty here is itertools.groupby, which separates the individual columns into problem groups, by detecting columns that are all whitespaces.

1

print(solve_2506(D06.input_data, parse_250602))

1

13215665360076

zip(*list) and itertools.groupby are the new weapons in the arsenal!

07 splitting beams in the lab Tachyon manifolds

1. we are in a Tachyon manifold, which is simply a 2D grid field;
2. there is (only) one beam of light passing through the field;
3. the beam passes straight through if there is no hindrance, and splits to left and right if encountering a splitter;
4. part 1 needs to count how many splitters have been hit on;
5. part 2 needs to count how many individual paths the beam passe through.

Since we need to get the indices of the beams and the splitters, we can parse the data using list comprehension with enumeration. This keep the indices whose values meet a certain creterion. And we can discard the splitter rows that don’t actually have splitters.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def parse_2507(data: str) -> tuple[set[int], list[set[int]]]:
    """Parse manifold into start column and splitter rows."""
    lines = data.splitlines()
    start = {i for i, ch in enumerate(lines[0]) if ch == 'S'}
    splitter_rows = [
        {i for i, ch in enumerate(line) if ch == '^'}
        for line in lines[1:]
    ]
    splitter_rows = [s for s in splitter_rows if s]
    return start, splitter_rows

D07 = models.Puzzle(year=2025, day=7)
lines = D07.input_data.splitlines()
start, splitter_rows = parse_2507(D07.input_data)
print(len(lines), len(lines[0]))
print(len(splitter_rows), sum(line.count('^') for line in lines))

1
2

142 141
70 1650

For part 1, a splitter is activated only if:

1. there is a splitter in the first place;
2. a beam is present in the previous row.

So this check can be done by comparing the existence of beams in one row, with the existence of splitters in the next row, and this can be done elegantly with set operations. Concretely, A-B are kept as is, and B-A updated with shifts, then we take the union of the two to pass to the next step.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def step_beams(beams: set[int], splitters: set[int]) -> tuple[set[int], int]:
    """Advance beams through one splitter row and count activations."""
    hits = beams & splitters
    misses = beams - splitters
    spawned = {col + d for col in hits for d in (-1, 1)}
    return misses | spawned, len(hits)

def solve_250701(data: str) -> int:
    """Part 1: count activated splitters.

    O(sum(len(beams) + len(splitters))) across rows.
    """
    beams, splitter_rows = parse_2507(data)
    total = 0
    for splitters in splitter_rows:
        beams, activations = step_beams(beams, splitters)
        total += activations
    return total

print(solve_250701(D07.input_data))

1

1524

I haven’t used the set operations before, so this has been a useful exercise.

For part 2, we need to count the number of distinct paths (timelines) the beam took. My original solution was to store the complete path trajectories, but it turned out to be too memory intensive. Then it occurred to me that we only need to count the number of paths, not trace all of them. This is a big difference, since counting them only requires some summary statistics of the paths, not the paths themselves. In fact, at each step in the manifold, we can count the total spawned paths by counting how many end points there are, and how many distinct paths pass through each ending point. And this info can easily be stored in a dict.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def step_counts(paths: dict[int, int], splitters: set[int]) -> dict[int, int]:
    """Advance all timeline counts through one splitter row."""
    new_paths: dict[int, int] = {}
    for col, count in paths.items():
        if col in splitters:
            for ncol in (col - 1, col + 1):
                new_paths[ncol] = new_paths.get(ncol, 0) + count
        else:
            new_paths[col] = new_paths.get(col, 0) + count
    return new_paths

def solve_250702(data: str) -> int:
    """Part 2: count timelines after all splits.

    O(sum(len(paths) + len(splitters))) across rows.
    """
    beams, splitter_rows = parse_2507(data)
    paths = {col: 1 for col in beams}
    for splitters in splitter_rows:
        # print(paths)
        paths = step_counts(paths, splitters)
    return sum(paths.values())

print(solve_250702(D07.input_data))

1

32982105837605

I had originally had some trouble updating the paths dict, because with splitting beams we have to asign values to keys that doesn’t yet exist. But of course such a common scenario is already covered by an existing dict method dict.get(key, default), which returns the corresponding value is the key exists, and returns a default value otherwise.

Incidentally today’s puzzle has some terminologies that I don’t know, like Tachyon manifolds, and some connections that I’m not aware of, like quantum fields. Nevertheless this does not in anyway interferes with solving the puzzle. This is a common pattern in computer science, or more specifically algorithm design. A specific problem from a specific domain can be narrated in a specific domain language, but all those specificity can often be abstracted away when devising the algorithm and solving the problem. However this is not saying all the specificities do not matter: on the contrary, simply running a computer program to get an answer is useless, if we can’t apply it back to the specific problems.

08 connecting junction boxes in the playground

1. We are in a playground with junction boxes, each with a unique 3D coordinate.
2. We repeatedly connect the closest pairs of boxes (by straight-line distance), creating connected groups.
3. For part 1, we process the first 1000 closest pairs (even if some are already connected), then multiply the sizes of the three largest circuits.
4. For part 2, we keep processing closest pairs until all boxes are in one group; then multiply the x coordinates of the last pair that merges the final two circuits.

A subtle but important point that confused me in the beginning: the problem says “closest pairs”, not “successful merges.” In the example, after “ten shortest connections” only nine merges happen because one pair was already in the same circuit. So we must process the pairs in order, allowing no-ops.

We need to connect individual nodes into separate graphs. The key issues to solve include: 1, which nodes to connect; 2, how to connect; 3, what information to extract from the connected nodes. After figuring out which nodes to connect, which simply calculates the paired distances and rank them, the key problem is graph manipulation. The right abstraction here is Union-Find (disjoint set union). Union, on surface, is connecting two nodes, but in reality it’s connecting the roots of the two nodes, and for this reason we need to know which circuit each box belongs to, and the sizes of those circuits; the actual edges are irrelevant.

1
2
3
4
5
6
7

def parse_2508(data: str) -> list[tuple[int, int, int]]:
    """Parse coordinates from 'x,y,z' lines."""
    return [tuple(map(int, line.split(','))) for line in data.splitlines()]

D08 = models.Puzzle(year=2025, day=8)
points = parse_2508(D08.input_data)
print(len(points), points[0])

1

1000 (54996, 20819, 75067)

Getting the sorted distance together with the corresponding indices is easy. The distances are used for sorting, while the indices are used later to guide which points to connect, in which order.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from itertools import combinations

def sorted_pairs_2508(points: list[tuple[int, int, int]]) -> list[tuple[int, int, int]]:
    """Return (dist2, i, j) for all pairs, sorted by dist2.

    dist2 is squared Euclidean distance (ordering is unchanged).
    """
    pairs = []
    for i, j in combinations(range(len(points)), 2):
        x1, y1, z1 = points[i]
        x2, y2, z2 = points[j]
        d2 = (x1 - x2) ** 2 + (y1 - y2) ** 2 + (z1 - z2) ** 2
        pairs.append((d2, i, j))
    return sorted(pairs)

The key is the union-find algorithm. Each node is initiated as an independent group, of size 1, with itself as its parent. find traces a graph to its root, it follows parents and compresses the path so future lookups are faster. union merges two roots, updates the size of the new root, and decrements components. We use group_sizes to read off the sizes of all current circuits.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class UnionFind:
    """Disjoint set union with path compression.

    We keep it simple: always attach one root under the other.
    """
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        """Merge sets containing x and y. Return True if a merge happened."""
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        self.parent[ry] = rx # simply attanch the second group to the first
        self.size[rx] += self.size[ry]
        self.components -= 1
        return True

    def group_sizes(self) -> list[int]:
        return [self.size[i] for i in range(len(self.parent)) if self.parent[i] == i]

uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
print(sorted(uf.group_sizes(), reverse=True), uf.components)  # [2, 2, 1], 3

uf.union(1, 3)  # merges the {0,1} and {2,3} circuits
print(sorted(uf.group_sizes(), reverse=True), uf.components)  # [4, 1], 2

1
2

[2, 2, 1] 3
[4, 1] 2

For part 1, process the first 1000 closest pairs, then take the top three circuit sizes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

from math import prod

def solve_250801(data: str) -> int:
    """Part 1: product of sizes of the three largest circuits.

    O(n^2 log n) time for sorting all pairs, O(n^2) space.
    """
    points = parse_2508(data)
    pairs = sorted_pairs_2508(points)
    uf = UnionFind(len(points))

    for _, i, j in pairs[:1000]:
        uf.union(i, j)

    sizes = sorted(uf.group_sizes(), reverse=True)
    return prod(sizes[:3])

print(solve_250801(D08.input_data))

1

112230

Part 2 only changes the stopping condition: keep processing closest pairs until there’s a single circuit, and return the product of the x-coordinates of the last successful merge.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def solve_250802(data: str) -> int:
    """Part 2: product of x-coordinates from the last merging pair.

    O(n^2 log n) time for sorting all pairs, O(n^2) space.
    """
    points = parse_2508(data)
    pairs = sorted_pairs_2508(points)
    uf = UnionFind(len(points))

    for _, i, j in pairs:
        if uf.union(i, j) and uf.components == 1:
            return points[i][0] * points[j][0]

print(solve_250802(D08.input_data))

1

2573952864

It is actually quite difficult to get the right level of abstraction. I wandered about for quite a while till it’s clear that the union-find algorithm should only operate on the indices; and all of the indice operations, with memory, should be included. However, everything else, including the distances and the ranked pair of indices, should NOT be part of this abstraction. This is evident from the fact that the UnionFind class is initiated with only the #nodes and nothing else. This might feel obvious in retrospect, but leaky abstractions caused me a lot of headache before I came up to the right abstraction.

Once Union-Find is in place, part 2 just change the stopping rule.

09 rectangular tile patterns in the movie theatre

1. We are now in the movie theatre, and we are to redecorate the floor, which is covered in tiles of various colors.
2. There are red tiles; between consecutive red tiles there are green tiles; and the interior enclosed by the red/green loop is also green.
3. For part 1, we choose two red tiles as opposite corners of a rectangle and want the maximum area.
4. For part 2, we still want the maximum area, but with the extra requirement that the rectangle must lie entirely on red or green tiles.

Parsing the data is trivial.

1
2
3
4
5
6
7

def parse_2509(data: str) -> list[tuple[int, int]]:
    """Parse red tile coordinates as (x, y) pairs."""
    return [tuple(map(int, line.split(','))) for line in data.splitlines()]

D09 = models.Puzzle(year=2025, day=9)
red = parse_2509(D09.input_data)
print(len(red), red[:3])

1

496 [(98026, 50027), (98026, 51253), (98365, 51253)]

Part 1 is simple. With less than 500 points, try every pair of red tiles as opposite corners is computationally quite feasible.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from itertools import combinations

def solve_250901(data: str) -> int:
    """Part 1: maximum rectangle area from two red corners.

    O(n^2) time, O(1) extra space.
    """
    red = parse_2509(data)
    return max(
        (abs(x2 - x1) + 1) * (abs(y2 - y1) + 1)
        for (x1, y1), (x2, y2) in combinations(red, 2)
    )

print(solve_250901(D09.input_data))

1

4750297200

The only thing worth taking note of is how the area is calculated. The red tiles are squares with areas themselves, not just points (which have no area), and thus the +1 in the formula.

Part 2 is the real problem of the day. We can still iterate over all pairs of opposite corners, but then we need to check all tiles of the resulting rectangle is in the red-green encircled area. This entails several problems:

1. what this enclosed area is actually like. This is actually a problem for part 1, but with part 1 being so easy we didn’t even bother to deal with it.
2. how to check if a point is in the enclosed area. This is the core problem.
3. which points we have to check for such enclosion.

The enclosed area turns out to be a rectilinear polygon, but I only figured it out after quite some data explorations, including the term rectilinear itself. And to check for enclosion there is a well established algorithm called ray casting, but I know nothing about it. Besides, we are now in a (100K, 100K) area, each rectangle thus has a vast area, so there are a HUGE amount of points to check (if we avoid being clever), the computation has increased immensely.

I tried to implement the ray casting algorithm, but got buried in the implementation details and edge cases, and I got stuck on the problem for a whole week. Finally I reworked the puzzle after having finished day 10 and 11, and simply used an existing package, shapely, which has established and well polished methods for all 3 issues. So in the end I solved the problem by not solving it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

from shapely.geometry import Polygon
from shapely.prepared import prep

def solve_250902(data: str) -> int:
    """Part 2: maximum rectangle area fully covered by red/green tiles.

    Uses shapely for containment checks (non-stdlib).
    O(n^2) rectangle checks; containment is fast with a prepared polygon.
    """
    red = parse_2509(data)
    poly = Polygon(red)
    prepared = prep(poly)

    best = 0
    for (x1, y1), (x2, y2) in combinations(red, 2):
        xmin, xmax = (x1, x2) if x1 <= x2 else (x2, x1)
        ymin, ymax = (y1, y2) if y1 <= y2 else (y2, y1)
        rect = Polygon([(xmin, ymin), (xmin, ymax), (xmax, ymax), (xmax, ymin)])
        if prepared.covers(rect):
            area = (xmax - xmin + 1) * (ymax - ymin + 1)
            if area > best:
                best = area
    return best

print(solve_250902(D09.input_data))

1

1578115935

I still need to come back and figure out how to implement the algorithm properly. I tried to look into the shapely implementations, but they are buried in optimized code God knows where. This remains the biggest challange of AOC 2025 for me, and the only case that I considered a failure.

There is one solution, which I stumbled upon in the forums, that is a data-compression first approach. This starts by noticing that while the area is large (100K times 100K), we only have less than 500 points, which means that there must by many in-the-middle points that we don’t really have to check. The idea is to do a coordinate compression first, finding out which points in the 100K field actually matters (are the edges and corners), solve the problem on this compressed grid first, and then project back to the original grid to find the areas. The reduced grid being small enough, that we might be able to just brute-force through it. While I still don’t know how to solve it exactly, this is a brilliant approach to simplify the problem, and I intend to try it later.

10 combining machine switches in the factory

1. We are in the factory, which has a big amount of machines and yet none of them are working.
2. Each machine has N indicator lights, N joltage levels, and M switches;
3. The switches can manipulate both the lights and the joltages;
4. Part 1: find the minimum number of button presses to reach the target on/off pattern; multiple presses of the same buton cancels out.
5. Part 2: ignore the lights and use the same switches to increment counters to target joltage values; now presses are nonnegative integers.

For this one, I’m quite proud of myself, for being able to carefully comb through the word soup and parse it to clear matrix multiplication operations and optimization problems. Both parts use the same data format, just different variables, so when refactoring I combined them together with a boolean switch. We have till now mostly parsed data with splitlines or split, but for more complex data patterns we need regular expressions.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import re
import numpy as np

def parse_2510(data: str, use_joltage: bool = False) -> list[tuple[np.ndarray, np.ndarray]]:
    """Return list of (y, XT) where y is target, XT is N x M toggle matrix."""
    parsed = []
    for line in data.splitlines():
        if use_joltage:
            target = re.search(r'\{([0-9,]+)\}', line).group(1)
            target = [int(x) for x in target.split(',')]
        else:
            diagram = re.search(r'\[([.#]+)\]', line).group(1)
            target = [1 if c == '#' else 0 for c in diagram]

        switches = re.findall(r'\(([0-9,]+)\)', line)
        indices_list = [[int(s) for s in sw.split(',')] for sw in switches]

        N = len(target)
        M = len(indices_list)
        X = np.zeros((M, N), dtype=int)
        for i, inds in enumerate(indices_list):
            X[i, inds] = 1

        y = np.array(target, dtype=int).reshape(-1, 1)
        parsed.append((y, X.T))
    return parsed

D10 = models.Puzzle(year=2025, day=10)
ex = D10.examples[0].input_data
data = D10.input_data

For part 1 we resorted to brute force exhaustive search, but with early stopping. This is feasible, firstly because the number of switches for each machine is limited. But more importantly because pressing the same switches twice cancels out, we should either press a button, or don’t; the search space for each switch is thus just {0, 1}, so we have a closed exploration space.

Since we aim to find the minimum number of presses, we search by the number of presses, starting from 1, and early stop once a matching combination is found.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

from itertools import combinations
from math import comb

def construct_ws(M: int, m: int) -> np.ndarray:
    """Create [M, C(M,m)] matrix of switch vectors with exactly m presses."""
    K = comb(M, m)
    ws = np.zeros((M, K), dtype=int)
    for i, combo in enumerate(combinations(range(M), m)):
        ws[list(combo), i] = 1
    return ws

def solve_251001(data: str) -> int:
    """Part 1: minimum presses to match lights (mod 2).

    Uses NumPy for matrix multiplication (non-stdlib).
    """
    parsed = parse_2510(data, use_joltage=False)
    total = 0
    for y, XT in parsed:
        _, M = XT.shape
        for m in range(0, M + 1):
            ws = construct_ws(M, m)
            ys = (XT @ ws) % 2
            if np.any(np.all(ys == y, axis=0)):
                total += m
                break
    return total

print(solve_251001(data))

1

542

The same method won’t work on part 2. Now the targets are positive integers, and each press increases the counter, so the search space is now infinite, which renders exhaustive search pointless. However by formulating the problem as minimizing sum(w) subject to XT @ w = y and w >= 0, it becomes an standard integer linear programming problem, and I simply used SciPy’s linprog with integrality=1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from scipy.optimize import linprog

def solve_251002(data: str) -> int:
    """Part 2: minimum presses to match joltage counters (ILP).

    Uses SciPy linprog with integrality=1.
    """
    parsed = parse_2510(data, use_joltage=True)
    total = 0
    for y, XT in parsed:
        M = XT.shape[1]
        res = linprog(c=[1] * M, A_eq=XT, b_eq=y.ravel(), integrality=1)
        total += int(round(res.fun))
    return total

print(solve_251002(data))

1

20871

I still don’t quite understand why it works, but with some trial and error on some example problems I’ve managed to make it work. I’m always interested in how linear programming works; I intend to implement the algorithm myself later.

11 counting server paths for the reactor

1. We are given a directed graph of server devices, one line per device;
2. each line is node: child1 child2 ... meaning data flows from node to children;
3. part 1: count all distinct paths from you to out;
4. part 2: count all distinct paths from svr to out that pass through both fft and dac.

We simply parse the data into a dict of parent-children pairs, with the children being a set.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def parse_2511(data: str) -> dict[str, set[str]]:
    """Parse graph as parent -> children sets."""
    graph: dict[str, set[str]] = {}
    for line in data.splitlines():
        parent, children = line.split(':')
        graph[parent] = set(children.split())
    return graph

D11 = models.Puzzle(year=2025, day=11)
graph = parse_2511(D11.input_data)
print(len(graph), sum(len(v) for v in graph.values()))

1

643 1738

The core of the problem is counting paths in a directed acyclic graph. This is a classic dynamic programming problem, where the problem can be decomposed into multiple subproblems, and each subproblem of the same format as the overall problem. Besides, in each of the subproblem and sub-subproblems, the same computation has to be carried out repeatedly.

Because of this, we need to carefully manage two things, formulating the solution in a way that the same problem-solving logic can be reused, and memoization.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

from functools import lru_cache

def count_paths(graph: dict[str, set[str]], start: str, end: str) -> int:
    """Count paths from start to end in a DAG."""
    @lru_cache(maxsize=None)
    def dfs(node: str) -> int:
        if node == end:
            return 1
        return sum(dfs(child) for child in graph.get(node, ()))
    return dfs(start)

def solve_251101(data: str) -> int:
    """Part 1: count paths from you to out.

    DFS + memoization on node.
    O(V+E) time, O(V) space.
    """
    graph = parse_2511(data)
    return count_paths(graph, start='you', end='out')

print(solve_251101(D11.input_data))

1

574

I originally solved part 1 without considering any edge cases, since there was none; and I didn’t even bother with memoization, since the computation is manageable without it. And then for part 2 I had to patch it up again and again to fix all the edge cases.

Recursive functions are hard to understand and reason with. It’s better to print out the result of each iteration to understand how it’s stacked up.

Part 2 adds some constraint: the path must pass through two specific nodes, fft and dac. Since one must be before the other, I used a rather silly approach to determine which is before which, but it worked. My original implementation for part 1 is quite limited, I used it to count #(fft -> dac), if fft is before dac it will not finish, since I didn’t use memoization and it’s very slow; and if dac is before fft it will throw an error, since I didn’t take such reverse direction cases into consideration. So using this weird method I figured out their order in the directed graph, and fft is upstream of dac.

That means every valid path factors into three independent segments: and we can count the unique paths of each segment independently, then multiply them together, i.e. #(svr -> fft) * #(fft -> dac) * #(dac -> out).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def solve_251102(data: str) -> int:
    """Part 2: paths from svr to out passing through fft and dac.

    Factor into three independent path counts.
    O(V+E) per segment, O(V) space.
    """
    graph = parse_2511(data)
    count0 = count_paths(graph, start='svr', end='fft')
    count1 = count_paths(graph, start='fft', end='dac')
    count2 = count_paths(graph, start='dac', end='out')
    return count0 * count1 * count2

print(solve_251102(D11.input_data))

1

306594217920240

12 fitting present shapes in the Christmas tree farm

1. We are in the Christmas tree farm,
2. we have a number of Christmas presents, in one of the different shapes, all fitted in a 3x3 grid;
3. we also have a list of regions, each a rectangle of a given size, to accomodate the gifts;
4. gifts can be rotated or flipped; to be fitted into the given regions, but without overlap;
5. day 12 has only one problem, to count how many of the given regions can fit all required shapes.

Parse the data:

• shapes into a dict of index:shape pairs,
• regions into a nesting list of region width, length, and a tuple of required shape counts.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def parse_2512(data: str) -> tuple[dict[int, list[str]], list[tuple[int, int, tuple[int, ...]]]]:
    """Parse shapes and region specs."""
    shapes: dict[int, list[str]] = {}
    regions: list[tuple[int, int, tuple[int, ...]]] = []
    current = None
    rows: list[str] = []

    for line in data.splitlines():
        if not line:
            continue
        if line.endswith(':') and line[:-1].isdigit(): # starting new shapes
            if current is not None:
                shapes[current] = rows
            current = int(line[:-1])
            rows = []
        elif 'x' in line and ':' in line: # starting new regions
            area, nums = line.split(':')
            w, h = map(int, area.split('x'))
            counts = tuple(map(int, nums.split()))
            regions.append((w, h, counts))
        else: # accumulating lines for current shape
            rows.append(line)

    if current is not None:
        shapes[current] = rows
    return shapes, regions

D12 = models.Puzzle(year=2025, day=12)
shapes, regions = parse_2512(D12.input_data)
print(len(shapes), len(regions))

1

6 1000

This is an interesting parsing problem, because the input data have two distinct parts which require different parsing logic. Also, the data parsing is line by line, but each shape takes up multiple lines, so we also need a way to accumulate lines for each shape.

As to the problem itself, this is a hard problem with a simple solution. We want to fit a number of irregular shaped presents into a regular rectangular region, there must be a minimum area requirement, where all the shapes fit perfectly together; and a maximum area requirement, where none of the shapes can fit together, and we thus have to spare a 3x3 grid for each of them. We can first check whether each region’s area is in this (minimum, maximum) range, and filter out the regions that ain’t. For regions with area less than the minimum no fitting is possible; for regions with areas bigger than the maximum we can simply put the gifts consecutively, each in a 3x3 grid, so the solution is trivial.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

shape_ids = sorted(shapes)
filled = [sum(c == '#' for c in ''.join(shapes[i])) for i in shape_ids]
box = [len(shapes[i]) * len(shapes[i][0]) for i in shape_ids]  # 3x3 here
classifications = [0] * len(regions)

for i, (w, h, counts) in enumerate(regions):
    area = w * h
    compact = sum(n * f for n, f in zip(counts, filled))
    loose = sum(n * b for n, b in zip(counts, box))
    if compact > area: # no solution possible
        classifications[i] = 1
    if loose <= area: # no work necessay
        classifications[i] = 2

for i in [0, 1, 2]:
    print(i, sum(c==i for c in classifications))

1
2
3

0 0
1 519
2 481

As it turns out, of the 1000 problem regions, 519 of them are not possible, 481 of them are trivial, and none of them requires actual work. So the feasible ones are identical to the trivial ones.

1
2
3
4

def solve_2512(data: str) -> int:
    return sum(c==2 for c in classifications)

print(solve_2512(D12.input_data))

1

481