Like 0
Fork 0

Last active 1734411390 • Unlisted

Zikeji revised this gist 1734411390. Go to revision

1 file changed, 301 insertions

day16.js(file created)

@@ -0,0 +1,301 @@
1 + const { readFileSync } = require("fs");
2 +
3 + /**
4 + * @typedef {object} Coords
5 + * @property {number} x
6 + * @property {number} y
7 + */
8 +
9 + class Reindeer {
10 + static DIRECTIONS = {
11 + "<": { x: -1, y: 0 },
12 + "^": { x: 0, y: -1 },
13 + ">": { x: 1, y: 0 },
14 + v: { x: 0, y: 1 },
15 + };
16 +
17 + /** @type {string[][]} */
18 + maze = [];
19 +
20 + /** @type {Coords} */
21 + pos = {
22 + x: 0,
23 + y: 0,
24 + };
25 +
26 + /** @type {Coords} */
27 + end = {
28 + x: 0,
29 + y: 0,
30 + };
31 +
32 + /** @type {keyof Reindeer.DIRECTIONS} */
33 + direction;
34 +
35 + /** @type {string[]} */
36 + path = [];
37 +
38 + /** @type {number} */
39 + score;
40 +
41 + /**
42 + * @param {string[][]} maze
43 + * @param {Coords} position
44 + * @param {Coords} end
45 + * @param {keyof Reindeer.DIRECTIONS} direction
46 + * @param {string[]} path
47 + */
48 + constructor(maze, x, y, endX, endY, direction = ">", path = [], score = 0) {
49 + this.maze = maze;
50 + this.pos.x = x;
51 + this.pos.y = y;
52 + (this.end.x = endX), (this.end.y = endY), (this.direction = direction);
53 + this.path = path;
54 + this.score = score;
55 + }
56 +
57 + /** @returns {Reindeer} */
58 + clone() {
59 + return new Reindeer(
60 + this.maze,
61 + this.pos.x,
62 + this.pos.y,
63 + this.end.x,
64 + this.end.y,
65 + this.direction,
66 + [...this.path],
67 + this.score
68 + );
69 + }
70 +
71 + /**
72 + * @param {boolean} ccw Counter-clockwise
73 + * @returns {Reindeer}
74 + */
75 + rotate(ccw = false) {
76 + const keys = Object.keys(Reindeer.DIRECTIONS);
77 + let index = keys.indexOf(this.direction);
78 + index += !ccw ? 1 : -1;
79 + if (index >= keys.length) {
80 + index = 0;
81 + }
82 + if (index < 0) {
83 + index = keys.length - 1;
84 + }
85 + this.direction = keys[index];
86 + this.score += 1000;
87 + return this;
88 + }
89 +
90 + /**
91 + * Move in the current facing direction.
92 + * @returns {boolean|Reindeer} True if reached end, false if impossible move or existing move, itself otherwise.
93 + */
94 + move() {
95 + let newX = this.pos.x + Reindeer.DIRECTIONS[this.direction].x;
96 + let newY = this.pos.y + Reindeer.DIRECTIONS[this.direction].y;
97 +
98 + if (this.maze[newY][newX] === "#") {
99 + return false;
100 + }
101 +
102 + if (this.path.some((r) => r.startsWith(`${newX},${newY},`))) {
103 + return false;
104 + }
105 +
106 + const key = `${newX},${newY},${this.direction}`;
107 +
108 + this.path.push(key);
109 +
110 + this.score += 1;
111 + if (newX === this.end.x && newY === this.end.y) {
112 + this.path.pop();
113 + return true;
114 + }
115 + this.pos.x = newX;
116 + this.pos.y = newY;
117 + return this;
118 + }
119 +
120 + visualize() {
121 + const maze = this.maze.map((y) => [...y]);
122 + for (const path of this.path) {
123 + const [x, y, dir] = path.split(",");
124 + maze[y][x] = dir;
125 + }
126 + return maze.map((y) => y.join("")).join("\n");
127 + }
128 + }
129 +
130 + class Logger {
131 + successes = 0;
132 + failures = 0;
133 + queued = 1;
134 + ops = 0;
135 + lOps = 0;
136 +
137 + last = 0;
138 + start;
139 + constructor() {
140 + this.start = new Date().getTime();
141 + process.stdout.write("\n");
142 + }
143 + /** @param {Reindeer} input */
144 + write(input) {
145 + const curTs = new Date().getTime();
146 + if (curTs - this.last > 1000) {
147 + process.stdout.clearLine(0);
148 + process.stdout.cursorTo(0);
149 + const parts = [];
150 + parts.push(`queued=${this.queued}`);
151 + parts.push(`successes=${this.successes}`);
152 + parts.push(`failures=${this.failures}`);
153 + parts.push(`current_reindeer_score=${input.score}`);
154 + parts.push(`ops/s=${this.ops - this.lOps}`);
155 + parts.push(`duration=${Math.round(((curTs - this.start) / 1000) * 100) / 100}s`);
156 + this.lOps = this.ops;
157 + process.stdout.write(parts.join(" "));
158 + this.last = curTs;
159 + }
160 + }
161 + }
162 +
163 + const queue = new (class {
164 + /** @type {{element: Reindeer, priority: number}[]} */
165 + elements = [];
166 + flipped = false;
167 +
168 + /**
169 + * @param {Reindeer} element
170 + * @param {number} priority
171 + */
172 + enqueue(element, priority) {
173 + this.elements.push({ element, priority });
174 + this.elements.sort((a, b) =>
175 + this.flipped ? b.priority - a.priority : a.priority - b.priority
176 + );
177 + }
178 +
179 + /** @returns {Reindeer} */
180 + dequeue() {
181 + return this.elements.shift().element;
182 + }
183 +
184 + /** @returns {boolean} */
185 + isEmpty() {
186 + return this.elements.length === 0;
187 + }
188 + })();
189 +
190 + /**
191 + * @param {typeof queue} queue
192 + * @param {number|null} lowestScore
193 + * @returns {Reindeer[]}
194 + */
195 + const getReindeers = (queue, lowestScore = null) => {
196 + const logger = new Logger();
197 + /** @type {Map<`${number},${number}.${keyof Reindeer.DIRECTIONS}`, number>} */
198 + const visited = new Map();
199 + /** @type {Reindeer[]} */
200 + const matches = [];
201 +
202 + while (!queue.isEmpty()) {
203 + const reindeer = queue.dequeue();
204 + logger.queued = queue.elements.length;
205 + logger.ops += 1;
206 + logger.write(reindeer);
207 +
208 + if (lowestScore !== null && reindeer.score > lowestScore) {
209 + continue;
210 + }
211 +
212 + const stateKey = `${reindeer.pos.x},${reindeer.pos.y},${reindeer.direction}`;
213 + if (visited.has(stateKey)) {
214 + const visitedScore = visited.get(stateKey);
215 + if (lowestScore === null && visitedScore <= reindeer.score) {
216 + continue;
217 + } else if (lowestScore !== null && visitedScore < reindeer.score) {
218 + continue;
219 + }
220 + }
221 + visited.set(stateKey, reindeer.score);
222 +
223 + const newDeer = [
224 + reindeer.clone(),
225 + reindeer.clone().rotate(),
226 + reindeer.clone().rotate(true),
227 + ];
228 +
229 + for (const splitDeer of newDeer) {
230 + const result = splitDeer.move();
231 + if (result === true) {
232 + logger.successes += 1;
233 + matches.push(splitDeer);
234 + continue;
235 + }
236 +
237 + if (result === false) {
238 + logger.failures += 1;
239 + continue;
240 + }
241 +
242 + queue.enqueue(splitDeer, splitDeer.score);
243 + }
244 + }
245 +
246 + logger.last = 0;
247 + logger.write(matches[matches.length - 1]);
248 +
249 + return matches;
250 + };
251 +
252 + const main = () => {
253 + const input = readFileSync(0).toString();
254 + const maze = input.split("\n").map((y) => y.split(""));
255 +
256 + const theFirstReindeer = new Reindeer(
257 + maze,
258 + maze[maze.findIndex((y) => y.includes("S"))].indexOf("S"),
259 + maze.findIndex((y) => y.includes("S")),
260 + maze[maze.findIndex((y) => y.includes("E"))].indexOf("E"),
261 + maze.findIndex((y) => y.includes("E"))
262 + );
263 +
264 + queue.enqueue(theFirstReindeer, 0);
265 + const successfulReindeer = getReindeers(queue);
266 + const answerOne = Math.min(...successfulReindeer.map((r) => r.score));
267 +
268 + // if you want to visualize the maze, uncomment this
269 + // console.log(
270 + // successfulReindeer.find(r => r.score === answer).visualize()
271 + // );
272 +
273 + process.stdout.write("\n");
274 + console.log(`Part One: ${answerOne}`);
275 +
276 + queue.enqueue(theFirstReindeer, 0);
277 + queue.flipped = true;
278 + /** @type {Reindeer[]} */
279 + const bestReindeer = getReindeers(queue, answerOne);
280 +
281 + const oMaze = maze.map((y) => [...y].map((s) => (["S", "E"].includes(s) ? "O" : s)));
282 + for (const reindeer of bestReindeer) {
283 + for (const path of reindeer.path) {
284 + const [x, y] = path.split(",");
285 + oMaze[y][x] = "O";
286 + }
287 + }
288 +
289 + // if you want to view the optimized seating map
290 + // console.log(oMaze.map(y => y.join("")).join("\n"));
291 +
292 + const answerTwo = oMaze.reduce(
293 + (acc, y) => acc + y.filter((s) => s === "O").length,
294 + 0
295 + );
296 +
297 + process.stdout.write("\n");
298 + console.log(`Part Two: ${answerTwo}`);
299 + };
300 +
301 + main();
Newer Older

Powered by Opengist ⋅ Load: 47ms⋅

English