2025 Advent of Code Summary

Day 12

1. Enumerate all unique rotations/reflections of each shape and represent each possible placement as a bitmask of occupied cells. Search for a non-overlapping selection of placements matching the required counts.
2. Happy holiday :)

Day 11

1. Counts graph by running memoized DFS on the directed graph where each node’s value is the sum of its successors’ values, with out as the base case of 1.
2. Same, but arguments the state with a bitmask tracking whether dac and fft have been visited so that only paths whose mask has both bit set contribute at out.

Day 10

1. BFS on bitmask states where the start is all-off, each button is an XOR toggle mask, and the minimal number of process is the shortest path distance from start to target, summed over all machines.
2. Choose nonnegative integers \(x_k\) (button press counts) so that for each counter \(j\), \(\sum_{k: j\in \text{button } k} x_k = t_j\), then minimize \(\sum_k x_k\) rather than exploring raw counter states. A BFS over counter configurations blows up because the state space grows something like \(\prod_j(t_j+1)\) (I think, unproven), so it’s far more scalable to hand this ILP to a solver like z3 and let it find the minimal solution.

Day 9

1. Brute-force.
2. Okay, now we are talking.. Draw the red-loop polygon and flood-fill from the outside to mark disallowed tiles, then check every pair of red corners and keep only those rectangles whose entire area (via a prefix-sum check) lies within the remaining allowed region. My approach and implementation with C++ took around six minute to complete.

Day 8

1. Kruskal-style unions on all edges order by distance, but stop after the 1000 shortest edges.
2. Keep going past 1000 edges until everything is connected.

Day 7

1. Brute-force. For some reason, I thought it asks to count how many | at the end…
2. DP. Define f(r, c) that returns the number of timelines from cell (r, c) downward (splitting on ^), and memorize it so each cell’s count is computed once and reused.

fn dp(r, c):
  if r == last_row:
    return 1
  if grid[r+1][c] == '^':   // splitter below
    return dp(r + 1, c - 1) + dp(r + 1, c + 1)
  else:                     // straight down
    return dp(r + 1, c)

Day 6

1. Split by space, then simulation.
2. Split it into vertical problem block at all-space columns, then for each block read digits top-to-bottom in each column (right to left) to form numbers.

g = [list(r.ljust(w)) for r in rows]
sep = [all(g[r][c] == ' ' for r in range(h)) for c in range(w)]

Day 5

1. Brute-force.
2. Merge intervals.

Day 4

1. Simulation.
2. Simulation, but multiple rounds.

Day 3

1. Brute-force.
2. Treat each row as: “remove some digits so the remaining 12 are as big as possible from left to right”. Hint: use monotonic stack.

Day 2

1. Brute-force. For each range (l, r), check all integers from 1 up to half the number of digits in r, inclusive.
2. Similar idea, but remember to handle duplicates. For example, 1111 can be represented as 1 repeated four times or 11 repeated two times.

Day 1

1. Modular arithmetic.
2. Brute-force.

Last edited: Dec 10, 2025