Day 4/2021 - Giant Squid

Day four of AoC 2021 (available at https://adventofcode.com/2021/day/4) takes a surreal turn: a giant squid has attached itself to the submarine and wants to play Bingo. You've got to know when to hold 'em, know when to fold 'em — especially when part two asks us to deliberately lose.

The input has drawn numbers on the first line, followed by 5×5 Bingo boards separated by blank lines.

Parsing the Input

This is the first puzzle this year where parsing is genuinely tedious. We need to extract the draw sequence and multiple boards:

interface BingoGame {
    numbers: number[];
    tickets: BingoTicket[];
}

class BingoTicket {
    numbers: number[][];
    hits: number[] = [];
    won: boolean = false;
    
    constructor(numbers: number[][]) {
        this.numbers = numbers;
    }
    
    hasNumber(n: number): boolean {
        return this.numbers.some(row => row.includes(n));
    }
    
    mark(n: number): void {
        if (this.hasNumber(n)) {
            this.hits.push(n);
        }
    }
    
    isWinner(): boolean {
        // Check rows
        for (const row of this.numbers) {
            if (row.every(n => this.hits.includes(n))) {
                return true;
            }
        }
        // Check columns
        for (let col = 0; col < 5; col++) {
            const column = this.numbers.map(row => row[col]);
            if (column.every(n => this.hits.includes(n))) {
                return true;
            }
        }
        return false;
    }
    
    getRemaining(): number[] {
        return this.numbers.flat().filter(n => !this.hits.includes(n));
    }
    
    reset(): void {
        this.hits = [];
        this.won = false;
    }
}

For parsing the boards, I used regex to handle the inconsistent spacing (single-digit numbers are padded):

const regex = /^\s*(\d+)\s+(\d+)\s+(\d+)\s+(\d+)\s+(\d+)$/;

Regex101 is invaluable here. The boards have variable spacing, and regex handles it cleanly.

Part One: First Winner

Draw numbers until a board wins. Calculate the score: sum of unmarked numbers × winning number.

const partOne = (input: BingoGame, debug: boolean) => {
    const draws = input.numbers.slice();
    const tickets = input.tickets;
    tickets.forEach(t => t.reset());
    
    let winner: BingoTicket | null = null;
    
    while (!winner) {
        const draw = draws.shift()!;
        
        for (const ticket of tickets) {
            ticket.mark(draw);
            if (ticket.isWinner()) {
                winner = ticket;
                break;
            }
        }
    }
    
    const remaining = winner.getRemaining();
    const sum = remaining.reduce((a, b) => a + b, 0);
    const lastDraw = winner.hits[winner.hits.length - 1];
    
    return sum * lastDraw;
};

Part Two: Let the Squid Win

Now we need to find the last board to win. The strategy: keep playing until all boards have won, tracking which one wins last.

The Mutation Bug

My first attempt used for...of with array splicing to remove winning boards:

for (const ticket of tickets) {
    ticket.mark(draw);
    if (ticket.isWinner()) {
        winner = ticket;
        tickets.splice(tickets.indexOf(ticket), 1); // BUG!
        break;
    }
}

The break was a copy-paste error from part one. It stopped after marking the first ticket that had the drawn number, not after finding a winner. Boards weren't getting marked properly.

But there's a deeper issue: mutating an array while iterating with for...of skips elements.

If you have [1, 2, 3, 4, 5] and remove element at index 2 (the 3), everything shifts left. The loop's internal index advances to 3, which now points to 5 — you've skipped 4 entirely.

The fix: use an index-based loop and adjust the index when removing:

for (let i = 0; i < tickets.length; i++) {
    const ticket = tickets[i];
    ticket.mark(draw);
    if (ticket.isWinner()) {
        winner = ticket;
        tickets.splice(i, 1);
        i--; // Compensate for the removal
    }
}

Or better: track wins with a flag instead of removing:

const partTwo = (input: BingoGame, debug: boolean) => {
    const draws = input.numbers.slice();
    const tickets = input.tickets;
    tickets.forEach(t => t.reset());
    
    let winner: BingoTicket | null = null;
    let winCount = 0;
    
    while (winCount !== tickets.length) {
        const draw = draws.shift()!;
        
        for (const ticket of tickets) {
            if (ticket.won) continue;
            
            ticket.mark(draw);
            if (ticket.isWinner()) {
                ticket.won = true;
                winner = ticket;
                winCount++;
            }
        }
    }
    
    const remaining = winner!.getRemaining();
    const sum = remaining.reduce((a, b) => a + b, 0);
    const lastDraw = winner!.hits[winner!.hits.length - 1];
    
    return sum * lastDraw;
};

Now we don't modify the array at all — we just skip boards that have already won.

The Reset Problem

Another gotcha: objects are passed by reference. If part one modifies the tickets (adding hits), part two gets the modified versions. The reset() method clears state between runs:

reset(): void {
    this.hits = [];
    this.won = false;
}

Always call it before processing to ensure clean state.

Performance

The solution runs in about 30ms. It's not optimal — we recalculate isWinner() and check hits.includes() repeatedly. A production version would use Sets for O(1) lookups and cache winner status. But for a one-shot puzzle, it's fast enough.

Takeaways

1. Don't mutate arrays while iterating: If you must remove elements during iteration, use index-based loops and adjust the index, or use a flag-based approach.

2. for...of hides the index: This abstraction is great until you need to modify the collection. Then it bites you.

3. Copy-paste bugs are real: The break statement from part one didn't belong in part two. Always review pasted code.

4. Reset state between runs: When objects are reused, ensure they start in a clean state. Reference semantics mean part one's modifications persist into part two.

5. Classes can help organize complex state: The BingoTicket class encapsulates the board, hits, and win logic. It's not the prettiest class (public properties everywhere), but it's better than juggling raw arrays.

The full solution is available in the repository.