31:T4f3,function move(initGrid, [rowStart, colStart], [rowEnd, colEnd], t) { const [nRows, nCols] = [initGrid.length, initGrid[0].length]; const visited = blank(initGrid); visited[rowStart][colStart] = t; while (visited[rowEnd][colEnd] === ".") { const grid = gridAt(initGrid, t + 1); const spaces = []; // Where can we get to in one step from all the cells that could be visited at this time? for (let row = 0; row < nRows; row++) { for (let col = 0; col < nCols; col++) { if (visited[row][col] === t) { if (col < nCols - 1 && grid[row][col + 1] === ".") { spaces.push([row, col + 1]); // Can move right } if (row < nRows - 1 && grid[row + 1][col] === ".") { spaces.push([row + 1, col]); // Can move down } if (grid[row][col] === ".") { spaces.push([row, col]); // Can wait } if (row > 0 && grid[row - 1][col] === ".") { spaces.push([row - 1, col]); // Can move up } if (col > 0 && grid[row][col - 1] === ".") { spaces.push([row, col - 1]); // Can move left } } } } spaces.forEach(([row, col]) => (visited[row][col] = t + 1)); t++; } return t; }32:T4ad,## Reflection Another day, another graph search. This time with a changing set of edges as time progresses. Not an especially hard puzzle except I had a number of silly errors that gave me credible but wrong answers. My first attempts modelled the state such that it could be incremented time step at a time. This required cells containing multiple blizzards to be stored such that they could be separated for moving on to the next time step. This worked, but was slow. A useful insight was that the state at any given time could be found by moving every initial cell by the given time offset modulus the interior grid width or height (depending on direction). Since the initial state contains no overlaps, I didn't need to worry about storing multiple blizzards in a single location. The second insight was we don't need to store the path itself, just how many steps between origin and destination. This allowed all visited cells to be represented by a grid storing the time they were most recently visited. This allowed a frontier of cells at any give time to be expanded, including over previously visited cells. As soon as that frontier hits the destination for the first time we can stop.33:[] 2f:{"title":"Advent of Code: 2022 Day 24","cells":[{"id":0,"value":"# Advent of Code: 2022 Day 24\n\nSee [Blizzard Basin](https://adventofcode.com/2022/day/24).","pinned":false,"hidden":false,"mode":"md"},{"id":886,"value":"viewof inputChooser = Inputs.file({\n label: \"Puzzle input: \",\n accept: \".txt\",\n required: true\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":884,"value":"## Part 1\n\n**What is the fewest number of minutes required to avoid the blizzards and reach the goal?**","pinned":false,"hidden":false,"mode":"md"},{"id":858,"value":"Parsing is simple, storing the map as a grid.","pinned":false,"hidden":false,"mode":"md"},{"id":196,"value":"function parse(input) {\n return input.split(\"\\n\").map((l) => l.split(\"\"));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":860,"value":"We need to be able to know the location of the blizzards at any point in time. Because each blizzard moves linearly in unit steps, we can calculate its position for any time, rotating when a blizzard reaches an edge cell.","pinned":false,"hidden":false,"mode":"md"},{"id":683,"value":"function blank(grid) {\n const [nRows, nCols] = [grid.length, grid[0].length];\n return AOC.gMapWithLocation(\n (r, c, v) =>\n r === 0 || r === nRows - 1 || c === 0 || c === nCols - 1 ? v : \".\",\n grid\n );\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":232,"value":"function gridAt(grid, t) {\n const [nRows, nCols] = [grid.length, grid[0].length];\n const grid2 = blank(grid);\n for (let r = 1; r < nRows - 1; r++) {\n for (let c = 1; c < nCols - 1; c++) {\n if (grid[r][c] === \">\") {\n grid2[r][((c - 1 + t) % (nCols - 2)) + 1] = \">\";\n } else if (grid[r][c] === \"<\") {\n grid2[r][((c - 1 + t * (nCols - 2) - t) % (nCols - 2)) + 1] = \"<\";\n } else if (grid[r][c] === \"v\") {\n grid2[((r - 1 + t) % (nRows - 2)) + 1][c] = \"v\";\n } else if (grid[r][c] === \"^\") {\n grid2[((r - 1 + t * (nRows - 2) - t) % (nRows - 2)) + 1][c] = \"^\";\n }\n }\n }\n return grid2;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":862,"value":"The main search algorithm considers all the cells that could be visited in the nest time step from all the cells visitable at the current time. This could be in any direction and could involve visiting previously visited cells. If a cell is visited for the first time, this will be shortest time to get to that cell. We therefore stop expanding the visited cells as soon as we first visit the destination location.","pinned":false,"hidden":false,"mode":"md"},{"id":772,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":12,"value":"function part1(input) {\n const initGrid = parse(input);\n const [nRows, nCols] = [initGrid.length, initGrid[0].length];\n return move(initGrid, [0, 1], [nRows - 1, nCols - 2], 0);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":19,"value":"**${AOC.timer(part1,puzzleInput,1)}**","pinned":false,"hidden":false,"mode":"md"},{"id":8,"value":"## Part 2\n**What is the fewest number of minutes required to reach the goal, go back to the start, then reach the goal again?**","pinned":false,"hidden":false,"mode":"md"},{"id":877,"value":"The main search work was done for Part 1. We just now need to swap origin and destination for the return journey, along with the time to start the simulation. One more repeat journey from original source to destination completes the trip.","pinned":false,"hidden":false,"mode":"md"},{"id":14,"value":"function part2(input) {\n const initGrid = parse(input);\n const [nRows, nCols] = [initGrid.length, initGrid[0].length];\n const topLeft = [0, 1];\n const bottomRight = [nRows - 1, nCols - 2];\n\n const trip1 = move(initGrid, topLeft, bottomRight, 0);\n const trip2 = move(initGrid, bottomRight, topLeft, trip1);\n return move(initGrid, topLeft, bottomRight, trip2);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":17,"value":"**${AOC.timer(part2,puzzleInput,1)}**","pinned":false,"hidden":false,"mode":"md"},{"id":666,"value":"$32","pinned":false,"hidden":false,"mode":"md"},{"id":21,"value":"md `---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":25,"value":"import { Renderer } from \"@jwolondon/renderer\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":310,"value":"import { AOC } from \"@jwolondon/aoc-utilities\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":22,"value":"## Data","pinned":false,"hidden":false,"mode":"md"},{"id":28,"value":"test1 = `#.######\n#>>.<^<#\n#.<..<<#\n#>v.><>#\n#<^v^^>#\n######.#`","pinned":false,"hidden":false,"mode":"ojs"},{"id":31,"value":"puzzleInput = inputChooser.text()","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}