Zikeji / AoC Day 18

const input = require("fs").readFileSync(0).toString(); const mazeSize = 71; const bytesReadPartOne = 1024; /** * @param {string} input * @param {number} size * @param {number} simulateFirstXBytes * @returns {string[][]} */ const simulateMapState = (input, size, simulateFirstXBytes) => { const grid = [...new Array(size).keys()].map(() => [...new Array(size).keys()].map(() => '.')); /** @type {Coords[]} */ const inputPredictions = input.split("\n").map((c) => ({ x: parseInt(c.split(',')[0]), y: parseInt(c.split(',')[1]) })); for (let i = 0; i < simulateFirstXBytes; i += 1) { grid[inputPredictions[i].y][inputPredictions[i].x] = '#'; } return grid; } /** * @typedef {object} Coords * @property {number} x * @property {number} y */ class Escapee { static DIRECTIONS = { '<': { x: -1, y: 0, }, '^': { x: 0, y: -1, }, '>': { x: 1, y: 0, }, 'v': { x: 0, y: 1, }, }; /** @type {string[][]} */ map = []; /** @type {Coords} */ pos = { x: 0, y: 0, }; /** @type {Coords} */ end = { x: 0, y: 0, } /** @type {keyof Escapee.DIRECTIONS} */ direction; /** @type {string[]} */ path = []; /** @type {number} */ score; /** * @param {string[][]} maze * @param {Coords} position * @param {Coords} end * @param {keyof Escapee.DIRECTIONS} direction * @param {string[]} path */ constructor(maze, x, y, endX, endY, direction = '>', path = [], score = 0) { this.map = maze; this.pos.x = x; this.pos.y = y; this.end.x = endX; this.end.y = endY; this.direction = direction; this.path = path; this.score = score; } /** @returns {Escapee} */ clone() { return new Escapee( this.map, this.pos.x, this.pos.y, this.end.x, this.end.y, this.direction, [...this.path], this.score, ); } /** * @param {boolean} ccw Counter-clockwise * @returns {Escapee} */ rotate(ccw = false) { const keys = Object.keys(Escapee.DIRECTIONS); let index = keys.indexOf(this.direction); index += !ccw ? 1 : -1; if (index >= keys.length) { index = 0; } if (index < 0) { index = keys.length - 1; } this.direction = keys[index]; return this; } /** * Move in the current facing direction. * @returns {boolean|Escapee} True if reached end, false if impossible move or existing move, itself otherwise. */ move() { let newX = this.pos.x + Escapee.DIRECTIONS[this.direction].x; let newY = this.pos.y + Escapee.DIRECTIONS[this.direction].y; if (newX < 0 || newX >= this.map.length || newY < 0 || newY >= this.map.length || this.map[newY][newX] === '#') { return false; } if (this.path.some(r => r.startsWith(`${newX},${newY},`))) { return false; } const key = `${newX},${newY},${this.direction}`; this.path.push(key); this.score += 1; if (newX === this.end.x && newY === this.end.y) { this.path.pop(); return true; } this.pos.x = newX; this.pos.y = newY; return this; } visualize() { const maze = this.map.map(y => [...y]); for (const path of this.path) { const [x, y, dir] = path.split(","); maze[y][x] = dir; } return maze.map(y => y.join("")).join("\n"); } } const map = simulateMapState( input, mazeSize, bytesReadPartOne, ); const ourEscapee = new Escapee(map, 0, 0, map.length-1, map.length-1); const logger = new class { successes = 0; failures = 0; queued = 1; last = 0; ops = 0; bytes = bytesReadPartOne; lOps = 0; /** @param {Escapee} input */ write(input) { const curTs = new Date().getTime(); if (curTs - this.last > 1000) { process.stdout.clearLine(0); process.stdout.cursorTo(0); const parts = []; parts.push(`queued=${this.queued}`); parts.push(`successes=${this.successes}`); parts.push(`failures=${this.failures}`); parts.push(`current_escapee_steps=${input.score}`); parts.push(`bytes=${this.bytes}`); parts.push(`ops/s=${this.ops - this.lOps}`); this.lOps = this.ops; process.stdout.write(parts.join(' ')); this.last = curTs; } } } const queue = new class { /** @type {{element: Escapee, priority: number}[]} */ elements = []; /** * @param {Escapee} element * @param {number} priority */ enqueue(element, priority) { this.elements.push({ element, priority }); this.elements.sort((a, b) => a.priority - b.priority); } /** @returns {Escapee} */ dequeue() { return this.elements.shift().element; } /** @returns {boolean} */ isEmpty() { return this.elements.length === 0; } } /** * @param {boolean} stopOnFirst * @returns {Escapee[]} */ const solveMaze = (stopOnFirst = false) => { /** @type {Escapee[]} */ const successful = []; queue.enqueue(ourEscapee, 0); /** @type {Map<`${number},${number}.${keyof Escapee.DIRECTIONS}`, number>} */ const minScores = new Map(); while (!queue.isEmpty()) { const Escapee = queue.dequeue(); logger.queued = queue.elements.length; logger.ops += 1; logger.write(Escapee); const stateKey = `${Escapee.pos.x},${Escapee.pos.y},${Escapee.direction}`; if (minScores.has(stateKey) && minScores.get(stateKey) <= Escapee.score) { continue; } minScores.set(stateKey, Escapee.score); const newEscapees = [ Escapee.clone(), Escapee.clone().rotate(), Escapee.clone().rotate(true), ]; for (const splitEscapee of newEscapees) { const result = splitEscapee.move(); if (result === true) { logger.successes += 1; successful.push(splitEscapee); if (stopOnFirst) { return successful; } continue; } if (result === false) { logger.failures += 1; continue; } queue.enqueue(splitEscapee, splitEscapee.score); } } return successful; } const successfulEscapees = solveMaze(); const answerOne = Math.min(...successfulEscapees.map(r => r.score)); process.stdout.clearLine(0); process.stdout.cursorTo(0); console.log( `Part One: ${answerOne}` ); for (let i = bytesReadPartOne; i <= input.split("\n").length; i += 1) { logger.bytes = i; const mapAtTime = simulateMapState( input, mazeSize, i, ); ourEscapee.map = mapAtTime; queue.enqueue(ourEscapee, 0); const result = solveMaze(true); if (result.length === 0) { process.stdout.clearLine(0); process.stdout.cursorTo(0); console.log(`Part Two: ${input.split("\n")[i-1]}`); break; } }