Solution to Advent of Code 2020 Day 19, with a cache for memoization

AOC_2020-19_Cache.js

// Define run parameters
const INPUT_FILE = 'day19-input-part2.txt';
const END_OF_LINE = '\r\n';

// Define types
/**
 * @typedef {string[]} Message
 */
/**
 * @typedef {number | string} RuleToken
 */
/**
 * @typedef {RuleToken[]} RuleSequence
 */
/**
 * @typedef {RuleSequence[]} Rule
 */
/**
 * @typedef {object} InputData
 * @property {Map<number, Rule>} rules
 * @property {Message[]} messages
 */

// Load input data
const inputData = (function () {
    // read input file as UTF 8
    const inputText = require('fs').readFileSync(INPUT_FILE, 'utf-8');

    // Split into major sections
    const [ ruleSectionText, messageSectionText ] = inputText.split(`${ END_OF_LINE }${ END_OF_LINE }`).map(section => section.split(END_OF_LINE));
    
    // extract rules
    /** @type {[number, RuleSequence[]][]} */
    const rules = ruleSectionText.map(ruleText => {
        // split rule line into sections
        const [ ruleNumText, ruleDefText ] = ruleText.trim().split(': ');

        // create rule tuple
        return [
            // get rule number
             parseInt(ruleNumText),

            // get rule options
            ruleDefText.split(' | ').map(option =>
                // get option sequence
                option.split(' ').map(token => {
                    if (token.startsWith('"')) {
                        // token is a string character to match
                        return token.substring(1, token.length - 1);
                    } else {
                        // token is a reference to another rule
                        return parseInt(token);
                    }
                })
            )
        ];
    });
    
    // create map of rules
    const rulesMap = new Map(rules);

    // trim messages and split into chars
    const messages = messageSectionText.map(message => Array.from(message.trim()));

    /** @type {InputData} */
    const data = { rules: rulesMap, messages };
    return data;
})();

/**
 * Checks if a message matches a specified rule
 * @param {Message} message 
 * @param {Rule} startRule 
 * @returns {boolean}
 */
function testMessageAgainstRule(message, startRule) {
    const NO_MATCH = 0;

    /** @type {Map<number, Map<RuleSequence, number[]>>} */
    const subtreeCache = new Map();
    /** @param {number} offset @param {RuleSequence} sequence @returns {number[]} */
    function getCachedSubTree(offset, sequence) {
        if (!subtreeCache.has(offset)) return undefined;
        return subtreeCache.get(offset).get(sequence);
    }
    /** @param {number} offset @param {RuleSequence} sequence @param {number[]} subtree */
    function saveCachedSubTree(offset, sequence, subtree) {
        let sequenceCache = subtreeCache.get(offset);
        if (!sequenceCache) {
            sequenceCache = new Map();
            subtreeCache.set(offset, sequenceCache);
        }
        sequenceCache.set(sequence, subtree);
    }

    /** @param {number} offset @param {RuleSequence} sequence @param {number} seqIndex @param {number} loopCount @returns {number[]} */
    function testAt(offset, sequence, seqIndex, loopCount) {
        // if we overflow the end, then fail
        if (offset >= message.length) {
            return [ NO_MATCH ];
        }

        // if we recurse too many times without a match, then fail
        if (loopCount > message.length) {
            return [ NO_MATCH ];
        }

        // get current token
        const token = sequence[seqIndex];
        const nextSeqIndex = seqIndex + 1;
        const isEndOfSequence = nextSeqIndex >= sequence.length;

        // if we have just entered a sequence, then try to use cached value
        if (seqIndex === 0) {
            const cachedResults = getCachedSubTree(offset, sequence);
            if (cachedResults) {
                return cachedResults;
            }
        }

        /** @type {number[]} */
        let nextOffsets;
        if (typeof(token) === 'number') {
            // token is rule reference
            const nextRule = inputData.rules.get(token);

            // test each option
            nextOffsets = nextRule.map(nextSeq => testAt(offset, nextSeq, 0, loopCount + 1)).flat();

        } else {
            // check current symbol
            if (message[offset] === token) {
                nextOffsets = [ offset + 1 ];
            } else {
                nextOffsets = [ NO_MATCH ];
            }
        }

        // if this is NOT the end of the sequence, then check next
        if (!isEndOfSequence) {
            nextOffsets = nextOffsets
                .filter(consumed => consumed !== NO_MATCH)
                .map(off => testAt(off, sequence, nextSeqIndex, 0))
                .flat();
        }

        // return all the offsets that should be checked next
        const results = nextOffsets.filter(consumed => consumed !== NO_MATCH);

        // cache results
        if (seqIndex === 0) {
            saveCachedSubTree(offset, sequence, results);
        }

        return results;
    }
    
    // Check if any of the matches used exactly all the characters from the input
    return startRule
        .map(sequence => testAt(0, sequence, 0, 0))
        .flat()
        .filter(off => off !== NO_MATCH)
        .some(off => off === message.length);
}

const rule0 = inputData.rules.get(0);

const messagesMatchingRule0 = inputData.messages.filter(message => testMessageAgainstRule(message, rule0));
console.log(`Number of messages matching rule 0 = ${ messagesMatchingRule0.length }`);