2f:T58f,usefulValves = { let newValves = valves.map((v) => { return { name: v.name, //rate: ["EA", "QN", "GW", /*"KB",*/ "LR", "TH", "SA" /*, "YG"*/].includes( rate: ["EA", "QN", "GW", "SA", "FL", "AT", "TO"].includes(v.name) ? //rate: true v.rate : /*0, //*/ v.rate, next: v.next.map((n) => { return { name: n, weight: 1 }; }), open: v.open }; }); let removed = true; while (removed) { removed = false; let idx = 0; while (!removed && idx < newValves.length) { let v = newValves[idx]; if (v.rate == 0 && v.name != "AA") { v.next.forEach((n) => { let nextV = newValves.find((valve) => valve.name == n.name); nextV.next = nextV.next.filter((nv) => nv.name != v.name); v.next .filter((nn) => nn.name != n.name) .forEach((vn) => { let nv = nextV.next.filter((nv) => nv.name == vn.name); if (nv.length == 1 && nv[0].weight > vn.weight + n.weight) { nv[0].weight = vn.weight + n.weight; } else if (nv.length == 0) { nextV.next.push({ name: vn.name, weight: vn.weight + n.weight }); } }); }); newValves.splice(idx, 1); removed = true; } idx++; } } return newValves; }30:Td9d,// former recursive solution ... flow = { const MINUTES = 20; let log = []; let maxFlow = 0; let path = []; let openedValves = []; let maxPath = []; let cnt = 0; let startTime = new Date(); function move(minute, nextValves, currentFlow, totalFlow) { if ( totalFlow + currentFlow + (maxRate * (MINUTES - minute + 1) * (MINUTES - minute + 2)) / 2 < maxFlow ) { return; } nextValves.forEach((next) => { //log.push("MOVE minute " + minute + " valve " + next.name); if ( openedValves.length == 0 || path .filter((p, idx) => idx >= openedValves[openedValves.length - 1]) .indexOf(next.name) < 0 ) { let valve = usefulValves.find((valve) => valve.name == next.name); if (minute < MINUTES) { path.push(valve.name); //log.push("path " + path.map((el) => el)); move( minute + next.weight, valve.next, currentFlow, totalFlow + Math.min(next.weight, MINUTES - minute) * currentFlow ); if (valve.rate > 0) { open( minute + next.weight, valve, currentFlow, totalFlow + Math.min(next.weight, MINUTES - minute) * currentFlow ); } path.pop(); } else { //log.push("result " + [totalFlow, ...path.map((el) => el)]); cnt++; } if (totalFlow > maxFlow) { maxFlow = totalFlow; maxPath.push([totalFlow].concat(path.map((el) => el))); } } }); } function open(minute, valve, currentFlow, totalFlow) { //log.push("OPEN minute " + minute + " valve " + valve.name); let newFlow = currentFlow; let removedInValves = new Map(); if (!valve.open) { path.push("open " + valve.name); valve.open = true; newFlow += valve.rate; openedValves.push(path.length - 1); if (valve.next.length == 1) { //log.push("opened " + valve.name); usefulValves.forEach((v) => { let idx = v.next.map((n) => n.name).indexOf(valve.name); if (idx >= 0) { removedInValves.set(v, v.next); v.next = v.next.filter((n, i) => i != idx); //log.push("removed " + valve.name + " in " + v.name); } }); } if (minute < MINUTES) { move(minute + 1, valve.next, newFlow, totalFlow + newFlow); } else { //log.push([totalFlow, ...path.map((el) => el)]); cnt++; } path.pop(); valve.open = false; //log.push("closed " + valve.name + " again "); openedValves.pop(); removedInValves.forEach((next, v) => { v.next = next; //log.push("added " + valve.name + " back to " + v.name); }); } else { if (minute < MINUTES) { move(minute + 1, valve.next, newFlow, totalFlow + newFlow); } else { //log.push([totalFlow, ...path.map((el) => el)]); cnt++; } } if (totalFlow > maxFlow) { maxFlow = totalFlow; maxPath.push([totalFlow].concat(path.map((el) => el))); } } //open(0, valves[0], 0, 0); move(1, usefulValves.find((v) => v.name == "AA").next, 0, 0); return { minute: MINUTES, maxPath: maxPath, maxFlow: maxFlow, cnt: cnt, time: (new Date().getTime() - startTime.getTime()) / 1000 + "sec", log: log }; }31:T4f6,// open current value, i.e. will increase flow per minute in the future openValve = function (valve) { // create state object for opened valve let openedValve = { curr: valve.curr, path: valve.path.map((p) => p), // copy! valves: new Map(), // empty Map, copied down below openedValves: valve.openedValves.map((o) => o), // copy! openedRate: valve.openedRate, closedRate: valve.closedRate, maxRate: valve.maxRate, flow: valve.flow }; // deep copy all valves (Map) by looping them valve.valves.forEach((v) => openedValve.valves.set(v.name, Object.assign({}, v)) ); // now open current valve ... let thisValve = getValve(openedValve.valves,valve.curr); openedValve.path.push("open"); thisValve.open = true; // ... and update in state object openedValve.openedValves.push(openedValve.path.length - 2); openedValve.openedRate += thisValve.rate; openedValve.closedRate -= thisValve.rate; //??? if (thisValve.next.length == 1) { openedValve.valves.forEach((v) => { v.next = v.next.filter((n, i) => i != v.next.indexOf(valve.curr)); }); } // return new object, containing values according to opened valve return openedValve; }32:Tdfd,result1 = { let log = []; let startTime = new Date(); let lastTime = new Date(); let maxFlow = 0; let bestFlows = new Map(); // start with valve "AA" and some initial values let nextValves = [ { curr: "AA", path: ["AA"], valves: new Map(), openedValves: [], openedRate: 0, closedRate: valves.reduce((acc, curr) => (acc += curr.rate), 0), flow: 0 } ]; valves.forEach((v) => nextValves[0].valves.set(v.name, v)); let minute = 0; let cnt = 0; while (minute < maxMinutes) { let newNextValves = []; minute++; // loop valves for (let valve of nextValves) { let openedOrMoved = false; // increase current flow by open valves valve.flow += valve.openedRate; if (valve.flow > maxFlow) { maxFlow = valve.flow; } /* if ( valve.flow + (maxRate * (maxMinutes - minute) * (maxMinutes - minute - 1)) / 2 < maxFlow ) { continue; } */ let key = [minute, valve.curr, valve.openedRate].join("-"); if (bestFlows.get(key) < valve.flow) { continue; } bestFlows.set(key, valve.flow); cnt++; if (new Date().getTime() - lastTime.getTime() > 1000) { lastTime = new Date(); yield { minute: minute, nextValves: nextValves, maxFlow: maxFlow, cnt: cnt, time: (new Date().getTime() - startTime.getTime()) / 1000 + "sec", log: log }; } let thisValve = getValve(valve.valves, valve.curr); // try open current valve if (!thisValve.open && thisValve.rate > 0) { if ( valve.flow + valve.openedRate + Math.abs( maxRate * (maxMinutes - minute) * (maxMinutes - minute - 2) ) / 4 > maxFlow ) { newNextValves.push(openValve(valve)); openedOrMoved = true; } } // or move to next valves thisValve.next.forEach((n) => { if ( valve.openedValves.length == 0 || valve.path .filter( (p, idx) => idx >= valve.openedValves[valve.openedValves.length - 1] ) .indexOf(n) < 0 ) { if ( valve.flow + valve.openedRate + Math.abs( maxRate * (maxMinutes - minute) * (maxMinutes - minute - 2) ) / 4 > maxFlow ) { newNextValves.push(moveToValve(valve, n)); openedOrMoved = true; } } }); if (!openedOrMoved) { if ( valve.flow + valve.openedRate + (maxRate * (maxMinutes - minute) * (maxMinutes - minute - 2)) / 4 > maxFlow ) { //newNextValves.push(moveToValve(valve, valve.curr)); } } } // loop again with new valves nextValves = newNextValves; nextValves.sort((a, b) => b.flow - a.flow); //if (minute == 6) log.push(nextValves.map((n) => n.path.map((el) => el))); yield { minute: minute, nextValves: nextValves, maxFlow: maxFlow, cnt: cnt, time: (new Date().getTime() - startTime.getTime()) / 1000 + "sec", log: log }; } // return results yield { minute: minute, nextValves: nextValves, maxFlow: maxFlow, cnt: cnt, time: (new Date().getTime() - startTime.getTime()) / 1000 + "sec", log: log }; }33:[{"id":"1acb5303a23ebeda8931f4c4f19cb72760512a1389f1b41e408f1d370914736d332d9b41caa1ea8bfc147b85bf9e1072a5e9f5bf1a06fe7f7235b3398de0601f","href":"https://static.observableusercontent.com/files/1acb5303a23ebeda8931f4c4f19cb72760512a1389f1b41e408f1d370914736d332d9b41caa1ea8bfc147b85bf9e1072a5e9f5bf1a06fe7f7235b3398de0601f","name":"input.txt","type":"text/plain","lastModified":1672789393021.227,"size":2936}] 2d:{"title":"Day 16 - ","cells":[{"id":0,"value":"# Day 16 - ","pinned":false,"hidden":false,"mode":"md"},{"id":5,"value":"inputs0 = `Valve AA has flow rate=0; tunnels lead to valves DD, II, BB\nValve BB has flow rate=13; tunnels lead to valves CC, AA\nValve CC has flow rate=2; tunnels lead to valves DD, BB\nValve DD has flow rate=20; tunnels lead to valves CC, AA, EE\nValve EE has flow rate=3; tunnels lead to valves FF, DD\nValve FF has flow rate=0; tunnels lead to valves EE, GG\nValve GG has flow rate=0; tunnels lead to valves FF, HH\nValve HH has flow rate=22; tunnel leads to valve GG\nValve II has flow rate=0; tunnels lead to valves AA, JJ\nValve JJ has flow rate=21; tunnel leads to valve II`","pinned":true,"hidden":false,"mode":"ojs"},{"id":156,"value":"inputs = FileAttachment(\"input.txt\").text()","pinned":true,"hidden":false,"mode":"ojs"},{"id":7,"value":"// split input by line and map attributes by position in line (estimated by \" \", \"=\", \";\" and \",\")\nvalves = inputs0\n .split(\"\\n\")\n .filter((line) => line.length > 0)\n .map((line) => {\n return {\n name: line.split(\" \")[1],\n rate: Number(line.split(\"=\")[1].split(\";\")[0]),\n next: line.split(\",\").map((part) => part.slice(-2)),\n open: false\n };\n })","pinned":true,"hidden":false,"mode":"ojs"},{"id":934,"value":"$2f","pinned":true,"hidden":false,"mode":"ojs"},{"id":641,"value":"// maximum possible rate across all valves\nmaxRate = Math.max(...valves.map((v) => v.rate))","pinned":true,"hidden":false,"mode":"ojs"},{"id":13,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":303,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":772,"value":"// retrieve valve object from Map by its name\ngetValve = function (allValves, valveName) {\n let valve = allValves.get(valveName);\n if (valve == undefined) {\n //???\n //return valves.find((valve) => valve.name == valveName);\n }\n return valve;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":305,"value":"// move to next valve (from-to)\nmoveToValve = function (from, to) {\n // create state object at destination\n let movedToValve = {\n curr: to,\n path: from.path.map((p) => p), // copy!\n valves: new Map(), // empty Map, copied down below\n openedValves: from.openedValves.map((o) => o), // copy!\n openedRate: from.openedRate,\n closedRate: from.closedRate,\n flow: from.flow\n };\n\n // deep copy all valves (Map) by looping them\n from.valves.forEach((v) =>\n movedToValve.valves.set(v.name, Object.assign({}, v))\n );\n\n if (from.curr != to) {\n // add destinatoon to path (if not already there, a 'no-op' move)\n movedToValve.path.push(to);\n }\n\n // return new object, containing values according to destination valve\n return movedToValve;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":307,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":506,"value":"result1","pinned":true,"hidden":false,"mode":"ojs"},{"id":603,"value":"maxFlow = result1.nextValves.sort((a, b) => b.flow - a.flow)[0]","pinned":true,"hidden":false,"mode":"ojs"},{"id":373,"value":"maxMinutes = 20","pinned":true,"hidden":false,"mode":"ojs"},{"id":166,"value":"mermaid`graph LR \n${valves\n .map((v, idx) =>\n v.next\n .map((n) =>\n valves.map((v) => v.name).indexOf(n) <= idx ||\n path.includes(v.name + \"-\" + n) ||\n path.includes(n + \"-\" + v.name)\n ? \"\"\n : v.name +\n /*(path.includes(v.name + \"-\" + n)\n ? \"----|\" + (1 + path.indexOf(v.name + \"-\" + n)) + \"|\"\n : \"-..-\")*/\n \"-.-\" +\n n\n )\n .join(\"\\n\")\n )\n .join(\"\\n\")}\n${Array.from(maxFlow.valves.values())\n .map(\n (v) =>\n v.name +\n /*v.open ||*/ (path.includes(v.name) ? \"[\" : \"\") +\n \"[\" +\n v.name +\n \" - \" +\n v.rate +\n \"]\" +\n /*v.open ||*/ (path.includes(v.name) ? \"]\" : \"\")\n )\n .join(\"\\n\")}\n${path\n .map((el, idx) => el.split(\"-\").join(\" --->|\" + (idx + 1) + \"| \"))\n .join(\"\\n\")}\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":915,"value":"mermaid`graph LR \n${valves\n .map((v, idx) =>\n v.next\n .map((n) =>\n valves.map((v) => v.name).indexOf(n) <= idx\n ? \"\"\n : v.name +\n \"[\" +\n v.name +\n \" - \" +\n v.rate +\n \"]\" +\n /*(path.includes(v.name + \"-\" + n)\n ? \"----|\" + (1 + path.indexOf(v.name + \"-\" + n)) + \"|\"\n : \"-..-\")*/\n \"-----\" +\n n\n )\n .join(\"\\n\")\n )\n .join(\"\\n\")}\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":989,"value":"mermaid`flowchart LR \n${usefulValves\n .map((v, idx) =>\n v.next.map((n) => v.name + \"[\" + v.name + \" - \" + v.rate + \"]\").join(\"\\n\")\n )\n .join(\"\\n\")}\n${usefulValves\n .map((v, idx) =>\n v.next\n .map((n) =>\n usefulValves.map((v) => v.name).indexOf(n.name) <= idx\n ? \"\"\n : v.name + \"-----|\" + n.weight + \"|\" + n.name\n )\n .join(\"\\n\")\n )\n .join(\"\\n\")}\nstyle AA stroke:#333,stroke-width:4px\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":255,"value":"path /*[\n \"DD\",\n \"open DD\",\n \"CC\",\n \"BB\",\n \"open BB\",\n \"AA\",\n \"II\",\n \"JJ\",\n \"open JJ\",\n \"II\",\n \"AA\",\n \"DD\",\n \"EE\",\n \"FF\",\n \"GG\",\n \"HH\",\n \"open HH\",\n \"GG\",\n \"FF\",\n \"EE\",\n \"open EE\",\n \"DD\",\n \"CC\",\n \"open CC\",\n \"DD\",\n \"CC\",\n \"BB\",\n \"AA\"\n] [\n \"GW\",\n \"open\",\n \"LC\",\n \"QN\",\n \"open\",\n \"GE\",\n \"AX\",\n \"EA\",\n \"open\",\n \"PL\",\n \"AA\",\n \"GJ\",\n \"TH\",\n \"open\",\n \"TP\",\n \"LR\",\n \"open\",\n \"XR\",\n \"KB\",\n \"open\",\n \"IT\",\n \"WB\",\n \"NA\",\n \"open\",\n \"XE\",\n \"XX\",\n \"open\",\n \"XE\",\n \"NA\"\n] */ = flow.maxPath[flow.maxPath.length - 1]\n .slice(1)\n //.filter((p) => p.indexOf(\"open\") < 0)\n /*maxFlow.path*/\n .map((p, idx, arr) =>\n idx > 0\n ? (arr[idx - 1].indexOf(\"open\") < 0 ? arr[idx - 1] : arr[idx - 2]) +\n (p.indexOf(\"open\") ? \"-\" + p : \"\")\n : \"AA-\" + p\n )","pinned":true,"hidden":false,"mode":"ojs"},{"id":1075,"value":"flow.maxPath[flow.maxPath.length - 1].slice(1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":415,"value":"result1.nextValves.sort((a, b) => b.flow - a.flow)[0].path","pinned":true,"hidden":false,"mode":"ojs"},{"id":420,"value":"valves.reduce(\n (acc, curr) =>\n (acc += result1.nextValves\n .sort((a, b) => b.flow - a.flow)[0]\n .open.includes(curr.name)\n ? 0\n : curr.rate),\n 0\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":422,"value":"result1.nextValves.sort((a, b) => b.flow - a.flow)[0].open","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}