Solution to Advent of Code 2020 Day 16 that uses two field-position mapping algorithms to solve a challenge input

AOC_2020-16-Dual.js

function parseInput(path) {
    // split input into main sections
    const [ fields, myTicket, nearTickets ] = require('fs').readFileSync(path, 'utf-8').split('\r\n\r\n');

    // parse into single object
    return {
        // extract list of fields and requirements
        fields: Array.from(fields.matchAll(/^([\w ]+): ([\w\d -]+)$/gm)).map(([, name, reqs], i) => ({
            name,
            options: reqs.split(' or ').map(req => {
                const [, min, max] = req.match(/(\d+)-(\d+)/);
                return {
                    min: parseInt(min),
                    max: parseInt(max)
                };
            })
        })),

        // extract my ticket
        myTicket: myTicket.split('\r\n')[1].split(',').map(field => parseInt(field)),

        // extract nearby tickets
        nearTickets: nearTickets.split('\r\n').slice(1).map(t => t.split(',').map(field => parseInt(field)))
    };
}

const input = parseInput('input-challenge.txt');

// find invalid tickets
const validFieldRanges = input.fields.map(field => field.options).flat();
const invalidFieldValues = input.nearTickets
    .flat()
    .filter(value => validFieldRanges.every(option => value < option.min || value > option.max))
;

// collect all valid tickets
const allValidTickets = input.nearTickets
    .filter(ticket => !ticket.some(value => invalidFieldValues.includes(value)))
    .concat([ input.myTicket ])
;

// List of departure fields (the ones we care about)
const departureFields = [ 'departure location', 'departure station', 'departure platform', 'departure track', 'departure date', 'departure time' ];

// compute field names
const fieldPositions = new Map();
const remainingFields = Array.from(input.fields);
const remainingFieldPositions = remainingFields.map((_, i) => i);

function mapField(field, position) {
    // save field position
    fieldPositions.set(field.name, position);

    // mark field and position as consumed
    remainingFields.splice(remainingFields.indexOf(field), 1);
    remainingFieldPositions.splice(remainingFieldPositions.indexOf(position), 1);
}

function testValues(field, ticketValues) {
    return ticketValues.every(value =>
        field.options.some(option => value >= option.min && value <= option.max)
    );
}

(function () {
    // loop while we have fields, since we have to progressively narrow the search space
    while (remainingFields.length > 0 ) {
        let didFindAMatch = false;

        // loop through each field by position
        for (const i of remainingFieldPositions) {
            // get all the ticket values from this position
            const ticketValues = allValidTickets.map(t => t[i]).flat();
        
            // find each field against this position
            const matchingFields = remainingFields.filter(field => testValues(field, ticketValues));
            
            // if there is exactly one, then we found the match
            if (matchingFields.length === 1) {
                // save field position
                mapField(matchingFields[0], i);

                // keep iterating - we haven't failed yet
                didFindAMatch = true;
            }
        }

        // loop through each field by name
        for (const field of remainingFields) {
            // test each position against this field
            const matchingPositions = remainingFieldPositions.filter(pos => testValues(field, allValidTickets.map(t => t[pos]).flat()));

            // if there is exactly one, then we found the match
            if (matchingPositions.length === 1) {
                // save field position
                mapField(field, matchingPositions[0]);

                // keep iterating - we haven't failed yet
                didFindAMatch = true;
            }
        }

        // detect and break out of stalls
        if (!didFindAMatch) {
            // allow stopping early if departure fields are found
            if (departureFields.every(fName => fieldPositions.has(fName))) {
                console.log(`Search stalled, but all departure fields were found.`);
                return;
            }

            // We did not find enough fields, RIP
            throw new Error(`Search stalled - no new matches found and ${ remainingFields.length } remaining.`);
        }
    }
})();

const part1Answer = invalidFieldValues.reduce((sum, value) => sum + value, 0);
console.log(`Part 1: The sum of invalid fields is ${ part1Answer }`); // Expected: 20058

const part2Answer = departureFields
    .map(field => fieldPositions.get(field))
    .map(fieldPosition => input.myTicket[fieldPosition])
    .reduce((prod, value) => prod * value, 1)
;
console.log(`Part 2: The product of "departure" fields is ${ part2Answer }`); // Expected: 366871907221