Solution to Advent of Code 2020 Day 10

AOC_2020_Day10.js

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

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

/**
 * @typedef Adapter A charging adapter
 * @type {object}
 * @property {number} jolts Jolt value of the adapter
 * @property {null | number} numDownstreamChains Number of distinct downstream chains between this adapter in the device. Null if not computed.
 * @property {Adapter[]} compatibleAdapters Array of adapters that can be connected to this one.
 */

// parse into adapter objects and track compatible downstream adapters
/** @type {Adapter[]} */
const adapters = inputNumbers.map(jolts => ({
    jolts,
    numDownstreamChains: null,
    compatibleAdapters: []
}));

// populate directed graph
for (const adapter of adapters) {
    adapter.compatibleAdapters = adapters.filter(a => a.jolts > adapter.jolts && (a.jolts - adapter.jolts) < 4)
}

// compute device jolts
const deviceJolts = adapters[adapters.length - 1].jolts + 3;

function chainAllAdapters() {
    /** @type {{ offset: number, jolts: number}[]} */
    const chain = [];

    let currentJolts = 0;
    for (const adapter of adapters) {
        // compute amount of jolts to jump
        const offset = adapter.jolts - currentJolts

        // sanity check
        if (offset > 3 || offset < 0) {
            throw new Error(`Broken chain: ${ currentJolts} => ${ adapter.jolts }`);
        }

        // add to chain
        chain.push({
            offset,
            jolts: adapter.jolts
        });

        // udpate jolt tracking
        currentJolts = adapter.jolts;
    }

    // add device
    chain.push({
        offset: 3,
        jolts: deviceJolts
    });

    return chain;
}

function countAllPossibleChains() {
    /**
     * 
     * @param {Adapter} adapter 
     * @returns {number}
     */
    function countChainsFrom(adapter) {
        // if there is no memoized solution, then we need to compute it
        if (adapter.numDownstreamChains === null) {
            // if this is the last adapter in the chain, then it must be close enough to the device
            if (adapter.compatibleAdapters.length === 0) {
                // this chain is only valid if it ends exactly 3 jolts from the device
                const isValidTerminator = deviceJolts - adapter.jolts === 3;
                adapter.numDownstreamChains = isValidTerminator ? 1 : 0;

            } else {
                // this is not the last adapter, so we count normally
                adapter.numDownstreamChains = adapter.compatibleAdapters.reduce((chainCount, compatibleAdapter) => chainCount + countChainsFrom(compatibleAdapter), 0);
            }
        }

        // return memoized solution
        return adapter.numDownstreamChains;
    }

    // create a fake "adapter" for the plane to kick-start the algorithm
    /** @type {Adapter} */
    const planeAdapter = {
        jolts: 0,
        numDownstreamChains: null,
        compatibleAdapters: adapters.filter(a => a.jolts < 4)
    };

    // compute total chains
    return countChainsFrom(planeAdapter);
}

// Part 1
const allAdaptersChain = chainAllAdapters();
const allAdapters1JoltDiffs = allAdaptersChain.filter(step => step.offset === 1);
const allAdapters3JoltDiffs = allAdaptersChain.filter(step => step.offset === 3);
console.log(`Part 1: ${ allAdapters1JoltDiffs.length * allAdapters3JoltDiffs.length }`);

// Part 2
const totalChains = countAllPossibleChains();
console.log(`Part 2: Found ${ totalChains } total chains.`);