Advent of Code 2021 Day 4
Try the simulator!
The task at hand: Solve for X where
X = the Nth board to win at Bingo!
- N is the first
- N is the last
- A multi-line string containing space- or comma-separated numbers from
- A random series of numbers to be drawn
- 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
- Reading the input:
- Separating the parts:
let [numbers, ...cards] = file.split('\n\n')
- 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
- Looping through each number, and for each number, looping through each card: This was an iterative process of continuous improvement in syntax - first
forEach, and finally
- Stopping early if this card is among the winners:
if (winners.includes(cardID)) return
- Finding a match: looking for the number in the card:
- Knowing the index, using it to find the row and column of the original card array:
[row, col] = [(match - (match % 5)) / 5, match % 5]
- Marking the number:
card[row][col] = 'x'
- Checking whether the row is now marked:
- Checking whether the column is now marked:
card.map(row => row[col]).every(isNaN)
- 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
Here's a visual description of how my algorithm works
The much more rewarding task: building a visualization tool!
- It needed the usual look and feel, heading,
textareafor 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:
- 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
- I had to refactor my
forEachmethods into separate iterators, and be sure to increment or reset them at the appropriate times in the code
- I had to maintain and clear the interval that would otherwise run for the length of the list of numbers
- 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!
- 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)