commit e86f9394074a8cd4e5695c72714703c6a01981b5
parent 23a6a2543bb57aeeb2a62445624e01af95b7145c
Author: finwo <finwo@pm.me>
Date: Sat, 17 Dec 2022 19:40:15 +0100
2022/17 solution
Diffstat:
2 files changed, 263 insertions(+), 0 deletions(-)
diff --git a/2022/day-17/index.js b/2022/day-17/index.js
@@ -0,0 +1,262 @@
+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}`);
diff --git a/2022/day-17/sample b/2022/day-17/sample
@@ -0,0 +1 @@
+>>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>
