Like 0
Fork 0

Last active 1734504449 • Unlisted

Zikeji revised this gist 1734504449. Go to revision

1 file changed, 287 insertions

day18.js(file created)

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

Powered by Opengist ⋅ Load: 62ms⋅

English