-
Notifications
You must be signed in to change notification settings - Fork 0
/
day20.js
125 lines (101 loc) · 2.76 KB
/
day20.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
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
124
125
import read from "../readFile.js";
const input = await read(20);
const modules = Object
.fromEntries(input.split("\n")
.map(l => l.split(" -> "))
.map(m => {
// broadcaster
if (m[0] === "broadcaster") {
return ["broadcaster", {
targets: m[1].split(", ")
}];
}
// %
if (m[0][0] === "%") {
return [m[0].slice(1), {
type: m[0][0],
targets: m[1].split(", "),
state: 0
}];
}
// &
return [m[0].slice(1), {
type: m[0][0],
targets: m[1].split(", "),
dependencies: {}
}];
})
);
/*
modules = {
broadcaster: {
targets: [
moduleName,
...
]
},
flipFlopName: {
type: "%",
targets: [
moduleName,
...
],
state: 0|1
},
conjunctionName: {
type: "&",
targets: [
moduleName,
...
],
dependencies: {
moduleName: 0|1,
...
}
},
...
}
*/
for (const moduleName of Object.keys(modules)) {
for (const target of modules[moduleName].targets) {
if (modules[target] && modules[target].type === "&") {
modules[target].dependencies[moduleName] = 0;
}
}
}
const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
const lcm = (a, b) => a * b / gcd(a, b);
const rxDependency = Object.keys(modules).find(x => modules[x].targets.includes("rx"));
const rxDependencies = Object.keys(modules).filter(x => modules[x].targets.includes(rxDependency));
let numLow = 0;
let numHigh = 0;
let cycleLength = 1;
for (let i = 0; rxDependencies.length || i <= 1000; i++) {
if (i === 1000) console.log(numLow * numHigh);
const pulsesToProcess = [];
numLow++; // button press
modules["broadcaster"].targets.forEach(target => pulsesToProcess.push({ to: target, pulse: 0, from: "broadcaster" }));
while (pulsesToProcess.length) {
const { to, pulse, from } = pulsesToProcess.shift();
if (pulse === 0) numLow++;
else numHigh++;
const module = modules[to];
if (!module) continue;
if (module.type === "%") {
if (pulse === 1) continue;
const newState = 1 - module.state;
module.state = newState;
module.targets.forEach(target => pulsesToProcess.push({ to: target, pulse: newState, from: to }));
} else { // &
module.dependencies[from] = pulse;
const allHigh = Object.keys(module.dependencies).findIndex(d => module.dependencies[d] === 0) === -1;
const newPulse = allHigh ? 0 : 1;
module.targets.forEach(target => pulsesToProcess.push({ to: target, pulse: newPulse, from: to }));
if (!allHigh && rxDependencies.includes(to)) {
rxDependencies.splice(rxDependencies.indexOf(to), 1);
cycleLength = lcm(cycleLength, i + 1);
}
}
}
}
console.log(cycleLength);