aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--2022/16-proboscidea-volcanium/.eslintrc.json44
-rw-r--r--2022/16-proboscidea-volcanium/example10
-rw-r--r--2022/16-proboscidea-volcanium/first.js76
-rw-r--r--2022/16-proboscidea-volcanium/input56
-rw-r--r--2022/16-proboscidea-volcanium/package.json8
-rw-r--r--2022/16-proboscidea-volcanium/priority_queue.js55
-rw-r--r--2022/16-proboscidea-volcanium/second.js88
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);
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-10 14:27:35 +0000