Some friends play a simple dice game. The players players take turns in a fixed order (player 0, player 1, ..., then player 0 again), and each turn is one roll of a fair die with faces 1 to faces. A roll wins when it shows one of the winning highest faces (for example winning = 1 means only the top face wins). The first player to roll a winning face wins the game. If rounds full rounds pass (every player has rolled rounds times) with no winner, the game ends in a draw.
Write game_chances(players, faces, winning, rounds) that returns a list of players + 1 exact probabilities: the chance that player 0 wins, that player 1 wins, ..., and finally the chance of a draw. Each probability is a tuple (numerator, denominator) in lowest terms ((0, 1) for 0).
Examples
Input: players = 2, faces = 6, winning = 1, rounds = 1
Output: [(1, 6), (5, 36), (25, 36)]
Explanation: player 0 wins on the first roll with 1/6. Player 1 wins if player 0 missed
(5/6) and player 1 then hits (1/6): 5/36. A draw needs both to miss: 25/36.
Input: players = 2, faces = 6, winning = 1, rounds = 2
Output: [(61, 216), (305, 1296), (625, 1296)]
Explanation: player 0 wins in round 1 (1/6) or in round 2 after two misses
(25/36 · 1/6 = 25/216): 36/216 + 25/216 = 61/216 in total.
Constraints
1 <= players <= 10,1 <= faces <= 20,0 <= winning <= faces1 <= roundsandplayers * rounds <= 60
Goals
- Find the probability that nothing happens for a while by multiplying complements
- Split "player i wins" into disjoint cases by the round in which it happens
- Check that the probabilities of all possible results add up to 1