AoC 2021 D4: Giant Squid

| Problem statement | Source code | Tags: Data structures

Part 1

The main problems to solve are: (1) where is the number on the board? (2) how to check for a win? (3) how to count the total score? A nice observation is that we don't need a physical 2D array for any of these tasks. For task 1, we can use a Map<number, [row: number, col: number]> to look up the position of a number; a 2D array would take 25 lookups. For task 2, we can track the number of marked numbers in each row and column. For each marked number, we increment the corresponding row and column counters; if any of them reaches 5, we have a win. For task 3, we can maintain a running total of unmarked numbers, which starts as the sum of the board; when we mark a number, we subtract it from the total.

This is the part for parsing the input and setting up the data structures:

const seq = data[0].split(",").map((n) => parseInt(n, 10));
const boards = data
  .slice(2)
  .join("\n")
  .split("\n\n")
  .map((s) => {
    const board = s.split("\n").map((line) =>
      line
        .trim()
        .split(/\s+/)
        .map((n) => parseInt(n, 10)),
    );
    const mapping = new Map<number, [number, number]>();
    for (let r = 0; r < board.length; r++) {
      for (let c = 0; c < board[r].length; c++) {
        mapping.set(board[r][c], [r, c]);
      }
    }
    return {
      mapping,
      rowCount: Array(board.length).fill(0),
      colCount: Array(board[0].length).fill(0),
      boardSum: board.flat().reduce((a, b) => a + b, 0),
    };
  });

This is the part for playing the game:

const scores: number[] = [];
const won = new Set<number>();
for (const n of seq) {
  for (const [i, data] of boards.entries()) {
    const { mapping, rowCount, colCount } = data;
    if (!mapping.has(n) || won.has(i)) continue;
    const [r, c] = mapping.get(n)!;
    rowCount[r]++;
    colCount[c]++;
    data.boardSum -= n;
    const isWon = rowCount[r] === 5 || colCount[c] === 5;
    if (isWon) {
      scores.push(data.boardSum * n);
      won.add(i);
    }
  }
}

The answer to part 1 is scores[0], score for the first winning board.

Part 2

The answer to part 2 is scores[scores.length - 1], score for the last winning board.

← Previous Back to AoC Index Next →