DEV Community

Cover image for Crab Combat
Robert Mion
Robert Mion

Posted on

Crab Combat

Advent of Code 2020 Day 22

Try the simulator!

Algorithm simulator for Part 1

Task: Solve for X where...

X = the winning player's score
Enter fullscreen mode Exit fullscreen mode

Example input

Player 1:
9
2
6
3
1

Player 2:
5
8
4
7
10
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Here's a visualization of my algorithm
Algorithm visualization

Try the simulator!

Algorithm simulator for Part 1

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

Algorithm simulator for part 2

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!

Latest comments (0)