Day 08

3D Point Clustering

Orignal Post

Given 3D points, merge them into clusters by connecting closest pairs first (Kruskal-style). Part 1: product of top 3 cluster sizes after N merges. Part 2: last edge needed to unify all points.

Algorithm

• Parse input into XYZ points

• Generate all pairs sorted by squared distance (quadrance)

• State: clusters (set of sets), sorted pairs queue, merge counter

• Merge logic: pop closest pair, if in different clusters → union them

• Part 1: merge N times, stream cluster sizes descending

• Part 2: merge until single cluster, return last merged pair

Key Abstractions

• qd — squared Euclidean distance (avoids sqrt)

• Store effect — mutable state for cluster bookkeeping

• unfold! — iterate until abort, collecting results

Key Insight

This is Kruskal's MST algorithm in disguise. Sorting edges by weight (distance) and merging components greedily gives the minimum spanning tree. Part 1 asks for intermediate cluster sizes; Part 2 asks for the final edge that completes the tree.

Day 09

Rectilinear Polygon Area

Original Post

Given a list of corner points forming a rectilinear polygon (all edges axis-aligned) find the largest rectangle that has two corners from the input and is entirely contained within the polygon.

Algorithm

• Parse corner coordinates

• Part 1 - Just enumerate all pairs with no containment check needed

And the area being

Part 2 - The Scaling Problem

Attempt 1 - Naive BFS Flood Fill (Too Slow)

The idea is to flood fill from outside to find exterior cells. Everything NOT reached is interior.

Problems with this approach

• rest ++ neighbors is O(n) per step leading to O(n^2) total

• For coords in range 0 to 100000 thats 10 billion cells to visit

Attempt 2 - Optimized BFS (Still Too Slow)

Fixed the O(n) append but the real problem is the coordinate range itself.

Attempt 3 - Coordinate Compression (Works!)

Key insight - Between consecutive unique coordinates polygon behavior is uniform. E.g. for the sample input we can compress coords (2 7 9 11) to (0 1 2 3) and work in a tiny 4x4 grid instead of a 10x10 grid. For real inputs this compresses 100Kx100K to about 100x100!

Example:

2D Prefix Sum for O(1) Rectangle Queries

Once we have an inside/outside grid we build a prefix sum. This lets us query any rectangle in O(1) via inclusion-exclusion.

Example:

Full Part 2 Solution

Complexity Comparison

• Naive BFS - O(W x H) - 10 billion ops for 100Kx100K grid

• Compressed - O(n^2) - about 10000 ops for 100 corners

• Speedup about 1000000x

Key Functions

• compressPoints - Extract unique coords and build index maps

• compressPoint - Map original to compressed index

• findEdgesCompressed - Find edges in compressed space

• floodFillOutsideCompressed - BFS on tiny compressed grid

• buildPrefixSum - 2D prefix sum for O(1) queries

• queryRect - Count inside cells in rectangle

• isValidPair - Check if rectangle fits entirely inside

Day 10

Command XOR & Linear Optimization

Original Post

Given commands that toggle bit positions and target bit patterns:

• Part1: Find minimum subset of commands whose XOR equals target (Boolean algebra)

• Part 2: Find minimum sum of command usages satisfying linear constraints (Integer LP)

Input Format

Each line: [target] (cmd1) (cmd2) ... {costs}

