Last active 1735070597 Unlisted

Zikeji revised this gist 1735070597. 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