Day 08-12 #adventofcode

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

day08.parse : Text -> [XYZ]
day08.parse =
  lines >> List.map
    (Text.split ?, >> List.filterMap Text.toInt >> (cases
      [x, y, z] -> Some (XYZ x y z)
      _         -> None) >> Optional.getOrBug "invalid input")

• Generate all pairs sorted by squared distance (quadrance)

sortedPairs : [XYZ] -> [(XYZ, XYZ)]
sortedPairs xs =
  use Boolean not
  use List isEmpty
  zs = Each.toList do
    ys = each (List.tails xs)
    guard (isEmpty ys |> not)
    match ys with
      []      -> bug "impossible"
      p +: ps ->
        guard (isEmpty ps |> not)
        q = each ps
        (p, q)
  zs |> sortBy (uncurry qd)

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

initialState : [XYZ] -> (Set (Set XYZ), [(XYZ, XYZ)], Nat)
initialState xs =
  (Set.fromList (List.map Set.singleton xs), sortedPairs xs, 0)

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

mergeAttempt : '{Store (Set (Set b), [(b, b)], Nat)} Optional (b, b)
mergeAttempt =
  do
    match Store.get with
      (clusts, (p, q) +: pts, n) ->
        match clusts |> Set.toList |> List.find (Set.contains p) with
          Some pclust ->
            if Set.contains q pclust then
              Store.put (clusts, pts, n)
              Some (p, q)
            else
              match clusts
                |> Set.toList
                |> List.find (Set.contains q) with
                Some qclust ->
                  clusts' =
                    clusts
                      |> Set.deletes [qclust, pclust]
                      |> Set.insert (Set.union pclust qclust)
                  Store.put (clusts', pts, n)
                  Some (p, q)
                None -> None
          None -> None
      _ -> None

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

day08.solve_ : Nat -> [XYZ] -> '{Stream Nat} ()
day08.solve_ n xs =
  use Nat + == >=
  use Optional getOrBug
  use Store get
  ys =
    List.last
      <| (unfold! (initialState xs) do
        i = get |> at3
        if i == n then abort
        else
          Store.modify cases (c, p, n) -> (c, p, n + 1)
          mergeAttempt()
            |> Optional.map (_ -> get |> at1)
            |> getOrBug "impossible")
  ys
    |> getOrBug "impossible"
    |> Set.toList
    |> List.map Set.size
    |> sortWith (>=)
    |> Stream.fromList

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

solve__ : [XYZ] -> (XYZ, XYZ)
solve__ xs =
  use Nat ==
  use Optional getOrBug
  go =
    do
      (st, _, _) = Store.get
      if Set.size st == 1 then abort
      else mergeAttempt() |> getOrBug "impossible"
  unfold! (initialState xs) go |> List.last |> getOrBug "impossible"

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.

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

day09.parse : Text -> [XY]
day09.parse =
  lines >> List.map
    (Text.split ?, >> List.filterMap Text.toInt >> (cases
      [x, y] -> Some (XY x y)
      _      -> None) >> Optional.getOrBug "invalid input")

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

allRects : [XY] -> [Nat]
allRects xs =
  xs |> List.tails |> (List.flatMap cases
    p +: ps -> ps |> List.map (q -> area p q)
    _       -> [])

And the area being

area : XY -> XY -> Nat
area a b =
  use Int diff
  use Nat * +
  (XY x1 y1) = a
  (XY x2 y2) = b
  (diff x1 x2 + 1) * (diff y1 y2 + 1)

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.

 Before flood fill:              After flood fill:
 ┌─────────────────┐             ┌─────────────────┐
 │ · · · · · · · · │             │ █ █ █ █ █ █ █ █ │
 │ · · * * * * · · │             │ █ █ * * * * █ █ │
 │ · · *     * · · │      →      │ █ █ *     * █ █ │
 │ · · * * * * · · │             │ █ █ * * * * █ █ │
 │ · · · · · · · · │             │ █ █ █ █ █ █ █ █ │
 └─────────────────┘             └─────────────────┘

 * = border    · = unknown    █ = outside (flooded)
               (empty) = inside (not flooded)

bfs : [XY] -> Set XY -> Set XY -> (Int, Int, Int, Int) -> Set XY
bfs queue visited border = cases
  (minX, maxX, minY, maxY) ->
    use Int + - < >
    use List ++
    use Set contains
    outofBounds = cases
      XY x y -> x < minX || x > maxX || y < minY || y > maxY
    match queue with
      [] -> visited
      XY x y +: rest ->
        if outofBounds (XY x y) || contains (XY x y) border
          || contains (XY x y) visited then
          bfs rest visited border (minX, maxX, minY, maxY)
        else
          visited' = Set.insert (XY x y) visited
          neighbors =
            [ XY (x + +1) y
            , XY (x - +1) y
            , XY x (y + +1)
            , XY x (y - +1)
            ]
          bfs
            (rest ++ neighbors)
            visited'
            border
            (minX, maxX, minY, maxY)

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)

