commit 23a6a2543bb57aeeb2a62445624e01af95b7145c
parent 96935fb8eb497d4d111e645ffc57b8e0792fea56
Author: finwo <finwo@pm.me>
Date: Fri, 16 Dec 2022 17:17:02 +0100
2022/16 solution
Diffstat:
2 files changed, 173 insertions(+), 0 deletions(-)
diff --git a/2022/day-16/index.js b/2022/day-16/index.js
@@ -0,0 +1,163 @@
+const fs = require('fs');
+const through = require('through2');
+const line_by_line = require('../common/line-for-line');
+
+String.prototype.startsWith = function(subject) {
+ return this.substr(0, subject.length) === subject;
+};
+
+const valves = {};
+const map = {};
+const nmap = {};
+const rmap = [];
+
+
+// Consistent-cost Dijkstra
+function costFinder(from, to) {
+ const cost = Object.keys(valves)
+ .reduce((r, key) => {
+ r[key] = Infinity;
+ return r;
+ }, {});
+ cost[from] = 0;
+ const openSet = [from];
+ while(openSet.length) {
+ openSet.sort((a,b) => a.cost - b.cost);
+ const active = openSet.shift();
+ for(const next of valves[active].tunnels) {
+ const nCost = cost[active]+1;
+ if (next == to) {
+ return nCost;
+ }
+ if (nCost < cost[next]) {
+ cost[next] = nCost;
+ openSet.push(next);
+ }
+ }
+ }
+ return cost[to]
+}
+
+fs.createReadStream('input')
+ .pipe(line_by_line())
+
+ // Minor parsing
+ .pipe(through.obj(function(line, enc, cb) {
+ line = line.toString();
+ if (!line) return cb();
+ const valve = { state: false, total: 0 };
+ const parts = line.split(' ');
+ parts.shift();
+ valve.id = parts.shift();
+ parts.shift();
+ parts.shift();
+ valve.rate = parseInt(parts.shift().replace(/[^\d\-]/g, ''));
+ parts.shift();
+ parts.shift();
+ parts.shift();
+ parts.shift();
+ valve.tunnels = parts.map(s => s.replace(/,/g,''));
+ valves[valve.id] = valve;
+ cb();
+ }))
+
+ .on('finish', () => {
+ console.log('loaded');
+
+ // Precalculate cost between all valves
+ const COST = {};
+ for(let src of Object.keys(valves)) {
+ for(let dst of Object.keys(valves)) {
+ COST[src+dst] = costFinder(src, dst);
+ }
+ }
+
+ // Remove non-interesting valves
+ for(const valve of Object.values(valves)) {
+ if(valve.id == 'AA') continue;
+ if (valve.rate) continue;
+ delete valves[valve.id];
+ }
+
+ // Name to value map
+ let i = 1;
+ let targets = 0;
+ for(const name of Object.keys(valves)) {
+ nmap[name] = i;
+ rmap[i] = name;
+ targets += i;
+ i *= 2;
+ }
+
+ // Initialize solution finder
+ const totalTime = 26;
+ const actorCount = 2;
+ let maxPressure = 0;
+ let timer = 0;
+ let minlen = Infinity;
+ const openStates = [
+ {
+ valves: nmap['AA'],
+ actors: new Array(actorCount).fill(0).map(() => ({ location: 'AA', time: 0 })),
+ pressure: 0,
+ }
+ ];
+
+ map[nmap['AA'].toString(2)] = 0;
+
+ while(openStates.length) {
+ if (openStates.length < minlen) minlen = openStates.length;
+ if (--timer < 0) { timer = 1e5; console.log(minlen); minlen = Infinity; }
+
+ const state = openStates.pop();
+
+ // Track max pressure released
+ if (state.pressure > maxPressure) {
+ maxPressure = state.pressure;
+ console.log({ maxPressure });
+ }
+
+ // All valves opened, no further work on this path
+ if (state.valves == targets) {
+ continue;
+ }
+
+ for(const idx in state.actors) {
+ const actor = state.actors[idx];
+ // Skip current actor if over-time
+ if (actor.time > totalTime) continue;
+ // Emulate move + valve open
+ for(i=1; i<targets; i*=2) {
+ // Don't attempt valves already opened
+ if (state.valves & i) continue;
+ // Calculate cost & result of moving+opening currently selected valve
+ const cost = COST[actor.location + rmap[i]] + 1;
+ const aCost = actor.time + cost;
+ const pressure = (totalTime - aCost) * valves[rmap[i]].rate;
+ const result = state.valves ^ i;
+ if (aCost > totalTime) continue;
+ // Push to open states
+ const newPressure = state.pressure + ((totalTime-aCost) * valves[rmap[i]].rate);
+ const newActors = [...state.actors];
+ newActors[idx] = {
+ location: rmap[i],
+ time: aCost,
+ };
+
+ const cacheKey = result.toString(2);
+ if ((!map[cacheKey]) || (newPressure > map[cacheKey])) {
+ map[cacheKey] = newPressure;
+ openStates.push({
+ valves: result,
+ actors: newActors,
+ pressure: newPressure,
+ });
+ }
+ }
+ }
+
+ }
+
+ console.log('');
+ console.log({ maxPressure });
+ });
diff --git a/2022/day-16/sample b/2022/day-16/sample
@@ -0,0 +1,10 @@
+Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
+Valve BB has flow rate=13; tunnels lead to valves CC, AA
+Valve CC has flow rate=2; tunnels lead to valves DD, BB
+Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
+Valve EE has flow rate=3; tunnels lead to valves FF, DD
+Valve FF has flow rate=0; tunnels lead to valves EE, GG
+Valve GG has flow rate=0; tunnels lead to valves FF, HH
+Valve HH has flow rate=22; tunnel leads to valve GG
+Valve II has flow rate=0; tunnels lead to valves AA, JJ
+Valve JJ has flow rate=21; tunnel leads to valve II
