Expand description
§Crab Combat
We start things off with a pun, by implementing a Deck of cards that is also a Deque or
double-ended queue backed by a
circular buffer. Why use our own implementation when there is a perfectly good VecDeque
already available? The answer is speed. As there are at most fifty cards in the pack, the Deck
can use a fix sized stack allocated array, avoiding the expensive heap allocations that
VecDeque must use.
Deck also keeps the score up to date as cards are added and removed, as this comes in useful
during part two. To update the score when a card is removed we subtract the card’s value
multiplied by the size of the deck. For example if 5 is removed then the new
score is 67 - 5 * 4 = 47.
| Deck ↓ | Weight | Score | Sum |
|---|---|---|---|
| 5 | 4 | 67 | 29 |
| 8 | 3 | ||
| 7 | 2 | ||
| 9 | 1 |
When adding a card, it helps to have the sum of the existing cards. The new score is the old score added to the new sum. For example if 6 is added to the deck:
| Old Score | New Score | Difference |
|---|---|---|
| 5 * 4 | 5 * 5 | 5 |
| 8 * 3 | 8 * 4 | 8 |
| 7 * 2 | 7 * 3 | 7 |
| 9 * 1 | 9 * 2 | 9 |
| - | 6 * 1 | 6 |
| Total: 67 | Total: 102 | Total: 35 |
§Part One
The winner will always eventually be the player that starts with card 50 as they can never lose this card in a round. However we need to play the full game in order to find out the score of the winner’s deck.
§Part Two
We use two tricks to speed things up, one deterministic and one probabilistic.
The deterministic trick is an observation that if Player 1 holds the high card in a recursive game, then they will always eventually win. This comes from the fact that all cards are unique, so the highest card is always greater than the size of the remaining deck, so a further recursive game will never trigger when this card is played in a round. This means that Player 1 will never lose this card, so will either win outright or by triggering the repetition rule.
This observation does not hold for Player 2. Although they can never lose the high card, they could lose by the repetition rule, so the round needs to be played out in full.
The probabilistic trick is an observation that the score makes a surprisingly good hash function. Instead of storing the entire deck in the previously seen cache, we can store only the combined hash of both decks, with a very good probability of no collisions.
Structs§
Enums§
- Winner 🔒
Functions§
- combat 🔒