bfsOptimized :
  [XY] -> Set XY -> Set XY -> (Int, Int, Int, Int) -> Set XY
bfsOptimized queue visited border = cases
  (minX, maxX, minY, maxY) ->
    use Int + - < >
    use List ++
    use Set contains
    outOfBounds = cases
      XY x y -> x < minX || x > maxX || y < minY || y > maxY
    isBlocked b v pt =
      outOfBounds pt || contains pt b || contains pt v
    go q v =
      match q with
        [] -> v
        XY x y +: rest ->
          if contains (XY x y) v then go rest v
          else
            v' = Set.insert (XY x y) v
            neighbors =
              [ XY (x + +1) y
              , XY (x - +1) y
              , XY x (y + +1)
              , XY x (y - +1)
              ]
            newNeighbors =
              neighbors
                |> List.filter (isBlocked border v' >> Boolean.not)
            go (newNeighbors ++ rest) v'
    go queue visited

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:

 Original coordinates:           Compressed coordinates:
 x = [2, 7, 9, 11]              x' = [0, 1, 2, 3]
 y = [1, 3, 5, 7]               y' = [0, 1, 2, 3]

 Original grid: ~100 cells       Compressed grid: 4×4 = 16 cells!

compressPoints : [XY] -> ([Int], [Int], Map Int Int, Map Int Int)
compressPoints pts =
  use List map
  xs = pts |> map x |> uniqueSorted
  ys = pts |> map y |> uniqueSorted
  xMap = buildIndexMap xs
  yMap = buildIndexMap ys
  (xs, ys, xMap, yMap)

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:

 Inside grid (1=inside, 0=outside):     Prefix sum:

     0   1   2   3                          0   1   2   3
   ┌───┬───┬───┬───┐                      ┌───┬───┬───┬───┐
 3 │ 0 │ 0 │ 1 │ 1 │                    3 │ 0 │ 1 │ 4 │ 7 │
   ├───┼───┼───┼───┤                      ├───┼───┼───┼───┤
 2 │ 1 │ 1 │ 1 │ 1 │                    2 │ 0 │ 1 │ 3 │ 5 │
   ├───┼───┼───┼───┤        →             ├───┼───┼───┼───┤
 1 │ 1 │ 1 │ 0 │ 1 │                    1 │ 0 │ 1 │ 2 │ 3 │
   ├───┼───┼───┼───┤                      ├───┼───┼───┼───┤
 0 │ 0 │ 1 │ 1 │ 1 │                    0 │ 0 │ 1 │ 2 │ 3 │
   └───┴───┴───┴───┘                      └───┴───┴───┴───┘

 prefix[i][j] = count of 1s in rectangle (0,0) to (i,j)

queryRect : Grid Int -> XY -> XY -> Int
queryRect prefix c1 c2 =
  use Int + -
  use Optional getOrElse
  (XY i1 j1) = c1
  (XY i2 j2) = c2
  (prefix |> get (i2 + +1) (j2 + +1) |> getOrElse +0)
    - (prefix |> get i1 (j2 + +1) |> getOrElse +0)
    - (prefix |> get (i2 + +1) j1 |> getOrElse +0)
    + (prefix |> get i1 j1 |> getOrElse +0)

Full Part 2 Solution

day09.part2 : '{IO, Exception} ()
day09.part2 =
  do
    solve input =
      use List size
      parsedInput = day09.parse input
      (xs, ys, xMap, yMap) = parsedInput |> compressPoints
      n = size xs
      m = size ys
      insideGrid = buildInsideGrid parsedInput xMap yMap n m
      match buildPrefixSum insideGrid n m with
        prefix@(Grid m) ->
          allPairs = uniquePairs parsedInput
          validPairs =
            allPairs
              |> (List.filterMap cases
                (c1, c2) ->
                  if isValidPair c1 c2 xMap yMap prefix then
                    Some (area c1 c2)
                  else None)
          List.maximum validPairs
            |> Optional.getOrElse 0
            |> Nat.toText
    submitSolution (Day 9) (Part 2) solve

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

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}

