Advent of Code 2020 Day 22
Try the simulator!
Task: Solve for X where...
X = the winning player's score
Example input
Player 1:
9
2
6
3
1
Player 2:
5
8
4
7
10
It represents:
- One shuffled deck of cards split evenly amongst two players
Part 1
The algorithm I planned to write
Split the input into an array with two elements, each an array of numbers
While one of the nested arrays is not empty
Determine which array contains a larger number in its first location
Remove both first numbers from each array
Insert both numbers at the end of the array that originally contained the larger number, with the larger number being inserted first and the smaller number inserted last
For each number in the non-empty array
Accumulate a sum, starting at 0, according the following instructions:
Multiply the current number by the difference between the length of the array and its index
Add this number to the accumulating number
Return the accumulated sum
The algorithm I wrote to get a correct answer
Split the input into an array with two elements, each an array of numbers
While both nested arrays are not empty
Create a list of two numbers - each the first number from the respective nested arrays - and sort them so the larger one is before the smaller one
Determine the deck that should receive both numbers in their new order by checking which nested array has the larger number in its first location
Insert both numbers in order of [larger, smaller] at the end of the that array
Remove the first element from each array
Filter the array of arrays such that only the non-empty array is kept
For each number in the non-empty array
Accumulate a sum, starting at 0, according the following instructions:
Multiply the current number by the difference between the length of the array and its index
Add this number to the accumulating number
Return the accumulated sum
Here's a visualization of my algorithm
Try the simulator!
Part 2
The moment I saw Part 2
- In video games today, bosses often have phases
An example: Shovel Knight's Tinker Knight boss
The first phase seems so easy, that there's bound to be a second phase
Alas, there is...and it is exponentially more difficult that the first
This is how today's - and many of Advent of Code's - challenges feel.
Attempt 1
- I pieced it together quite aimlessly, repurposing bits of code into recursive functions
- My algorithm was not correct
- I realized after taking a break that I didn't even fully understand the conditions of playing Recursive Combat
- I also realized that I couldn't just return who the winner is, but whether the game should end entirely if the infinity rule took effect
I was excited to try again with all these lessons learned and knowledge gained.
Attempt 2: starting with pseudocode
Split the input into an array with two items, each an array containing numbers
*Play Recursive Combat
Create a memo: an array with two empty arrays
While both decks have cards
**Determine the winner
Does the memo with each combination of card arrangements from this game include one mimicking the current arrangement of either array?
If this is true for either player
The winner is Player 1
And this round and game must end
Return to * with winner and game-breaking status as true
Add the card arrangements from each deck to the memo
Do the number of cards - minus the first - in each player's deck equal an amount that is less than the first card's value?
If this is true for either player
The winner is the player with the higher-value card
Else - the number of cards in each player's deck - minus the first - equal an amount that is greater than or equal to the first card's value
Return to * with winner and game-breaking status as false
If this is true for both players
The winner is the result of continuing at * with modified decks, such that each deck only contains as many cards - minus the first one - as specified by the value of the first card
Return to * with winner and game-breaking status as false
With winner and game-breaking status now known:
If game-breaking status is true
Break out of loop, returning winning player
Else - game-breaking status is false
Insert the number on the card from the winning player in the winning player's deck
Insert the number on the card from the losing player in the winning player's deck
Remove the first card from each deck
For each number in the winning player's array
Accumulate a sum, starting at 0, according the following instructions:
Multiply the current number by the difference between the length of the array and its index
Add this number to the accumulating number
Return the accumulated sum
Working from pseudocode towards a correct answer
What should one of the functions return?
- I knew the winner-finding function should return a winner and a boolean as to whether the calling recursive combat function's while loop should break
- But for a while, I didn't know what the recursive combat function should return
- Turns out, it also needed to return a winner!
- It is called from within the winner-finding function to generate the winner that should be returned back to recursive combat
- It is also called to kick off the program, which needs to know the winner in case the full decks of cards generated an infinite loop
What should pass the test? Both or any?
- I knew I had to check if either deck met a few conditions
- I clearly still struggle to initially identify whether to use the logical and
&&or logical or||operators in JavaScript - Turns out, both conditional checks required
||so that they will always return the first check if it is true
Other minor details
- The memo didn't need to be a unique set. It is fine as an array.
- This challenge was especially difficult because it really required writing the whole algorithm before running to check for accuracy. At that point, there were a lot of areas ripe for errors.
- Luckily, using the example input as reference, I debugged my algorithm until it generated the correct answer for that input
- Thankfully, my puzzle input had no further tricks in it, and I generated the correct answer immediately!
My working algorithm
Sub-routine: Play Recursive Combat
Accepts three parameters:
1. Array with two elements, each an array of numbers
2. A positive integer representing the game number
3. An optional array with two elements, each an array of strings, representing a growing memo of card arrangements
Create two empty values:
1. Winner: to become 0 or 1
2. Abort: to become a boolean
While at least one of the decks is not empty:
Determine the winner of this round by calling the winner-finding sub-routine, passing three arguments:
1. Array representing decks of cards
2. Game number
3. Memo
Parse the returned value and proceed accordingly:
Set Winner to either 0 or 1
If Abort is true:
Exit and terminate the enclosing loop early
Else - Abort is false:
Add the arrangement of cards to the respective memo arrays
Insert at the end of the winning deck's array two values in order:
1. Winning player's drawn card
2. Losing player's drawn card
Remove the first numbers from each players' deck
Return the winner
Sub-routine: Find the winner
Accepts three parameters:
1. Array with two elements, each an array of numbers
2. A positive integer representing the game number
3. An array with two elements, each an array of strings, representing a growing memo of card arrangements
If the memo includes a stringified stamp of either deck's current arrangement of cards:
Return a pair indicating the winner is Player 1 and Abort is true
Else if either player's drawn card's value is greater than the remaining quantity of cards in their decks in the current game:
Return a pair indicating the winner is the player with the higher-value drawn card and Abort is false
Else if either player's drawn card's value is less than or equal to the remaining quantity of cards in their decks in the current game:
Return a pair indicating the winner is the player who won a new game using a deck with a subset of cards - starting from the card after the one drawn, and including only as many cards after until having as many cards as indicated by the value of the drawn card - and Abort is false
Set Winner equal to the result (0 or 1) or calling Play Recursive Combat sub-routine, passing in the parsed input arrays of decks and 1 (indicating game number 1)
For each number in the array within decks associated with the winning player
Accumulate a sum, starting at 0, according the following instructions:
Multiply the current number by the difference between the length of the array and its index
Add this number to the accumulating number
Return the accumulated sum
Visualizing a recursive algorithm
- Unlike in other simulators, I couldn't leverage an iterator that walks through each step mimicking a for-loop
- Instead, I had to run the algorithm - and accumulate an array of strings representing a log from each step during the program
- The tricky parts were figuring out what to print at each step within both sub-routines
- The result comes close to mimicking the output shown in the challenge's example
- When finished, my simulator even displays additional fun stats like: number of games played, highest rounds in any single game, and total rounds played
Try the simulator
This challenge felt so rewarding to solve, especially Part 2.
And the simulator was a bigger bonus achievement in its own sense.
On to the next!
Top comments (0)