Solution for Advent of Code 2020 Day 13 Part 2 using Euler's Extended Algorithm to solve very large inputs

AOC_2020_Day13_Part2_EEA.js

const fs = require('fs');

/**
 * 
 * @param {bigint} a 
 * @param {bigint} n
 */
function solveMMI(a, n) {
    let t = 0n;
    let newT = 1n;
    let r = n;
    let newR = a;

    while (newR !== 0n) {
        const quotient = r / newR;

        const tmpT = t;
        t = newT;
        newT = tmpT - (quotient * newT);

        const tmpR = r;
        r = newR;
        newR = tmpR - (quotient * newR);
    }

    if (r > 1n) {
        throw new Error('not invertible');
    }

    if (t < 0n) {
        t += n; 
    }

    return t;
}

/**
 * @param {{a: bigint, n: bigint}[]} system 
 */
function solveCRT(system) {
    const prod = system.reduce((p, con) => p * con.n, 1n);
    return system.reduce((sm, con) => {
        const p = prod / con.n;
        const mmi = solveMMI(p, con.n);
        sm = sm + (con.a * mmi * p);

        return sm;
    }, 0n) % prod;
}

const inputs = fs.readFileSync('day13-input.txt', 'utf-8')
.split('\r\n')[1]
.split(',')
.map((id, i) => ({ id, i }))
.filter(eq => eq.id !== 'x')
.map(eq => {
    const n = parseInt(eq.id.trim());
    return {
        n: BigInt(n),
        i: eq.i,
        a: BigInt(n - eq.i)
    };
});

const solution = solveCRT(inputs);

// verify output
for (const input of inputs) {
    const target = solution - input.a;
    if (target % input.n !== 0n) {
        console.log(`Validation error`, input);
    }
}

// expected for input: 556100168221141
console.log(`Part 2: ${ solution }`);