Zikeji / day16.js

const { readFileSync } = require("fs"); /** * @typedef {object} Coords * @property {number} x * @property {number} y */ class Reindeer { static DIRECTIONS = { "<": { x: -1, y: 0 }, "^": { x: 0, y: -1 }, ">": { x: 1, y: 0 }, v: { x: 0, y: 1 }, }; /** @type {string[][]} */ maze = []; /** @type {Coords} */ pos = { x: 0, y: 0, }; /** @type {Coords} */ end = { x: 0, y: 0, }; /** @type {keyof Reindeer.DIRECTIONS} */ direction; /** @type {string[]} */ path = []; /** @type {number} */ score; /** * @param {string[][]} maze * @param {Coords} position * @param {Coords} end * @param {keyof Reindeer.DIRECTIONS} direction * @param {string[]} path */ constructor(maze, x, y, endX, endY, direction = ">", path = [], score = 0) { this.maze = 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 {Reindeer} */ clone() { return new Reindeer( this.maze, this.pos.x, this.pos.y, this.end.x, this.end.y, this.direction, [...this.path], this.score ); } /** * @param {boolean} ccw Counter-clockwise * @returns {Reindeer} */ rotate(ccw = false) { const keys = Object.keys(Reindeer.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]; this.score += 1000; return this; } /** * Move in the current facing direction. * @returns {boolean|Reindeer} True if reached end, false if impossible move or existing move, itself otherwise. */ move() { let newX = this.pos.x + Reindeer.DIRECTIONS[this.direction].x; let newY = this.pos.y + Reindeer.DIRECTIONS[this.direction].y; if (this.maze[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.maze.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"); } } class Logger { successes = 0; failures = 0; queued = 1; ops = 0; lOps = 0; last = 0; start; constructor() { this.start = new Date().getTime(); process.stdout.write("\n"); } /** @param {Reindeer} 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_reindeer_score=${input.score}`); parts.push(`ops/s=${this.ops - this.lOps}`); parts.push(`duration=${Math.round(((curTs - this.start) / 1000) * 100) / 100}s`); this.lOps = this.ops; process.stdout.write(parts.join(" ")); this.last = curTs; } } } const queue = new (class { /** @type {{element: Reindeer, priority: number}[]} */ elements = []; flipped = false; /** * @param {Reindeer} element * @param {number} priority */ enqueue(element, priority) { this.elements.push({ element, priority }); this.elements.sort((a, b) => this.flipped ? b.priority - a.priority : a.priority - b.priority ); } /** @returns {Reindeer} */ dequeue() { return this.elements.shift().element; } /** @returns {boolean} */ isEmpty() { return this.elements.length === 0; } })(); /** * @param {typeof queue} queue * @param {number|null} lowestScore * @returns {Reindeer[]} */ const getReindeers = (queue, lowestScore = null) => { const logger = new Logger(); /** @type {Map<`${number},${number}.${keyof Reindeer.DIRECTIONS}`, number>} */ const visited = new Map(); /** @type {Reindeer[]} */ const matches = []; while (!queue.isEmpty()) { const reindeer = queue.dequeue(); logger.queued = queue.elements.length; logger.ops += 1; logger.write(reindeer); if (lowestScore !== null && reindeer.score > lowestScore) { continue; } const stateKey = `${reindeer.pos.x},${reindeer.pos.y},${reindeer.direction}`; if (visited.has(stateKey)) { const visitedScore = visited.get(stateKey); if (lowestScore === null && visitedScore <= reindeer.score) { continue; } else if (lowestScore !== null && visitedScore < reindeer.score) { continue; } } visited.set(stateKey, reindeer.score); const newDeer = [ reindeer.clone(), reindeer.clone().rotate(), reindeer.clone().rotate(true), ]; for (const splitDeer of newDeer) { const result = splitDeer.move(); if (result === true) { logger.successes += 1; matches.push(splitDeer); continue; } if (result === false) { logger.failures += 1; continue; } queue.enqueue(splitDeer, splitDeer.score); } } logger.last = 0; logger.write(matches[matches.length - 1]); return matches; }; const main = () => { const input = readFileSync(0).toString(); const maze = input.split("\n").map((y) => y.split("")); const theFirstReindeer = new Reindeer( maze, maze[maze.findIndex((y) => y.includes("S"))].indexOf("S"), maze.findIndex((y) => y.includes("S")), maze[maze.findIndex((y) => y.includes("E"))].indexOf("E"), maze.findIndex((y) => y.includes("E")) ); queue.enqueue(theFirstReindeer, 0); const successfulReindeer = getReindeers(queue); const answerOne = Math.min(...successfulReindeer.map((r) => r.score)); // if you want to visualize the maze, uncomment this // console.log( // successfulReindeer.find(r => r.score === answer).visualize() // ); process.stdout.write("\n"); console.log(`Part One: ${answerOne}`); queue.enqueue(theFirstReindeer, 0); queue.flipped = true; /** @type {Reindeer[]} */ const bestReindeer = getReindeers(queue, answerOne); const oMaze = maze.map((y) => [...y].map((s) => (["S", "E"].includes(s) ? "O" : s))); for (const reindeer of bestReindeer) { for (const path of reindeer.path) { const [x, y] = path.split(","); oMaze[y][x] = "O"; } } // if you want to view the optimized seating map // console.log(oMaze.map(y => y.join("")).join("\n")); const answerTwo = oMaze.reduce( (acc, y) => acc + y.filter((s) => s === "O").length, 0 ); process.stdout.write("\n"); console.log(`Part Two: ${answerTwo}`); }; main();