day24.js
· 5.1 KiB · JavaScript
Raw
/**
* @typedef {object} Sequence
* @property {string[]} inputs
* @property {string} gate
* @property {string} output
*/
/**
* @param {Sequence[]} sequence
* @returns {Sequence[]}
*/
const sort = (sequence) => {
const sequenceObj = {};
for (const next of sequence) {
sequenceObj[next.output] = next;
}
const seen = new Set();
const stack = [];
/** @param {string} wire */
const topologicalSort = (wire) => {
if (!seen.has(wire)) {
seen.add(wire);
const r1 = sequenceObj[wire].inputs[0];
const r2 = sequenceObj[wire].inputs[1];
if (r1 in sequenceObj) topologicalSort(r1);
if (r2 in sequenceObj) topologicalSort(r2);
stack.push(wire);
}
}
for (const wire in sequenceObj) {
topologicalSort(wire);
}
return stack.filter(wire => wire in sequenceObj).map(wire => sequenceObj[wire]);
}
/**
* @param {string} input
* @returns {System}
*/
const parseInput = (input) => {
const [initialValues, sequenceLines] = input.split(/\r?\n\r?\n/g).map(v => v.split(/\r?\n/g).filter(v => v.length > 0));
const system = new System();
initialValues.forEach((v) => {
const [register, value] = v.split(': ');
system.registers[register] = parseInt(value);
});
system.sequence = sort(sequenceLines.map(v => {
const [r1, gate, r2, _, r3] = v.split(' ');
return {
inputs: [r1, r2],
gate,
output: r3,
};
}));
return system;
}
class System {
/** @type {Record<string, number>} */
registers = {};
/** @type {Sequence[]} */
sequence = [];
static gates = {
AND(i1, i2) {
return i1 & i2;
},
OR(i1, i2) {
return i1 | i2;
},
XOR(i1, i2) {
return i1 ^ i2;
}
};
/**
* @param {Record<string, number>} registers
* @param {string} designation
* @returns {string}
*/
static readRegisterBinary(registers, designation) {
return Object.keys(registers)
.filter(k => k.startsWith(designation))
.sort((a, b) => parseInt(a.slice(1)) - parseInt(b.slice(1)))
.reduce((a, k) => a = `${registers[k]}${a}`, '')
}
/**
* Simulate the logic running and return the output.
* @returns {number}
*/
simulate() {
const sequence = this.sequence.map(r => ({ ...r }));
const registers = { ...this.registers };
for (const next of sequence) {
const { inputs, gate, output } = next;
registers[output] = System.gates[gate](registers[inputs[0]], registers[inputs[1]]);
}
return parseInt(System.readRegisterBinary(registers, 'z'), 2);
}
}
const input = require('fs').readFileSync(0, 'utf-8');
const system = parseInput(input);
console.log('Part One:', system.simulate());
const swapRand = () => {
const rSwaps = [];
while (true) {
if (rSwaps.length === 8) break;
const rNext = Math.floor(Math.random() * (system.sequence.length))
if (!rSwaps.includes(rNext)) {
rSwaps.push(rNext);
}
}
const swapGroups = [rSwaps.slice(0, 2), rSwaps.slice(2, 4), rSwaps.slice(4, 6), rSwaps.slice(6, 8)];
const sequenceBackup = system.sequence.map(r => ({ ...r }));
const swaps = [];
for (const [r1, r2] of swapGroups) {
const v1 = system.sequence[r1].output;
const v2 = system.sequence[r2].output;
system.sequence[r1].output = v2;
system.sequence[r2].output = v1;
swaps.push(v1, v2);
}
system.sequence = sort(system.sequence);
const out = system.simulate();
system.sequence = sequenceBackup;
return {
out,
swaps: [...swaps].sort(),
orig: swaps
};
}
const x = System.readRegisterBinary(system.registers, 'x');
const y = System.readRegisterBinary(system.registers, 'y');
const expected = parseInt(x, 2) + parseInt(y, 2);
const logger = new class {
ops = 0;
lOps = 0;
lOpsTs = new Date().getTime();
incrOps() {
const curTs = new Date().getTime();
if (curTs - this.lOpsTs >= 1000) {
this.lOps = this.ops;
this.ops = 0;
this.lOpsTs = curTs;
}
this.ops += 1;
}
last = 0;
write(lastOut, force) {
const curTs = new Date().getTime();
if (force === true || curTs - this.last > 250) {
process.stdout.clearLine(1);
process.stdout.cursorTo(0);
const parts = [];
parts.push(`ops/s=${this.lOps}`);
parts.push(`last_out=${lastOut}`);
process.stdout.write(parts.join(' '));
this.last = curTs;
}
}
}
console.log();
while (true) {
logger.incrOps()
const { out, swaps, orig } = swapRand();
if (out === expected) {
process.stdout.clearLine(1);
process.stdout.cursorTo(0);
process.stdout.write(`Match: ${swaps.join(',')} [${orig.join(',')}]\n`);
process.stdout.write('\n');
}
logger.write(swaps.join(','));
}
| 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 | } |