advent-of-code

index.js (6411B)

---

 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;
 };
 
 function s(nodes, l) {
   return nodes.map(n => [n[0]+2,n[1]+l+3]);
 }
 
 let cave  = [];
 // const cave  = [ // Test pattern
 //   0b000000000,
 //   0b001110100,
 //   0b000000000,
 //   0b001000100,
 //   0b001111100,
 //   0b001000100,
 //   0b000000000,
 //   0b001111100,
 //   0b000010000,
 //   0b001111100,
 //   0b000000000,
 // ];
 const rocks = [
   [
     0b1111000,
   ],
   [
     0b010000,
     0b111000,
     0b010000,
   ],
   [
     0b111000, // Yes, it's flipped XY
     0b100000, // LSB = left
     0b100000, // i0 = bottom
   ],
   [
     0b1000,
     0b1000,
     0b1000,
     0b1000,
   ],
   [
     0b11000,
     0b11000,
   ],
 ];
 
 function printCave() {
   let i = cave.length + 6;
   while(--i >= 0) {
     process.stdout.write('|');
     for(let x=1; x<=7; x++) {
       if ( (rock[i - rp]|0) & (1<<x) ) {
         process.stdout.write('@');
       } else if ( (cave[i]|0) & (1<<x) ) {
         process.stdout.write('#');
       } else {
         process.stdout.write('.');
         // process.stdout.write(' ');
       }
     }
     process.stdout.write('|\n');
   }
   process.stdout.write('+-------+\n');
 }
 
 // How large should our cache key be
 const lookback = 40;
 
 // Fetch jet pattern
 const pattern = fs.readFileSync('input', 'utf-8');
 // const pattern = fs.readFileSync('sample', 'utf-8');
 const jets    = [];
 for(const c of pattern.split('')) {
   if (c == '>') jets.push(2);
   if (c == '<') jets.push(0);
 }
 
 // Tracker for the next jet
 let   j  = 0;
 const jl = jets.length;
 const J  = pattern.trim().repeat(3);
 
 // Rock statistics
 let   rockCount  = 0;
 // const rockTarget = 10000000000;
 const rockTarget = 1000000000000;
 // const rockTarget = 2022;
 let   rockHeight = 0;
 
 
 // Tracker for falling rocks
 let   r    = 0;
 const rl   = rocks.length;
 let   rp   = 0;
 let   rock = false;
 
 let storeCache = 0;
 const cache = {};
 const cycle = jets.length * rocks.length;
 let  cc = 0;
 
 // Time tracking to give an estimate & start
 const startTime = Date.now();
 while(rockCount < rockTarget) {
 
   let cacheKey = r.toString(16) + cave.map(l => ('0'+l.toString(16)).substr(-2)).join('');
   if (cache[cacheKey]) {
 
     // Merge 2 cache keys, skipping a simulation step
     const nextKey = cache[cacheKey].n;
     if (cache[cache[cacheKey].n]) {
       const nextKey = cache[cacheKey].n;
       cache[cacheKey].cave  = cache[nextKey].cave;
       cache[cacheKey].j    += cache[nextKey].j;
       cache[cacheKey].c    += cache[nextKey].c;
       cache[cacheKey].h    += cache[nextKey].h;
       cache[cacheKey].n     = cache[nextKey].n;
     }
 
     if (rockCount + cache[cacheKey].c <= rockTarget) {
       cave        = [...cache[cacheKey].cave];
       j           = (j + cache[cacheKey].j) % jl;
       r           = (r + cache[cacheKey].c) % rl;
       rockCount  += cache[cacheKey].c;
       rockHeight += cache[cacheKey].h;
       cacheKey    = cache[cacheKey].n;
       continue;
     } else {
       // console.log("FAIL", cacheKey, cache[cacheKey]);
     }
   } else {
     // console.log("MISS", cacheKey);
   }
 
   if (cc > cycle) {
     storeCache = true;
   } else {
     cc += 1;
   }
 
 
   // let stateKey = r.toString(16);
   // for(let i=0; i<cave.length; i++) {
   //   stateKey += ('0' + cave[i].toString(16)).substr(-2);
   //   stateKey += cave[i].toString(16);
   // }
   // if ((cave.length == lookback) && cache[stateKey]) {
   //   let hit = false;
   //   // console.log({ J, sub: J.substr(j, cache[stateKey].J.length), j: cache[stateKey].J })
   //   if (J.substr(j, cache[stateKey].j) == cache[stateKey].J) {
   //     cave        = [...cache[stateKey].cave];
   //     j           = (j + cache[stateKey].j) % jl;
   //     rockCount  += 1;
   //     rockHeight += cache[stateKey].h;
   //     // console.log({ c: cache[stateKey] });
   //     continue;
   //   }
   //   // printCave();
   //   // continue;
   // }
 
   let rockJets = '';
 
   // if (cache[stateKey]) console.log(`Got state cache for ${stateKey} (${Object.values(cache).length})`);
   // console.log( stateKey );
   // cache[stateKey] = true;
 
   // Spawn new rock
   rock = rocks[r];
   r = (r+1) % rl;
   rp = cave.length + 3;
 
   // console.log(`\nA new rock begins falling:`);
   // printCave();
 
   while(rock) {
 
     // Fetch jet movement
     const jet = jets[j];
     j = (j+1) % jl;
     rockJets += jet ? '>' : '<';
 
     // Calculate jet-based movement
     let newRock = [];
     for(let i=0; i<rock.length; i++) {
       newRock[i] = (rock[i] >> 1) << jet;
     }
 
     // Wall collision
     let hitWall = false;
     for(let i=0; i<newRock.length; i++) {
       const check = 1 | (cave[i+rp]|0) | 256; // Bitmap of current height
       if (newRock[i] & check) { hitWall = true; break; }
     }
 
     // Move if possible
     if (!hitWall) rock = newRock;
 
     // console.log(`\nJet of gas pushes the rock ${jet ? 'right' : 'left'}${(rock === newRock) ? '' : ', but nothing happens'}:`);
     // printCave();
 
     // Calculate gravity-based movement
     rp--;
     let hitBottom = rp < 0; // Floor check
     if (!hitBottom) {
       for(let i=0; i<rock.length; i++) {
         const check = 1 | (cave[i+rp]|0) | 256; // Bitmap of current height
         if (rock[i] & check) { hitBottom = true; break; } // Rock check
       }
     }
 
     // Move or block
     if (hitBottom) {
       rp++; // Move back
 
       // Solidify
       const before = cave.length;
       for(let i=0; i<rock.length; i++) {
         if (!cave[rp+i]) cave[rp+i] = 0; // Initialize cave area
         cave[rp+i] |= rock[i];           // Overlay rock
       }
       rock = false;
 
       rockCount  += 1;
       const diff = cave.length - before;
       rockHeight += diff;
 
       cave = cave.slice(-lookback);
       let newKey = (r%rl).toString(16) + cave.map(l => ('0'+l.toString(16)).substr(-2)).join('');
 
       if (storeCache) {
         cache[cacheKey] = {
           n: newKey,
           c: 1,
           cave: [...cave],
           h: diff,
           j: rockJets.length,
         };
       }
 
 
       // console.log(`\nRock falls 1 unit, causing it to come to rest:`);
       // printCave();
 
     } else {
       // console.log(`\nRock falls 1 unit:`);
       // printCave();
     }
 
   }
 
 }
 
 console.log(`\nStatus report:`);
 console.log(`  Rock count - ${rockCount}`);
 console.log(`  Height     - ${rockHeight}`);