Mathematicians Steve Humble and Yutaka Nishiyama invented a randomness game to highlight a surprising result in probability, based on a principle discovered by Walter Penney.

The game is played with an ordinary deck of 52 cards, containing 26 red cards and 26 black cards. The cards are dealt out in a row, one after another. Before dealing begins, the first player claims an ordered sequence of colors that might turn up while dealing the cards. Then the second player claims another ordered sequence of colors that might turn up while dealing the cards, which must have the same length as the sequence of the first player. As the cards are dealt, if one of the claimed sequences of successive card colors turns up, the player who claimed it wins a point. Then all cards are removed from the table, and the dealing continues with the remaining cards in the deck. When all 52 cards have been dealt, the player who has collected the most points wins (in a typical game, 7 to 9 points are won).

For example, let's say you and I are playing the game, and you choose the sequence red-black-red. I then choose red-red-black. The following six card colors are dealt:

So far, no one has won yet. A sixth card is put down, which turns out to be a red card. Ah! red-black-red is your sequence. You've one, which gives you one point. You gather up the seven cards and put them by your side, and the dealing continues with the remaining 45 cards.

This sounds like a perfectly even game, but in fact the second player has a strategy that will given him a significant advantage. When the first player has chosen his sequence, say red-black-red (or RBR for short), the second player changes the middle color (in this case he obtains red), adds it to the start of the sequence, discards the last color (in this case he is left with red-black), and claims the resulting sequence (in this case RRB). Believe it or not, but this gives the second player a 82.7% chance to win the game if 7 points are score in total. In general, this strategy gives a decided advantage to the second player no matter which sequence his opponent has chosen. In a computer simulation of 1,000 games, Humble and Nishiyama got these results:

Assignment

We will represent the color of a card by an uppercase letter: R for red and B for black. This way, we can represent an ordered sequence of colors as a string that only contains the letters R and B. Your task:

• Write a function counter that takes an ordered sequence of three colors. This represents the ordered sequence of colors claimed by the first player. The function must return the ordered sequence of three colors claimed by the second player, if he applies the strategy outlined in the introduction of this assignment. If no valid ordered sequence of three colors is passed to the function, an AssertionError must be raised with the message invalid sequence.

• Write a function score that takes three ordered sequences of colors: i) the sequence of colors claimed by the first player, ii) the sequence of colors claimed by the second player (not necessarily by applying the strategy outline in the introduction of this assignment) and iii) the sequence of colors in which all cards of the deck are dealt. The function must return a tuple containing two integers that respectively represent the score of the first and the second player at the end of the game.

• Write a function winner that takes three ordered sequences of colors: i) the sequence of colors claimed by the first player, ii) the sequence of colors claimed by the second player (not necessarily by applying the strategy outline in the introduction of this assignment) and iii) the sequence of colors in which all cards of the deck are dealt. The function must return the value 1 if the first player wins the game, the value 2 if the second player wins the game, and the value 0 if the game ends in a tie.

The functions score and winner must raise an AssertionError with the message invalid sequences, if the sequences passed to the function do not meet the following conditions:

• the first two sequences must be different ordered sequences of colors that have the same length; the number of cards in these sequence should not necessarily be three

• the third argument must represent the ordered sequence of colors in which an ordinary deck of cards (containing 26 red cards and 26 black cards) are dealt during the game

Example

>>> counter('RRR')
'BRR'
>>> counter('RBB')
'RRB'
>>> counter('BBB')
'RBB'
>>> counter('RBRBRBRB')
Traceback (most recent call last):
AssertionError: invalid sequence
>>> counter('RGB')
Traceback (most recent call last):
AssertionError: invalid sequence

>>> score('BRR', 'RRR', 'RBRBRRBBBBBRRRRRRRRBRRRBRRRBRBBBBBBRRBBBRRRBRBBBBBBR')
(6, 2)
>>> score('RBR', 'BRR', 'BBBBRBRBRBRRBRRBBBRBRBBRRRBBBBRRRBBBRRRRRBBRRBBRRBRR')
(4, 6)
>>> score('BRR', 'RRB', 'BRRRRBRRBRRBBBBRBBRBRBBRRBRRRRRBBBBBRBRBBRRRBRBRBBBR')
(4, 4)
>>> score('BBR', 'BRB', 'BBRBBRRBBRBBRBRBBBBBRBRRRBRBBBRBRRRBRRRBBRRRRRRBBRRR')
Traceback (most recent call last):
AssertionError: invalid sequences
>>> score('RGB', 'BRB', 'RRBBBBRRRRBBRRBRBRRRBBRRBRRBBRBBBRRBBBBRBBRBRRBRRRBB')
Traceback (most recent call last):
AssertionError: invalid sequences

>>> winner('BRR', 'RRR', 'RBRBRRBBBBBRRRRRRRRBRRRBRRRBRBBBBBBRRBBBRRRBRBBBBBBR')
1
>>> winner('RBR', 'BRR', 'BBBBRBRBRBRRBRRBBBRBRBBRRRBBBBRRRBBBRRRRRBBRRBBRRBRR')
2
>>> winner('BRR', 'RRB', 'BRRRRBRRBRRBBBBRBBRBRBBRRBRRRRRBBBBBRBRBBRRRBRBRBBBR')
0
>>> winner('BBR', 'BRB', 'BBRBBRRBBRBBRBRBBBBBRBRRRBRBBBRBRRRBRRRBBRRRRRRBBRRR')
Traceback (most recent call last):
AssertionError: invalid sequences
>>> winner('RGB', 'BRB', 'RRBBBBRRRRBBRRBRBRRRBBRRBRRBBRBBBRRBBBBRBBRBRRBRRRBB')
Traceback (most recent call last):
AssertionError: invalid sequences

Resources

• Humble S, Nishiyama Y (2010). Humble-Nishiyama randomness game - a new variation on Penney's coin game. Mathematics Today. ¹

• Nishiyama Y, Humble S (2014). Winning odds. Plus Magazine 55. ²