2d:null 2e:["$","title",null,{"children":"Advent of Code: 2023 Day 16 | Jo Wood | Observable"}] 33:T6f4,{ const { photons, history } = view; const grid = AOC.gMap((c) => 0, parse(puzzleInput)); const [nRows, nCols] = [grid.length, grid[0].length]; const rcHash = (hash) => Math.floor(hash / 9); const toPos = (rcHash) => ({ row: Math.floor(rcHash / nCols), col: rcHash % nCols }); const trails = [...new Set([...history].map(rcHash))].map(toPos); return Plot.plot({ style: `background:black; font-family:'Source Code Pro'; font-size:18;`, height: 900, width: 900, margin: 10, marginTop: 50, x: { domain: [0, nCols] }, y: { domain: [0, nRows], reverse: true }, marks: [ Plot.rect(trails, { x1: (d) => d.col, y1: (d) => d.row, x2: (d) => d.col + 1, y2: (d) => d.row + 1, fill: "rgba(150,255,150,0.2)" }), Plot.arrow(tileData, { x1: "x1", y1: "y1", x2: "x2", y2: "y2", stroke: "green", headLength: 0 }), Plot.dot(photons, { x: (d) => d.c + 0.5, y: (d) => d.r + 0.5, fill: "yellow", opacity: 0.1, r: 12 }), Plot.dot(photons, { x: (d) => d.c + 0.5, y: (d) => d.r + 0.5, fill: "yellow", opacity: 0.25, r: 6 }), Plot.dot(photons, { x: (d) => d.c + 0.5, y: (d) => d.r + 0.5, fill: "rgb(255,255,50)", r: 2 }), Plot.text([`Energised tiles: ${trails.length}`], { x: nCols, y: 0, dy: -20, textAnchor: "end", fill: "rgb(0,255,0)" }), Plot.text([`Enervated tiles: ${nRows * nCols - trails.length}`], { x: 0, y: 0, dy: -20, textAnchor: "start", fill: "green" }) ] }); }34:T5cc,function* movePhotons({ photons, history }, optics) { reset; const [nRows, nCols] = [optics.length, optics[0].length]; const inGrid = (r, c, nRows, nCols) => r >= 0 && c >= 0 && r < nRows && c < nCols; while (photons.length > 0) { const next = []; for (const b of photons) { const hash = b.r * nCols * 9 + b.c * 9 + (b.dir[0] + 1) + (b.dir[1] + 1) * 3; if ( b.r >= 0 && b.c >= 0 && b.r < nRows && b.c < nCols && !history.has(hash) ) { history.add(hash); const optic = optics[b.r][b.c]; const newDir = rotate(b.dir, optic); if ( (optic === "-" && newDir[0] !== 0) || (optic === "|" && newDir[1] !== 0) ) { const altDir = optic === "-" ? [0, -1] : [1, 0]; const oppDir = optic === "-" ? [0, 1] : [-1, 0]; if (inGrid(b.r + altDir[0], b.c + altDir[1], nRows, nCols)) { next.push({ r: b.r, c: b.c, dir: altDir }); } if (inGrid(b.r + oppDir[0], b.c + oppDir[1], nRows, nCols)) { next.push({ r: b.r, c: b.c, dir: oppDir }); } } else { b.dir = newDir; if (inGrid(b.r + b.dir[0], b.c + b.dir[1], nRows, nCols)) { next.push({ r: b.r + b.dir[0], c: b.c + b.dir[1], dir: b.dir }); } } } } photons = next; yield Promises.delay(60, { photons, history }); } return { photons, history }; }35:[] 31:{"id":"301ccf9619b342c5","slug":"advent-of-code-2023-day-16","title":"Advent of Code: 2023 Day 16","thumbnail":"3beca8b14a715c1b439ed78f36fb96c5520edd245545b56dee9dd9a5ba5c99d1","access_level":"public","create_time":"$D2023-11-25T08:30:26.783Z","update_time":"$D2024-12-02T18:33:18.482Z","view_time":null,"first_public_time":"$D2023-12-16T10:23:37.635Z","has_unpublished_edits":null,"fork":true,"stars":3,"starred":false,"owner":{"type":"team","id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":"starter_2024"},"version":638,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"e2432cc13dc447d3","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":null}],"members":[{"type":"individual","id":"e2432cc13dc447d3","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":null,"role":"editor"}],"comments":[{"id":"1be1547f928b0c12","reply_to_id":null,"content":"My solution was to save the input as a text file attachment, instead of pasting it in a cell as I usually do.","create_time":"$D2023-12-17T22:17:21.672Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null}}],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"7c06b943868869e4","slug":"advent-of-code-2023","title":"Ξ🎄Advent of Code 2023","owner":{"id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood"}},"type":"notebook","body":{"title":"Advent of Code: 2023 Day 16","cells":[{"id":0,"value":"# Advent of Code: 2023 Day 16\n\nSee [The Floor Will Be Lava](https://adventofcode.com/2023/day/16).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":620,"value":"viewof inputChooser = Inputs.file({\n label: \"Puzzle input: \",\n accept: \".txt\",\n required: true\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":624,"value":"## Part 1\nWith the beam starting in the top-left heading right, **how many tiles end up being energized?**","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":57,"value":"### Parsing\n\nTo avoid problems with non-escaped `\\` symbols, I've replaced each input `\\` with an `╲` (and for visual symmetry, `/` with `╱`). Then the parsing is a simple case of transferring the symbols into a 2d array.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":73,"value":"function parse(input) {\n return input.split(\"\\n\").map((row) => row.split(\"\"));\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":285,"value":"### Algorithm\n\nWe will need to store both the position and direction of a photon as it moves around the grid. Because the mirrors will rotate directions, we can store direction as a simple 2-element vector, with north as `[0,-1]`, east as `[0,1]` etc.\n\nThis allows us to provide a rotate function that will change direction whenever a mirror is encountered:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":232,"value":"function rotate(dir, tile) {\n if (tile === \"╱\") {\n return [-dir[1], -dir[0]]; // Mirror rotates beam clockwise 90 degrees\n }\n if (tile === \"╲\") {\n return [dir[1], dir[0]]; // Mirror rotates beam anticlockwise 90 degrees\n }\n return dir;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":290,"value":"The core beam traversal process starts with a queue of photons containing just one eastward photon in the top-left of the grid. It pops off the first photon in the queue and sends it in the direction of travel, rotating as necessary when it hits a mirror. If it falls off the edge of the grid we move on to the next item in the queue. If the photon encounters a splitter, it pushes a new photon pointing in the right direction onto the queue and then continues to move the existing photon.\n\nIt is possible that a beam path can fall into an infinite internal loop. so additionally we need to keep track of previous photon positions and directions. If we ever encounter one that matches the current photon's position and direction we can stop processing that photon.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":180,"value":"function energised(tiles, start = { r: 0, c: 0, dir: [0, 1] }) {\n const grid = AOC.gMap(() => 0, tiles);\n const [nRows, nCols] = [grid.length, grid[0].length];\n const history = new Set();\n const photons = [start];\n grid[start.r][start.c] = 1;\n\n while (photons.length > 0) {\n const b = photons.shift();\n const hash =\n b.r * nCols * 9 + b.c * 9 + (b.dir[0] + 1) + (b.dir[1] + 1) * 3;\n if (!history.has(hash)) {\n history.add(hash);\n const tile = tiles[b.r][b.c];\n b.dir = rotate(b.dir, tile);\n if (tile === \"-\" && b.dir[0] !== 0) {\n photons.push({ r: b.r, c: b.c, dir: [0, -1] });\n b.dir = [0, 1];\n } else if (tile === \"|\" && b.dir[1] !== 0) {\n photons.push({ r: b.r, c: b.c, dir: [1, 0] });\n b.dir = [-1, 0];\n }\n const [r, c] = [b.r + b.dir[0], b.c + b.dir[1]];\n if (r >= 0 && c >= 0 && r < nRows && c < nCols) {\n grid[r][c] = 1;\n photons.push({ r: r, c: c, dir: b.dir });\n }\n }\n }\n return AOC.sum(grid.flat());\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"function part1(input) {\n return energised(parse(puzzleInput));\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":52,"value":"**${AOC.timer(part1,puzzleInput,100)}**","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":347,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":432,"value":"viewof reset = Inputs.button(\"Reset\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"## Part 2\nFind the initial beam configuration that energizes the largest number of tiles; **how many tiles are energized in that configuration?**","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":302,"value":"The Part 1 approach, which is parameterised to work with any start position, is fast enough that we can simply test all possible starts and find the largest one.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":212,"value":"function maxEnergised(tiles) {\n const [nRows, nCols] = [tiles.length, tiles[0].length];\n let maxE = 0;\n\n for (let r = 0; r < nRows; r++) {\n maxE = Math.max(\n maxE,\n energised(tiles, { r: r, c: 0, dir: [0, 1] }),\n energised(tiles, { r: r, c: nCols - 1, dir: [0, -1] })\n );\n }\n\n for (let c = 1; c < nCols - 1; c++) {\n maxE = Math.max(\n maxE,\n energised(tiles, { r: 0, c: c, dir: [1, 0] }),\n energised(tiles, { r: nRows - 1, c: c, dir: [-1, 0] })\n );\n }\n return maxE;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"function part2(input) {\n return maxEnergised(parse(input));\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":34,"value":"**${AOC.timer(part2,puzzleInput,1)}**","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$$","database":"$undefined"},{"id":61,"value":"## Reflection\n\nThis wasn't too hard a problem for a mid-month weekend puzzle. I had some initial problems with Observable trying to be clever with the input text that could contain pairs of `\\` symbols, so I thought it safer to replace the mirror symbols with unicode characters that would not trigger escapes.\n\nThe worked example in the instructions where it symbolises where a finite number of different beam trajectories hit each cell initially distracted me from the possibility of some total internal reflection resulting in infinite looping pathways. But keeping track of the beam history was sufficient to deal with that possibility.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":611,"value":"My routine effectively depth-first searches the space, dealing with each photon in turn, adding new split photons to process to the end of the queue. For the visualization I used a breadth-first approach so all photons could be seen in 'real time'. The history set, which is used to stop infinite looping was useful in the visualization for showing the trails of energised tiles left by the photons.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":20,"value":"---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":22,"value":"import { AOC } from \"@jwolondon/aoc-utilities\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"## Data","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":29,"value":"testInput = `.|...╲....\n|.-.╲.....\n.....|-...\n........|.\n..........\n.........╲\n....╱.╲╲..\n.-.-╱..|..\n.|....-|.╲\n..╱╱.|....`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"puzzleInput = (await inputChooser.text())\n .replace(/\\\\/g, \"╲\")\n .replace(/\\//g, \"╱\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":319,"value":"_Visualization related functions:_","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":473,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":435,"value":"view = movePhotons(\n {\n photons: [{ r: 0, c: 0, dir: [0, 1] }],\n history: new Set()\n },\n parse(puzzleInput)\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":349,"value":"","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":359,"value":"tileData = {\n const tiles = parse(puzzleInput);\n const oData = [];\n const symbolLen = 0.35;\n for (let row = 0; row < tiles.length; row++) {\n for (let col = 0; col < tiles[0].length; col++) {\n if (tiles[row][col] != \".\") {\n let [x1, y1, x2, y2] = [col + 0.5, row + 0.5, col + 0.5, row + 0.5];\n switch (tiles[row][col]) {\n case \"-\":\n x1 -= symbolLen;\n x2 += symbolLen;\n break;\n case \"|\":\n y1 -= symbolLen;\n y2 += symbolLen;\n break;\n case \"╱\":\n x1 -= symbolLen;\n x2 += symbolLen;\n y1 += symbolLen;\n y2 -= symbolLen;\n break;\n case \"╲\":\n x1 -= symbolLen;\n x2 += symbolLen;\n y1 -= symbolLen;\n y2 += symbolLen;\n break;\n }\n\n oData.push({\n x1: x1,\n y1: y1,\n x2: x2,\n y2: y2\n });\n }\n }\n }\n return oData;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 32:"$31:body"