[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}

• [.##.] — 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!

 Meet-in-the-Middle XOR Strategy:

 Commands: [c₀, c₁, c₂, c₃, c₄, c₅]   Target: T
           ╰──── Left ────╯╰─ Right ─╯

 Step 1: Build left table (all 2³ = 8 subsets)
 ┌─────────┬────────────┬───────┐
 │ Mask    │ XOR Result │ Count │
 ├─────────┼────────────┼───────┤
 │ 000     │ 0          │ 0     │
 │ 001     │ c₀         │ 1     │
 │ 010     │ c₁         │ 1     │
 │ 011     │ c₀⊕c₁      │ 2     │
 │ ...     │ ...        │ ...   │
 └─────────┴────────────┴───────┘

 Step 2: Search right half
 For each right subset R:
   rightXor = XOR of selected commands
   needed = T ⊕ rightXor  (what left half must provide)
   if needed in leftTable:
     total = leftCount + rightCount  ← candidate solution!

Bit-Packing Commands

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

Command.fromList : [Nat] -> Command
Command.fromList =
  use Nat +
  List.foldLeft (acc -> Nat.shiftLeft 1 >> (+) acc) 0 >> Command

Building the Left Table

buildLeftTable : [Command] -> Map Command (Nat, Nat)
buildLeftTable xs = 
  withInitialValue Map.empty do
    use Nat < ^
    Each.run do
      mask = Each.range 0 (2 ^ List.size xs)
      xorResult = xorSubset xs mask
      count = Nat.popCount mask
      Store.modify
        (Map.alter
          (cases
            None -> Some (mask, count)
            Some (_, c) ->
              if count < c then Some (mask, count)
              else Some (mask, c))
          xorResult)
    Store.get

XOR-ing a Subset

xorSubset : [Command] -> Nat -> Command
xorSubset xs mask = 
  withInitialValue (Command 0) do
    Each.run do
      i = Each.range 0 (List.size xs)
      guard (isSetBit i mask)
      Store.modify cases
        Command x ->
          newX =
            List.at i xs
              |> (Optional.map cases Command c -> Nat.xor x c)
              |> Optional.getOrElse 0
          Command newX
    Store.get

day10.part1 : '{IO, Exception} ()
day10.part1 = do
  solve input =
    day10.parse input |> (List.filterMap cases
      (t, rc, _) ->
        c = rc |> List.map Command.fromList
        (left, right) = List.halve c
        leftMap = buildLeftTable left
        result = searchRightHalf right leftMap t
        result |> Optional.map at1) |> Nat.sum |> Nat.toText
  up.submitSolution (Day 10) (Part 1) solve

---

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".

 Example: commands = [[0,1,2,3,4], [0,3,4], [0,1,2,4,5], [1,2]]
          target = [10, 11, 11, 5, 10, 5]

 Position 0 hit by: cmd0, cmd1, cmd2       → x₀ + x₁ + x₂      = 10
 Position 1 hit by: cmd0, cmd2, cmd3       → x₀ + x₂ + x₃      = 11
 Position 2 hit by: cmd0, cmd2, cmd3       → x₀ + x₂ + x₃      = 11
 Position 3 hit by: cmd0, cmd1             → x₀ + x₁           = 5
 Position 4 hit by: cmd0, cmd1, cmd2       → x₀ + x₁ + x₂      = 10
 Position 5 hit by: cmd2                   → x₂                = 5

 Matrix form [A|b]:
 ┌                     ┐
 │ 1  1  1  0 │ 10     │
 │ 1  0  1  1 │ 11     │
 │ 1  0  1  1 │ 11     │
 │ 1  1  0  0 │  5     │
 │ 1  1  1  0 │ 10     │
 │ 0  0  1  0 │  5     │
 └                     ┘

Gaussian Elimination Pipeline

┌──────────────────┐     ┌─────────────────┐     ┌──────────────────┐
│   Build Matrix   │ ──► │    Gaussian     │ ──► │ Back Substitute  │
│  from commands   │     │   Elimination   │     │  or Search Free  │
└──────────────────┘     └─────────────────┘     └──────────────────┘
         │                       │                        │
         ▼                       ▼                        ▼
    [A | b]              Row echelon form         Solution vector
    augmented            + pivot columns          [x₀, x₁, ..., xₙ]
      matrix

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.

buildMatrix
  [[0, 1, 2, 3, 4], [0, 3, 4], [0, 1, 2, 4, 5], [1, 2]]
  [10, 11, 11, 5, 10, 5]

[ [+1, +1, +1, +0, +10]
, [+1, +0, +1, +1, +11]
, [+1, +0, +1, +1, +11]
, [+1, +1, +0, +0, +5]
, [+1, +1, +1, +0, +10]
, [+0, +0, +1, +0, +5]
]

Gaussian Elimination

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

 Gaussian Elimination Steps:

 Original:                    After elimination:
 ┌─────────────┐              ┌─────────────┐
 │ 1  1  1  10 │              │ 1  1  1  10 │  ← pivot at col 0
 │ 1  0  1  11 │              │ 0  1  0   5 │  ← pivot at col 1
 │ 1  0  1  11 │   ────►      │ 0  0  1   5 │  ← pivot at col 2
 │ 1  1  0   5 │              │ 0  0  0   0 │  (redundant)
 │ 1  1  1  10 │              │ 0  0  0   0 │  (redundant)
 │ 0  0  1   5 │              │ 0  0  0   0 │  (redundant)
 └─────────────┘              └─────────────┘

 Pivot columns: [0, 1, 2]  →  x₃ is FREE variable

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.

findPivotRow 0 0 [[+0, +3], [+0, +5], [+6, +7], [+0, +9]]

Some 2

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.

eliminateRowsBelowPivot
  0 0 [[+1, +0, +16], [+0, +1, +19], [+0, +1, +19], [+1, +0, +16]]

[[+1, +0, +16], [+0, +1, +19], [+0, +1, +19], [+0, +0, +0]]

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

subtractRow [+4, +5, +6] [+1, +2, +3] (+2, +3)

[+5, +4, +3]

Free Variables & Optimization

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

freeVars [0, 1] 3

[2]

When free variables exist, we enumerate assignments:

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

generateAllAssignments 3 +2

[ [+0, +0, +0]
, [+0, +0, +1]
, [+0, +0, +2]
, [+0, +1, +0]
, [+0, +1, +1]
, [+0, +1, +2]
, [+0, +2, +0]
, [+0, +2, +1]
, [+0, +2, +2]
, [+1, +0, +0]
, [+1, +0, +1]
, [+1, +0, +2]
, [+1, +1, +0]
, [+1, +1, +1]
, [+1, +1, +2]
, [+1, +2, +0]
, [+1, +2, +1]
, [+1, +2, +2]
, [+2, +0, +0]
, [+2, +0, +1]
, [+2, +0, +2]
, [+2, +1, +0]
, [+2, +1, +1]
, [+2, +1, +2]
, [+2, +2, +0]
, [+2, +2, +1]
, [+2, +2, +2]
]

Back Substitution

 Back-substitution (bottom-up):

 Row 2: x₂ = 5                    → x₂ = 5
 Row 1: x₁ = 5                    → x₁ = 5
 Row 0: x₀ + x₁ + x₂ = 10        → x₀ = 10 - 5 - 5 = 0

 If x₃ is free, try x₃ ∈ [0..max] and pick minimum sum solution

Full Solver

solveLinear : [[Nat]] -> [Nat] -> Optional Int
solveLinear commands target =
  use Int >=
  use List size
  numVars = size commands
  matrix = buildMatrix commands target
  (reducedMatrix, pCols) = guassianEliminate matrix
  fv = freeVars pCols (size commands)
  if List.isEmpty fv then
    match backSubstitute reducedMatrix pCols (size commands) None with
      None -> None
      Some solution ->
        if List.all (flip (>=) +0) solution then
          Some (Int.sum solution)
        else None
  else
    max =
      target
        |> List.maximum
        |> Optional.map Nat.toInt
        |> Optional.getOrElse +0
    searchMin reducedMatrix pCols fv numVars max

day10.part2 : '{IO, Exception} ()
day10.part2 =
  do
    solve input =
      input
        |> day10.parse
        |> (List.map cases (_, xs, ys) -> (xs, ys))
        |> List.filterMap (uncurry solveLinear)
        |> Int.sum
        |> Int.toText
    up.submitSolution (Day 10) (Part 2) solve

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 ...

day11.parse : Text ->{Exception} Map Text [Text]
day11.parse input =
  parser = do
    use Parse space
    t = Parse.takeUntil (OneOf ":")
    ignore colon()
    ignore space()
    xs = sep1! space nonWhitespace
    (t, xs)
  runOrRaise (sep1 newline parser) input |> Map.fromList

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).

