diff options
Diffstat (limited to '2022/16-proboscidea-volcanium')
| -rw-r--r-- | 2022/16-proboscidea-volcanium/.eslintrc.json | 44 | ||||
| -rw-r--r-- | 2022/16-proboscidea-volcanium/example | 10 | ||||
| -rw-r--r-- | 2022/16-proboscidea-volcanium/first.js | 76 | ||||
| -rw-r--r-- | 2022/16-proboscidea-volcanium/input | 56 | ||||
| -rw-r--r-- | 2022/16-proboscidea-volcanium/package.json | 8 | ||||
| -rw-r--r-- | 2022/16-proboscidea-volcanium/priority_queue.js | 55 | ||||
| -rw-r--r-- | 2022/16-proboscidea-volcanium/second.js | 88 |
7 files changed, 337 insertions, 0 deletions
diff --git a/2022/16-proboscidea-volcanium/.eslintrc.json b/2022/16-proboscidea-volcanium/.eslintrc.json new file mode 100644 index 0000000..81e57d1 --- /dev/null +++ b/2022/16-proboscidea-volcanium/.eslintrc.json @@ -0,0 +1,44 @@ +{ + "env": { + "es2021": true, + "node": true + }, + "extends": [ + "eslint:recommended", + "plugin:node/recommended" + ], + "overrides": [ + { + "files": ["*.js"], + "rules": { + "no-constant-condition": "off" + } + } + ], + "parserOptions": { + "ecmaVersion": "latest", + "sourceType": "module" + }, + "rules": { + "indent": [ + "error", + "tab" + ], + "linebreak-style": [ + "error", + "unix" + ], + "quotes": [ + "error", + "double" + ], + "semi": [ + "error", + "always" + ], + "node/no-unsupported-features/es-syntax": [ + "error", + { "ignores": ["modules"] } + ] + } +} diff --git a/2022/16-proboscidea-volcanium/example b/2022/16-proboscidea-volcanium/example new file mode 100644 index 0000000..9f30acc --- /dev/null +++ b/2022/16-proboscidea-volcanium/example @@ -0,0 +1,10 @@ +Valve AA has flow rate=0; tunnels lead to valves DD, II, BB +Valve BB has flow rate=13; tunnels lead to valves CC, AA +Valve CC has flow rate=2; tunnels lead to valves DD, BB +Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE +Valve EE has flow rate=3; tunnels lead to valves FF, DD +Valve FF has flow rate=0; tunnels lead to valves EE, GG +Valve GG has flow rate=0; tunnels lead to valves FF, HH +Valve HH has flow rate=22; tunnel leads to valve GG +Valve II has flow rate=0; tunnels lead to valves AA, JJ +Valve JJ has flow rate=21; tunnel leads to valve II diff --git a/2022/16-proboscidea-volcanium/first.js b/2022/16-proboscidea-volcanium/first.js new file mode 100644 index 0000000..a7274aa --- /dev/null +++ b/2022/16-proboscidea-volcanium/first.js @@ -0,0 +1,76 @@ +import * as fs from "fs"; +import { PriorityQueue } from "./priority_queue.js"; + +const regexp = /Valve ([A-Z]+) has flow rate=(\d+); tunnels? leads? to valves? ([A-Z, ]+)/; + +let valves = {}; +let uv = []; // useful valves + +fs.readFileSync("input", "utf8") + .trim() + .split("\n") + .map(line => { + let a = line.match(regexp); + valves[a[1]] = { + cost: undefined, + label: a[1], + links: a[3].split(", "), + rate: a[2], + computePathCostTo: function (target) { + Object.values(valves).forEach(v => v.cost = 0); + let nq = new PriorityQueue(); + nq.enqueue(this, 0); + while (true) { + let n = nq.dequeue(); + if (n.element.label === target) { + return n.element.cost + 1; // +1 to account for opening the valve + } + n.element.links.forEach(l => { + let v = valves[l]; + if (v.cost === 0) { + v.cost = n.element.cost + 1; + nq.enqueue(v, v.cost); + } + }); + } + }, + }; + if (a[2] > 0) { + uv.push(a[1]); + } + }); + + +let paths = {}; +uv.forEach(v => { + paths["AA"+v] = valves["AA"].computePathCostTo(v); + uv.forEach(w => { + if (v !== w) { + paths[v+w] = valves[v].computePathCostTo(w); + paths[w+v] = paths[v+w]; + } + }); +}); + +let max = 0; +let parcours = [{current: "AA", actives: uv, timeLeft: 30, pressure: 0}]; +for(let i=0; i<parcours.length; i++) { + let p = parcours[i]; + p.pressure += valves[p.current].rate * p.timeLeft; + if (max < p.pressure) { + max = p.pressure; + } + p.actives.forEach(v => { + const cost = paths[p.current+v]; + if (p.timeLeft - cost > 0) { + parcours.push({ + current:v, + actives:p.actives.filter(f => f !== v), // this creates a shallow copy + timeLeft: p.timeLeft - cost, + pressure: p.pressure, + }); + } + }); +} + +console.log(max); diff --git a/2022/16-proboscidea-volcanium/input b/2022/16-proboscidea-volcanium/input new file mode 100644 index 0000000..801a1ab --- /dev/null +++ b/2022/16-proboscidea-volcanium/input @@ -0,0 +1,56 @@ +Valve XC has flow rate=0; tunnels lead to valves YK, AM +Valve ME has flow rate=0; tunnels lead to valves UU, SX +Valve EP has flow rate=0; tunnels lead to valves YS, QU +Valve GR has flow rate=0; tunnels lead to valves QZ, OG +Valve FA has flow rate=0; tunnels lead to valves DB, DP +Valve UJ has flow rate=0; tunnels lead to valves XN, CH +Valve QU has flow rate=0; tunnels lead to valves EP, YK +Valve OX has flow rate=19; tunnels lead to valves RI, PV +Valve VI has flow rate=0; tunnels lead to valves WI, XN +Valve IQ has flow rate=0; tunnels lead to valves QL, OG +Valve XO has flow rate=0; tunnels lead to valves GU, UI +Valve IY has flow rate=0; tunnels lead to valves VC, NT +Valve YS has flow rate=24; tunnel leads to valve EP +Valve XN has flow rate=7; tunnels lead to valves DG, UJ, VD, VI, OU +Valve AM has flow rate=6; tunnels lead to valves KA, NC, XC, TP, SI +Valve IH has flow rate=8; tunnels lead to valves TW, CH, WY, EC +Valve ZR has flow rate=18; tunnel leads to valve RI +Valve FP has flow rate=14; tunnels lead to valves DP, UF +Valve KA has flow rate=0; tunnels lead to valves VC, AM +Valve NC has flow rate=0; tunnels lead to valves UI, AM +Valve EC has flow rate=0; tunnels lead to valves IH, GU +Valve DG has flow rate=0; tunnels lead to valves AA, XN +Valve RI has flow rate=0; tunnels lead to valves OX, ZR +Valve NJ has flow rate=0; tunnels lead to valves YK, TW +Valve OG has flow rate=12; tunnels lead to valves GR, WY, IQ, UE +Valve IB has flow rate=0; tunnels lead to valves VB, UU +Valve RP has flow rate=0; tunnels lead to valves UI, OU +Valve OU has flow rate=0; tunnels lead to valves XN, RP +Valve NT has flow rate=0; tunnels lead to valves IY, AA +Valve MN has flow rate=0; tunnels lead to valves LX, VC +Valve SI has flow rate=0; tunnels lead to valves AM, AA +Valve VB has flow rate=0; tunnels lead to valves KT, IB +Valve UI has flow rate=4; tunnels lead to valves YI, XO, LX, NC, RP +Valve DL has flow rate=0; tunnels lead to valves GU, UE +Valve CH has flow rate=0; tunnels lead to valves UJ, IH +Valve WI has flow rate=0; tunnels lead to valves VI, VC +Valve GU has flow rate=11; tunnels lead to valves EC, XO, DL, SX +Valve KT has flow rate=17; tunnels lead to valves PV, VB +Valve TW has flow rate=0; tunnels lead to valves IH, NJ +Valve UE has flow rate=0; tunnels lead to valves DL, OG +Valve PV has flow rate=0; tunnels lead to valves KT, OX +Valve DP has flow rate=0; tunnels lead to valves FP, FA +Valve TP has flow rate=0; tunnels lead to valves VD, AM +Valve YI has flow rate=0; tunnels lead to valves AA, UI +Valve LX has flow rate=0; tunnels lead to valves UI, MN +Valve QZ has flow rate=0; tunnels lead to valves GR, UU +Valve DB has flow rate=23; tunnel leads to valve FA +Valve SX has flow rate=0; tunnels lead to valves ME, GU +Valve QL has flow rate=0; tunnels lead to valves AA, IQ +Valve YK has flow rate=16; tunnels lead to valves NJ, XC, QU +Valve VC has flow rate=5; tunnels lead to valves UF, KA, WI, IY, MN +Valve VD has flow rate=0; tunnels lead to valves TP, XN +Valve WY has flow rate=0; tunnels lead to valves IH, OG +Valve AA has flow rate=0; tunnels lead to valves YI, DG, QL, NT, SI +Valve UF has flow rate=0; tunnels lead to valves VC, FP +Valve UU has flow rate=15; tunnels lead to valves QZ, IB, ME diff --git a/2022/16-proboscidea-volcanium/package.json b/2022/16-proboscidea-volcanium/package.json new file mode 100644 index 0000000..1619895 --- /dev/null +++ b/2022/16-proboscidea-volcanium/package.json @@ -0,0 +1,8 @@ +{ + "type": "module", + "dependencies": { + "eslint": "^8.30.0", + "eslint-plugin-node": "^11.1.0", + "jslint": "^0.12.1" + } +} diff --git a/2022/16-proboscidea-volcanium/priority_queue.js b/2022/16-proboscidea-volcanium/priority_queue.js new file mode 100644 index 0000000..c1a5b65 --- /dev/null +++ b/2022/16-proboscidea-volcanium/priority_queue.js @@ -0,0 +1,55 @@ +export class QElement { + constructor(element, priority) { + this.element = element; + this.priority = priority; + } +} + +export class PriorityQueue { + constructor() { + this.items = []; + } + + enqueue(element, priority) { + var qElement = new QElement(element, priority); + var contain = false; + + for (var i = 0; i < this.items.length; i++) { + if (this.items[i].priority > qElement.priority) { + this.items.splice(i, 0, qElement); + contain = true; + break; + } + } + if (!contain) { + this.items.push(qElement); + } + } + dequeue() { + if (this.isEmpty()){ + throw "Attempting to dequeue an empty queue"; + } + return this.items.shift(); + } + front() { + if (this.isEmpty()){ + throw "Attempting to front an empty queue"; + } + return this.items[0]; + } + rear() { + if (this.isEmpty()){ + throw "Attempting to rear an empty queue"; + } + return this.items[this.items.length - 1]; + } + isEmpty() { + return this.items.length == 0; + } + printPQueue() { + var str = ""; + for (var i = 0; i < this.items.length; i++) + str += this.items[i].element + " "; + return str; + } +} diff --git a/2022/16-proboscidea-volcanium/second.js b/2022/16-proboscidea-volcanium/second.js new file mode 100644 index 0000000..18c6f84 --- /dev/null +++ b/2022/16-proboscidea-volcanium/second.js @@ -0,0 +1,88 @@ +import * as fs from "fs"; +import { PriorityQueue } from "./priority_queue.js"; + +const regexp = /Valve ([A-Z]+) has flow rate=(\d+); tunnels? leads? to valves? ([A-Z, ]+)/; + +let valves = {}; +let uv = []; // useful valves + +fs.readFileSync("input", "utf8") + .trim() + .split("\n") + .map(line => { + let a = line.match(regexp); + valves[a[1]] = { + cost: undefined, + label: a[1], + links: a[3].split(", "), + rate: a[2], + computePathCostTo: function (target) { + Object.values(valves).forEach(v => v.cost = 0); + let nq = new PriorityQueue(); + nq.enqueue(this, 0); + while (true) { + let n = nq.dequeue(); + if (n.element.label === target) { + return n.element.cost + 1; // +1 to account for opening the valve + } + n.element.links.forEach(l => { + let v = valves[l]; + if (v.cost === 0) { + v.cost = n.element.cost + 1; + nq.enqueue(v, v.cost); + } + }); + } + }, + }; + if (a[2] > 0) { + uv.push(a[1]); + } + }); + + +let paths = {}; +uv.forEach(v => { + paths["AA"+v] = valves["AA"].computePathCostTo(v); + uv.forEach(w => { + if (v !== w) { + paths[v+w] = valves[v].computePathCostTo(w); + paths[w+v] = paths[v+w]; + } + }); +}); + +let max = 0; +let parcours = [{current: "AA", actives: uv, steps: [], timeLeft: 26, pressure: 0}]; +for(let i=0; i<parcours.length; i++) { + let p = parcours[i]; + p.pressure += valves[p.current].rate * p.timeLeft; + if (max < p.pressure) { + max = p.pressure; + } + p.actives.forEach(v => { + const cost = paths[p.current+v]; + if (p.timeLeft - cost > 0) { + parcours.push({ + current:v, + actives:p.actives.filter(f => f !== v), // this creates a shallow copy + steps: [...p.steps, v], + timeLeft: p.timeLeft - cost, + pressure: p.pressure, + }); + } + }); +} +parcours.sort((a, b) => b.pressure-a.pressure); // let's process all these paths and look for two that do not intersec and improve our max +for (let i = 0; i < parcours.length; i++) { + if (parcours[i].pressure + parcours[0].pressure < max) continue; + for (let j = i+1; j < parcours.length; j++) { + if (parcours[i].pressure+parcours[j].pressure < max) continue; + if (parcours[i].steps.every(s => !parcours[j].steps.includes(s))) + if (parcours[i].pressure+parcours[j].pressure > max) { + max = parcours[i].pressure+parcours[j].pressure; + } + } +} + +console.log(max); |