2c:null 2d:["$","title",null,{"children":"🎄 Advent of Code 2022: Day 12 | Mike Bostock | Observable"}] 32:T591,class Grid { constructor(n, m, startIndex, endIndex, values) { this.n = n; this.m = m; this.startIndex = startIndex; this.endIndex = endIndex; this.values = values; } *[Symbol.iterator]() { for (let y = 0, i = 0; y < this.n; ++y) { for (let x = 0; x < this.m; ++x, ++i) { yield [x, y, this.values[i]]; } } } *range() { for (let i = 0, n = this.n * this.m; i < n; ++i) { yield i; } } heightAt(i) { return this.values[i]; } *outgoingEdgesAt(i) { const h = this.heightAt(i) + 1; const [x, y] = this.position(i); if (0 < y && this.heightAt(i - this.m) <= h) yield i - this.m; if (y < this.n - 1 && this.heightAt(i + this.m) <= h) yield i + this.m; if (0 < x && this.heightAt(i - 1) <= h) yield i - 1; if (x < this.m - 1 && this.heightAt(i + 1) <= h) yield i + 1; } *incomingEdgesAt(i) { const h = this.heightAt(i) - 1; const [x, y] = this.position(i); if (0 < y && this.heightAt(i - this.m) >= h) yield i - this.m; if (y < this.n - 1 && this.heightAt(i + this.m) >= h) yield i + this.m; if (0 < x && this.heightAt(i - 1) >= h) yield i - 1; if (x < this.m - 1 && this.heightAt(i + 1) >= h) yield i + 1; } index(x, y) { return this.m * y + x; } x(i) { return i % this.m; } y(i) { return Math.floor(i / this.m); } position(i) { return [this.x(i), this.y(i)]; } }33:[{"id":"54add860936f801e4084955335b2881e74f4c7cbf143780bfadfd4aaea2389c0ac01981d6ac3e5a9feb7cd3dd69162bc34e7a3c6dc7cf5ac7846edd4d6ccad7d","href":"https://static.observableusercontent.com/files/54add860936f801e4084955335b2881e74f4c7cbf143780bfadfd4aaea2389c0ac01981d6ac3e5a9feb7cd3dd69162bc34e7a3c6dc7cf5ac7846edd4d6ccad7d","name":"input.txt","type":"text/plain","lastModified":1670911381572.826,"size":6355}] 30:{"id":"481a58ab5c198e70","slug":"advent-of-code-2022-day-12","title":"🎄 Advent of Code 2022: Day 12","thumbnail":"1b7ed4b75a3bc1fe7cc7eaf8c3740f93838d92122e1a9118c71055d21ba577a8","access_level":"public","create_time":"$D2022-12-13T04:46:22.112Z","update_time":"$D2022-12-13T18:08:05.768Z","view_time":null,"first_public_time":"$D2022-12-13T07:36:17.044Z","has_unpublished_edits":null,"fork":false,"stars":4,"starred":false,"owner":{"type":"team","id":"8c2e47252fd4995c","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":"pro_2026","bio":"Visualization toolmaker. Founder @observablehq. Creator @d3. Former @nytgraphics. Pronounced BOSS-tock."},"version":591,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"074c414ad1d825f5","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":null,"bio":"Visualization toolmaker. Founder @observablehq. Creator @d3. Former @nytgraphics. Pronounced BOSS-tock."}],"members":[{"type":"individual","id":"074c414ad1d825f5","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":{"id":"76221098c5a818c6","slug":"advent-of-code-2022","title":"🎄 Advent of Code 2022","owner":{"id":"8c2e47252fd4995c","login":"mbostock","name":"Mike Bostock"}},"type":"notebook","body":{"titling":"auto","title":"🎄 Advent of Code 2022: Day 12","cells":[{"id":0,"value":"# 🎄 Advent of Code 2022: Day 12\n\nhttps://adventofcode.com/2022/day/12","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":3,"value":"test = `Sabqponm\nabcryxxl\naccszExk\nacctuvwj\nabdefghi\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"testGrid = parseGrid(test)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"function parseGrid(input) {\n const rows = input.trim().split(\"\\n\");\n const n = rows.length;\n const m = rows[0].length;\n const values = rows.flatMap((line) => line.split(\"\"));\n const startIndex = values.indexOf(\"S\");\n const endIndex = values.indexOf(\"E\");\n return new Grid(n, m, startIndex, endIndex, values.map(parseHeight));\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"function parseHeight(char) {\n return char === \"S\" ? parseHeight(\"a\")\n : char === \"E\" ? parseHeight(\"z\")\n : char.charCodeAt(0) - \"a\".charCodeAt(0);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":61,"value":"visualizeGrid(testGrid)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":535,"value":"visualizeGrid(testGrid, testGrid.startIndex)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":447,"value":"shortestPaths(testGrid)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"function visualizeGrid(grid, startIndex, endIndex = grid.endIndex, paths = shortestPaths(grid, endIndex)) {\n return Plot.plot({\n padding: 0,\n height: grid.n * 24 + 20,\n width: grid.m * 24 + 20,\n margin: 0,\n axis: null,\n color: {\n scheme: \"blues\"\n },\n marks: [\n Plot.cell(grid, {\n fill: \"2\",\n inset: 0.5\n }),\n startIndex === undefined\n ? Plot.arrow(paths, {\n filter: (j) => j >= 0,\n x1: (j, i) => grid.x(i),\n y1: (j, i) => grid.y(i),\n x2: (j, i) => grid.x(j),\n y2: (j, i) => grid.y(j),\n stroke: \"red\",\n inset: 4\n })\n : Plot.line(shortestPath(grid, startIndex, endIndex, paths), {\n stroke: \"red\",\n strokeWidth: 3\n }),\n Plot.text(grid, {\n text: \"2\"\n })\n ]\n });\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":442,"value":"function shortestPaths(grid, endIndex = grid.endIndex) {\n const visited = new Uint8Array(grid.n * grid.m);\n const distance = new Float64Array(grid.n * grid.m).fill(Infinity);\n const next = Int32Array.from({length: grid.n * grid.m}, (_, i) => i);\n next.distance = distance;\n let currentIndex = endIndex;\n distance[currentIndex] = 0;\n do {\n const currentDistance = distance[currentIndex] + 1;\n for (const nextIndex of grid.incomingEdgesAt(currentIndex)) {\n if (currentDistance < distance[nextIndex]) {\n distance[nextIndex] = currentDistance;\n next[nextIndex] = currentIndex;\n }\n }\n visited[currentIndex] = 1;\n currentIndex = d3.minIndex(distance, (d, i) => (visited[i] ? NaN : d)); // TODO priority queue?\n } while (distance[currentIndex] < Infinity);\n return next;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":403,"value":"function shortestPath(grid, startIndex = grid.startIndex, endIndex = grid.endIndex, paths = shortestPaths(grid, endIndex)) {\n const path = [grid.position(startIndex)];\n while (startIndex !== endIndex) {\n const nextIndex = paths[startIndex];\n if (nextIndex === startIndex) break; // path not found\n path.push(grid.position(nextIndex));\n startIndex = nextIndex;\n }\n return path;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":207,"value":"input = FileAttachment(\"input.txt\").text()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":209,"value":"grid = parseGrid(input)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":212,"value":"visualizeGrid(grid, grid.startIndex)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":215,"value":"shortestPath(grid).length - 1","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":305,"value":"d3.min(shortestPaths(grid).distance, (d, i) => grid.heightAt(i) === 0 ? d : NaN)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1"}} 31:"$30:body"