30:T546,function dijkstra(nodes, edges, start, goal, maxX, maxY) { let distances = initializeDistances(nodes, start) let pathsTo = new Map() let remainingNodes = new Map(Array.from(nodes.entries())) let goalFound = false while (remainingNodes.size > 0 && !goalFound) { let s1 = findMin(remainingNodes, distances) if (s1 === goal) goalFound = true remainingNodes.delete(s1) // update the distance to s1's neighbors let [x, y] = s1.split(" ").map(parseFloat) if (x > 0) { let leftNeighbor = `${x - 1} ${y}` updateDistances(s1, leftNeighbor, edges.get(`${s1} ${leftNeighbor}`), distances, pathsTo) } if (x < maxX) { let rightNeighbor = `${x + 1} ${y}` updateDistances(s1, rightNeighbor, edges.get(`${s1} ${rightNeighbor}`), distances, pathsTo) } if (y > 0) { let upNeighbor = `${x} ${y - 1}` updateDistances(s1, upNeighbor, edges.get(`${s1} ${upNeighbor}`), distances, pathsTo) } if (y < maxY) { let downNeighbor = `${x} ${y + 1}` updateDistances(s1, downNeighbor, edges.get(`${s1} ${downNeighbor}`), distances, pathsTo) } } // Once the distances have been computed, find the path let path = [] let node = goal while (node !== start) { path.push(node) node = pathsTo.get(node) } path.push(start) return path.reverse() }31:Tb32,function aStar(nodes, edges, start, goal, maxX, maxY) { let frontier = new PriorityQueue() frontier.queue(start, 0) let shortestPathTo = new Map() let costTo = new Map([[start, 0]]) let [goalX, goalY] = goal.split(" ").map(parseFloat) while (frontier.size() > 0) { let current = frontier.dequeue() let [currentX, currentY] = current.val.split(" ").map(parseFloat) if (currentX === goalX && currentY === goalY) { // build path let pathNode = current.val let path = [] while (pathNode !== start) { path.unshift(pathNode) pathNode = shortestPathTo.get(pathNode) } path.unshift(start) return path } if (currentX > 0) { let leftNeighbor = `${currentX - 1} ${currentY}` let newCost = costTo.get(current.val) + nodes.get(leftNeighbor) if ((!costTo.has(leftNeighbor)) || (newCost < costTo.get(leftNeighbor))) { costTo.set(leftNeighbor, newCost) let priority = newCost + Math.abs(goalX - (currentX - 1)) + Math.abs(goalY - currentY) // place the neighbor at its correct position frontier.queue(leftNeighbor, priority) shortestPathTo.set(leftNeighbor, current.val) } } if (currentX < maxX) { let rightNeighbor = `${currentX + 1} ${currentY}` let newCost = costTo.get(current.val) + nodes.get(rightNeighbor) if ((!costTo.has(rightNeighbor)) || (newCost < costTo.get(rightNeighbor))) { costTo.set(rightNeighbor, newCost) let priority = newCost + Math.abs(goalX - (currentX + 1)) + Math.abs(goalY - currentY) // place the neighbor at its correct position frontier.queue(rightNeighbor, priority) shortestPathTo.set(rightNeighbor, current.val) } } if (currentY > 0) { let upNeighbor = `${currentX} ${currentY - 1}` let newCost = costTo.get(current.val) + nodes.get(upNeighbor) if ((!costTo.has(upNeighbor)) || (newCost < costTo.get(upNeighbor))) { costTo.set(upNeighbor, newCost) let priority = newCost + Math.abs(goalX - currentX) + Math.abs(goalY - (currentY - 1)) // place the neighbor at its correct position frontier.queue(upNeighbor, priority) shortestPathTo.set(upNeighbor, current.val) } } if (currentY < maxY) { let downNeighbor = `${currentX} ${currentY + 1}` let newCost = costTo.get(current.val) + nodes.get(downNeighbor) if ((!costTo.has(downNeighbor)) || (newCost < costTo.get(downNeighbor))) { costTo.set(downNeighbor, newCost) let priority = newCost + Math.abs(goalX - currentX) + Math.abs(goalY - (currentY + 1)) // place the neighbor at its correct position frontier.queue(downNeighbor, priority) shortestPathTo.set(downNeighbor, current.val) } } } return null }32:Taa3,{ let colors = ["#440154","#440256","#450457","#450559","#46075a","#46085c","#460a5d","#460b5e","#470d60","#470e61","#471063","#471164","#471365","#481467","#481668","#481769","#48186a","#481a6c","#481b6d","#481c6e","#481d6f","#481f70","#482071","#482173","#482374","#482475","#482576","#482677","#482878","#482979","#472a7a","#472c7a","#472d7b","#472e7c","#472f7d","#46307e","#46327e","#46337f","#463480","#453581","#453781","#453882","#443983","#443a83","#443b84","#433d84","#433e85","#423f85","#424086","#424186","#414287","#414487","#404588","#404688","#3f4788","#3f4889","#3e4989","#3e4a89","#3e4c8a","#3d4d8a","#3d4e8a","#3c4f8a","#3c508b","#3b518b","#3b528b","#3a538b","#3a548c","#39558c","#39568c","#38588c","#38598c","#375a8c","#375b8d","#365c8d","#365d8d","#355e8d","#355f8d","#34608d","#34618d","#33628d","#33638d","#32648e","#32658e","#31668e","#31678e","#31688e","#30698e","#306a8e","#2f6b8e","#2f6c8e","#2e6d8e","#2e6e8e","#2e6f8e","#2d708e","#2d718e","#2c718e","#2c728e","#2c738e","#2b748e","#2b758e","#2a768e","#2a778e","#2a788e","#29798e","#297a8e","#297b8e","#287c8e","#287d8e","#277e8e","#277f8e","#27808e","#26818e","#26828e","#26828e","#25838e","#25848e","#25858e","#24868e","#24878e","#23888e","#23898e","#238a8d","#228b8d","#228c8d","#228d8d","#218e8d","#218f8d","#21908d","#21918c","#20928c","#20928c","#20938c","#1f948c","#1f958b","#1f968b","#1f978b","#1f988b","#1f998a","#1f9a8a","#1e9b8a","#1e9c89","#1e9d89","#1f9e89","#1f9f88","#1fa088","#1fa188","#1fa187","#1fa287","#20a386","#20a486","#21a585","#21a685","#22a785","#22a884","#23a983","#24aa83","#25ab82","#25ac82","#26ad81","#27ad81","#28ae80","#29af7f","#2ab07f","#2cb17e","#2db27d","#2eb37c","#2fb47c","#31b57b","#32b67a","#34b679","#35b779","#37b878","#38b977","#3aba76","#3bbb75","#3dbc74","#3fbc73","#40bd72","#42be71","#44bf70","#46c06f","#48c16e","#4ac16d","#4cc26c","#4ec36b","#50c46a","#52c569","#54c568","#56c667","#58c765","#5ac864","#5cc863","#5ec962","#60ca60","#63cb5f","#65cb5e","#67cc5c","#69cd5b","#6ccd5a","#6ece58","#70cf57","#73d056","#75d054","#77d153","#7ad151","#7cd250","#7fd34e","#81d34d","#84d44b","#86d549","#89d548","#8bd646","#8ed645","#90d743","#93d741","#95d840","#98d83e","#9bd93c","#9dd93b","#a0da39","#a2da37","#a5db36","#a8db34","#aadc32","#addc30","#b0dd2f","#b2dd2d","#b5de2b","#b8de29","#bade28","#bddf26","#c0df25","#c2df23","#c5e021","#c8e020","#cae11f","#cde11d","#d0e11c","#d2e21b","#d5e21a","#d8e219","#dae319","#dde318","#dfe318","#e2e418","#e5e419","#e7e419","#eae51a","#ece51b","#efe51c","#f1e51d","#f4e61e","#f6e620","#f8e621","#fbe723","#fde725"] let samples = Math.floor(colors.length / 9) let res = [] for (let i = 0; i < 9; i++) { res.push(colors[i*samples]) } return res }33:T61f,function readInput(txt, scaleFactor = 1) { let nodes = new Map() let edges = new Map() let maxX = 0 let maxY = 0 txt.trim().split("\n").forEach( (line, y, lines) => { maxY = lines.length * scaleFactor - 1 line.split("").forEach( (char, x, chars) => { maxX = chars.length * scaleFactor - 1 for (let scaleX = 1; scaleX <= scaleFactor; scaleX++) { for (let scaleY = 1; scaleY <= scaleFactor; scaleY++) { let nodeX = x + line.length * (scaleX - 1) let nodeY = y + lines.length * (scaleY - 1) let nodeId = `${nodeX} ${nodeY}` // register the node let riskFactor = parseFloat(char) + scaleX - 1 + scaleY - 1 while (riskFactor > 9) riskFactor -= 9 nodes.set(nodeId, riskFactor) // register links to its neighbors, for now remember the target if (nodeX > 0) { edges.set(`${nodeId} ${nodeX - 1} ${nodeY}`, `${nodeX - 1} ${nodeY}`) } if (nodeX < maxX) { edges.set(`${nodeId} ${nodeX + 1} ${nodeY}`, `${nodeX + 1} ${nodeY}`) } if (nodeY > 0) { edges.set(`${nodeId} ${nodeX} ${nodeY - 1}`, `${nodeX} ${nodeY - 1}`) } if (nodeY < maxY) { edges.set(`${nodeId} ${nodeX} ${nodeY + 1}`, `${nodeX} ${nodeY + 1}`) } } } }) }) for (let [edge, target] of edges.entries()) { edges.set(edge, nodes.get(target)) } return { nodes: nodes, edges: edges, maxX: maxX, maxY, maxY } }34:[{"id":"dfda5a2441695a343e829ed09ce59b6fe054a8ff41f6a57259aa93d5d5298b2505342268da118335dc4f81c132f7a762568d38eb87e85494ed90d631d6a49f9f","href":"https://static.observableusercontent.com/files/dfda5a2441695a343e829ed09ce59b6fe054a8ff41f6a57259aa93d5d5298b2505342268da118335dc4f81c132f7a762568d38eb87e85494ed90d631d6a49f9f","name":"15_input.txt","type":"text/plain","lastModified":1639586598389.317,"size":10100}] 2e:{"title":"Day 15: Chiton","cells":[{"id":0,"value":"# Day 15: Chiton","pinned":false,"hidden":false,"mode":"md"},{"id":3,"value":"## Part 1","pinned":false,"hidden":false,"mode":"md"},{"id":46,"value":"pathDijkstra = {\n let datasetUsed = smallTest\n let nodes = datasetUsed.nodes\n let edges = datasetUsed.edges\n let goal = `${datasetUsed.maxX} ${datasetUsed.maxY}`\n return dijkstra(nodes, edges, \"0 0\", goal, datasetUsed.maxX, datasetUsed.maxY).map( node => nodes.get(node)).reduce( (curr, acc) => acc + curr) - nodes.get(\"0 0\")\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":27,"value":"function initializeDistances(nodes, startId) {\n let distances = new Map()\n for (let [id, risk] of nodes)\n distances.set(id, Infinity)\n distances.set(startId, 0)\n return distances\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":34,"value":"function findMin(nodes, distances) {\n let min = null\n let node = \"\"\n for (let nodeId of nodes.keys()) {\n if (distances.get(nodeId) < min || min === null) {\n min = distances.get(nodeId)\n node = nodeId\n }\n }\n return node\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":36,"value":"function updateDistances(node1, node2, edgeRisk, distances, pathsTo) {\n if (distances.get(node2) > distances.get(node1) + edgeRisk) {\n distances.set(node2, distances.get(node1) + edgeRisk)\n pathsTo.set(node2, node1)\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":38,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":7,"value":"## Part 2","pinned":false,"hidden":false,"mode":"md"},{"id":141,"value":"viewof scanScale = Inputs.range([1, 5], {label: \"Scan scale\", step: 1, value: 1})","pinned":false,"hidden":false,"mode":"ojs"},{"id":155,"value":"viewof displayScale = Inputs.range([1, 15], {label: \"Display scale\", step: 1, value: 1})","pinned":true,"hidden":false,"mode":"ojs"},{"id":123,"value":"{\n let datasetUsed = input\n return displayGraph(datasetUsed.nodes, datasetUsed.edges, datasetUsed.maxX, datasetUsed.maxY, pathAStar[0], false, displayScale)\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":216,"value":"pathAStar = {\n let datasetUsed = input\n let nodes = datasetUsed.nodes\n let edges = datasetUsed.edges\n let goal = `${datasetUsed.maxX} ${datasetUsed.maxY}`\n let path = aStar(nodes, edges, \"0 0\", goal, datasetUsed.maxX, datasetUsed.maxY)\n let length = path.map( node => nodes.get(node)).reduce( (curr, acc) => acc + curr) - nodes.get(\"0 0\")\n return [path, length]\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":246,"value":"class PriorityQueue {\n constructor() {\n this.values = []\n }\n\n getValueIndex(val) {\n return this.values.findIndex( storedValue => storedValue.val === val)\n }\n\n queue(val, priority) {\n let currentIndex = this.getValueIndex(val)\n if (currentIndex !== -1) {\n let previousValue = this.values.splice(currentIndex, 1)[0]\n previousValue.priority = priority\n this.values.push(previousValue)\n } else {\n this.values.push({val: val, priority: priority})\n }\n\n let index = this.values.length - 1\n let elt = this.values[index]\n while (index > 0) {\n let preceding = this.values[index - 1]\n if (preceding.priority >= elt.priority)\n break\n this.values[index - 1] = elt\n this.values[index] = preceding\n index--\n }\n }\n\n dequeue() {\n return this.values.pop()\n }\n\n size() {\n return this.values.length\n }\n\n getAt(idx) {\n if (idx >= 0 && idx < this.values.length)\n return this.values[idx]\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":210,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":10,"value":"# Input","pinned":false,"hidden":false,"mode":"md"},{"id":131,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":118,"value":"function displayGraph(nodes, edges, maxX, maxY, path=[], showEdges = false, scale = 1) {\n let colors = [\"#440154\", \"#482878\", \"#3e4989\", \"#31678e\", \"#26828e\", \"#1e9c89\", \"#32b67a\", \"#67cc5c\", \"#addc30\"].reverse()\n \n let output = `\"\n return svg`${output}`\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":23,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":21,"value":"test = readInput(`1163751742\n1381373672\n2136511328\n3694931569\n7463417111\n1319128137\n1359912421\n3125421639\n1293138521\n2311944581`, scanScale)","pinned":true,"hidden":false,"mode":"ojs"},{"id":54,"value":"smallTest = readInput(`116\n138\n213`, scanScale)","pinned":true,"hidden":false,"mode":"ojs"},{"id":102,"value":"input = FileAttachment(\"15_input.txt\").text().then(txt =>readInput(txt, scanScale))","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}