advent-of-code

index.js (4400B)

---

 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 });
   });