-
Notifications
You must be signed in to change notification settings - Fork 0
/
solution.js
89 lines (81 loc) · 2.64 KB
/
solution.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
const fs = require('fs');
const input = fs.readFileSync('input.txt', 'utf8').trim().split('\n');
const grid = input.map(row => row.split(''));
const rows = grid.length;
const cols = grid[0].length;
for(let part of ['part1', 'part2']) {
const intersections = new Set();
for (let row = 0; row < rows; row++) {
for (let col = 0; col < cols; col++) {
let neighborCount = 0;
const directions = [['^', -1, 0], ['v', 1, 0], ['<', 0, -1], ['>', 0, 1]];
for (const [_, dx, dy] of directions) {
if (0 <= row + dx && row + dx < rows && 0 <= col + dy && col + dy < cols && grid[row + dx][col + dy] !== '#') {
neighborCount += 1;
}
}
if (neighborCount > 2 && grid[row][col] !== '#') {
intersections.add(`${row},${col}`);
}
}
}
let startPoint;
for (let col = 0; col < cols; col++) {
if (grid[0][col] === '.') {
intersections.add(`0,${col}`);
startPoint = `0,${col}`;
}
if (grid[rows - 1][col] === '.') {
intersections.add(`${rows - 1},${col}`);
endPoint = `${rows - 1},${col}`;
}
}
const edgeList = {};
for (const intersection of intersections) {
edgeList[intersection] = [];
const [rowVal, colVal] = intersection.split(',').map(Number);
const queue = [[rowVal, colVal, 0]];
const visited = new Set();
while (queue.length) {
const [r, c, dist] = queue.shift();
const hash = `${r},${c}`;
if (visited.has(hash)) {
continue;
}
visited.add(hash);
if (intersections.has(hash) && hash !== intersection) {
edgeList[intersection].push([`${r},${c}`, dist]);
continue;
}
const directions = [['^', -1, 0], ['v', 1, 0], ['<', 0, -1], ['>', 0, 1]];
for (const [dir, dx, dy] of directions) {
if (0 <= r + dx && r + dx < rows && 0 <= c + dy && c + dy < cols && grid[r + dx][c + dy] !== '#') {
if (part === 'part1' && ['<', '>', '^', 'v'].includes(grid[r][c]) && grid[r][c] !== dir) {
continue;
}
queue.push([r + dx, c + dy, dist + 1]);
}
}
}
}
let count = 0;
let maxDistance = 0;
const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
function dfs(node, distance) {
count += 1;
const [r, c] = node.split(',').map(Number);
if (visited[r][c]) {
return;
}
visited[r][c] = true;
if (r === rows - 1) {
maxDistance = Math.max(maxDistance, distance);
}
for (const [neighbor, neighborDist] of edgeList[node]) {
dfs(neighbor, distance + neighborDist);
}
visited[r][c] = false;
}
dfs(startPoint, 0);
console.log(part, ': ', maxDistance)
}