countPaths : Text -> Text -> [Text] -> Map Text [Text] -> Nat
countPaths start target via graph =
  vs = Set.fromList via
  go g target memo v need =
    use Map put
    use Nat +
    use Text ==
    newNeed = Set.delete v need
    match Map.get (v, newNeed) memo with
      Some k -> (k, memo)
      None   ->
        if v == target then
          k = if Set.isEmpty newNeed then 1 else 0
          (k, put (v, newNeed) k memo)
        else
          (sum, newMemo) =
            neighbors v g |> List.foldLeft_
              (0, memo) (b sbntuafq6f1 -> let
                n = sbntuafq6f1
                (acc, m) = b
                (s, newM) = go g target m n newNeed
                (acc + s, newM))
          (sum, put (v, newNeed) sum newMemo)
  (acc, _) = go graph target Map.empty start vs
  acc

Notes

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

Entrypoints

day11.part1 : '{IO, Exception} ()
day11.part1 =
  do
    solve input =
      input |> day11.parse |> countPaths "you" "out" [] |> Nat.toText
    up.submitSolution (Day 11) (Part 1) solve

day11.part2 : '{IO, Exception} ()
day11.part2 =
  do
    solve input =
      input
        |> day11.parse
        |> countPaths "svr" "out" ["dac", "fft"]
        |> Nat.toText
    up.submitSolution (Day 11) (Part 2) solve

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):

