commit e8d9887147cddfb6d491eb900fb9b5fa6a4ba5a4
parent e77d3288cff330a6b2cd1c658c18460819ed4231
Author: finwo <finwo@pm.me>
Date: Sat, 24 Dec 2022 19:54:26 +0100
2022/24 solution
Diffstat:
3 files changed, 228 insertions(+), 0 deletions(-)
diff --git a/2022/day-24/index.js b/2022/day-24/index.js
@@ -0,0 +1,215 @@
+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,
+});
diff --git a/2022/day-24/sample1 b/2022/day-24/sample1
@@ -0,0 +1,7 @@
+#.#####
+#.....#
+#>....#
+#.....#
+#...v.#
+#.....#
+#####.#
diff --git a/2022/day-24/sample2 b/2022/day-24/sample2
@@ -0,0 +1,6 @@
+#.######
+#>>.<^<#
+#.<..<<#
+#>v.><>#
+#<^v^^>#
+######.#
