-
Notifications
You must be signed in to change notification settings - Fork 0
/
21.mjs
123 lines (100 loc) · 3.19 KB
/
21.mjs
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import { readInput, getStraightAdjacentPositions } from "./utils.mjs";
const input = readInput(import.meta);
const isCycling = (arr, cycleLength) => {
for (let i = 0; i < cycleLength; i++) {
if (arr[i] !== arr[i + cycleLength]) {
return false;
}
}
return true;
};
const addToCircular = (arr, el, cycleLength) => {
arr.push(el);
if (arr.length > 2 * cycleLength) {
arr.shift();
}
};
const solve = (input, targetStep, hasBounds = false) => {
const lines = input.split("\n");
const [I, J] = [lines.length, lines[0].length];
const rocks = new Set();
let bounds = new Set();
let lastVisited = new Set();
for (const [i, line] of lines.entries()) {
for (const [j, c] of line.split("").entries()) {
if (c === "#") rocks.add(JSON.stringify([i, j]));
if (c === "S") {
bounds.add(JSON.stringify([i, j]));
}
}
}
const transpose = ([i, j]) => {
const nI = i % I;
const nJ = j % J;
return [nI < 0 ? I + nI : nI, nJ < 0 ? J + nJ : nJ];
};
const inBounds = ([i, j]) => i >= 0 && i < I && j >= 0 && j < J;
const boundPointsVariations = [];
const diffVariations = [];
const cycleLength = I;
let result = 0n;
let cycleStart;
let k = 0;
for (; k < targetStep + 1; k++) {
const newBounds = new Set();
const visited = new Set();
if (k % 2 === targetStep % 2) {
result += BigInt(bounds.size);
}
for (const pointStr of bounds) {
const [oI, oJ] = JSON.parse(pointStr);
visited.add(pointStr);
getStraightAdjacentPositions(oI, oJ)
.filter(
([i, j]) =>
(!hasBounds || inBounds([i, j])) &&
!rocks.has(JSON.stringify(transpose([i, j]))) &&
!lastVisited.has(JSON.stringify([i, j])),
)
.forEach(([i, j]) => {
newBounds.add(JSON.stringify([i, j]));
});
}
const boundPointsVariation = BigInt(newBounds.size - bounds.size);
const boundPointsVariationDiff = BigInt(
boundPointsVariation - (boundPointsVariations.at(-cycleLength) ?? 0n),
);
addToCircular(boundPointsVariations, boundPointsVariation, cycleLength);
addToCircular(diffVariations, boundPointsVariationDiff, cycleLength);
bounds = newBounds;
lastVisited = visited;
if (isCycling(diffVariations, cycleLength)) {
if (!cycleStart) {
cycleStart = k;
}
if (k - cycleStart > cycleStart) {
// has been cycling for more steps than the step it started cycling (random heuristic xd)
break;
}
} else {
cycleStart = undefined;
}
}
let boundSize = BigInt(bounds.size);
let cycleBoundPointVariations = boundPointsVariations.slice(cycleLength);
let cycleDiffVariations = diffVariations.slice(cycleLength);
k += 1; // next iteration
const offset = k % cycleLength;
for (; k < targetStep + 1; k++) {
if (k % 2 === targetStep % 2) {
result += BigInt(boundSize);
}
const index = (k - offset) % cycleLength;
cycleBoundPointVariations[index] += cycleDiffVariations[index];
boundSize += cycleBoundPointVariations[index];
}
return result;
};
console.log(solve(input, 64, true));
console.time("run p2");
console.timeLog("run p2", solve(input, 26501365));