aboutsummaryrefslogtreecommitdiff
path: root/2022
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--2022/16-proboscidea-volcanium/first.js3
-rw-r--r--2022/16-proboscidea-volcanium/priority_queue.js36
-rw-r--r--2022/16-proboscidea-volcanium/second.js3
-rw-r--r--2022/18-Boiling-Boulders/second.js4
-rw-r--r--2022/19-Not-Enough-Minerals/.eslintrc.json44
-rw-r--r--2022/19-Not-Enough-Minerals/example2
-rw-r--r--2022/19-Not-Enough-Minerals/first.js106
-rw-r--r--2022/19-Not-Enough-Minerals/input30
-rw-r--r--2022/19-Not-Enough-Minerals/package.json11
-rw-r--r--2022/19-Not-Enough-Minerals/priority_queue.js39
-rw-r--r--2022/19-Not-Enough-Minerals/second.js112
11 files changed, 358 insertions, 32 deletions
diff --git a/2022/16-proboscidea-volcanium/first.js b/2022/16-proboscidea-volcanium/first.js
index a7274aa..504ad54 100644
--- a/2022/16-proboscidea-volcanium/first.js
+++ b/2022/16-proboscidea-volcanium/first.js
@@ -18,8 +18,7 @@ fs.readFileSync("input", "utf8")
rate: a[2],
computePathCostTo: function (target) {
Object.values(valves).forEach(v => v.cost = 0);
- let nq = new PriorityQueue();
- nq.enqueue(this, 0);
+ let nq = new PriorityQueue(this);
while (true) {
let n = nq.dequeue();
if (n.element.label === target) {
diff --git a/2022/16-proboscidea-volcanium/priority_queue.js b/2022/16-proboscidea-volcanium/priority_queue.js
index c1a5b65..b9be08b 100644
--- a/2022/16-proboscidea-volcanium/priority_queue.js
+++ b/2022/16-proboscidea-volcanium/priority_queue.js
@@ -6,50 +6,34 @@ export class QElement {
}
export class PriorityQueue {
- constructor() {
+ constructor(elt) {
this.items = [];
+ if (elt !== undefined) {
+ this.enqueue(elt, 0);
+ }
}
enqueue(element, priority) {
- var qElement = new QElement(element, priority);
- var contain = false;
+ let qElement = new QElement(element, priority);
- for (var i = 0; i < this.items.length; i++) {
+ for (let i = 0; i < this.items.length; ++i) {
if (this.items[i].priority > qElement.priority) {
this.items.splice(i, 0, qElement);
- contain = true;
- break;
+ return;
}
}
- if (!contain) {
- this.items.push(qElement);
- }
+ this.items.push(qElement);
}
dequeue() {
- if (this.isEmpty()){
- throw "Attempting to dequeue an empty queue";
- }
- return this.items.shift();
+ return this.items.shift(); // pop highest priority, use shift() for lower priority
}
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;
+ return this.items.length === 0;
}
}
diff --git a/2022/16-proboscidea-volcanium/second.js b/2022/16-proboscidea-volcanium/second.js
index 18c6f84..3b41645 100644
--- a/2022/16-proboscidea-volcanium/second.js
+++ b/2022/16-proboscidea-volcanium/second.js
@@ -18,8 +18,7 @@ fs.readFileSync("input", "utf8")
rate: a[2],
computePathCostTo: function (target) {
Object.values(valves).forEach(v => v.cost = 0);
- let nq = new PriorityQueue();
- nq.enqueue(this, 0);
+ let nq = new PriorityQueue(this);
while (true) {
let n = nq.dequeue();
if (n.element.label === target) {
diff --git a/2022/18-Boiling-Boulders/second.js b/2022/18-Boiling-Boulders/second.js
index a1f57a7..18101ee 100644
--- a/2022/18-Boiling-Boulders/second.js
+++ b/2022/18-Boiling-Boulders/second.js
@@ -28,7 +28,7 @@ function solve(input) {
let [x, y, z] = line.split(",").map(n => parseInt(n));
min = Math.min(min, x, y, z);
max = Math.max(max, x, y, z);
- })
+ });
min -=1;
max +=1;
// start with an edge and fill up the space
@@ -40,7 +40,7 @@ function solve(input) {
const eltstr = elt.join(",");
const [x, y, z] = elt;
if (x < min || x > max || y < min || y > max || z < min || z > max) continue;
- if (visited.has(eltstr)) continue
+ if (visited.has(eltstr)) continue;
if (input.includes(eltstr)) continue;
visited.add(eltstr);
count += countSides(x, y, z, input);
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));
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-10 10:58:25 +0000