Alternate version of 2020 day 10 challenge that uses no recursion (for a challenge)

AOC_2020_Day10_NoRecurse.js

const { parseInputFile } = require('../utils/parser');

class Queue {
    constructor() {
        this.head = null;
        this.tail = null;
    }

    push(value) {
        const node = {
            value,
            next: null
        };

        if (this.tail) {
            this.tail.next = node;
        } else {
            this.tail = node;
        }

        if (!this.head) {
            this.head = node;
        }
    }

    peek() {
        if (this.head) {
            return this.head.value;
        } else {
            return undefined;
        }
    }

    pop() {
        if (this.head) {
            const retVal = this.head.value;
            if (this.head === this.tail) {
                this.head = null;
                this.tail = null;
            } else {
                this.head = this.head.next;
            }
            return retVal;
        } else {
            return undefined;
        }
    }

    isEmpty() {
        return this.head === null;
    }
};

// parse input file into array of numbers
const inputNumbers = parseInputFile('day10-challenge.txt', /^(\d+)$/gm)
    .map(([_, num]) => BigInt(parseInt(num)))
    .sort((a, b) => a === b ? 0 : (a > b ? 1 : -1)) // JS uses an alaphabetic sort by default, even for numbers
;

/**
 * @typedef Adapter A charging adapter
 * @type {object}
 * @property {BigInt} jolts Jolt value of the adapter
 * @property {null | BigInt} numDownstreamChains Number of distinct downstream chains between this adapter in the device. Null if not computed.
 * @property {Adapter[]} prevAdapters Array of adapters that can feed into this one
 * @property {Adapter[]} nextAdapters Array of adapters that this one feeds into
 */

/**
 * @param {BigInt} jolts 
 * @returns {Adapter}
 */
function makeAdapter(jolts) {
    return {
        jolts,
        numDownstreamChains: null,
        prevAdapters: [],
        nextAdapters: []
    }
}

// create a fake "adapter" for the plane to kick-start the algorithm
const planeAdapter = makeAdapter(0n);

// parse into directed graph
/** @type {Adapter[]} */
const adapters = [];
for (let i = inputNumbers.length - 1; i >= 0; i--) {
    const jolts = inputNumbers[i];

    const adapter = makeAdapter(jolts);

    adapters[i] = adapter;

    for (let j = i + 1; j < inputNumbers.length; j++) {
        const nextAdapter = adapters[j];
        if (nextAdapter.jolts - jolts > 3n) {
            break;
        }
        adapter.nextAdapters.push(nextAdapter);
        nextAdapter.prevAdapters.push(adapter);
    }

    if (adapter.jolts < 4n) {
        planeAdapter.nextAdapters.push(adapter);
        adapter.prevAdapters.push(planeAdapter);
    }
}

function countAllPossibleChains() {
    const queue = new Queue();

    // start from root adapter
    const root = adapters[adapters.length - 1];
    queue.push(root);

    while (!queue.isEmpty()) {
        /** @type {Adapter} */
        const adapter = queue.pop();

        // skip adapters that are already processed
        if (adapter.numDownstreamChains === null) {
            // if not populated, then see if we can populate it now
            const unfilledDownstreamAdapters = adapter.nextAdapters.filter(a => a.numDownstreamChains === null);
            if (unfilledDownstreamAdapters.length === 0) {
                // if all of the dependencies are calculated, then calculate and memoize this adapter
                if (adapter === root) {
                    // if this is the root, then set default value
                    adapter.numDownstreamChains = 1n;
                } else {
                    adapter.numDownstreamChains = adapter.nextAdapters.reduce((total, a) => total + a.numDownstreamChains, 0n);
                }

                // queue dependents now that we are populated
                adapter.prevAdapters.forEach(a => queue.push(a));
            } else {
                // if we still can't populate, then push everything that we depend on
                unfilledDownstreamAdapters.forEach(a => queue.push(a));
            }
        }
    }

    return planeAdapter.numDownstreamChains;
}

// time it
const startTime = process.hrtime.bigint();
const totalChains = countAllPossibleChains();
const endTime = process.hrtime.bigint();

const totalTime = endTime - startTime;
const totalTimeMs = Number(totalTime) / 1000000;

const totalChainsString = String(totalChains);
const nonZeroDigits = totalChainsString.match(/^([1-9]\d+[1-9])0+$/)[1];
const last10NonZeroDigis = nonZeroDigits.substring(nonZeroDigits.length - 10);
console.log(`Found ...${ last10NonZeroDigis } total chains in ${totalTimeMs}ms.`);