• [.##.] — target bit pattern (`.` = 0, # = 1)

• (3), (1,3) — commands that toggle bit positions

• {3,5,4,7} — costs/targets for Part 2

Part 1: Meet-in-the-Middle XOR Search

The Problem

Find smallest subset of commands whose XOR produces the target. With n commands, naive enumeration is O(2^n).

Key Insight: Halve the Search Space

Split commands into left/right halves. For left half of size n/2:

• Enumerate all 2^(n/2) subsets → store XOR results in hash map

• For each right-half subset, compute needed = target XOR rightXor

• Look up needed in left map — if found, we have a solution!

Bit-Packing Commands

Commands are packed into Nat as bit vectors for fast XOR:

Building the Left Table

XOR-ing a Subset

---

Part 2: Linear Programming via Gaussian Elimination

The Problem

Now commands can be used multiple times. Find non-negative integer solution minimizing total usage count.

Formulation as Linear System

Each target position gives an equation. Commands are variables indicating "how many times used".

Gaussian Elimination Pipeline

Building the Coefficient Matrix

buildMatrix commands target builds a matrix from the commands and target. The matrix is a list of rows, where each row is a list of coefficients for the variables in the commands. The target is a list of values for the target variables.

Gaussian Elimination

Guassian elimination to row echelon form. Returns (reduced matrix, pivot columns)

Key Operations

Finding pivot row:

findPivotRow col startRow matrix finds the first row in matrix that has a non-zero value in column col, starting from row startRow.

Row elimination:

eliminateRowsBelowPivot pRow pCol matrix eliminates the rows below the pivot row in matrix by subtracting the pivot row from each of the rows below the pivot row.

Scaling to avoid fractions:

subtract destRow srcRow (m1, m2) subtracts srcRow from destRow by multiplying srcRow by m2 and destRow by m1, then subtracting the result.

To avoid fractions, scale: newRow = destRow * pivotValue - srcRow * elementValue

Free Variables & Optimization

freeVars pivots numVars find which columns are free i.e. not pivots.

When free variables exist, we enumerate assignments:

generateAllAssignments numFree max generates all possible assignments of values between 0 and max to numFree variables.

Back Substitution

Full Solver

Day 11

Paths With Must-Visit Nodes

Original Post

Input is a directed graph. We count paths from a start node to out, optionally requiring that a given set of “via” nodes get touched at least once.

Input Format

Each line: src: dst1 dst2 ...

Problem

Count directed paths from start to target such that every node in via is visited ≥ 1 times.

• Part 1: start = "you", target = "out", via = []

• Part 2: start = "svr", target = "out", via = ["dac", "fft"]

Algorithm: DP over (node, remainingVia)

Track remaining required nodes as need : Set Text.

• On each step from node v, set need' = Set.delete v need.

• If v == target, accept iff need is empty.

• Memoize results by key (v, need).

Notes

This assumes the input graph is “well-behaved” for this recursion (e.g. no cycles that can repeat forever without shrinking need).

Entrypoints

Day 12

Jigsaw Polyomino Feasibility

Original Post

Given ASCII art block templates & grid specs, determine feasible arrangements.

Part 1: Count grids where all blocks have ≥1 valid placement

Input Format

Blocks defined as ASCII art (`#` = cell, . = empty):

Grid specs: {rows}x{cols}: c₀ c₁ ... c₅ where cᵢ = count of block i to place.

Problem: Polyomino Packing Feasibility

Each block is a polyomino (7-cell shape). Apply $D_4$ dihedral group transformations:

• 4 rotations: 0°, 90°, 180°, 270° -4 flips + rotations: flipH, flipH+rot90, flipH+rot180, flipH+rot270

→ Up to 8 distinct orientations (fewer if symmetries exist)

Data Pipeline

Block Representation

Orientation Generation via $D_4$

Transforms are function compositions over Cell :

Placement Templates

For each orientation, enumerate valid anchor positions:

Part 1: Quick Feasibility Check

Strategy: Empty Placement Detection

Instead of solving the full constraint satisfaction problem, check:

> Does every block type have ≥1 valid placement in the grid?

If any block has zero valid placements → grid is infeasible

Early Rejection: Area Constraint

Memoization: Template Caching

Templates depend only on (rows, cols) — cache across grids:

Part 1 Solution

It should not work...

This is a polyomino packing problem — NP-complete in general. I wanted to solve it using - Dancing Links (Algorithm X)

• Columns = piece constraints + cell constraints

• Rows = valid placements

• Find all subsets of placements that:

  • Find all subsets of placements that:

  • Use each piece exactly once (exact cover on piece columns)

    • Use each piece exactly once (exact cover on piece columns)

    • Cover each cell ≤1 time (at most once on cell columns)

But, all of my attempts took forever to prepare the basic building blocks like the matrix with placements. So I just thought of doing the empty placement check instead.

Why Empty Placement Check Works

If ∃ block with 0 valid placements → no solution exists (pigeonhole).

Converse not true: all blocks having ≥1 placement doesn't guarantee a solution (blocks may conflict). But for this puzzle's input, the check sufficed.

No Part 2

Day 12 is the final puzzle of AoC 2025 — no Part 2.

Happy holidays 🎄