2022-19 in js

7 files changed, 344 insertions, 0 deletions

diff --git a/2022/19-Not-Enough-Minerals/.eslintrc.json b/2022/19-Not-Enough-Minerals/.eslintrc.json
new file mode 100644
index 0000000..81e57d1
--- /dev/null
+++ b/2022/19-Not-Enough-Minerals/.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/19-Not-Enough-Minerals/example b/2022/19-Not-Enough-Minerals/example
new file mode 100644
index 0000000..f39c094
--- /dev/null
+++ b/2022/19-Not-Enough-Minerals/example
@@ -0,0 +1,2 @@
+Blueprint 1: Each ore robot costs 4 ore. Each clay robot costs 2 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 2 ore and 7 obsidian.
+Blueprint 2: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 8 clay. Each geode robot costs 3 ore and 12 obsidian.
diff --git a/2022/19-Not-Enough-Minerals/first.js b/2022/19-Not-Enough-Minerals/first.js
new file mode 100644
index 0000000..1f7f64a
--- /dev/null
+++ b/2022/19-Not-Enough-Minerals/first.js
@@ -0,0 +1,106 @@
+import * as fs from "fs";
+import { PriorityQueue } from "./priority_queue.js";
+
+const regexp = /Blueprint (?<id>\d+): Each ore robot costs (?<ore_ore>\d+) ore. Each clay robot costs (?<clay_ore>\d+) ore. Each obsidian robot costs (?<obsidian_ore>\d+) ore and (?<obsidian_clay>\d+) clay. Each geode robot costs (?<geode_ore>\d+) ore and (?<geode_obsidian>\d+) obsidian./;
+
+const ORE=0, CLAY=1, OBSIDIAN=2, GEODE=3;
+const startingRobots = [1, 0, 0, 0];
+const startingRes = [0, 0, 0, 0];
+const startingTtl = 24;
+
+class Robot {
+	constructor(type, ore, clay, obsidian) {
+		this.type = type;
+		this.cost = [ore, clay, obsidian, 0];
+	}
+	canAfford(res) {
+		return this.cost.map((r, i) => res[i] >= r).reduce((acc, v) => acc && v);
+	}
+	schedule(from) { // from is the state we are scheduling from
+		const time = 1 + Math.max( // 1 turn to build + time to gather the limiting resource
+			...this.cost.map((r, i) => from.res[i] >= r ? 0 : Math.ceil((r - from.res[i])/from.robots[i])) // (cost - res)/prod_rate
+		);
+		if (time >= from.ttl) return null; // we don't have time to build this
+		return new State(
+			from.robots.map((r, i) => i === this.type ? r+1 : r),
+			from.res.map((r, i) => r + from.robots[i] * time - this.cost[i]),
+			from.ttl - time,
+		);
+	}
+}
+
+class State {
+	constructor(robots, res, ttl) {
+		this.robots = robots;
+		this.res = res;
+		this.ttl = ttl;
+	}
+	nextStates(blueprint) {
+		let ns = [];
+		if (this.ttl > 2) {
+			if (blueprint.maxes[ORE] > this.robots[ORE]) {
+				ns.push(blueprint.bots[ORE].schedule(this));
+			}
+			if (blueprint.maxes[CLAY] > this.robots[CLAY]) {
+				ns.push(blueprint.bots[CLAY].schedule(this));
+			}
+			if (blueprint.maxes[OBSIDIAN] > this.robots[OBSIDIAN] && this.robots[CLAY] > 0) {
+				ns.push(blueprint.bots[OBSIDIAN].schedule(this));
+			}
+			if (this.robots[OBSIDIAN] > 0) {
+				ns.push(blueprint.bots[GEODE].schedule(this));
+			}
+		}
+		return ns.filter(s => s !== null);
+	}
+}
+
+class Blueprint {
+	constructor(b) {
+		this.id = b.id;
+		this.bots = [
+			new Robot(ORE, b.ore_ore, 0, 0),
+			new Robot(CLAY, b.clay_ore, 0, 0),
+			new Robot(OBSIDIAN, b.obsidian_ore, b.obsidian_clay, 0),
+			new Robot(GEODE, b.geode_ore, 0, b.geode_obsidian),
+		];
+		this.maxes = this.bots.map(r => r.cost).reduce((acc, b) => b.map((v, i) => Math.max(v, acc[i])));
+	}
+	maxGeodes() {
+		let max = { max: 0 };
+		let nq = new PriorityQueue(new State(startingRobots, startingRes, startingTtl));
+		while(!nq.isEmpty()) {
+			let elt = nq.dequeue();
+			const state = elt.element;
+			if (state.ttl > 1 ) state.nextStates(this).forEach(s => nq.enqueue(s, s.res[GEODE]));
+			if (state.robots[GEODE] === 0) continue;
+			state.max = state.res[GEODE] + state.robots[GEODE] * state.ttl; // compute this state to the end of the ttl for geodes
+			if (max.max < state.max) max = state;
+		}
+		return max.max;
+	}
+}
+
+function load(filename) {
+	return fs.readFileSync(filename, "utf8")
+		.trim()
+		.split("\n")
+		.map(line => new Blueprint(line.match(regexp).groups));
+}
+
+let example = load("example");
+let input = load("input");
+
+function solve(input) {
+	let count = 0;
+	input.forEach(b => count += b.id * b.maxGeodes());
+	return count;
+}
+
+const exampleOutput = solve(example);
+if (exampleOutput !== 33) {
+	console.log("Example failed with " + exampleOutput);
+	process.exit(1); // eslint-disable-line
+}
+
+console.log(solve(input));
diff --git a/2022/19-Not-Enough-Minerals/input b/2022/19-Not-Enough-Minerals/input
new file mode 100644
index 0000000..b91fffb
--- /dev/null
+++ b/2022/19-Not-Enough-Minerals/input
@@ -0,0 +1,30 @@
+Blueprint 1: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 20 clay. Each geode robot costs 4 ore and 7 obsidian.
+Blueprint 2: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 19 clay. Each geode robot costs 3 ore and 8 obsidian.
+Blueprint 3: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 14 clay. Each geode robot costs 4 ore and 15 obsidian.
+Blueprint 4: Each ore robot costs 4 ore. Each clay robot costs 2 ore. Each obsidian robot costs 2 ore and 16 clay. Each geode robot costs 2 ore and 8 obsidian.
+Blueprint 5: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 4 ore and 8 obsidian.
+Blueprint 6: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 7 clay. Each geode robot costs 3 ore and 8 obsidian.
+Blueprint 7: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 8 clay. Each geode robot costs 2 ore and 18 obsidian.
+Blueprint 8: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 4 ore and 15 clay. Each geode robot costs 4 ore and 9 obsidian.
+Blueprint 9: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 20 clay. Each geode robot costs 2 ore and 12 obsidian.
+Blueprint 10: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 20 clay. Each geode robot costs 2 ore and 12 obsidian.
+Blueprint 11: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 3 ore and 8 obsidian.
+Blueprint 12: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 16 clay. Each geode robot costs 2 ore and 9 obsidian.
+Blueprint 13: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 15 clay. Each geode robot costs 3 ore and 20 obsidian.
+Blueprint 14: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 17 clay. Each geode robot costs 4 ore and 16 obsidian.
+Blueprint 15: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 16 clay. Each geode robot costs 3 ore and 15 obsidian.
+Blueprint 16: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 18 clay. Each geode robot costs 3 ore and 8 obsidian.
+Blueprint 17: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 11 clay. Each geode robot costs 3 ore and 8 obsidian.
+Blueprint 18: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 9 clay. Each geode robot costs 2 ore and 10 obsidian.
+Blueprint 19: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 19 clay. Each geode robot costs 4 ore and 12 obsidian.
+Blueprint 20: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 4 ore and 9 obsidian.
+Blueprint 21: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 7 clay. Each geode robot costs 3 ore and 10 obsidian.
+Blueprint 22: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 10 clay. Each geode robot costs 2 ore and 14 obsidian.
+Blueprint 23: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 15 clay. Each geode robot costs 2 ore and 13 obsidian.
+Blueprint 24: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 7 clay. Each geode robot costs 4 ore and 17 obsidian.
+Blueprint 25: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 20 clay. Each geode robot costs 2 ore and 10 obsidian.
+Blueprint 26: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 8 clay. Each geode robot costs 3 ore and 19 obsidian.
+Blueprint 27: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 20 clay. Each geode robot costs 3 ore and 14 obsidian.
+Blueprint 28: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 15 clay. Each geode robot costs 2 ore and 13 obsidian.
+Blueprint 29: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 17 clay. Each geode robot costs 3 ore and 19 obsidian.
+Blueprint 30: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 13 clay. Each geode robot costs 3 ore and 11 obsidian.
diff --git a/2022/19-Not-Enough-Minerals/package.json b/2022/19-Not-Enough-Minerals/package.json
new file mode 100644
index 0000000..23be024
--- /dev/null
+++ b/2022/19-Not-Enough-Minerals/package.json
@@ -0,0 +1,11 @@
+{
+	"type": "module",
+	"engines": {
+		"node": ">=18.10.0"
+	},
+	"dependencies": {
+		"eslint": "^8.30.0",
+		"eslint-plugin-node": "^11.1.0",
+		"jslint": "^0.12.1"
+	}
+}
diff --git a/2022/19-Not-Enough-Minerals/priority_queue.js b/2022/19-Not-Enough-Minerals/priority_queue.js
new file mode 100644
index 0000000..76e513c
--- /dev/null
+++ b/2022/19-Not-Enough-Minerals/priority_queue.js
@@ -0,0 +1,39 @@
+export class QElement {
+	constructor(element, priority) {
+		this.element = element;
+		this.priority = priority;
+	}
+}
+
+export class PriorityQueue {
+	constructor(elt) {
+		this.items = [];
+		if (elt !== undefined) {
+			this.enqueue(elt, 0);
+		}
+	}
+
+	enqueue(element, priority) {
+		let qElement = new QElement(element, priority);
+
+		for (let i = 0; i < this.items.length; ++i) {
+			if (this.items[i].priority > qElement.priority) {
+				this.items.splice(i, 0, qElement);
+				return;
+			}
+		}
+		this.items.push(qElement);
+	}
+	dequeue() {
+		return this.items.pop(); // pop highest priority, use shift() for lower priority
+	}
+	front() {
+		return this.items[0];
+	}
+	rear() {
+		return this.items[this.items.length - 1];
+	}
+	isEmpty() {
+		return this.items.length === 0;
+	}
+}
diff --git a/2022/19-Not-Enough-Minerals/second.js b/2022/19-Not-Enough-Minerals/second.js
new file mode 100644
index 0000000..37939db
--- /dev/null
+++ b/2022/19-Not-Enough-Minerals/second.js
@@ -0,0 +1,112 @@
+import * as fs from "fs";
+import { PriorityQueue } from "./priority_queue.js";
+
+const regexp = /Blueprint (?<id>\d+): Each ore robot costs (?<ore_ore>\d+) ore. Each clay robot costs (?<clay_ore>\d+) ore. Each obsidian robot costs (?<obsidian_ore>\d+) ore and (?<obsidian_clay>\d+) clay. Each geode robot costs (?<geode_ore>\d+) ore and (?<geode_obsidian>\d+) obsidian./;
+
+const ORE=0, CLAY=1, OBSIDIAN=2, GEODE=3;
+const startingRobots = [1, 0, 0, 0];
+const startingRes = [0, 0, 0, 0];
+const startingTtl = 32;
+
+class Robot {
+	constructor(type, ore, clay, obsidian) {
+		this.type = type;
+		this.cost = [ore, clay, obsidian, 0];
+	}
+	canAfford(res) {
+		return this.cost.map((r, i) => res[i] >= r).reduce((acc, v) => acc && v);
+	}
+	schedule(from) { // from is the state we are scheduling from
+		const time = 1 + Math.max( // 1 turn to build + time to gather the limiting resource
+			...this.cost.map((r, i) => from.res[i] >= r ? 0 : Math.ceil((r - from.res[i])/from.robots[i])) // (cost - res)/prod_rate
+		);
+		if (time >= from.ttl) return null; // we don't have time to build this
+		return new State(
+			from.robots.map((r, i) => i === this.type ? r+1 : r),
+			from.res.map((r, i) => r + from.robots[i] * time - this.cost[i]),
+			from.ttl - time,
+		);
+	}
+}
+
+class State {
+	constructor(robots, res, ttl) {
+		this.robots = robots;
+		this.res = res;
+		this.ttl = ttl;
+	}
+	nextStates(blueprint) {
+		let ns = [];
+		if (this.ttl > 1) {
+			if (blueprint.maxes[ORE] > this.robots[ORE]) {
+				ns.push(blueprint.bots[ORE].schedule(this));
+			}
+			if (blueprint.maxes[CLAY] > this.robots[CLAY]) {
+				ns.push(blueprint.bots[CLAY].schedule(this));
+			}
+			if (blueprint.maxes[OBSIDIAN] > this.robots[OBSIDIAN] && this.robots[CLAY] > 0) {
+				ns.push(blueprint.bots[OBSIDIAN].schedule(this));
+			}
+			if (this.robots[OBSIDIAN] > 0) {
+				ns.push(blueprint.bots[GEODE].schedule(this));
+			}
+		}
+		return ns.filter(s => s !== null);
+	}
+	hasPotentialForNewMax(max) {
+		let potential = this.res[GEODE] + this.ttl * this.robots[GEODE] + this.ttl * (this.ttl + 1) / 2;
+		return potential >= max;
+	}
+}
+
+class Blueprint {
+	constructor(b) {
+		this.id = b.id;
+		this.bots = [
+			new Robot(ORE, b.ore_ore, 0, 0),
+			new Robot(CLAY, b.clay_ore, 0, 0),
+			new Robot(OBSIDIAN, b.obsidian_ore, b.obsidian_clay, 0),
+			new Robot(GEODE, b.geode_ore, 0, b.geode_obsidian),
+		];
+		this.maxes = this.bots.map(r => r.cost).reduce((acc, b) => b.map((v, i) => Math.max(v, acc[i])));
+	}
+	maxGeodes() {
+		let max = { max: 0 };
+		let nq = new PriorityQueue(new State(startingRobots, startingRes, startingTtl));
+		while(!nq.isEmpty()) {
+			let elt = nq.dequeue();
+			const state = elt.element;
+			if (!state.hasPotentialForNewMax(max.max)) continue;
+			if (state.ttl > 1 ) state.nextStates(this).forEach(s => nq.enqueue(s, s.res[GEODE]));
+			if (state.robots[GEODE] === 0) continue;
+			state.max = state.res[GEODE] + state.robots[GEODE] * state.ttl; // compute this state to the end of the ttl for geodes
+			if (max.max < state.max) max = state;
+		}
+		return max.max;
+	}
+}
+
+function load(filename) {
+	return fs.readFileSync(filename, "utf8")
+		.trim()
+		.split("\n")
+		.map(line => new Blueprint(line.match(regexp).groups))
+		.slice(0, 3);
+}
+
+let example = load("example");
+let input = load("input");
+
+function solve(input) {
+	let count = 1;
+	input.forEach(b => count *= b.maxGeodes());
+	return count;
+}
+
+const exampleOutput = solve(example);
+if (exampleOutput !== 56 * 62) {
+	console.log("Example failed with " + exampleOutput);
+	process.exit(1); // eslint-disable-line
+}
+
+console.log(solve(input));