AoCG2021 Leftover: Recursive Combat

Question

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.

Test cases

P1 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]

P2 wins

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]

Answer 1

JavaScript, 146 145 134 bytes

c=d=>(d[[[A,B]=d,B]]^=Y=B[0])?(X=A[0])?d[w=A[X]+B[Y]?c(d.map(a=>a.slice(1,a[0]+1))):Y>X|0].push(d[w].shift(),d[w^1].shift())&&c(d):1:0

Try it online!

Takes the decks as an array of arrays of integers, top first; this array will be modified. Returns 0 for player 1 winning, 1 for player 2 winning.

-12 from the original by removing h and instead reusing d, as well as a modification of an idea from tsh.

Explanation

(d[[[A,B]=d,B]]^=Y=B[0])?…:0

• A and B are set to the decks of player 1 and 2, respectively.
• The default toString of arrays joins with commas, which is injective for arrays of integers, but not for arrays of arrays of integers – for example, it does not distinguish [[1,2],[3]] and [[1],[2,3]]. For that reason, toString is instead (implicitly) called on a new array, which lists the elements of A once and the elements of B twice. This distinguishes all possibilities because the numbers that appear twice must be from B while the numbers that appear once must be from A.
• Additional properties of d are used to keep track of which configurations of cards have been seen before.
  • Indexing with a new string finds undefined, which gets converted to 0 before the XOR makes it equal B[0].
  • Indexing with a previously-seen string finds the previous value of B[0], which is necessarily equal to the current value, thus the XOR changes it to 0. (Player 1 wins immediately.)
  • If B is empty, B[0] is undefined, which also gets converted to 0. The string has to be new, making the result 0. (Player 1 wins immediately.)
• Also, Y is set to Player 2's top card.

(X=A[0])?…:1

• X is set to Player 1's top card; Player 2 wins immediately if Player 1's deck is empty.

d[w=A[X]+B[Y]?c(d.map(a=>a.slice(1,a[0]+1))):Y>X|0]…

• A[X] and B[Y] check whether the players have enough cards for a recursive sub-game, yielding the value of the last card to be used if there are enough, or undefined if there are not enough. The sum is a positive integer (truthy) if both are positive integers, or NaN (falsy) if at least one is undefined.
• If there are enough cards, c is called to determine the winner of the recursive sub-game, using slice to extract the appropriate cards.
• Otherwise, Y>X determines the winner, and |0 converts it to an integer, 0 or 1.
• w is set to the (0-indexed) winner.

d[w=…].push(d[w].shift(),d[w^1].shift())&&c(d)

• The two shifts take out the top cards of the winner and non-winner in that order, and push puts them on the bottom of the winner's deck.
• Finally, c(d) calls the function again to repeat the analysis.

Answer 2

Charcoal, 114 bytes

⊞υ⟦⟧≔⟦✂θ⟧ηＷυ«≔№§υ±¹θε⊞§υ±¹✂θ¿›⬤θ∧κ›Ｌκ§κ⁰ε«⊞υ⟦⟧⊞η✂θＵＭθ✂κ¹⊕§κ⁰»«¿›⬤θκε≔‹§θ⁰§θ¹ε«≔∧⊟υ¬§θ⁰ε≔⊟ηθ»Ｆ²⊞§θ姧θ⁺λε⁰ＵＭθΦκν»»ε

Try it online! Link is to verbose version of code. Takes input as a pair of lists and outputs - if player 2 wins, nothing if player 1 wins. Explanation: Charcoal doesn't really do recursion, so here's an iterative approach.

⊞υ⟦⟧

Start tracking previously seen positions for the top-level game.

≔⟦✂θ⟧η

Create a dummy "calling game state" for the top-level game.

Ｗυ«

Repeat until all games have been resolved.

≔№§υ±¹θε

See whether this position has been seen in this game or not.

⊞§υ±¹✂θ

Save a (shallow) copy of this position to this game.

¿›⬤θ∧κ›Ｌκ§κ⁰ε«

If a recursive game is possible, then:

⊞υ⟦⟧

Start tracking previously seen positions for the sub-game.

⊞η✂θ

Save the calling game state for the sub-game.

ＵＭθ✂κ¹⊕§κ⁰

Create the state for the sub-game.

»«¿›⬤θκε

Otherwise, if this is a new position and both players still have cards, then...

≔‹§θ⁰§θ¹ε

... see who wins this position.

«≔∧⊟υ¬§θ⁰ε≔⊟ηθ»

Otherwise, remove the previously seen positions for this game, see whether Player 1 lost by running out of cards, and restore the calling game state.

Ｆ²⊞§θ姧θ⁺λε⁰

Append the top card of both the winner and loser to the winner's hand.

ＵＭθΦκν

And remove them from the top of both players' hands.

»»ε

Output whether Player 2 won.

Answer 3

Wolfram Language (Mathematica), 127 bytes

f=##!={}&&Check[#&@@@#,#&@@#=={}]/.{c__}:>MapAt[#~Join~{c}[[{n,-n}]]&,Rest/@#,n=If[f@@Check[{##2}[[;;#]]&@@@#',0<c],2,1]]~f~##&

Try it online!

Input a list containing the decks in order, i.e. as [{P1, P2}]. Returns False if P1 wins, and True if P2 wins.

##&!={}&&                       check for a loop
Check[#&@@@#,                   attempt to take one card from each deck
  #&@@#=={}]                      if not possible, check which deck is empty
/.{c__}:>                       the current round's cards are c:
 MapAt[#~Join~{c}[[{n,-n}]]&,     append both cards in the correct order
   Rest/@#,                         to the winner's deck,
   n=If[                            deciding the winner by:
     f@@Check[{##2}[[;;#]]&@@@#',     attempt to play a subgame
       0<c],                            if not possible, the higher card
     2,1]                           bool -> player number
 ]~f~##                           recurse

Answer 4

Python3, 264 bytes:

k=lambda x,y,a,b,h,r:([a,[y,x]+a][r],[[x,y]+b,b][r],h+[[a+[x],b+[y]]])
def f(a,b,h=[]):  
 if[a,b]in h:return 1
 if not all([a,b]):return len(a)>0
 x,y=a.pop(),b.pop()
 if x<=len(a)and y<=len(b):return f(*k(x,y,a,b,h,f(a[-x:],b[-y:])))
 return f(*k(x,y,a,b,h,x>y))

Try it online!

Answer 5

Scala, 150 bytes

(a,b,s)=>if(a.isEmpty)2 else if(b.isEmpty|s(a->b))1 else if(a(0)>b(0))f(a.tail:+a(0):+b(0),b.tail,s+(a->b)) else f(a.tail,b.tail:+b(0):+a(0),s+(a->b))

Try it on Scastie

Answer 6

Python 3, 262 bytes

def r(a,b,h=[]):
    while 1:
        if h.count((a,b))or not b:return 1
        if not a:return 2
        h.append((a.copy(),b.copy()));c,d=a.pop(0),b.pop(0)
        if len(a)>=c and len(b)>=d:q=r(a[:c],b[:d]);a+=([],[c,d])[q];b+=([d,c],[])[q]
        else:a+=([c,d],[])[d>c];b+=([d,c],[])[c>d]

Takes the top of the deck as element 0 in the lists, and returns 1 for Player 1 winning, 0 for player 2 winning.

Try it online!