Solution to Advent of Code 2020 Day 9 in JavaScript

AOC_2020_Day9.js

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

// parse input file into array of numbers
const inputNumbers = parseInputFile('day9-input.txt', /^(\d+)$/gm)
    .map(([_, num]) => parseInt(num))
;

/**
 * Finds the minimum and maximum values of all the numbers in {@link inputNumbers} between indexes start and end.
 * 
 * @param {number} start Start index of range
 * @param {number} end End index of range
 * @returns {number[]} Tuple of two numbers - min and max of range.
 */
function findRange(start, end) {
    let min = inputNumbers[start];
    let max = inputNumbers[start];

    // Loop through each of the previous 25 numbers to find min and max.
    // First index is skipped because it is preloaded above
    for (let i = start + 1; i < end; i++) {
        const num = inputNumbers[i];

        if (num > max) {
            max = num;
        } else if (num < min) {
            min = num;
        }
    }

    return [ min, max ];
}

/**
 * Brute-force scan to find the min and max of the past 25 numbets from pos
 * @param {number} pos Position to search from
 * @returns {number[]} Tuple of two numbers - min and max of range.
 */
function scanMinMax(pos) {
    return findRange(pos - 25, pos);
}

/**
 * Update the min and max range to reflect a right shift of one position.
 * @param {number} pos New position to search from (previous 25 are range)
 * @param {number} min The previous minimum value
 * @param {number} max The previous maximum value
 * @returns {number[]} Tuple of two numbers - min and max of range.
 */
function syncMinMax(pos, min, max) {
    // check if we are dropping the min or max
    const lastNum = inputNumbers[pos - 26];
    if (lastNum === min || lastNum === max) {
        // rescan the whole range to find new endpoints
        [ min, max ] = scanMinMax(pos);

        
    // if we did not drop an endpoint, then check if we added a new one
    } else {
        const nextNum = inputNumbers[pos - 1];
        if (nextNum < min) {
            // adding new min
            min = nextNum;
        }
        if (nextNum > max) {
            // adding new max
            max = nextNum;
        }
    }

    return [ min, max ];
}

/**
 * Brute-force check if a number at index pos is a sum of two of the previous 25 numbers
 * @param {number} pos Position to check
 * @return {boolean} true if the number at pos is a sum
 */
function isSum(pos) {
    const num = inputNumbers[pos];

    // brute force O(n^2) check
    for (let x = pos - 25; x < pos; x++) {
        for (let y = x; y < pos; y++) {
            if (num === inputNumbers[x] + inputNumbers[y]) {
                return true;
            }
        }
    }

    return false;
}

/**
 * Finds the index of the first number that is not a sum of the previous 25 numbers
 * @returns {number} Index of the number that was found
 * @throws {Error} If no number is found
 */
function findBadIndex() {
    let min = 0;
    let max = 0;

    // validate every number past preamble
    for (let i = 25; i < inputNumbers.length; i++) {
        // update min / max for later numbers
        [ min, max ] = syncMinMax(i, min, max);

        const num = inputNumbers[i];

        // short circuit if number is out of range
        if (num < (min * 2) || num > (max * 2)) {
            console.log(`Out of range: ${ num } @ ${ i }`);
            return i;
        }

        // manually check if in range
        if (!isSum(i)) {
            console.log(`Not a sum: ${ num } @ ${ i }`);
            return i;
        }
    }

    throw new Error('No bad number found');
}

// Part 1

const badIndex = findBadIndex();
const badNum = inputNumbers[badIndex];
console.log(`Part 1: found first bad number ${ badNum } at index ${ badIndex }.`);

// Part 2

/**
 * Finds a range of numbers that sum to {@link badNum}.
 * @returns {number[]} Tuple of two numbers - min and max of range.
 */
function findNumsThatTotalBadNum() {
    for (let start = 0; start < inputNumbers.length; start++) {
        let rangeTotal = inputNumbers[start];

        for (let end = start + 1; end < inputNumbers.length; end++) {
            rangeTotal += inputNumbers[end];

            // if we find the number, then this is the range
            if (rangeTotal === badNum) {
                return [ start, end ];
            }

            // end this range if we overflow badNum
            if (rangeTotal > badNum) {
                break;
            }
        }
    }

    throw new Error(`Failed to find a contigous range totalling ${ badNum }.`);
}

const [ badStart, badEnd ] = findNumsThatTotalBadNum();
const [ badMin, badMax ] = findRange(badStart, badEnd);
const weakness = badMin + badMax;
console.log(`Part 2: found weakness ${ weakness } @ [${ badStart }, ${ badEnd }].`);