advent-of-code

index.js (6360B)

---

 const fs = require('fs');
 
 const directions = {
   '0,-1': '^',
   '1,0' : '>',
   '0,1' : 'v',
   '-1,0': '<',
 };
 
 function mod(n, m) {
   return ((n%m)+m)%m;
 }
 
 function clone(subject) {
   return JSON.parse(JSON.stringify(subject));
 }
 
 function drawmap(width, height, init, elf, blizzards) {
   for(let y=-1; y<=height; y++) {
     for(let x=-1; x<=width; x++) {
 
       if (elf[0] == x && elf[1] == y) {
         if(blizzards.find(blizzard => blizzard.x == x && blizzard.y == y)) {
           process.stdout.write('D');
         } else {
           process.stdout.write('E');
         }
         continue;
       }
 
       let here = blizzards.filter(blizzard => blizzard.x == x && blizzard.y == y);
       if (here.length >  9) { process.stdout.write('X'); continue; }
       if (here.length >  1) { process.stdout.write(here.length.toString()); continue; }
       if (here.length == 1) { process.stdout.write(directions[here[0].d.join(',')]); continue; }
 
       if (init.start[0] == x && init.start[1] == y) {
         process.stdout.write('.');
         continue;
       }
 
       if (init.target[0] == x && init.target[1] == y) {
         process.stdout.write('.');
         continue;
       }
 
       if (y == -1    ) { process.stdout.write('#'); continue; }
       if (x == -1    ) { process.stdout.write('#'); continue; }
       if (y == height) { process.stdout.write('#'); continue; }
       if (x == width ) { process.stdout.write('#'); continue; }
 
       process.stdout.write('.');
     }
     process.stdout.write('\n');
   }
 }
 
 // const input = fs.readFileSync('sample1', 'utf-8')
 // const input = fs.readFileSync('sample2', 'utf-8')
 const input = fs.readFileSync('input', 'utf-8')
   .split('\n')
   .filter(l => l)
 
 // Parse starting location
 const init = {};
 init.start     = [ input.shift().indexOf('.') - 1, -1];
 init.target    = [ input.pop().indexOf('.') - 1, input.length ];
 init.blizzards = [];
 
 // Fetch map size
 const height = input.length;
 const width  = input[0].length - 2;
 
 // Parse blizzards
 for(let y=0; y<input.length; y++) {
   const line = input[y].substr(1, input[y].length - 2);
   for(let x=0; x<line.length; x++) {
     switch(line.charAt(x)) {
       case '^': init.blizzards.push({ d: [ 0,-1], x, y }); break;
       case '>': init.blizzards.push({ d: [ 1, 0], x, y }); break;
       case 'v': init.blizzards.push({ d: [ 0, 1], x, y }); break;
       case '<': init.blizzards.push({ d: [-1, 0], x, y }); break;
     }
   }
 }
 
 // console.log(init);
 // console.log(blizzards);
 
 function findPath(from, to, starttime) {
   const had = [];
   let mintime = Infinity;
   let minpath = null;
   let openset = [[...from, starttime, [from]]];
   let counter = 0;
   let logscore  = Infinity;
   let logdist   = Infinity;
   let logtime   = Infinity;
   let loglength = Infinity;
   while(openset.length) {
     const p = openset.pop();
     let [x,y,time,hist] = p;
 
     // Calculate distance to go
     const dist = Math.abs(x - to[0]) + Math.abs(y - to[1]);
 
     // // Handle logging to show progress
     // if (dist           < logdist  ) logdist   = dist;
     // if (openset.length < loglength) loglength = openset.length;
     // if (time           < logtime  ) logtime   = time;
     // if ((time+dist)    < logscore ) logscore  = (time+dist);
     // if (counter++ >= 1e3) {
     //   console.log({
     //     score: logscore,
     //     l: loglength,
     //     time: logtime,
     //     dist: logdist,
     //   });
     //   logdist = loglength = logtime = logscore = Infinity;
     //   counter = 0;
     // }
 
     // Stop if we're certainly not making the record
     if ((dist + time) > mintime) continue;
     time++;
 
     // Calculate state at location
     const blizzards = clone(init.blizzards);
     for(const blizzard of blizzards) {
       blizzard.x = mod(blizzard.x + (blizzard.d[0] * time), width );
       blizzard.y = mod(blizzard.y + (blizzard.d[1] * time), height);
     }
 
     // Calculate possible moves
     let tries = [
                               [ p[0]    , p[1] - 1 ],
       [ p[0] - 1, p[1]     ], [ p[0]    , p[1]     ], [ p[0] + 1, p[1]     ],
                               [ p[0]    , p[1] + 1 ],
     ];
 
     for(const pos of tries) {
 
       // Found target
       if (pos[0] == to[0] && pos[1] == to[1]) {
         // console.log(`finished in ${time} minutes`);
         if (time < mintime) {
           // console.log('new record', time);
           mintime = time;
           minpath = [...hist, pos];
         }
         continue;
       }
 
       // Out-of-bounds
       const isStart = pos[0] == from[0] && pos[1] == from[1];
       if (pos[0] <       0 && !isStart) continue;
       if (pos[1] <       0 && !isStart) continue;
       if (pos[0] >= width  && !isStart) continue;
       if (pos[1] >= height && !isStart) continue;
 
       // Skip already added
       had[pos[1]]               = had[pos[1]] || [];
       had[pos[1]][pos[0]]       = had[pos[1]][pos[0]] || [];
       if (had[pos[1]][pos[0]][time]) continue;
       had[pos[1]][pos[0]][time] = true;
 
       // Occupied by blizzard
       if (blizzards.find(blizzard => blizzard.x == pos[0] && blizzard.y == pos[1])) {
         continue;
       }
 
       // Add to the open set
       openset.push([...pos, time, [...hist, pos]]);
     }
 
     // Order ASC by xdist + ydist
     openset.sort((a,b) => {
       const ad = Math.abs(a[0] - to[0]) + Math.abs(a[1] - to[1]);
       const bd = Math.abs(b[0] - to[0]) + Math.abs(b[1] - to[1]);
       return bd - ad;
     });
     // openset.sort((a, b) => a[2] - b[2]);
     // console.log(openset.map(s => Math.abs(s[0] - to[0]) + Math.abs(s[1] - to[1]) + s[2]));
 
     // Limit openset length by removing worst options
     while (openset.length > 1e4) {
       openset.shift();
     }
   }
 
   return minpath.length - 1;
 }
 
 // const pass1 = 299;
 const pass1 = findPath(init.start , init.target, 0);
 const pass2 = findPath(init.target, init.start , pass1);
 const pass3 = findPath(init.start , init.target, pass1 + pass2);
 
 // const minblizzards = clone(init.blizzards);
 // for(let i=0; i<minpath.length; i++) {
 
 //   process.stdout.write(`\n== Minute ${i} ==\n`);
 //   drawmap(width, height, init, minpath[i], minblizzards);
 
 //   for(const blizzard of minblizzards) {
 //     blizzard.x = mod(blizzard.x + blizzard.d[0], width );
 //     blizzard.y = mod(blizzard.y + blizzard.d[1], height);
 //   }
 // }
 
 console.log({
   pass1,
   pass2,
   pass3,
   total: pass1 + pass2 + pass3,
 });