From 3430a7074b85b12bb16d9906c04e857448e85f44 Mon Sep 17 00:00:00 2001 From: Julien Dessaux Date: Wed, 28 Dec 2022 20:03:29 +0100 Subject: 2022-19 in js --- 2022/16-proboscidea-volcanium/first.js | 3 +- 2022/16-proboscidea-volcanium/priority_queue.js | 36 +++----- 2022/16-proboscidea-volcanium/second.js | 3 +- 2022/18-Boiling-Boulders/second.js | 4 +- 2022/19-Not-Enough-Minerals/.eslintrc.json | 44 ++++++++++ 2022/19-Not-Enough-Minerals/example | 2 + 2022/19-Not-Enough-Minerals/first.js | 106 ++++++++++++++++++++++ 2022/19-Not-Enough-Minerals/input | 30 +++++++ 2022/19-Not-Enough-Minerals/package.json | 11 +++ 2022/19-Not-Enough-Minerals/priority_queue.js | 39 +++++++++ 2022/19-Not-Enough-Minerals/second.js | 112 ++++++++++++++++++++++++ 11 files changed, 358 insertions(+), 32 deletions(-) create mode 100644 2022/19-Not-Enough-Minerals/.eslintrc.json create mode 100644 2022/19-Not-Enough-Minerals/example create mode 100644 2022/19-Not-Enough-Minerals/first.js create mode 100644 2022/19-Not-Enough-Minerals/input create mode 100644 2022/19-Not-Enough-Minerals/package.json create mode 100644 2022/19-Not-Enough-Minerals/priority_queue.js create mode 100644 2022/19-Not-Enough-Minerals/second.js 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 (?\d+): Each ore robot costs (?\d+) ore. Each clay robot costs (?\d+) ore. Each obsidian robot costs (?\d+) ore and (?\d+) clay. Each geode robot costs (?\d+) ore and (?\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 (?\d+): Each ore robot costs (?\d+) ore. Each clay robot costs (?\d+) ore. Each obsidian robot costs (?\d+) ore and (?\d+) clay. Each geode robot costs (?\d+) ore and (?\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)); -- cgit v1.2.3