2022-16 in js

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);