commit 5f6a3409d8bb742b4a42f79f7ba1885372ddb96e
parent e8d9887147cddfb6d491eb900fb9b5fa6a4ba5a4
Author: finwo <finwo@pm.me>
Date: Sun, 25 Dec 2022 00:57:04 +0100
2022/19 solution
Diffstat:
2 files changed, 234 insertions(+), 0 deletions(-)
diff --git a/2022/day-19/index.js b/2022/day-19/index.js
@@ -0,0 +1,232 @@
+const fs = require('fs');
+
+String.prototype.startsWith = function(subject) {
+ return this.substr(0, subject.length) === subject;
+};
+
+const blueprints = fs.readFileSync('input', 'utf-8')
+// const blueprints = fs.readFileSync('sample', 'utf-8')
+ .split('\n')
+ .filter(l => l)
+ .map(l => l.match(/\d+/g).map(d => parseInt(d)))
+ .map(l => ({
+ id : l[0],
+ ore : { ore: l[1] },
+ clay : { ore: l[2] },
+ obsidian: { ore: l[3], clay : l[4] },
+ geode : { ore: l[5], obsidian: l[6] },
+ }))
+;
+
+function canBuild(blueprint, resources, name) {
+ for(const resourceType in blueprint[name]) {
+ if (blueprint[name][resourceType] > resources[resourceType]) return false;
+ }
+ return true;
+}
+
+function step(resources, robots, amount = 1) {
+ for(const resourceType in robots) {
+ resources[resourceType] += robots[resourceType] * amount;
+ }
+}
+
+function when(blueprint, resources, robots, name) {
+ let timeCost = 0;
+ resources = {...resources};
+ while(!canBuild(blueprint, resources, name)) {
+ timeCost++;
+ step(resources, robots);
+ }
+ return timeCost;
+}
+
+function simulate(blueprint, time) {
+ let maxGeodes = 0;
+ let counter = 0;
+ const max = {
+ clay: blueprint.obsidian.clay,
+ ore : Math.max(
+ blueprint.geode.ore,
+ blueprint.obsidian.ore,
+ ),
+ };
+ const openset = [{
+ time: 0,
+ resources: {
+ ore : 0,
+ clay : 0,
+ obsidian : 0,
+ geode : 0,
+ },
+ robots: {
+ ore : 1,
+ clay : 0,
+ obsidian : 0,
+ geode : 0,
+ },
+ }];
+ let minlen = Infinity;
+ let maxlen = -Infinity;
+ let mintime = Infinity;
+ let logint = 1e4;
+ let logtime = Date.now() + logint;
+ while(openset.length) {
+ // Calculate END state
+ const state = openset.pop();
+ const total = {
+ ore : state.resources.ore + (state.robots.ore * (time - state.time)),
+ clay : state.resources.clay + (state.robots.clay * (time - state.time)),
+ obsidian: state.resources.obsidian + (state.robots.obsidian * (time - state.time)),
+ geode : state.resources.geode + (state.robots.geode * (time - state.time)),
+ };
+
+ if (openset.length < minlen ) minlen = openset.length;
+ if (openset.length > maxlen ) maxlen = openset.length;
+ if (state.time < mintime) mintime = state.time;
+ counter++;
+ if (Date.now() >= logtime) {
+ logtime += logint;
+ console.log(JSON.stringify({
+ time: mintime,
+ l: minlen,
+ h: maxlen, counter,
+ maxGeodes,
+ }));
+ minlen = Infinity;
+ maxlen = -Infinity;
+ mintime = Infinity;
+ counter = 0;
+ }
+
+ // Keep track of max geodes
+ if (total.geode > maxGeodes) {
+ maxGeodes = total.geode;
+ }
+
+ // Build geode robot
+ if (canBuild(blueprint, total, 'geode')) {
+ const skip = 1 + when(blueprint, state.resources, state.robots, 'geode');
+ // console.log(`Can build obsidian after after ${skip} minute(s) at ${state.time + skip}`);
+ if ((state.time + skip) < time) {
+ // console.log(` Building`);
+ openset.push({
+ time: state.time + skip,
+ resources: {
+ ore : state.resources.ore + (state.robots.ore * skip) - blueprint.geode.ore,
+ clay : state.resources.clay + (state.robots.clay * skip),
+ obsidian : state.resources.obsidian + (state.robots.obsidian * skip) - blueprint.geode.obsidian,
+ geode : state.resources.geode + (state.robots.geode * skip),
+ },
+ robots: {
+ ...state.robots,
+ geode : state.robots.geode + 1,
+ },
+ });
+ } else {
+ // console.log(` Takes too much time, ditching state: ${state.time + skip} >= ${time}`);
+ }
+ }
+
+ // Build obsidian robot
+ if (canBuild(blueprint, total, 'obsidian')) {
+ const skip = 1 + when(blueprint, state.resources, state.robots, 'obsidian');
+ // console.log(`Can build obsidian after after ${skip} minute(s) at ${state.time + skip}`);
+ if ((state.time + skip + 1) < time) {
+ // console.log(` Building`);
+ openset.push({
+ time: state.time + skip,
+ resources: {
+ ore : state.resources.ore + (state.robots.ore * skip) - blueprint.obsidian.ore,
+ clay : state.resources.clay + (state.robots.clay * skip) - blueprint.obsidian.clay,
+ obsidian : state.resources.obsidian + (state.robots.obsidian * skip),
+ geode : state.resources.geode + (state.robots.geode * skip),
+ },
+ robots: {
+ ...state.robots,
+ obsidian : state.robots.obsidian + 1,
+ },
+ });
+ } else {
+ // console.log(` Takes too much time, ditching state: ${state.time + skip} >= ${time}`);
+ }
+ }
+
+ // Build clay robot
+ if (canBuild(blueprint, total, 'clay') && state.robots.clay < max.clay) {
+ const skip = 1 + when(blueprint, state.resources, state.robots, 'clay');
+ // console.log(`Can build clay after after ${skip} minute(s) at ${state.time + skip}`);
+ if ((state.time + skip + 2) < time) {
+ // console.log(` Building`);
+ openset.push({
+ time: state.time + skip,
+ resources: {
+ ore : state.resources.ore + (state.robots.ore * skip) - blueprint.clay.ore,
+ clay : state.resources.clay + (state.robots.clay * skip),
+ obsidian : state.resources.obsidian + (state.robots.obsidian * skip),
+ geode : state.resources.geode + (state.robots.geode * skip),
+ },
+ robots: {
+ ...state.robots,
+ clay : state.robots.clay + 1,
+ },
+ });
+ } else {
+ // console.log(` Takes too much time, ditching state: ${state.time + skip} >= ${time}`);
+ }
+
+ // state.time += skip;
+ // step(state.resources, state.robots, skip);
+ // state.resources.ore -= blueprint.clay.ore;
+
+ // console.log(`Can build clay after after ${skip} minute(s)`);
+ }
+
+ // Build ore robot
+ if (canBuild(blueprint, total, 'ore') && state.robots.ore < max.ore) {
+ const skip = 1 + when(blueprint, state.resources, state.robots, 'ore');
+ // console.log(`Can build ore after after ${skip} minute(s) at ${state.time + skip}`);
+ if ((state.time + skip + 1) < time) {
+ // console.log(` Building`);
+ openset.push({
+ time: state.time + skip,
+ resources: {
+ ore : state.resources.ore + (state.robots.ore * skip) - blueprint.ore.ore,
+ clay : state.resources.clay + (state.robots.clay * skip),
+ obsidian : state.resources.obsidian + (state.robots.obsidian * skip),
+ geode : state.resources.geode + (state.robots.geode * skip),
+ },
+ robots: {
+ ...state.robots,
+ ore : state.robots.ore + 1,
+ },
+ });
+ } else {
+ // console.log(` Takes too much time, ditching state: ${state.time + skip} >= ${time}`);
+ }
+ }
+
+ // Sort by most important resources
+ openset.sort((a, b) => {
+ return 0 ||
+ (a.resources.geode - b.resources.geode ) ||
+ (a.resources.obsidian - b.resources.obsidian) ||
+ (a.resources.clay - b.resources.clay ) ||
+ (a.resources.ore - b.resources.ore );
+ });
+
+ }
+
+ console.log({ id: blueprint.id, time, maxGeodes });
+ return maxGeodes;
+}
+
+let step1 = 0;
+let step2 = 1;
+for(let i=0; i<blueprints.length; i++)
+ step1 += simulate(blueprints[i], 24) * blueprints[i].id;
+
+for(let i=0; i<Math.min(blueprints.length, 3); i++)
+ step2 *= simulate(blueprints[i], 32);
+
+console.log({ step1, step2 });
diff --git a/2022/day-19/sample b/2022/day-19/sample
@@ -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.
