Snap (card game)

When I was a child I used to play a variation of Snap to stake soccer trading cards.
"Game" is an overstatement because the only role of the players is to secretly prepare their starting piles. As the game starts there are no choices other than just perform the game algorithm.

Rules

There is no maximum number of players and they all start with a fixed number of cards.
Players in turn play the top card of their piles on a common pile (initially empty).

If the current player has no cards, the common pile bottom card will be played.

When a player happens to play an equal card to that on top of the common pile:

• This player will take the common pile and append it face-down to his own pile. (Players' piles are face-down but the common pile is face-up, so the pair of equal cards should end up at the bottom)
• Anyone with no cards is out of the game.
• This player has to resume the game replenish the common pile with their top card as usual.

The game ends in one of three scenarios:

• one player has all the cards (they win)
• all the cards are in the common pile, the next player rotates it but doesn't form a pair (the common pile can't be taken)
• one previous state of the game reoccurs (the game gets stuck in a loop)

Step by step game examples

1) Initial configuration: "abba abca"

p1      p2      common pile

1   abba    abca
2   bba     abca    a
3   bba     bca     aa
4           TAKES
5   bba     bcaaa
6   bba     caaa    b
7   ba      caaa    bb
8   TAKES
9   babb    caaa
10   abb     caaa    b
11   abb     aaa     bc
12   bb      aaa     bca
13   bb      aa      bcaa
14           TAKES
15   bb      aabcaa
16   bb      abcaa   a
17   b       abcaa   ab
18   b       bcaa    aba
19           bcaa    abab
20           caa     ababb
21   OUT     TAKES
22           caaababb

============ p2 wins ============

2) Initial configuration: "abba acab"

p1      p2      common pile

1   abba    acab
2   bba     acab    a
3   bba     cab     aa
4           TAKES
5   bba     cabaa
6   bba     abaa    c
7   ba      abaa    cb
8   ba      baa     cba
9   a       baa     cbab
10   a       aa      cbabb
11           TAKES
12   a       aacbabb
13   a       acbabb  a
14           acbabb  aa
15   TAKES
16   aa      acbabb
17   a       acbabb  a
18   a       cbabb   aa
19           TAKES
20   a       cbabbaa
21   a       babbaa  c
22           babbaa  ca
23           abbaa   cab
24           abbaa   abc
25           bbaa    abca
26           bbaa    bcaa
27   TAKES
28   bcaa    bbaa
29   caa     bbaa    b
30   caa     baa     bb
31           TAKES
32   caa     baabb
33   caa     aabb    b
34   aa      aabb    bc
35   aa      abb     bca
36   a       abb     bcaa
37   TAKES
38   abcaa   abb
39   bcaa    abb     a
40   bcaa    bb      aa
41           TAKES
42   bcaa    bbaa
43   bcaa    baa     b
44   caa     baa     bb
45   TAKES
46   caabb   baa
47   aabb    baa     c
48   aabb    aa      cb
49   abb     aa      cba
50   abb     a       cbaa
51           TAKES
52   abb     acbaa
53   abb     cbaa    a
54   bb      cbaa    aa
55   TAKES
56   bbaa    cbaa
57   baa     cbaa    b
58   baa     baa     bc
59   aa      baa     bcb
60   aa      aa      bcbb
61           TAKES
62   aa      aabcbb
63   aa      abcbb   a
64   a       abcbb   aa
65   TAKES
66   aaa     abcbb
67   aa      abcbb   a
68   aa      bcbb    aa
69           TAKES
70   aa      bcbbaa
71   aa      cbbaa   b
72   a       cbbaa   ba
73   a       bbaa    bac
74           bbaa    baca
75           baa     bacab
76           baa     acabb
77   TAKES
78   acabb   baa
79   cabb    baa     a
80   cabb    aa      ab
81   abb     aa      abc
82   abb     a       abca
83   bb      a       abcaa
84   TAKES
85   bbabcaa a
86   babcaa  a       b
87   babcaa          ba
88   abcaa           bab
89   abcaa           abb
90           TAKES
91   abcaa   abb
92   abcaa   bb      a
93   bcaa    bb      aa
94   TAKES
95   bcaaaa  bb
96   caaaa   bb      b
97   caaaa   b       bb
98           TAKES
99   caaaa   bbb
100   caaaa   bb      b
101   aaaa    bb      bc
102   aaaa    b       bcb
103   aaa     b       bcba
104   aaa             bcbab
105   aa              bcbaba
106   aa              cbabab
107   a               cbababa
108   a               bababac
109                   bababaca
110                   ababacab // common pile can't be taken

