{
"path": "/3ma6z6vvbl22s",
"site": "at://did:plc:lvkhxfkdwqgwrpdek3h3q2gc/site.standard.publication/3m2ojl75sm22f",
"tags": [
"advent-of-code",
"unison-lang"
],
"$type": "site.standard.document",
"title": "Day 08-12 #adventofcode",
"content": {
"$type": "pub.leaflet.content",
"pages": [
{
"id": "019b2cea-fd45-7ff6-bb60-443246079d7a",
"$type": "pub.leaflet.pages.linearDocument",
"blocks": [
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Here are the remaining 5 days' solution write-ups. These are the Unison docs, which I have straightaway copied and pasted here. Each page includes a link to the original post, which renders much better with links to code, etc."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "I learnt a lot by thinking and solving this year's puzzles. It was a mixed bag, but a good mental exercise to end the year, nevertheless."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"id": "019b2ceb-c8ed-7224-ac71-e8a1377c3cd1",
"$type": "pub.leaflet.blocks.page"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"id": "019b2cef-2dfc-7224-ac7e-00c21001e343",
"$type": "pub.leaflet.blocks.page"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"id": "019b2cf1-b1f3-7224-ac93-c6270fac3642",
"$type": "pub.leaflet.blocks.page"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"id": "019b2cf4-cbd0-7224-acb1-99873c16ae78",
"$type": "pub.leaflet.blocks.page"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"id": "019b2cf5-ea67-7224-acbc-64a1817bbf81",
"$type": "pub.leaflet.blocks.page"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
}
]
},
{
"id": "019b2ceb-c8ed-7224-ac71-e8a1377c3cd1",
"$type": "pub.leaflet.pages.linearDocument",
"blocks": [
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 1,
"facets": [],
"plaintext": "Day 08"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "3D Point Clustering"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 12,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
},
{
"uri": "https://share.unison-lang.org/@kaychaks/advent-of-code/code/@kaychaks/year-2025/@ch06usto572kivk8k1eicj9cr1jleap4bbhmahj3pidbo9ci10n81ados0fu9tatm53k360a31kjpt7gnjj2a82n5scvvqohoosgm90/terms/day08/README",
"$type": "pub.leaflet.richtext.facet#link"
}
]
}
],
"plaintext": "Orignal Post"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "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."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Algorithm"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 21,
"byteStart": 18
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "Parse input into XYZ points"
},
"children": []
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "day08.parse : Text -> [XYZ]\nday08.parse =\n lines >> List.map\n (Text.split ?, >> List.filterMap Text.toInt >> (cases\n [x, y, z] -> Some (XYZ x y z)\n _ -> None) >> Optional.getOrBug \"invalid input\")",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Generate all pairs sorted by squared distance (quadrance)"
},
"children": []
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "sortedPairs : [XYZ] -> [(XYZ, XYZ)]\nsortedPairs xs =\n use Boolean not\n use List isEmpty\n zs = Each.toList do\n ys = each (List.tails xs)\n guard (isEmpty ys |> not)\n match ys with\n [] -> bug \"impossible\"\n p +: ps ->\n guard (isEmpty ps |> not)\n q = each ps\n (p, q)\n zs |> sortBy (uncurry qd)",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 5,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "State: clusters (set of sets), sorted pairs queue, merge counter"
},
"children": []
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "initialState : [XYZ] -> (Set (Set XYZ), [(XYZ, XYZ)], Nat)\ninitialState xs =\n (Set.fromList (List.map Set.singleton xs), sortedPairs xs, 0)",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 11,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "Merge logic: pop closest pair, if in different clusters → union them"
},
"children": []
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "mergeAttempt : '{Store (Set (Set b), [(b, b)], Nat)} Optional (b, b)\nmergeAttempt =\n do\n match Store.get with\n (clusts, (p, q) +: pts, n) ->\n match clusts |> Set.toList |> List.find (Set.contains p) with\n Some pclust ->\n if Set.contains q pclust then\n Store.put (clusts, pts, n)\n Some (p, q)\n else\n match clusts\n |> Set.toList\n |> List.find (Set.contains q) with\n Some qclust ->\n clusts' =\n clusts\n |> Set.deletes [qclust, pclust]\n |> Set.insert (Set.union pclust qclust)\n Store.put (clusts', pts, n)\n Some (p, q)\n None -> None\n None -> None\n _ -> None",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 6,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "Part 1: merge N times, stream cluster sizes descending"
},
"children": []
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "day08.solve_ : Nat -> [XYZ] -> '{Stream Nat} ()\nday08.solve_ n xs =\n use Nat + == >=\n use Optional getOrBug\n use Store get\n ys =\n List.last\n <| (unfold! (initialState xs) do\n i = get |> at3\n if i == n then abort\n else\n Store.modify cases (c, p, n) -> (c, p, n + 1)\n mergeAttempt()\n |> Optional.map (_ -> get |> at1)\n |> getOrBug \"impossible\")\n ys\n |> getOrBug \"impossible\"\n |> Set.toList\n |> List.map Set.size\n |> sortWith (>=)\n |> Stream.fromList",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 6,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "Part 2: merge until single cluster, return last merged pair"
},
"children": []
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "solve__ : [XYZ] -> (XYZ, XYZ)\nsolve__ xs =\n use Nat ==\n use Optional getOrBug\n go =\n do\n (st, _, _) = Store.get\n if Set.size st == 1 then abort\n else mergeAttempt() |> getOrBug \"impossible\"\n unfold! (initialState xs) go |> List.last |> getOrBug \"impossible\"",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Key Abstractions"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 2,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "qd — squared Euclidean distance (avoids sqrt)"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 5,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "Store effect — mutable state for cluster bookkeeping"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 7,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "unfold! — iterate until abort, collecting results"
},
"children": []
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Key Insight"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "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."
}
}
]
},
{
"id": "019b2cef-2dfc-7224-ac7e-00c21001e343",
"$type": "pub.leaflet.pages.linearDocument",
"blocks": [
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 1,
"facets": [],
"plaintext": "Day 09"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Rectilinear Polygon Area"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 13,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
},
{
"uri": "https://share.unison-lang.org/@kaychaks/advent-of-code/code/@kaychaks/year-2025/@ch06usto572kivk8k1eicj9cr1jleap4bbhmahj3pidbo9ci10n81ados0fu9tatm53k360a31kjpt7gnjj2a82n5scvvqohoosgm90/terms/day09/README",
"$type": "pub.leaflet.richtext.facet#link"
}
]
}
],
"plaintext": "Original Post"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 60,
"byteStart": 41
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "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."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Algorithm"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Parse corner coordinates"
},
"children": []
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "day09.parse : Text -> [XY]\nday09.parse =\n lines >> List.map\n (Text.split ?, >> List.filterMap Text.toInt >> (cases\n [x, y] -> Some (XY x y)\n _ -> None) >> Optional.getOrBug \"invalid input\")",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 6,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "Part 1 - Just enumerate all pairs with no containment check needed"
},
"children": []
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "allRects : [XY] -> [Nat]\nallRects xs =\n xs |> List.tails |> (List.flatMap cases\n p +: ps -> ps |> List.map (q -> area p q)\n _ -> [])",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "And the area being"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "area : XY -> XY -> Nat\narea a b =\n use Int diff\n use Nat * +\n (XY x1 y1) = a\n (XY x2 y2) = b\n (diff x1 x2 + 1) * (diff y1 y2 + 1)",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Part 2 - The Scaling Problem"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Attempt 1 - Naive BFS Flood Fill (Too Slow)"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "The idea is to flood fill from outside to find exterior cells. Everything NOT reached is interior."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": " Before flood fill: After flood fill:\n ┌─────────────────┐ ┌─────────────────┐\n │ · · · · · · · · │ │ █ █ █ █ █ █ █ █ │\n │ · · * * * * · · │ │ █ █ * * * * █ █ │\n │ · · * * · · │ → │ █ █ * * █ █ │\n │ · · * * * * · · │ │ █ █ * * * * █ █ │\n │ · · · · · · · · │ │ █ █ █ █ █ █ █ █ │\n └─────────────────┘ └─────────────────┘\n\n * = border · = unknown █ = outside (flooded)\n (empty) = inside (not flooded)",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "bfs : [XY] -> Set XY -> Set XY -> (Int, Int, Int, Int) -> Set XY\nbfs queue visited border = cases\n (minX, maxX, minY, maxY) ->\n use Int + - < >\n use List ++\n use Set contains\n outofBounds = cases\n XY x y -> x < minX || x > maxX || y < minY || y > maxY\n match queue with\n [] -> visited\n XY x y +: rest ->\n if outofBounds (XY x y) || contains (XY x y) border\n || contains (XY x y) visited then\n bfs rest visited border (minX, maxX, minY, maxY)\n else\n visited' = Set.insert (XY x y) visited\n neighbors =\n [ XY (x + +1) y\n , XY (x - +1) y\n , XY x (y + +1)\n , XY x (y - +1)\n ]\n bfs\n (rest ++ neighbors)\n visited'\n border\n (minX, maxX, minY, maxY)",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 8,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "Problems with this approach"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 17,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "rest ++ neighbors is O(n) per step leading to O(n^2) total"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "For coords in range 0 to 100000 thats 10 billion cells to visit"
},
"children": []
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Attempt 2 - Optimized BFS (Still Too Slow)"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "bfsOptimized :\n [XY] -> Set XY -> Set XY -> (Int, Int, Int, Int) -> Set XY\nbfsOptimized queue visited border = cases\n (minX, maxX, minY, maxY) ->\n use Int + - < >\n use List ++\n use Set contains\n outOfBounds = cases\n XY x y -> x < minX || x > maxX || y < minY || y > maxY\n isBlocked b v pt =\n outOfBounds pt || contains pt b || contains pt v\n go q v =\n match q with\n [] -> v\n XY x y +: rest ->\n if contains (XY x y) v then go rest v\n else\n v' = Set.insert (XY x y) v\n neighbors =\n [ XY (x + +1) y\n , XY (x - +1) y\n , XY x (y + +1)\n , XY x (y - +1)\n ]\n newNeighbors =\n neighbors\n |> List.filter (isBlocked border v' >> Boolean.not)\n go (newNeighbors ++ rest) v'\n go queue visited",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 74,
"byteStart": 27
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "Fixed the O(n) append but the real problem is the coordinate range itself."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Attempt 3 - Coordinate Compression (Works!)"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 11,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "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!"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Example:"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": " Original coordinates: Compressed coordinates:\n x = [2, 7, 9, 11] x' = [0, 1, 2, 3]\n y = [1, 3, 5, 7] y' = [0, 1, 2, 3]\n\n Original grid: ~100 cells Compressed grid: 4×4 = 16 cells!",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "compressPoints : [XY] -> ([Int], [Int], Map Int Int, Map Int Int)\ncompressPoints pts =\n use List map\n xs = pts |> map x |> uniqueSorted\n ys = pts |> map y |> uniqueSorted\n xMap = buildIndexMap xs\n yMap = buildIndexMap ys\n (xs, ys, xMap, yMap)",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "2D Prefix Sum for O(1) Rectangle Queries"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Once we have an inside/outside grid we build a prefix sum. This lets us query any rectangle in O(1) via inclusion-exclusion."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Example:"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": " Inside grid (1=inside, 0=outside): Prefix sum:\n\n 0 1 2 3 0 1 2 3\n ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐\n 3 │ 0 │ 0 │ 1 │ 1 │ 3 │ 0 │ 1 │ 4 │ 7 │\n ├───┼───┼───┼───┤ ├───┼───┼───┼───┤\n 2 │ 1 │ 1 │ 1 │ 1 │ 2 │ 0 │ 1 │ 3 │ 5 │\n ├───┼───┼───┼───┤ → ├───┼───┼───┼───┤\n 1 │ 1 │ 1 │ 0 │ 1 │ 1 │ 0 │ 1 │ 2 │ 3 │\n ├───┼───┼───┼───┤ ├───┼───┼───┼───┤\n 0 │ 0 │ 1 │ 1 │ 1 │ 0 │ 0 │ 1 │ 2 │ 3 │\n └───┴───┴───┴───┘ └───┴───┴───┴───┘\n\n prefix[i][j] = count of 1s in rectangle (0,0) to (i,j)",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "queryRect : Grid Int -> XY -> XY -> Int\nqueryRect prefix c1 c2 =\n use Int + -\n use Optional getOrElse\n (XY i1 j1) = c1\n (XY i2 j2) = c2\n (prefix |> get (i2 + +1) (j2 + +1) |> getOrElse +0)\n - (prefix |> get i1 (j2 + +1) |> getOrElse +0)\n - (prefix |> get (i2 + +1) j1 |> getOrElse +0)\n + (prefix |> get i1 j1 |> getOrElse +0)",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Full Part 2 Solution"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "day09.part2 : '{IO, Exception} ()\nday09.part2 =\n do\n solve input =\n use List size\n parsedInput = day09.parse input\n (xs, ys, xMap, yMap) = parsedInput |> compressPoints\n n = size xs\n m = size ys\n insideGrid = buildInsideGrid parsedInput xMap yMap n m\n match buildPrefixSum insideGrid n m with\n prefix@(Grid m) ->\n allPairs = uniquePairs parsedInput\n validPairs =\n allPairs\n |> (List.filterMap cases\n (c1, c2) ->\n if isValidPair c1 c2 xMap yMap prefix then\n Some (area c1 c2)\n else None)\n List.maximum validPairs\n |> Optional.getOrElse 0\n |> Nat.toText\n submitSolution (Day 9) (Part 2) solve",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Complexity Comparison"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Naive BFS - O(W x H) - 10 billion ops for 100Kx100K grid"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Compressed - O(n^2) - about 10000 ops for 100 corners"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 22,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "Speedup about 1000000x"
},
"children": []
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Key Functions"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 14,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "compressPoints - Extract unique coords and build index maps"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 13,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "compressPoint - Map original to compressed index"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 19,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "findEdgesCompressed - Find edges in compressed space"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 26,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "floodFillOutsideCompressed - BFS on tiny compressed grid"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 14,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "buildPrefixSum - 2D prefix sum for O(1) queries"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 9,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "queryRect - Count inside cells in rectangle"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 11,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "isValidPair - Check if rectangle fits entirely inside"
},
"children": []
}
]
}
}
]
},
{
"id": "019b2cf1-b1f3-7224-ac93-c6270fac3642",
"$type": "pub.leaflet.pages.linearDocument",
"blocks": [
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 1,
"facets": [],
"plaintext": "Day 10"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Command XOR & Linear Optimization"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 13,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
},
{
"uri": "https://share.unison-lang.org/@kaychaks/advent-of-code/code/@kaychaks/year-2025/@ch06usto572kivk8k1eicj9cr1jleap4bbhmahj3pidbo9ci10n81ados0fu9tatm53k360a31kjpt7gnjj2a82n5scvvqohoosgm90/terms/day10/README",
"$type": "pub.leaflet.richtext.facet#link"
}
]
}
],
"plaintext": "Original Post"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Given commands that toggle bit positions and target bit patterns:"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 5,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "Part1: Find minimum subset of commands whose XOR equals target (Boolean algebra)"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 6,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "Part 2: Find minimum sum of command usages satisfying linear constraints (Integer LP)"
},
"children": []
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Input Format"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 46,
"byteStart": 12
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "Each line: [target] (cmd1) (cmd2) ... {costs}"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": "[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 6,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 43,
"byteStart": 42
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "[.##.] — target bit pattern (`.` = 0, # = 1)"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 3,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 11,
"byteStart": 6
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "(3), (1,3) — commands that toggle bit positions"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 9,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "{3,5,4,7} — costs/targets for Part 2"
},
"children": []
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Part 1: Meet-in-the-Middle XOR Search"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "The Problem"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Find smallest subset of commands whose XOR produces the target. With n commands, naive enumeration is O(2^n)."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Key Insight: Halve the Search Space"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Split commands into left/right halves. For left half of size n/2:"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Enumerate all 2^(n/2) subsets → store XOR results in hash map"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 65,
"byteStart": 37
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "For each right-half subset, compute needed = target XOR rightXor"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 15,
"byteStart": 9
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "Look up needed in left map — if found, we have a solution!"
},
"children": []
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": " Meet-in-the-Middle XOR Strategy:\n\n Commands: [c₀, c₁, c₂, c₃, c₄, c₅] Target: T\n ╰──── Left ────╯╰─ Right ─╯\n\n Step 1: Build left table (all 2³ = 8 subsets)\n ┌─────────┬────────────┬───────┐\n │ Mask │ XOR Result │ Count │\n ├─────────┼────────────┼───────┤\n │ 000 │ 0 │ 0 │\n │ 001 │ c₀ │ 1 │\n │ 010 │ c₁ │ 1 │\n │ 011 │ c₀⊕c₁ │ 2 │\n │ ... │ ... │ ... │\n └─────────┴────────────┴───────┘\n\n Step 2: Search right half\n For each right subset R:\n rightXor = XOR of selected commands\n needed = T ⊕ rightXor (what left half must provide)\n if needed in leftTable:\n total = leftCount + rightCount ← candidate solution!",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Bit-Packing Commands"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 29,
"byteStart": 26
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "Commands are packed into Nat as bit vectors for fast XOR:"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "Command.fromList : [Nat] -> Command\nCommand.fromList =\n use Nat +\n List.foldLeft (acc -> Nat.shiftLeft 1 >> (+) acc) 0 >> Command",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Building the Left Table"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "buildLeftTable : [Command] -> Map Command (Nat, Nat)\nbuildLeftTable xs = \n withInitialValue Map.empty do\n use Nat < ^\n Each.run do\n mask = Each.range 0 (2 ^ List.size xs)\n xorResult = xorSubset xs mask\n count = Nat.popCount mask\n Store.modify\n (Map.alter\n (cases\n None -> Some (mask, count)\n Some (_, c) ->\n if count < c then Some (mask, count)\n else Some (mask, c))\n xorResult)\n Store.get",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "XOR-ing a Subset"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "xorSubset : [Command] -> Nat -> Command\nxorSubset xs mask = \n withInitialValue (Command 0) do\n Each.run do\n i = Each.range 0 (List.size xs)\n guard (isSetBit i mask)\n Store.modify cases\n Command x ->\n newX =\n List.at i xs\n |> (Optional.map cases Command c -> Nat.xor x c)\n |> Optional.getOrElse 0\n Command newX\n Store.get",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "day10.part1 : '{IO, Exception} ()\nday10.part1 = do\n solve input =\n day10.parse input |> (List.filterMap cases\n (t, rc, _) ->\n c = rc |> List.map Command.fromList\n (left, right) = List.halve c\n leftMap = buildLeftTable left\n result = searchRightHalf right leftMap t\n result |> Optional.map at1) |> Nat.sum |> Nat.toText\n up.submitSolution (Day 10) (Part 1) solve",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "---"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Part 2: Linear Programming via Gaussian Elimination"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "The Problem"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Now commands can be used multiple times. Find non-negative integer solution minimizing total usage count."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Formulation as Linear System"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Each target position gives an equation. Commands are variables indicating \"how many times used\"."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": " Example: commands = [[0,1,2,3,4], [0,3,4], [0,1,2,4,5], [1,2]]\n target = [10, 11, 11, 5, 10, 5]\n\n Position 0 hit by: cmd0, cmd1, cmd2 → x₀ + x₁ + x₂ = 10\n Position 1 hit by: cmd0, cmd2, cmd3 → x₀ + x₂ + x₃ = 11\n Position 2 hit by: cmd0, cmd2, cmd3 → x₀ + x₂ + x₃ = 11\n Position 3 hit by: cmd0, cmd1 → x₀ + x₁ = 5\n Position 4 hit by: cmd0, cmd1, cmd2 → x₀ + x₁ + x₂ = 10\n Position 5 hit by: cmd2 → x₂ = 5\n\n Matrix form [A|b]:\n ┌ ┐\n │ 1 1 1 0 │ 10 │\n │ 1 0 1 1 │ 11 │\n │ 1 0 1 1 │ 11 │\n │ 1 1 0 0 │ 5 │\n │ 1 1 1 0 │ 10 │\n │ 0 0 1 0 │ 5 │\n └ ┘",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Gaussian Elimination Pipeline"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": "┌──────────────────┐ ┌─────────────────┐ ┌──────────────────┐\n│ Build Matrix │ ──► │ Gaussian │ ──► │ Back Substitute │\n│ from commands │ │ Elimination │ │ or Search Free │\n└──────────────────┘ └─────────────────┘ └──────────────────┘\n │ │ │\n ▼ ▼ ▼\n [A | b] Row echelon form Solution vector\n augmented + pivot columns [x₀, x₁, ..., xₙ]\n matrix",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Building the Coefficient Matrix"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 27,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 63,
"byteStart": 55
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 76,
"byteStart": 70
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "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."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": "buildMatrix\n [[0, 1, 2, 3, 4], [0, 3, 4], [0, 1, 2, 4, 5], [1, 2]]\n [10, 11, 11, 5, 10, 5]",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": "[ [+1, +1, +1, +0, +10]\n, [+1, +0, +1, +1, +11]\n, [+1, +0, +1, +1, +11]\n, [+1, +1, +0, +0, +5]\n, [+1, +1, +1, +0, +10]\n, [+0, +0, +1, +0, +5]\n]",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Gaussian Elimination"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 82,
"byteStart": 51
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "Guassian elimination to row echelon form. Returns (reduced matrix, pivot columns)"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": " Gaussian Elimination Steps:\n\n Original: After elimination:\n ┌─────────────┐ ┌─────────────┐\n │ 1 1 1 10 │ │ 1 1 1 10 │ ← pivot at col 0\n │ 1 0 1 11 │ │ 0 1 0 5 │ ← pivot at col 1\n │ 1 0 1 11 │ ────► │ 0 0 1 5 │ ← pivot at col 2\n │ 1 1 0 5 │ │ 0 0 0 0 │ (redundant)\n │ 1 1 1 10 │ │ 0 0 0 0 │ (redundant)\n │ 0 0 1 5 │ │ 0 0 0 0 │ (redundant)\n └─────────────┘ └─────────────┘\n\n Pivot columns: [0, 1, 2] → x₃ is FREE variable",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Key Operations"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 18,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "Finding pivot row:"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 32,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 64,
"byteStart": 58
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 106,
"byteStart": 103
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 136,
"byteStart": 128
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "findPivotRow col startRow matrix finds the first row in matrix that has a non-zero value in column col, starting from row startRow."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": "findPivotRow 0 0 [[+0, +3], [+0, +5], [+6, +7], [+0, +9]]",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": "Some 2",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 16,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "Row elimination:"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 40,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 92,
"byteStart": 86
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "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."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": "eliminateRowsBelowPivot\n 0 0 [[+1, +0, +16], [+0, +1, +19], [+0, +1, +19], [+1, +0, +16]]",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": "[[+1, +0, +16], [+0, +1, +19], [+0, +1, +19], [+0, +0, +0]]",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 27,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "Scaling to avoid fractions:"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 32,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 51,
"byteStart": 45
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 66,
"byteStart": 59
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 90,
"byteStart": 84
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 98,
"byteStart": 96
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 112,
"byteStart": 105
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 120,
"byteStart": 118
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "subtract destRow srcRow (m1, m2) subtracts srcRow from destRow by multiplying srcRow by m2 and destRow by m1, then subtracting the result."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "To avoid fractions, scale: newRow = destRow * pivotValue - srcRow * elementValue"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": "subtractRow [+4, +5, +6] [+1, +2, +3] (+2, +3)",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": "[+5, +4, +3]",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Free Variables & Optimization"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 23,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "freeVars pivots numVars find which columns are free i.e. not pivots."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": "freeVars [0, 1] 3",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": "[2]",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "When free variables exist, we enumerate assignments:"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 34,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "generateAllAssignments numFree max generates all possible assignments of values between 0 and max to numFree variables."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": "generateAllAssignments 3 +2",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": "[ [+0, +0, +0]\n, [+0, +0, +1]\n, [+0, +0, +2]\n, [+0, +1, +0]\n, [+0, +1, +1]\n, [+0, +1, +2]\n, [+0, +2, +0]\n, [+0, +2, +1]\n, [+0, +2, +2]\n, [+1, +0, +0]\n, [+1, +0, +1]\n, [+1, +0, +2]\n, [+1, +1, +0]\n, [+1, +1, +1]\n, [+1, +1, +2]\n, [+1, +2, +0]\n, [+1, +2, +1]\n, [+1, +2, +2]\n, [+2, +0, +0]\n, [+2, +0, +1]\n, [+2, +0, +2]\n, [+2, +1, +0]\n, [+2, +1, +1]\n, [+2, +1, +2]\n, [+2, +2, +0]\n, [+2, +2, +1]\n, [+2, +2, +2]\n]",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Back Substitution"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": " Back-substitution (bottom-up):\n\n Row 2: x₂ = 5 → x₂ = 5\n Row 1: x₁ = 5 → x₁ = 5\n Row 0: x₀ + x₁ + x₂ = 10 → x₀ = 10 - 5 - 5 = 0\n\n If x₃ is free, try x₃ ∈ [0..max] and pick minimum sum solution",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Full Solver"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "solveLinear : [[Nat]] -> [Nat] -> Optional Int\nsolveLinear commands target =\n use Int >=\n use List size\n numVars = size commands\n matrix = buildMatrix commands target\n (reducedMatrix, pCols) = guassianEliminate matrix\n fv = freeVars pCols (size commands)\n if List.isEmpty fv then\n match backSubstitute reducedMatrix pCols (size commands) None with\n None -> None\n Some solution ->\n if List.all (flip (>=) +0) solution then\n Some (Int.sum solution)\n else None\n else\n max =\n target\n |> List.maximum\n |> Optional.map Nat.toInt\n |> Optional.getOrElse +0\n searchMin reducedMatrix pCols fv numVars max",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "day10.part2 : '{IO, Exception} ()\nday10.part2 =\n do\n solve input =\n input\n |> day10.parse\n |> (List.map cases (_, xs, ys) -> (xs, ys))\n |> List.filterMap (uncurry solveLinear)\n |> Int.sum\n |> Int.toText\n up.submitSolution (Day 10) (Part 2) solve",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
}
]
},
{
"id": "019b2cf4-cbd0-7224-acb1-99873c16ae78",
"$type": "pub.leaflet.pages.linearDocument",
"blocks": [
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 1,
"facets": [],
"plaintext": "Day 11"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Paths With Must-Visit Nodes"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 13,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
},
{
"uri": "https://share.unison-lang.org/@kaychaks/advent-of-code/code/@kaychaks/year-2025/@ch06usto572kivk8k1eicj9cr1jleap4bbhmahj3pidbo9ci10n81ados0fu9tatm53k360a31kjpt7gnjj2a82n5scvvqohoosgm90/terms/day11/README",
"$type": "pub.leaflet.richtext.facet#link"
}
]
}
],
"plaintext": "Original Post"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 67,
"byteStart": 64
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "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."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Input Format"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 30,
"byteStart": 12
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "Each line: src: dst1 dst2 ..."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "day11.parse : Text ->{Exception} Map Text [Text]\nday11.parse input =\n parser = do\n use Parse space\n t = Parse.takeUntil (OneOf \":\")\n ignore colon()\n ignore space()\n xs = sep1! space nonWhitespace\n (t, xs)\n runOrRaise (sep1 newline parser) input |> Map.fromList",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Problem"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 32,
"byteStart": 27
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 44,
"byteStart": 38
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 71,
"byteStart": 57
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
},
{
"index": {
"byteEnd": 74,
"byteStart": 71
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
},
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
},
{
"index": {
"byteEnd": 97,
"byteStart": 74
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "Count directed paths from start to target such that every node in via is visited ≥ 1 times."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 6,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
},
{
"index": {
"byteEnd": 22,
"byteStart": 9
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 39,
"byteStart": 25
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 50,
"byteStart": 42
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "Part 1: start = \"you\", target = \"out\", via = []"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 6,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
},
{
"index": {
"byteEnd": 22,
"byteStart": 9
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 39,
"byteStart": 25
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 62,
"byteStart": 42
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "Part 2: start = \"svr\", target = \"out\", via = [\"dac\", \"fft\"]"
},
"children": []
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Algorithm: DP over (node, remainingVia)"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 50,
"byteStart": 35
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "Track remaining required nodes as need : Set Text."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 25,
"byteStart": 24
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 58,
"byteStart": 33
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "On each step from node v, set need' = Set.delete v need."
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 15,
"byteStart": 4
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 34,
"byteStart": 30
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "If v == target, accept iff need is empty."
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 33,
"byteStart": 24
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "Memoize results by key (v, need)."
},
"children": []
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "countPaths : Text -> Text -> [Text] -> Map Text [Text] -> Nat\ncountPaths start target via graph =\n vs = Set.fromList via\n go g target memo v need =\n use Map put\n use Nat +\n use Text ==\n newNeed = Set.delete v need\n match Map.get (v, newNeed) memo with\n Some k -> (k, memo)\n None ->\n if v == target then\n k = if Set.isEmpty newNeed then 1 else 0\n (k, put (v, newNeed) k memo)\n else\n (sum, newMemo) =\n neighbors v g |> List.foldLeft_\n (0, memo) (b sbntuafq6f1 -> let\n n = sbntuafq6f1\n (acc, m) = b\n (s, newM) = go g target m n newNeed\n (acc + s, newM))\n (sum, put (v, newNeed) sum newMemo)\n (acc, _) = go graph target Map.empty start vs\n acc",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Notes"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 133,
"byteStart": 129
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "This assumes the input graph is “well-behaved” for this recursion (e.g. no cycles that can repeat forever without shrinking need)."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Entrypoints"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "day11.part1 : '{IO, Exception} ()\nday11.part1 =\n do\n solve input =\n input |> day11.parse |> countPaths \"you\" \"out\" [] |> Nat.toText\n up.submitSolution (Day 11) (Part 1) solve",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "day11.part2 : '{IO, Exception} ()\nday11.part2 =\n do\n solve input =\n input\n |> day11.parse\n |> countPaths \"svr\" \"out\" [\"dac\", \"fft\"]\n |> Nat.toText\n up.submitSolution (Day 11) (Part 2) solve",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
}
]
},
{
"id": "019b2cf5-ea67-7224-acbc-64a1817bbf81",
"$type": "pub.leaflet.pages.linearDocument",
"blocks": [
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 1,
"facets": [],
"plaintext": "Day 12"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Jigsaw Polyomino Feasibility"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 13,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
},
{
"uri": "https://share.unison-lang.org/@kaychaks/advent-of-code/code/@kaychaks/year-2025/@ch06usto572kivk8k1eicj9cr1jleap4bbhmahj3pidbo9ci10n81ados0fu9tatm53k360a31kjpt7gnjj2a82n5scvvqohoosgm90/terms/day12/README",
"$type": "pub.leaflet.richtext.facet#link"
}
]
}
],
"plaintext": "Original Post"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Given ASCII art block templates & grid specs, determine feasible arrangements."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 6,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "Part 1: Count grids where all blocks have ≥1 valid placement"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Input Format"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 43,
"byteStart": 42
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "Blocks defined as ASCII art (`#` = cell, . = empty):"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": "0:\n###\n##.\n##.\n\n1:\n###\n##.\n.##",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 46,
"byteStart": 13
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 59,
"byteStart": 55
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
},
{
"index": {
"byteEnd": 80,
"byteStart": 79
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "Grid specs: {rows}x{cols}: c₀ c₁ ... c₅ where cᵢ = count of block i to place."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": "4x4: 0 0 0 0 2 0 → place 2× block4 in 4×4 grid\n12x5: 1 0 1 0 2 2 → place 1×block0, 1×block2, 2×block4, 2×block5 in 12×5 grid",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Problem: Polyomino Packing Feasibility"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 26,
"byteStart": 17
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "Each block is a polyomino (7-cell shape). Apply $D_4$ dihedral group transformations:"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 57,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "4 rotations: 0°, 90°, 180°, 270° -4 flips + rotations: flipH, flipH+rot90, flipH+rot180, flipH+rot270"
},
"children": []
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "→ Up to 8 distinct orientations (fewer if symmetries exist)"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Data Pipeline"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": " ASCII Art → Block (Set Cell) → Orientations → PlacementTemplates\n ### {(0,0), (0,1), [8 transforms] [valid anchors\n ##. (1,0), (1,1), × orientations]\n ##. (2,0), (2,1)} ",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Block Representation"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "type Cell = day12.Cell.Cell Nat Nat",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "type Block = day12.Block.Block (Set Cell)",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "Block.fromList : [[Text]] -> [Block]\nBlock.fromList xs = Each.toList do\n use Char ==\n use List indexed\n block = each xs\n Block\n (Set.fromList <| (Each.toList do\n (row, y) = each (indexed block)\n (col, x) = each (row |> toCharList |> indexed)\n guard (col == ?#)\n Cell x y))",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Orientation Generation via $D_4$"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 47,
"byteStart": 43
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "Transforms are function compositions over Cell :"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "rot90 : Nat -> Cell -> Cell\nrot90 maxRow = cases Cell row col -> Cell col (maxRow Nat.- row)",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "flipH : Nat -> Cell -> Cell\nflipH maxCol = cases Cell row col -> Cell row (maxCol Nat.- col)",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "fromBlock : Block -> [Orientation]\nfromBlock b =\n use Block boundingBox\n (maxRow, maxCol) = boundingBox b\n transforms : [Cell -> Cell]\n transforms =\n [ id\n , rot90 maxRow\n , rot180 maxRow\n , rot270 maxRow\n , flipH maxCol\n , flipHAndRotate90 maxCol maxRow\n , flipHAndRotate180 maxCol maxRow\n , flipHAndRotate270 maxCol maxRow\n ]\n applyTransform fn = cases Block cells -> Block (Set.map fn cells)\n allOrients =\n transforms\n |> List.map (flip applyTransform b)\n |> Set.fromList\n |> Set.toList\n allOrients\n |> List.map (block -> Orientation block (boundingBox block))",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Placement Templates"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "For each orientation, enumerate valid anchor positions:"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "templates : Nat -> Nat -> [Orientation] -> [PlacementTemplate]\ntemplates rows cols orientations =\n use Each range\n use Nat -\n orientations |> (List.flatMap cases\n orientation@(Orientation _ (h, w)) ->\n Each.toList do\n row = range 0 (rows - h)\n col = range 0 (cols - w)\n anchor = Cell row col\n cells = translateCells orientation anchor\n PlacementTemplate orientation anchor cells)",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "plaintext",
"plaintext": "Placement Enumeration:\n\n Grid: 4×4 Block: 3×2\n\n Valid anchors: (0,0) (0,1) (0,2)\n (1,0) (1,1) (1,2)\n (2,0) (2,1) (2,2)\n\n For each anchor (r,c), translate block cells:\n translatedCells = {(r+dr, c+dc) | (dr,dc) ∈ blockCells}",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Part 1: Quick Feasibility Check"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Strategy: Empty Placement Detection"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Instead of solving the full constraint satisfaction problem, check:"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 13,
"byteStart": 8
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "> Does every block type have ≥1 valid placement in the grid?"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 22,
"byteStart": 18
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
},
{
"index": {
"byteEnd": 64,
"byteStart": 54
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "If any block has zero valid placements → grid is infeasible"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "checkEmptyPlacements : [[PlacementTemplate]] -> Boolean\ncheckEmptyPlacements = List.all (List.isEmpty >> Boolean.not)",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Early Rejection: Area Constraint"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "isFeasible : (Nat, Nat, [Nat]) -> Boolean\nisFeasible = cases\n (rows, cols, counts) ->\n use Nat * <=\n cellsNeeded = Nat.sum counts * 7\n cellsAvailable = rows * cols\n cellsNeeded <= cellsAvailable",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Memoization: Template Caching"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 38,
"byteStart": 26
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#code"
}
]
}
],
"plaintext": "Templates depend only on (rows, cols) — cache across grids:"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "solveOneGrid :\n [[Orientation]]\n -> (Nat, Nat, [Nat])\n ->{Store (Map (Nat, Nat) [[PlacementTemplate]])} Boolean\nsolveOneGrid orientationsList = cases\n (rows, cols, _) ->\n blockTemplates = \n getOrUpdate (rows, cols) do\n orientationsList |> List.map (templates rows cols)\n checkEmptyPlacements blockTemplates",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "Part 1 Solution"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.code",
"language": "haskell",
"plaintext": "day12.part1 : '{IO, Exception} ()\nday12.part1 = do\n solve input = day12.parse input |> (cases\n (ts, gs) ->\n blocks = Block.fromList ts\n orientationsList = fromBlocks blocks\n Nat.toText <| (withInitialValue Map.empty do\n Abort.toBug do\n Each.count do\n grid = each gs\n guard (isFeasible grid)\n solveOneGrid orientationsList grid))\n up.submitSolution (Day 12) (Part 1) solve",
"syntaxHighlightingTheme": "catppuccin-latte"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": ""
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "It should not work..."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 36,
"byteStart": 11
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
},
{
"index": {
"byteEnd": 123,
"byteStart": 96
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#bold"
}
]
}
],
"plaintext": "This is a polyomino packing problem — NP-complete in general. I wanted to solve it using - Dancing Links (Algorithm X)"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.unorderedList",
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Columns = piece constraints + cell constraints"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Rows = valid placements"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Find all subsets of placements that:"
},
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Find all subsets of placements that:"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Use each piece exactly once (exact cover on piece columns)"
},
"children": [
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Use each piece exactly once (exact cover on piece columns)"
},
"children": []
},
{
"$type": "pub.leaflet.blocks.unorderedList#listItem",
"content": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Cover each cell ≤1 time (at most once on cell columns)"
},
"children": []
}
]
}
]
}
]
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "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."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 3,
"facets": [],
"plaintext": "Why Empty Placement Check Works"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "If ∃ block with 0 valid placements → no solution exists (pigeonhole)."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [
{
"index": {
"byteEnd": 152,
"byteStart": 0
},
"features": [
{
"$type": "pub.leaflet.richtext.facet#italic"
}
]
}
],
"plaintext": "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."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.header",
"level": 2,
"facets": [],
"plaintext": "No Part 2"
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Day 12 is the final puzzle of AoC 2025 — no Part 2."
}
},
{
"$type": "pub.leaflet.pages.linearDocument#block",
"block": {
"$type": "pub.leaflet.blocks.text",
"facets": [],
"plaintext": "Happy holidays 🎄"
}
}
]
}
]
},
"bskyPostRef": {
"cid": "bafyreidv3k32yyj5so2qcknxngzialn6um2sqyq2liqkwddyh5kzhspxt4",
"uri": "at://did:plc:lvkhxfkdwqgwrpdek3h3q2gc/app.bsky.feed.post/3ma6z75hscs2s",
"commit": {
"cid": "bafyreigfonitbaq4dhuvpzt2gpgbgfqnqbu5zsv44wr2yx4kxzomryymbm",
"rev": "3ma6z75khxn23"
},
"validationStatus": "valid"
},
"description": "Finally it's done!",
"publishedAt": "2025-12-17T15:49:22.579Z"
}