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/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 ++++++++++++++++++++++++++ 7 files changed, 344 insertions(+) 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 (limited to '2022/19-Not-Enough-Minerals') 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