============ p1, p2 in game ============

3) Initial configuration: "bdad acbc abba"

p1          p2          p3          common pile

5                           TAKES
11   d           bc          abaa        bdcba
12   d           c           abaa        bdcbab
13   d           c           baa         bdcbaba
18   TAKES       OUT
28                           TAKES
33   dcbb                    bdaa        cbaa
34   TAKES
35   dcbbcbaa                bdaa
36   cbbcbaa                 bdaa        d
37   cbbcbaa                 daa         db
38   bbcbaa                  daa         dbc
39   bbcbaa                  aa          dbcd
40   bcbaa                   aa          dbcdb
41   bcbaa                   a           dbcdba
42   cbaa                    a           dbcdbab
43   cbaa                                dbcdbaba
44   baa                                 dbcdbabac
45   baa                                 bcdbabacd
46   aa                                  bcdbabacdb
47   aa                                  cdbabacdbb
48                           TAKES
49   aa                      cdbabacdbb
50   aa                      dbabacdbb   c
51   a                       dbabacdbb   ca
57                           bacdbb      dabcaa
58   TAKES
59   dabcaa                  bacdbb
60   abcaa                   bacdbb      d
61   abcaa                   acdbb       db
62   bcaa                    acdbb       dba
63   bcaa                    cdbb        dbaa
64                           TAKES
65   bcaa                    cdbbdbaa
66   bcaa                    dbbdbaa     c
67   caa                     dbbdbaa     cb
68   caa                     bbdbaa      cbd
69   aa                      bbdbaa      cbdc
70   aa                      bdbaa       cbdcb
71   a                       bdbaa       cbdcba
72   a                       dbaa        cbdcbab
73                           dbaa        cbdcbaba
78   TAKES
79   dcbabadcbb              aa                       // loop (line 19)

============ p1, p3 in game ============

N.B. game states are inviduated by piles configuration and current player. As you can see in example 2) lines 28, 42 are not the same game state.

Input

A list of players' piles (top to bottom) as:

• an array of strings ["code", "golf", "fold"], or
• a matrix of positive integers [[1,2,3,4],[5,2,6,7],[7,2,6,3]]

Players order is implied by piles order.

Output

A number indicating the player who wins or a list of numbers for the players who reach the end of the game.
You decide whether players are 0 or 1 indexed.

I/O Examples (1-indexed players):

"abca abba"      -> 1
"abba abca"      -> 2
"abba acab"      -> 1 2
"bdad acbc abba" -> 1 3
"fizz buzz"      -> 2
"robinhooda ndlittlejo hnwalkingt hroughthef orestlaugh ingbackand forthatwha ttheothero nehastosay" -> 9
• "If the current player has no cards they will rotate the common pile placing on top the card at the bottom." was not entirely clear to me until working through the second and third example games, perhaps a better wording would be "If the current player has no cards they will play the card from the bottom of the common pile"? Sep 5 '21 at 13:22
• Although I have already completed the challenge, I faced some difficulties and misunderstandings along the way. To make the challenge clearer for future viewers, maybe change wordings to be more precise? For instance it was not entirely clear that the player who takes the pile gets another turn. Perhaps anyone with no cards is out of the game. The player who took the pile has to then replenish the pile with one card is better because I was not sure who "they" was. Sep 5 '21 at 13:30
• @Domenico the edit is for inclusion, it's true that in my generation girls would have been de facto excluded from soccer card games or would have to argue to be let in (or because they weren't interested), but the world is a-changing! Sep 6 '21 at 8:04
• @Kaddath Oh, I didn't realize it. I'm Italian and we always use implied subject, so I perceived those "he" as required transparent links to "the player", avoid of gender meanings. Also didn't know of singular they. Anyway just blindly change all the "he" into "they" can upset the sense, as it did. I'll rephrase the whole thing. Sep 6 '21 at 12:29
• @Domenico Yes I didn't understand too the first time i read it in a question, I'm french and it would be weird for us to use plural for this Sep 6 '21 at 12:51

JavaScript (Node.js), 483 426 bytes

-57 bytes thanks to @emanresu A

Takes a list of strings as input and indexes from 0.

Try it online!

