This challenge is one of the two challenges which were planned for Advent of Code Golf 2021, but didn't fit into the 25-day schedule.
Related to AoC2020 Day 22, Part 2.
Combat is a simple two-player card game played with a deck of cards. A unique positive integer is written on each card. The game proceeds as follows:
- Shuffle and split the cards so that each player has their own deck.
- For each round...
- Both players draw their top card. The one with the higher-numbered card wins the round. The winner places both cards at the bottom of their own deck, so that the winner's card is above the other card.
- If a player owns all cards, the player wins.
Recursive Combat is a variant of Combat. The only difference is how to decide the winner of each round.
- Before either player deals a card, if there was a previous round in this game that had exactly the same cards in the same order in the same players' decks, the game instantly ends in a win for player 1. Previous rounds from other games are not considered. (This prevents infinite games of Recursive Combat.)
- Otherwise, this round's cards must be in a new configuration; the players begin the round by each drawing the top card of their deck as normal. If both players have at least as many cards remaining in their deck as the value of the card they just drew, the winner of the round is determined by playing a new game of Recursive Combat, where each player takes that many cards from the top of their own deck (excluding the cards drawn) to the "sub-game". When the sub-game ends, the cards are returned to the decks as they were before the sub-game, and the parent game proceeds like Combat: the winner of the sub-game (= the winner of the round) puts the two cards drawn at the bottom of their own deck, so that the winner's card is above the other card.
- Otherwise, at least one player must not have enough cards left in their deck to recurse; the winner of the round is the player with the higher-value card.
Note that the winner's card might have lower value than the other card in this version.
Let's call the two players Player 1 and Player 2. Given both player's decks at start, determine whether Player 1 will win the game of Recursive Combat or not.
Both decks are given as list of values written on each card. You can choose which side will be the top of the deck. It is guaranteed that both decks are non-empty and all numbers are unique positive integers.
For output, you can choose to
- output truthy/falsy using your language's convention (swapping is allowed), or
- use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.
Standard code-golf rules apply. The shortest code in bytes wins.
P1's deck, P2's deck (first number at the top) [43, 19], [2, 29, 14] (by infinite loop prevention) [10, 8, 2] [4, 3, 5, 6, 9, 1, 7] [2, 1, 10, 8] [7, 6, 5, 3, 9, 4] [2, 1, 7, 8, 9, 4, 5, 6] [10, 3]
P1's deck, P2's deck (first number at the top) [9, 2, 6, 3, 1], [5, 8, 4, 7, 10] [6, 2, 1, 8, 9, 4], [7, 3, 10, 5] [4, 6, 2, 1, 3], [8, 10, 7, 9, 5] [7, 4, 9, 2, 6, 1, 3], [10, 8, 5]