DEV Community

Cover image for Giant Squid
Robert Mion
Robert Mion

Posted on

Giant Squid

Advent of Code 2021 Day 4

Try the simulator!

Bingo simulator

The task at hand: Solve for X where

X = the Nth board to win at Bingo!

  1. N is the first
  2. N is the last

Input is

  • A multi-line string containing space- or comma-separated numbers from 0-25

It represents

  1. A random series of numbers to be drawn
  2. A collection of Bingo! cards

How solving felt like sculpting

  • The input was a slab of marble
  • The answers were hiding somewhere inside, waiting to be revealed
  • The chisel was my wealth of newly acquired puzzle-solving, computer science and algorithmic-thinking skills

One step at a time

  1. Reading the input: fs.readFileSync('filename.txt','utf-8')
  2. Separating the parts: let [numbers,] = file.split('\n\n')
  3. Turning each card into a 2D array of five arrays, each of length five, all values being numbers: quite the chaining of array methods with a little help from RegEx
  4. Looping through each number, and for each number, looping through each card: This was an iterative process of continuous improvement in syntax - first, then for, then forEach, and finally reduce with a forEach inside
  5. Stopping early if this card is among the winners: if (winners.includes(cardID)) return
  6. Finding a match: looking for the number in the card: card.flat(1).indexOf(n)
  7. Knowing the index, using it to find the row and column of the original card array: [row, col] = [(match - (match % 5)) / 5, match % 5]
  8. Marking the number: card[row][col] = 'x'
  9. Checking whether the row is now marked: card[row].every(isNaN)
  10. Checking whether the column is now marked: => row[col]).every(isNaN)
  11. If either is true, calculating the final score: card.flat(1).filter(Number).reduce((a,c) => a + c) * n

Parts 1 and 2 solved with one sub-25-line algorithm!

Parse the input as a multi-line string
Split the string at its first occurrence of two end of line characters, separating the series of numbers and the collection of Bingo! cards
Split the long string numbers at each ',' character, then coerce each string to a number
For each array of strings representing the Bingo! cards
  Split each string at the new-line character to create five arrays, each containing a string that represents one row in the 5x5 grid
    Split each string at the 1- or 2-length space character separating each number
      Filter the resulting array the remove any empty strings existing at location 1 - from an initial number in the string that was single-digit
        Coerce the resulting string into a number
For each number in the series - starting with an object containing two keys, each one storing an initially empty array for future scores and list of winning Bingo! cards
  For each Bingo! card
    If the growing list of winning Bingo! cards includes the index of this card, skip to the next card
    Look for - and store the index of - the current number in a flattened copy of the current Bingo! card
    If the number was found
      Determine what column it was in by calculating the remainder after dividing the index by 5 (e.g. 14 % 5 = 4: number is in the last column)
      Determine what row it was in by calculating the difference after subtracting from the index the remainder after dividing the index by 5, then dividing by 5 (e.g. 14 - (14 % 5) / 5 = 2: number is in the second row)
      Change the value in the Bingo! card at the found index from a number to an 'X' to 'mark' it
      Determine whether every value in the same row has been marked
      Determine whether every value in the same column has been marked
      If any of the two checks above is true
        Calculate this Bingo! card's score by...
          Creating a flattened copy of the nested arrays
          Filtering to exclude all X's, keeping only numbers
          For each number, accumulate a sum
          Store the product of the sum and the number that was drawn
        Add the score to the accumulating array of scores
        Add the index of this Bingo! card to the accumulating list of winners
For Part 1, return the first number from the list of scores
For Part 2, return the last number from the list of scores
Enter fullscreen mode Exit fullscreen mode

Here's my full algorithm written in JavaScript

Here's a visual description of how my algorithm works

Animation of algorithm

The much more rewarding task: building a visualization tool!

  • It needed the usual look and feel, heading, [Start] button and textarea for input entry
  • Since this puzzle is all about what happens during each iteration, it needed a [Play]/[Pause] button, a slider to adjust the speed of iteration, and a warning about flashing lights
  • And I needed to make a few significant modifications to my algorithm:
  1. I had to display and update each board on the screen: initially, after each new value was marked, and finally, when a row or column was marked and the card became a winner
  2. I had to refactor my reduce and forEach methods into separate iterators, and be sure to increment or reset them at the appropriate times in the code
  3. I had to maintain and clear the interval that would otherwise run for the length of the list of numbers
  4. I had to design a layout that accommodated a varying - likely large - quantity of Bingo! cards

I am incredibly proud of the resulting tool.

It was the funnest to build, funnest to watch, and funnest to interact with.

I encourage you to check it out!
Bingo simulator

In summary

  • I really impressed myself with this puzzle
  • When it was first released, I gave up almost immediately because I got frustrated when trying to think about looking up values in the card arrays
  • Flash forward a few months and over 20 documented puzzle attempts later, and that frustration was almost non-existent
  • In its place was more confidence in experimenting, troubleshooting, and understanding both the problem and data structures needed to solve it...eloquently!

This puzzle was the funnest mountain for my brain to climb thus far.

And the view at the top is bliss.

Top comments (0)