a=>{a=a.map(p=>[...p]);e=[];t=[];o=[];i=0;g=a.length;m=n=>(n%g+g)%g;r=_=>[...a.keys()].filter(x=>!d(x));d=x=>o.includes(x);q=_=>JSON.stringify([o,i,a,e]);for(;;){if(!d(i)&&(l=e.length==e.unshift(a[i].shift(t.push(q()))||e.pop())&&!a.filter(p=>p),(e==e&&e&&(i=m(i-1,a[i].push(...e.reverse())),e=[],o.push(...a.flatMap((p,j)=>p||d(j)?e:j))+1==g)||l)))return l?r():r();if(t.includes(q(i=m(i+1))))return r()}}

Unminified

(a) => {
a = a.map((p) => [...p]);
e = [];
t = [];
o = [];
i = 0;
g = a.length;
m = (n) => ((n % g) + g) % g;
r = (_) => [...a.keys()].filter((x) => !d(x));
d = (x) => o.includes(x);
q = (_) => JSON.stringify([o, i, a, e]);
for (;;) {
if (
!d(i) &&
((l = e.length == e.unshift(a[i].shift(t.push(q())) || e.pop()) && !a.filter((p) => p)),
(e == e && e && ((i = m(i - 1, a[i].push(...e.reverse()))), (e = []), o.push(...a.flatMap((p, j) => (p || d(j) ? e : j))) + 1 == g)) || l)
)
return l ? r() : r();
if (t.includes(q((i = m(i + 1))))) return r();
}
};

Python 3.8 (pre-release), 378 bytes

def f(s,p='',G=[],V=sorted,E=enumerate):
O=V(p.join(s))
while 1:
for i,S in E(s):
if S:p+=S;s[i]=S[1:]
elif""==S:p=p[1:]+p
if s[i]!=0<1<len(p)!=p[-2]==p[-1]:s[i]+=p;s=[P or 0for P in s];p=s[i];s[i]=s[i][1:]
C=s+[p,i]
if any(a and O==V(a)for a in s)or(O==V(p)*all(a!=b for a,b in zip(p,p[1:]+p)))or C in G:return[i for i,S in E(s)if S!=0]
G+=[C]

Try it online!

Takes in a list of strings, outputs a list of 0-indexed numbers. My code can be slightly changed to output a single value if a single player wins, but I see no rule preventing me from outputting as my code does.

Explanation

Stores game states in G. A state here is the list of strings followed by the pile and the number indicating whose turn it is (evidently, whose turn it is does make a difference). If the current state has been seen before, we break by setting T to 1. (breaks from the inner loop then from the outer loop)

For each iteration, if S is truthy (current string) we append its first letter to the pile and remove it from s[i]. If S is empty string, we rotate the pile.

A zero indicates that the player is out; we ignore such cases. If the last two characters of p are the same, we append the entire pile to the end of s[i] and reset it, before resuming the game in the same iteration.

The two other checks for the endgame are:

• if any of the sorted strings in s match the sorted O, or
• if the sorted pile equals sorted O and there are no neighboring pairs in the pile (end and beginning count as a pair).

To get the list of "in" players, we simply output all indices corresponding to a nonzero entry in s.

Any tips for shortening the code will be greatly appreciated. Thanks to @ovs for -28 -35 bytes!

• If you move the return statement where T=1;break currently is, you don't need any breaks or T, which saves a few bytes. And chained comparisons can probably save a few bytes as well
– ovs
Sep 5 '21 at 12:40
• @ovs thanks for the first tip! Not sure where I could use the chained comparisons though. Sep 5 '21 at 13:05
• s[i]!=0and len(p)>1and p[-2]==p[-1] -> s[i]!=0<1<len(p)!=p[-2]==p[-1]. And in the last if you might be able to replace O==sorted(p)and all(...) with (O==sorted(p)*all(...).
– ovs
Sep 5 '21 at 13:10
• I'm glad you liked it, is this one of your first challenges? Anyway, yes, a state of the game includes the current player, as you can se in the example 2) lines 28, 42 have the same piles configuration but the game doesn't end up in a loop. Unfortunately in that example the outcome is the same as would be in a simulation that wrongly detects a loop. If you want you can help me find a test case that differentiates it Sep 5 '21 at 15:58
• @Domenico You can just write a comment next to it saying "was seen before, but different player's turn" or something similar. Sep 5 '21 at 16:04

Perl 5, 209 bytes

sub{(@p,$i,$_,%s,@o)=pop=~/\w+/g;while((@w=grep$p[$_-1],1..@p)>1||y///c and!$s{$i,@p,@o}++){if(!$o[$i]&&($p[$i]=~s,.,,||s,.,,)&&($_.=$&)=~s/.*(.)\1$//){$p[$i].=$&;$p[$_]or$o[$_]=1for 0..$#p;next}$i=++\$i%@p}@w}

Try it online!