Solution to Advent of Code 2020 Day 22 Part 2

AOC_2020-22-2.js

const INPUT_FILE = 'day22-input.txt';

// Load dependencies and utilities
const { Axis } = require('../utils/axis');
const NodeFS = require('fs');

// Parse input
const initialPlayers = NodeFS.readFileSync(INPUT_FILE, 'utf-8').split(/(?:\r{2}|\n{2}|(?:\r\n){2})/g)
    .map(player => Axis.from(player.split(/(?:\r\n|\r|\n)/g).slice(1).map(card => parseInt(card.trim()))))
;

// Track number of current game
let currentGameNumber = 0;

/** @param {Axis<number>[]} players @returns {number} The ID of the winning player*/
function playGame(players, showOutput) {
    const gameNum = ++currentGameNumber;
    if (showOutput) console.log(`\n=== Game ${ gameNum } ===`);

    /** Set of all game configurations that have appeared so far */
    const pastGameStates = new Set();

    function hashGame() {
        return players.map(pCards => `[${ pCards.toArray().join(',') }]`).join('');
    }

    function printPlayers(playedCards) {
        if (showOutput) {
            console.log(players.map((pCards, pIdx) => `Player ${ pIdx + 1 }: ${ playedCards === undefined ? '' : (`[${ String(playedCards[pIdx]).padStart(2, ' ') }] <= `) }${ pCards.toArray().map(card => `[${ String(card).padStart(2, ' ') }]`).join('') }`).join('\n'));
        }
    }

    function findWinner(drawnCards) {
        // Check if we need to recurse or play normally
        if (players.every((pCards, pIdx) => pCards.length >= drawnCards[pIdx])) {
            // win by recursion
            const newPlayers = players.map((pCards, pIdx) => Axis.from(pCards.toArray().slice(0, drawnCards[pIdx])));
            return playGame(newPlayers, showOutput);

        } else {
            // win by normal gameplay
            const [ winnerIdx ] = drawnCards.reduce((winner, pCard, pIdx) => {
                const [, wCard] = winner;
                if (pCard > wCard) {
                    winner = [pIdx, pCard];
                }
                return winner;
            }, [0, drawnCards[0]]);
            
            return winnerIdx;
        }
    }
    
    function playRound() {
        // Only play a round if every player still has cards
        if (players.some(p => p.length === 0)) {
            throw new Error('Game is aleady over - one or more players has no cards');
        }
    
        // Check for infinite loop
        const gameHash = hashGame();
        if (pastGameStates.has(gameHash)) {
            // Player 1 (ID 0) wins if we enter a loop
            return 0;
        } else {
            pastGameStates.add(gameHash);
        }

        // draw cards (collect AND remove from original deck)
        const drawnCards = players.map(pCards => pCards.shift());
    
        // Print decks
        printPlayers(drawnCards);

        // Find the winner
        const winnerIdx = findWinner(drawnCards);
        const winner = players[winnerIdx];
    
        // insert under winner
        winner.push(drawnCards[winnerIdx]); // insert winner's card first
        drawnCards.filter((_, pIdx) => pIdx !== winnerIdx).forEach(card => winner.push(card)); // insert remaining cards
    
        // check for victory
        if (players.some(p => p.length === 0)) {
            return winnerIdx;
        }
    
        // return undefined if game is still in progress
        return undefined;
    }

    let winnerIdx = undefined;
    let round = 0;
    do {
        round++;
        if (showOutput) {
            console.log(`[ Game ${ gameNum } Round ${ round } ]`);
        }
    } while ((winnerIdx = playRound()) === undefined);

    if (showOutput) {
        console.log(`Player ${ winnerIdx + 1 } won game ${ gameNum }.`);
        printPlayers();
    }

    if (showOutput) console.log(`Finished game ${ gameNum }.`);
    return winnerIdx;
}

function computeScore(winnerIdx) {
    const winnerCards = initialPlayers[winnerIdx];
    return winnerCards.toArray().reduce((score, card, cardIdx, cardArr) => score + (card * (cardArr.length - cardIdx)), 0);
}

// Part 2
const winnerIdx = playGame(initialPlayers, false);
const winnerScore = computeScore(winnerIdx);
console.log(`\nPart 2: Player ${ winnerIdx + 1 } won with ${ winnerScore } points.`);