Day 22. Crab Combat

Problem statement

https://adventofcode.com/2020/day/22 (mirror)

Recursive Crab Combat, i.e. Part B might crash your browser due to insufficient RAM.

It feels like a shortcoming of clientside Blazor. Recursive method calls seem to consume a huge amount of memory. Unfortunately, the problem description explicitly includes recursion, and I don’t have a clue how to optimize that away.

The same code runs fine in a console app, with no memory issues.

My solution

Finding the solution on day 22 is as simple as directly implementing the Crab Combat rules stated in problem description.

In Part B, we need to memorize the deck configurations to check for any repeats. We do so by dumping the contents of both decks to a string:

string DeckHash(Queue<int> myDeck, Queue<int> crabDeck)
    => String.Join(",", myDeck.Select(element => element.ToString()).ToArray()) + ";" 
        + String.Join(",", crabDeck.Select(element => element.ToString()).ToArray());

Note that we separate cards and decks with a different character, to avoid generating the same “hash” in cases like below:

Deck A: 1 2                    Deck A: 1
Deck B: 3 4                    Deck B: 2 3 4
Hash:   "1,2;3,4"              Hash: "1;2,3,4"

To reduce the number of recursive calls, I used aggressive memoization. The outcome of a single game of Recursive Crab Combat is deterministic. Therefore, we can store the result of a given hash – and all intermediate states from the first to the last card played – and try to see if we already know the outcome of a configuration.

Note that this is different from checking for a loop in a single game of Recursive Crab Combat – we can potentially encounter the same deck configuration starting from a different initial deck!

Sadly, this approach did nothing to help overcome the RAM shortage issue; on my PC it always ends with a critical exception. 😑 I’m leaving it here, though – maybe it can complete on a machine with more RAM.