1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
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));
|
