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
Improve this question
\$\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\$ Commented 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\$ Commented 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\$ Commented 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\$ Commented 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\$ Commented Sep 6, 2021 at 12:51

3 Answers 3

Reset to default
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(); } };
Improve this answer
\$\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!

Improve this answer
\$\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\$ Commented Sep 5, 2021 at 12:40
  • \$\begingroup\$ @ovs thanks for the first tip! Not sure where I could use the chained comparisons though. \$\endgroup\$ Commented 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\$ Commented 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\$ Commented 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\$ Commented 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!

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.