Snap (card game)

Question

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

 1   bdad        acbc        abba
 2   dad         acbc        abba        b
 3   dad         cbc         abba        ba
 4   dad         cbc         bba         baa
 5                           TAKES
 6   dad         cbc         bbabaa
 7   dad         cbc         babaa       b
 8   ad          cbc         babaa       bd
 9   ad          bc          babaa       bdc
10   ad          bc          abaa        bdcb
11   d           bc          abaa        bdcba
12   d           c           abaa        bdcbab
13   d           c           baa         bdcbaba
14               c           baa         bdcbabad
15                           baa         bdcbabadc
16                           aa          bdcbabadcb
17                           aa          dcbabadcbb
18   TAKES       OUT
19   dcbabadcbb              aa
20   cbabadcbb               aa          d
21   cbabadcbb               a           da
22   babadcbb                a           dac
23   babadcbb                            daca
24   abadcbb                             dacab
25   abadcbb                             acabd
26   badcbb                              acabda
27   badcbb                              cabdaa
28                           TAKES
29   badcbb                  cabdaa
30   badcbb                  abdaa       c
31   adcbb                   abdaa       cb
32   adcbb                   bdaa        cba
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
52   a                       babacdbb    cad
53                           babacdbb    cada
54                           abacdbb     cadab
55                           abacdbb     adabc
56                           bacdbb      adabca
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
74                           baa         cbdcbabad
75                           baa         bdcbabadc
76                           aa          bdcbabadcb
77                           aa          dcbabadcbb
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.

• This is code-golf.

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

Answer 1

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[0])[0],(e[0]==e[1]&&e[1]&&(i=m(i-1,a[i].push(...e.reverse())),e=[],o.push(...a.flatMap((p,j)=>p[0]||d(j)?e:j))+1==g)||l)))return l?r():r()[0];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[0])[0]),
            (e[0] == e[1] && e[1] && ((i = m(i - 1, a[i].push(...e.reverse()))), (e = []), o.push(...a.flatMap((p, j) => (p[0] || d(j) ? e : j))) + 1 == g)) || l)
        )
            return l ? r() : r()[0];
        if (t.includes(q((i = m(i + 1))))) return r();
    }
};

Answer 2

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[0];s[i]=S[1:]
   elif""==S:p=p[1:]+p[0]
   if s[i]!=0<1<len(p)!=p[-2]==p[-1]:s[i]+=p;s=[P or 0for P in s];p=s[i][0];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[0])))or C in G:return[i for i,S in E(s)if S!=0]
   G+=[C]

Try it online!

Wow, was this a pain to write.

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!

Answer 3

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!