31:[] 2f:{"title":"Advent of Code: 2016 Day 22","cells":[{"id":0,"value":"# Advent of Code: 2016 Day 22","pinned":false,"hidden":false,"mode":"md"},{"id":628,"value":"viewof inputChooser = Inputs.file({\n label: \"Puzzle input: \",\n accept: \".txt\",\n required: true\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":626,"value":"See [Grid Computing](https://adventofcode.com/2016/day/22).\n\n## Part 1\n\n**How many viable pairs** of nodes are there?","pinned":false,"hidden":false,"mode":"md"},{"id":514,"value":"### Parsing\n\nTo find viable pairs we need to extract the row, column, used and available values from each input text line (ignoring the first two header lines). We can do this with a regex and then using the row and column values to populate a grid array:","pinned":false,"hidden":false,"mode":"md"},{"id":381,"value":"function buildGrid(input) {\n const lines = input.split(\"\\n\").slice(2); // Skip the headers\n const grd = [];\n for (const line of lines) {\n const [_, c, r, u, a] = line\n .match(/node-x(\\d+)-y(\\d+).*T\\s+(\\d+)T\\s+(\\d+)T/)\n .map(Number);\n if (!grd[r]) {\n grd[r] = [];\n }\n grd[r][c] = { u, a };\n }\n return grd;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":516,"value":"With the grid filled with 'used,available' pairs (`{u,a}`), we can compare each grid cell with each of the others accumulating the number of pairs where the used size doesn't exceed the available capacity. While this is an expensive ${tex`O(n^4)`} process, the small grid size (38x28) makes this feasible without the need for optimisation:","pinned":false,"hidden":false,"mode":"md"},{"id":376,"value":"function countViablePairs(grid) {\n let n = 0;\n for (let r1 = 0; r1 < grid.length; r1++) {\n for (let c1 = 0; c1 < grid[0].length; c1++) {\n if (grid[r1][c1].u !== 0) {\n for (let r2 = 0; r2 < grid.length; r2++) {\n for (let c2 = 0; c2 < grid[0].length; c2++) {\n if (grid[r1][c1].u <= grid[r2][c2].a && (c1 !== c2 || r1 !== r2)) {\n n++;\n }\n }\n }\n }\n }\n }\n return n;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":12,"value":"function part1(input) {\n return countViablePairs(buildGrid(input));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":19,"value":"**${AOC.timer(part1,puzzleInput,50)}**","pinned":false,"hidden":false,"mode":"md"},{"id":155,"value":"AOC.assert(part1(puzzleInput), 1038)","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"## Part 2\n\n**What is the fewest number of steps** required to move your goal data to node-x0-y0?","pinned":false,"hidden":false,"mode":"md"},{"id":477,"value":"\n\nWe can observe that most grid cells have a capacity and payload of less than 100T, but that a few have a much larger capacity and payload. These larger cells are effectively barriers to cell swapping. We can therefore simplify the grid into cells that can be swapped and those that cannot:","pinned":false,"hidden":false,"mode":"md"},{"id":472,"value":"function swappableGrid(grd) {\n return AOC.gMap((d) => d.u < 100, grd);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":597,"value":"We can build a [graph](https://observablehq.com/@jwolondon/gds-graph) of swappable adjacent cells in order to traverse the shortest path. To do this we will create a helper function that generates a string ID for each cell position:","pinned":false,"hidden":false,"mode":"md"},{"id":559,"value":"function nodeId(row, col) {\n return `n-${row}-${col}`;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":607,"value":"And then scan adjacent cells in the grid to build the graph:","pinned":false,"hidden":false,"mode":"md"},{"id":534,"value":"function buildGraph(capacityGrid) {\n const graph = new Graph();\n const grd = swappableGrid(capacityGrid);\n\n for (let row = 0; row < grd.length; row++) {\n for (let col = 0; col < grd[0].length; col++) {\n if (grd[row][col]) {\n const currentNodeId = nodeId(row, col);\n if (grd[row][col - 1]) {\n graph.addEdge(currentNodeId, nodeId(row, col - 1));\n }\n if (grd[row][col + 1]) {\n graph.addEdge(currentNodeId, nodeId(row, col + 1));\n }\n if (grd[row - 1] && grd[row - 1][col]) {\n graph.addEdge(currentNodeId, nodeId(row - 1, col));\n }\n if (grd[row + 1] && grd[row + 1][col]) {\n graph.addEdge(currentNodeId, nodeId(row + 1, col));\n }\n }\n }\n }\n return graph;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":479,"value":"The fewest cell swaps required to update the value at [0,0] will be the shortest path from the position of the single empty cell to the adjacent left of the top right corner of the grid (containing the data packet we want), then swap-move the top-right's packet and adjacent empty cell to the top left. \n\nWe can find the cell with the empty data with a simple scanning of the grid:","pinned":false,"hidden":false,"mode":"md"},{"id":481,"value":"function emptyCell(grd) {\n for (let row = 0; row < grd.length; row++) {\n for (let col = 0; col < grd[0].length; col++) {\n if (grd[row][col].u === 0) {\n return nodeId(row, col);\n }\n }\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":621,"value":"With the graph, start point and end point we can find the length of the shortest path from empty cell to adjacent to the top-right:","pinned":false,"hidden":false,"mode":"md"},{"id":609,"value":"function stepsToTR(grd) {\n const graph = buildGraph(grd);\n const start = emptyCell(grd);\n const end = nodeId(0, grd[0].length - 2); // Cell to the left of the top-right corner\n return graph.shortestPath(start, end).length;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":623,"value":"The final result will be this shortest path followed by shuffling the top-right data to the top-left using the adjacent empty cell to allow the move at each step. This requires 5 moves per cell: data->left; empty->down; empty->left; empty->left; empty->up. This is repeated two less than the number of columns:","pinned":false,"hidden":false,"mode":"md"},{"id":14,"value":"function part2(input) {\n const grd = buildGrid(input);\n return stepsToTR(grd) + 5 * (grd[0].length - 2);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":17,"value":"**${AOC.timer(part2,puzzleInput,10)}**","pinned":false,"hidden":false,"mode":"md"},{"id":181,"value":"AOC.assert(part2(puzzleInput), 252)","pinned":false,"hidden":false,"mode":"ojs"},{"id":21,"value":"md `---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":25,"value":"import { AOC } from \"@jwolondon/aoc-utilities\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":536,"value":"import { Graph } from \"@jwolondon/gds-graph\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":22,"value":"## Data","pinned":false,"hidden":false,"mode":"md"},{"id":31,"value":"puzzleInput = inputChooser.text()","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}