14
\$\begingroup\$

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.

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
\$\endgroup\$
11
  • 2
    \$\begingroup\$ "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"? \$\endgroup\$ Sep 5, 2021 at 13:22
  • 4
    \$\begingroup\$ 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. \$\endgroup\$
    – ophact
    Sep 5, 2021 at 13:30
  • 1
    \$\begingroup\$ @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! \$\endgroup\$
    – Kaddath
    Sep 6, 2021 at 8:04
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Domenico
    Sep 6, 2021 at 12:29
  • 1
    \$\begingroup\$ @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 \$\endgroup\$
    – Kaddath
    Sep 6, 2021 at 12:51

3 Answers 3

6
\$\begingroup\$

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();
    }
};
\$\endgroup\$
1
4
\$\begingroup\$

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!

\$\endgroup\$
5
  • \$\begingroup\$ 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 \$\endgroup\$
    – ovs
    Sep 5, 2021 at 12:40
  • \$\begingroup\$ @ovs thanks for the first tip! Not sure where I could use the chained comparisons though. \$\endgroup\$
    – ophact
    Sep 5, 2021 at 13:05
  • \$\begingroup\$ 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(...). \$\endgroup\$
    – ovs
    Sep 5, 2021 at 13:10
  • \$\begingroup\$ 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 \$\endgroup\$
    – Domenico
    Sep 5, 2021 at 15:58
  • \$\begingroup\$ @Domenico You can just write a comment next to it saying "was seen before, but different player's turn" or something similar. \$\endgroup\$
    – ophact
    Sep 5, 2021 at 16:04
3
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.