31:Tcf2,result = { // Let the standalone markdown cells to render first (thanks @Fil) await Promises.delay(1000); const start = performance.now(); const spots = [0, 1, 3, 5, 7, 9, 10]; const weights = [1, 10, 100, 1000]; // Probably faster than computing 10**value let target = 0; let moves = []; let count = 0; const chars = input.replaceAll(/[^ABCD]/g, ""); const m = []; for (let i=0; i= 0) { const dst = (v + 1) * 2; if (s.mobile[v] === 0 && s.pathClear(src, dst)) { s.cost += (Math.abs(dst-src) + s.empty[v]) * weights[v]; if (s.cost >= target && target !== 0) { return; } s.moves.push([s.empty[v] - 1, v, 0, src, 2, s.cost]); if (s.remaining === 1) { target = s.cost; moves = s.moves; return; } s.h[src] = -1; s.empty[v]--; s.remaining--; done = false; } } } for (let c=0; c<4; c++) { if (s.mobile[c] > 0) { const r = s.empty[c]; const v = m[r][c]; const src = (c + 1) * 2; const dst = (v + 1) * 2; if (s.mobile[v] === 0 && s.pathClear(src, dst)) { s.cost += (Math.abs(dst-src) + r + 1 + s.empty[v]) * weights[v]; if (s.cost >= target && target !== 0) { return; } s.moves.push([r, c, s.empty[v] - 1, v, 3, s.cost]); s.empty[c]++; s.mobile[c]--; s.empty[v]--; s.remaining--; done = false; } } } } // Tried to save a few states but it actually makes things slower. // The value of "min" was then added to the cost when challenging the target in the next block. // let min = 0; // const numberOfMoves = [[0, 2, 5, 10, 17], [0, 2, 5, 11, 18], [0, 2, 5, 11, 18], [0, 2, 5, 10, 17]]; // for (let c=0; c<4; c++) { // min += numberOfMoves[c][s.mobile[c] + s.empty[c]] * 10**c; // } for (let c=0; c<4; c++) { if (s.mobile[c] > 0) { const r = s.empty[c]; const src = (c + 1) * 2; for (const dst of spots) { if (s.h[dst] === -1 && s.pathClear(src, dst)) { const v = m[r][c]; const cost = s.cost + (Math.abs(dst-src) + r + 1) * weights[v]; if (cost < target || target === 0) { const next = s.clone(); next.h[dst] = v; next.empty[c]++; next.mobile[c]--; next.cost = cost; next.moves.push([r, c, 0, dst, 1, cost]); q.push(next); } } } } } } }32:Tf75,{ play; const scale = d3.scaleLinear().range([1200, 100]).domain([1, 100]); const xMargin = 0; const yMargin = 40; const xOffset = 12; const yOffset = 24; const solution = d3.select(".solution"); solution.selectAll("text").interrupt(); solution.select("svg").remove(); const svg = solution.append("svg") .attr("width", 240) .attr("height", 190) .attr("font-family", "monospace"); const cost = svg.append("text") .attr("class", "solution-label") .attr("x", 0) .attr("y", 20) .attr("font-family", "monospace") .style("display", solution.attr("data-show") === "true" ? "block" : "none") .text("Cost: 0"); const chars = input.replaceAll(/[^ABCD]/g, ""); const numberOfRows = chars.length / 4 + 3; for (let i=0; i 1 && [2, 4, 6, 8, 10].includes(j)) || (i === numberOfRows - 1 && [3, 5, 7, 9].includes(j)) ) { svg.append("text") .attr("x", xMargin + j * xOffset) .attr("y", yMargin + i * yOffset) .text("#"); } } } let r = 0; let c = 0; for (let i=0; i 0) { process(0); } function process(i) { const moveType = result.moves[i][4]; const value = result.moves[i][5]; if (moveType === 1) { const r = result.moves[i][0]; const c = result.moves[i][1]; const h = result.moves[i][3]; svg.select(`[data-position=m${r}-${c}]`) .attr("data-position", `h${h}`) .transition() .duration(scale(solution.attr("data-speed"))) .attr("y", yMargin + yOffset) .transition() .duration(scale(solution.attr("data-speed"))) .attr("x", xMargin + (h + 1) * xOffset) .on("end", () => { cost.text(`Cost: ${value}`); if (i < result.moves.length - 1) { process(i+1); } }); } else if (moveType === 2) { const r = result.moves[i][0]; const c = result.moves[i][1]; const h = result.moves[i][3]; svg.select(`[data-position=h${h}`) .attr("data-position", `m${r}-${c}`) .transition() .duration(scale(solution.attr("data-speed"))) .attr("x", xMargin + ((c + 1) * 2 + 1) * xOffset) .transition() .duration(scale(solution.attr("data-speed"))) .attr("y", yMargin + (r + 2) * yOffset) .on("end", () => { cost.text(`Cost: ${value}`); if (i < result.moves.length - 1) { process(i+1); } }); } else { const r1 = result.moves[i][0]; const c1 = result.moves[i][1]; const r2 = result.moves[i][2]; const c2 = result.moves[i][3]; svg.select(`[data-position=m${r1}-${c1}]`) .attr("data-position", `m${r2}-${c2}`) .transition() .duration(scale(solution.attr("data-speed"))) .attr("y", yMargin + yOffset) .transition() .duration(scale(solution.attr("data-speed"))) .attr("x", xMargin + ((c2 + 1) * 2 + 1) * xOffset) .transition() .duration(scale(solution.attr("data-speed"))) .attr("y", yMargin + (r2 + 2) * yOffset) .on("end", () => { cost.text(`Cost: ${value}`); if (i < result.moves.length - 1) { process(i+1); } }); } } }33:[] 2f:{"title":"Advent of code 2021 day 23","cells":[{"id":0,"value":"# Advent of code 2021 day 23","pinned":false,"hidden":false,"mode":"md"},{"id":491,"value":"Based on this [solution](https://github.com/geofduf/aoc2021/tree/main/day23) (naive approach) written in Go. This is a quick conversion to Javascript, so forgive the poor code readability. When I find some time, I will try to clean the code responsible for keeping track of the moves / playing the solution.\n\nIt takes a few seconds to compute the answer. The solution will appear in the cell below when ready.","pinned":false,"hidden":false,"mode":"md"},{"id":638,"value":"Current input answer : **${options.show ? result.wrapper.target : \"*hidden*\"}** (${result.moves.length} moves) in **${Math.round(result.elapsed)} ms**.","pinned":false,"hidden":false,"mode":"md"},{"id":562,"value":"viewof options = Inputs.form({\n show: Inputs.toggle({label: \"Show numbers:\"}),\n speed: Inputs.range([1, 100], {step: 1, value: 95, label: \"Speed\"})\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":598,"value":"viewof play = Inputs.button(\"Play\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":447,"value":"html`\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":908,"value":"You can try different inputs by editing the cell below. Be careful with the formatting, I didn't put much effort into validating the data.","pinned":false,"hidden":false,"mode":"md"},{"id":653,"value":"#### Input","pinned":false,"hidden":false,"mode":"md"},{"id":539,"value":"input = `\n#############\n#...........#\n###B#C#B#D###\n #D#C#B#A#\n #D#B#A#C#\n #A#D#C#A#\n #########\n`","pinned":true,"hidden":false,"mode":"ojs"},{"id":919,"value":"#### Code","pinned":false,"hidden":false,"mode":"md"},{"id":5,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":299,"value":"class State {\n\n constructor(m) {\n \n if (m !== undefined) {\n \n this.h = [-1, -1, -2, -1, -2, -1, -2, -1, -2, -1, -1]; \n this.empty = [0, 0, 0, 0];\n this.mobile = [0, 0, 0, 0];\n this.remaining = m.length * 4;\n this.cost = 0;\n this.moves = [];\n\n for (let r=m.length - 1; r>=0; r--) {\n for (let c=0; c<4; c++) {\n if (m[r][c] === c && this.mobile[c] === 0) {\n this.remaining--;\n }\n else {\n this.mobile[c]++;\n }\n }\n }\n \n } \n \n }\n\n pathClear(src, dst) {\n\n if (src > dst) {\n [src, dst] = [dst, src];\n }\n\n for (let c=src+1; c= 0) {\n return false;\n }\n }\n \n return true;\n\n }\n\n clone() {\n \n const s = new State();\n\n s.h = [...this.h];\n s.empty = [...this.empty];\n s.mobile = [...this.mobile];\n s.remaining = this.remaining;\n s.cost = this.cost;\n s.moves = [...this.moves];\n \n return s;\n\n }\n\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":649,"value":"#### Appendix","pinned":false,"hidden":false,"mode":"md"},{"id":240,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":673,"value":"{\n const solution = d3.select(\".solution\");\n solution.attr(\"data-show\", options.show);\n solution.attr(\"data-speed\", options.speed);\n if (options.show) {\n solution.select(\".solution-label\").style(\"display\", \"block\");\n }\n else {\n solution.select(\".solution-label\").style(\"display\", \"none\");\n }\n}","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}