Advent of Code 2021

Advent of Code 2021 - Day 4

This time, while solving the problems I also though of building my utilities functions that may result usefull for the other challenges as well. Once again, I'm not a good "code golfer" as I prefer readability, adding comments and naming variables as explicitely as possilble, so my solutions tend to be a bit longer then the one of other players.

Problem — Part 1

You're already almost 1.5km (almost a mile) below the surface of the ocean, already so deep that you can't see any sunlight. What you can see, however, is a giant squid that has attached itself to the outside of your submarine.

Maybe it wants to play bingo?

Bingo is played on a set of boards each consisting of a 5x5 grid of numbers. Numbers are chosen at random, and the chosen number is marked on all boards on which it appears. (Numbers may not appear on all boards.) If all numbers in any row or any column of a board are marked, that board wins. (Diagonals don't count.)

The submarine has a bingo subsystem to help passengers (currently, you and the giant squid) pass the time. It automatically generates a random order in which to draw numbers and a random set of boards (your puzzle input). For example:

7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1

22 13 17 11  0
 8  2 23  4 24
21  9 14 16  7
 6 10  3 18  5
 1 12 20 15 19

 3 15  0  2 22
 9 18 13 17  5
19  8  7 25 23
20 11 10 24  4
14 21 16 12  6

14 21 17 24  4
10 16 15  9 19
18  8 23 26 20
22 11 13  6  5
 2  0 12  3  7

After the first five numbers are drawn (7, 4, 9, 5, and 11), there are no winners, but the boards are marked as follows (shown here adjacent to each other to save space):

22 13 17 11  0         3 15  0  2 22        14 21 17 24  4
 8  2 23  4 24         9 18 13 17  5        10 16 15  9 19
21  9 14 16  7        19  8  7 25 23        18  8 23 26 20
 6 10  3 18  5        20 11 10 24  4        22 11 13  6  5
 1 12 20 15 19        14 21 16 12  6         2  0 12  3  7

After the next six numbers are drawn (17, 23, 2, 0, 14, and 21), there are still no winners:

22 13 17 11  0         3 15  0  2 22        14 21 17 24  4
 8  2 23  4 24         9 18 13 17  5        10 16 15  9 19
21  9 14 16  7        19  8  7 25 23        18  8 23 26 20
 6 10  3 18  5        20 11 10 24  4        22 11 13  6  5
 1 12 20 15 19        14 21 16 12  6         2  0 12  3  7

Finally, 24 is drawn:

22 13 17 11  0         3 15  0  2 22        14 21 17 24  4
 8  2 23  4 24         9 18 13 17  5        10 16 15  9 19
21  9 14 16  7        19  8  7 25 23        18  8 23 26 20
 6 10  3 18  5        20 11 10 24  4        22 11 13  6  5
 1 12 20 15 19        14 21 16 12  6         2  0 12  3  7

At this point, the third board wins because it has at least one complete row or column of marked numbers (in this case, the entire top row is marked: 14 21 17 24 4).

The score of the winning board can now be calculated. Start by finding the sum of all unmarked numbers on that board; in this case, the sum is 188. Then, multiply that sum by the number that was just called when the board won, 24, to get the final score, 188 * 24 = 4512.

To guarantee victory against the giant squid, figure out which board will win first. What will your final score be if you choose that board?

Your puzzle answer was 38594.

Solution — Part 1

Looking at the input, we will need to load the first line as the list of drawn numbers for our bingo. After that, we will have to create the boards as 5x5 matrix.

const input = loadInput();
const lines = input.split("\n");
// Parse the drawn values
const drawn = lines[0].split(",").map((x) => parseInt(x));
const boards = [];

Let's define the function that we will use to create all the boards

/**
 * Create a board from the given lines
 * @param {array} lines Array of lines
 * @returns {Matrix}
 */
function createBoard(lines) {
  const board = new Matrix(lines, " ", "int");
  board.format((x) => ({ val: x, mark: false }));
  return board;
}

I want to format every element of every board to contain also the attribute mark, to know if the selected element was marked. Another viable solution (looking at the request of the challenge) would be to have simply the number inside the element, and set it to null whenever marked. Since I don't know if later on the way the marked values will be of any use in the challenge, I prefer to keep them saved.

// Create the boards
for (let i = 2; i < lines.length; i += 6) {
  const board = createBoard(lines.slice(i, i + 5), i);
  boards.push(board);
}

For every drawn number, we will need to apply it on every board. I'll just create then the function to do so

/**
 * Mark the value on the board
 * @param {Matrix} board Board to apply the value to
 * @param {number} value Value to mark on the board
 */
function markValueOnBoard(board, value) {
  board.format((x) => {
    if (x.val === value) {
      x.mark = true;
    }
    return x;
  });
}

We also need to create the function to check if the board is actually completed

/**
 * Check if the board is complete
 * @param {Matrix} board Board to check
 * @returns {boolean}
 */
function checkIfBoardIsComplete(board) {
  // Check rows
  const rows = board.getRows();
  for (let i = 0; i < rows.length; i++) {
    const row = rows[i];
    if (row.every((x) => x.mark)) {
      return true;
    }
  }
  // Check cols
  const cols = board.getCols();
  for (let i = 0; i < cols.length; i++) {
    const col = cols[i];
    if (col.every((x) => x.mark)) {
      return true;
    }
  }
}

And the one to calculate the board score

/**
 * Calculate the score of the board
 * @param {Matrix} board Board to calculate the score for
 * @param {*} lastValue Last value drawn
 * @returns {number}
 */
function calculateBoardScore(board, lastValue) {
  let tot = 0;
  board.toArray().forEach((x) => {
    if (!x.mark) {
      tot += x.val;
    }
  });
  return tot * lastValue;
}

Now we can put all the pieces together

function main() {
  const input = loadInput();
  const lines = input.split("\n");
  // Parse the drawn values
  const drawn = lines[0].split(",").map((x) => parseInt(x));
  const boards = [];
  // Create the boards
  for (let i = 2; i < lines.length; i += 6) {
    const board = createBoard(lines.slice(i, i + 5), i);
    boards.push(board);
  }
  // Apply the values one by one
  for (let i = 0; i < drawn.length; i++) {
    const value = drawn[i];
    for (let j = 0; j < boards.length; j++) {
      const board = boards[j];
      markValueOnBoard(board, value);
      if (checkIfBoardIsComplete(board)) {
        return calculateBoardScore(board, value);
      }
    }
  }
  return -1;
}

Problem — Part 2

On the other hand, it might be wise to try a different strategy: let the giant squid win.

You aren't sure how many bingo boards a giant squid could play at once, so rather than waste time counting its arms, the safe thing to do is to figure out which board will win last and choose that one. That way, no matter which boards it picks, it will win for sure.

In the above example, the second board is the last to win, which happens after 13 is eventually called and its middle column is completely marked. If you were to keep playing until this point, the second board would have a sum of unmarked numbers equal to 148 for a final score of 148 * 13 = 1924.

Figure out which board will win last. Once it wins, what would its final score be?

Your puzzle answer was 21184.

Solution — Part 2

Well, lucky enough most of the code stays the same, we just need to find the last board that can win the game.

// ... 
for (let i = 0; i < drawn.length; i++) {
    const value = drawn[i];
    const remainingBoards = boards.filter((board) => board);
    for (let j = 0; j < boards.length; j++) {
      const board = boards[j];
      if (!board) {
        continue;
      }
      markValueOnBoard(board, value);
      if (checkIfBoardIsComplete(board)) {
        boards[j] = null;
      }
    }
    if (remainingBoards.length === 1) {
      return calculateBoardScore(remainingBoards[0], value);
    }
  }
// ...