0:
###
##.
##.

1:
###
##.
.##

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

4x4: 0 0 0 0 2 0    → place 2× block4 in 4×4 grid
12x5: 1 0 1 0 2 2   → place 1×block0, 1×block2, 2×block4, 2×block5 in 12×5 grid

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

 ASCII Art  →  Block (Set Cell)  →  Orientations  →  PlacementTemplates
   ###          {(0,0), (0,1),      [8 transforms]    [valid anchors
   ##.           (1,0), (1,1),                         × orientations]
   ##.           (2,0), (2,1)}                         

Block Representation

type Cell = day12.Cell.Cell Nat Nat

type Block = day12.Block.Block (Set Cell)

Block.fromList : [[Text]] -> [Block]
Block.fromList xs = Each.toList do
  use Char ==
  use List indexed
  block = each xs
  Block
    (Set.fromList <| (Each.toList do
      (row, y) = each (indexed block)
      (col, x) = each (row |> toCharList |> indexed)
      guard (col == ?#)
      Cell x y))

Orientation Generation via $D_4$

Transforms are function compositions over Cell :

rot90 : Nat -> Cell -> Cell
rot90 maxRow = cases Cell row col -> Cell col (maxRow Nat.- row)

flipH : Nat -> Cell -> Cell
flipH maxCol = cases Cell row col -> Cell row (maxCol Nat.- col)

fromBlock : Block -> [Orientation]
fromBlock b =
  use Block boundingBox
  (maxRow, maxCol) = boundingBox b
  transforms : [Cell -> Cell]
  transforms =
    [ id
    , rot90 maxRow
    , rot180 maxRow
    , rot270 maxRow
    , flipH maxCol
    , flipHAndRotate90 maxCol maxRow
    , flipHAndRotate180 maxCol maxRow
    , flipHAndRotate270 maxCol maxRow
    ]
  applyTransform fn = cases Block cells -> Block (Set.map fn cells)
  allOrients =
    transforms
      |> List.map (flip applyTransform b)
      |> Set.fromList
      |> Set.toList
  allOrients
    |> List.map (block -> Orientation block (boundingBox block))

Placement Templates

For each orientation, enumerate valid anchor positions:

templates : Nat -> Nat -> [Orientation] -> [PlacementTemplate]
templates rows cols orientations =
  use Each range
  use Nat -
  orientations |> (List.flatMap cases
    orientation@(Orientation _ (h, w)) ->
      Each.toList do
        row = range 0 (rows - h)
        col = range 0 (cols - w)
        anchor = Cell row col
        cells = translateCells orientation anchor
        PlacementTemplate orientation anchor cells)

Placement Enumeration:

 Grid: 4×4    Block: 3×2

 Valid anchors: (0,0) (0,1) (0,2)
                (1,0) (1,1) (1,2)
                (2,0) (2,1) (2,2)

 For each anchor (r,c), translate block cells:
   translatedCells = {(r+dr, c+dc) | (dr,dc) ∈ blockCells}

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

checkEmptyPlacements : [[PlacementTemplate]] -> Boolean
checkEmptyPlacements = List.all (List.isEmpty >> Boolean.not)

Early Rejection: Area Constraint

isFeasible : (Nat, Nat, [Nat]) -> Boolean
isFeasible = cases
  (rows, cols, counts) ->
    use Nat * <=
    cellsNeeded = Nat.sum counts * 7
    cellsAvailable = rows * cols
    cellsNeeded <= cellsAvailable

Memoization: Template Caching

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

solveOneGrid :
  [[Orientation]]
  -> (Nat, Nat, [Nat])
  ->{Store (Map (Nat, Nat) [[PlacementTemplate]])} Boolean
solveOneGrid orientationsList = cases
  (rows, cols, _) ->
    blockTemplates = 
      getOrUpdate (rows, cols) do
        orientationsList |> List.map (templates rows cols)
    checkEmptyPlacements blockTemplates

Part 1 Solution

day12.part1 : '{IO, Exception} ()
day12.part1 = do
  solve input = day12.parse input |> (cases
    (ts, gs) ->
      blocks = Block.fromList ts
      orientationsList = fromBlocks blocks
      Nat.toText <| (withInitialValue Map.empty do
        Abort.toBug do
          Each.count do
            grid = each gs
            guard (isFeasible grid)
            solveOneGrid orientationsList grid))
  up.submitSolution (Day 12) (Part 1) solve

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:
  1. Find all subsets of placements that:
  2. Use each piece exactly once (exact cover on piece columns)
     1. Use each piece exactly once (exact cover on piece columns)
     2. 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 🎄