Zikeji revised this gist . Go to revision
1 file changed, 194 insertions
day24.js(file created)
@@ -0,0 +1,194 @@ | |||
1 | + | /** | |
2 | + | * @typedef {object} Sequence | |
3 | + | * @property {string[]} inputs | |
4 | + | * @property {string} gate | |
5 | + | * @property {string} output | |
6 | + | */ | |
7 | + | ||
8 | + | /** | |
9 | + | * @param {Sequence[]} sequence | |
10 | + | * @returns {Sequence[]} | |
11 | + | */ | |
12 | + | const sort = (sequence) => { | |
13 | + | const sequenceObj = {}; | |
14 | + | ||
15 | + | for (const next of sequence) { | |
16 | + | sequenceObj[next.output] = next; | |
17 | + | } | |
18 | + | ||
19 | + | const seen = new Set(); | |
20 | + | const stack = []; | |
21 | + | ||
22 | + | /** @param {string} wire */ | |
23 | + | const topologicalSort = (wire) => { | |
24 | + | if (!seen.has(wire)) { | |
25 | + | seen.add(wire); | |
26 | + | const r1 = sequenceObj[wire].inputs[0]; | |
27 | + | const r2 = sequenceObj[wire].inputs[1]; | |
28 | + | if (r1 in sequenceObj) topologicalSort(r1); | |
29 | + | if (r2 in sequenceObj) topologicalSort(r2); | |
30 | + | stack.push(wire); | |
31 | + | } | |
32 | + | } | |
33 | + | ||
34 | + | for (const wire in sequenceObj) { | |
35 | + | topologicalSort(wire); | |
36 | + | } | |
37 | + | ||
38 | + | return stack.filter(wire => wire in sequenceObj).map(wire => sequenceObj[wire]); | |
39 | + | } | |
40 | + | ||
41 | + | /** | |
42 | + | * @param {string} input | |
43 | + | * @returns {System} | |
44 | + | */ | |
45 | + | const parseInput = (input) => { | |
46 | + | const [initialValues, sequenceLines] = input.split(/\r?\n\r?\n/g).map(v => v.split(/\r?\n/g).filter(v => v.length > 0)); | |
47 | + | const system = new System(); | |
48 | + | initialValues.forEach((v) => { | |
49 | + | const [register, value] = v.split(': '); | |
50 | + | system.registers[register] = parseInt(value); | |
51 | + | }); | |
52 | + | ||
53 | + | system.sequence = sort(sequenceLines.map(v => { | |
54 | + | const [r1, gate, r2, _, r3] = v.split(' '); | |
55 | + | return { | |
56 | + | inputs: [r1, r2], | |
57 | + | gate, | |
58 | + | output: r3, | |
59 | + | }; | |
60 | + | })); | |
61 | + | ||
62 | + | return system; | |
63 | + | } | |
64 | + | ||
65 | + | class System { | |
66 | + | /** @type {Record<string, number>} */ | |
67 | + | registers = {}; | |
68 | + | /** @type {Sequence[]} */ | |
69 | + | sequence = []; | |
70 | + | ||
71 | + | static gates = { | |
72 | + | AND(i1, i2) { | |
73 | + | return i1 & i2; | |
74 | + | }, | |
75 | + | OR(i1, i2) { | |
76 | + | return i1 | i2; | |
77 | + | }, | |
78 | + | XOR(i1, i2) { | |
79 | + | return i1 ^ i2; | |
80 | + | } | |
81 | + | }; | |
82 | + | ||
83 | + | /** | |
84 | + | * @param {Record<string, number>} registers | |
85 | + | * @param {string} designation | |
86 | + | * @returns {string} | |
87 | + | */ | |
88 | + | static readRegisterBinary(registers, designation) { | |
89 | + | return Object.keys(registers) | |
90 | + | .filter(k => k.startsWith(designation)) | |
91 | + | .sort((a, b) => parseInt(a.slice(1)) - parseInt(b.slice(1))) | |
92 | + | .reduce((a, k) => a = `${registers[k]}${a}`, '') | |
93 | + | } | |
94 | + | ||
95 | + | /** | |
96 | + | * Simulate the logic running and return the output. | |
97 | + | * @returns {number} | |
98 | + | */ | |
99 | + | simulate() { | |
100 | + | const sequence = this.sequence.map(r => ({ ...r })); | |
101 | + | const registers = { ...this.registers }; | |
102 | + | for (const next of sequence) { | |
103 | + | const { inputs, gate, output } = next; | |
104 | + | ||
105 | + | registers[output] = System.gates[gate](registers[inputs[0]], registers[inputs[1]]); | |
106 | + | } | |
107 | + | return parseInt(System.readRegisterBinary(registers, 'z'), 2); | |
108 | + | } | |
109 | + | } | |
110 | + | ||
111 | + | const input = require('fs').readFileSync(0, 'utf-8'); | |
112 | + | const system = parseInput(input); | |
113 | + | ||
114 | + | console.log('Part One:', system.simulate()); | |
115 | + | ||
116 | + | const swapRand = () => { | |
117 | + | const rSwaps = []; | |
118 | + | ||
119 | + | while (true) { | |
120 | + | if (rSwaps.length === 8) break; | |
121 | + | const rNext = Math.floor(Math.random() * (system.sequence.length)) | |
122 | + | if (!rSwaps.includes(rNext)) { | |
123 | + | rSwaps.push(rNext); | |
124 | + | } | |
125 | + | } | |
126 | + | ||
127 | + | const swapGroups = [rSwaps.slice(0, 2), rSwaps.slice(2, 4), rSwaps.slice(4, 6), rSwaps.slice(6, 8)]; | |
128 | + | ||
129 | + | const sequenceBackup = system.sequence.map(r => ({ ...r })); | |
130 | + | const swaps = []; | |
131 | + | for (const [r1, r2] of swapGroups) { | |
132 | + | const v1 = system.sequence[r1].output; | |
133 | + | const v2 = system.sequence[r2].output; | |
134 | + | system.sequence[r1].output = v2; | |
135 | + | system.sequence[r2].output = v1; | |
136 | + | swaps.push(v1, v2); | |
137 | + | } | |
138 | + | ||
139 | + | system.sequence = sort(system.sequence); | |
140 | + | ||
141 | + | const out = system.simulate(); | |
142 | + | system.sequence = sequenceBackup; | |
143 | + | return { | |
144 | + | out, | |
145 | + | swaps: [...swaps].sort(), | |
146 | + | orig: swaps | |
147 | + | }; | |
148 | + | } | |
149 | + | ||
150 | + | const x = System.readRegisterBinary(system.registers, 'x'); | |
151 | + | const y = System.readRegisterBinary(system.registers, 'y'); | |
152 | + | const expected = parseInt(x, 2) + parseInt(y, 2); | |
153 | + | ||
154 | + | const logger = new class { | |
155 | + | ops = 0; | |
156 | + | lOps = 0; | |
157 | + | lOpsTs = new Date().getTime(); | |
158 | + | incrOps() { | |
159 | + | const curTs = new Date().getTime(); | |
160 | + | if (curTs - this.lOpsTs >= 1000) { | |
161 | + | this.lOps = this.ops; | |
162 | + | this.ops = 0; | |
163 | + | this.lOpsTs = curTs; | |
164 | + | } | |
165 | + | this.ops += 1; | |
166 | + | } | |
167 | + | ||
168 | + | last = 0; | |
169 | + | write(lastOut, force) { | |
170 | + | const curTs = new Date().getTime(); | |
171 | + | if (force === true || curTs - this.last > 250) { | |
172 | + | process.stdout.clearLine(1); | |
173 | + | process.stdout.cursorTo(0); | |
174 | + | const parts = []; | |
175 | + | parts.push(`ops/s=${this.lOps}`); | |
176 | + | parts.push(`last_out=${lastOut}`); | |
177 | + | process.stdout.write(parts.join(' ')); | |
178 | + | this.last = curTs; | |
179 | + | } | |
180 | + | } | |
181 | + | } | |
182 | + | ||
183 | + | console.log(); | |
184 | + | while (true) { | |
185 | + | logger.incrOps() | |
186 | + | const { out, swaps, orig } = swapRand(); | |
187 | + | if (out === expected) { | |
188 | + | process.stdout.clearLine(1); | |
189 | + | process.stdout.cursorTo(0); | |
190 | + | process.stdout.write(`Match: ${swaps.join(',')} [${orig.join(',')}]\n`); | |
191 | + | process.stdout.write('\n'); | |
192 | + | } | |
193 | + | logger.write(swaps.join(',')); | |
194 | + | } |
Newer
Older