6
\$\begingroup\$

For this task, you're going to play a dice game, but first you must prepare for an overwhelming victory. The game itself is very simple. Both players roll a single die and whoever rolls highest scores a point. (On a tie, both players must reroll until someone scores.)

These aren't standard dice however. Each player can put any positive number on any side of the die as long as the number of sides match and the total of all the chosen numbers are the same. For example, one player might use a six sided die with the numbers [3, 3, 3, 3, 6, 6] while the other player uses a six sided die with the numbers [4, 4, 4, 4, 4, 4]. The interesting part of this game is that even with the same number of sides and the same total, different dice have different chances of winning. Using the example die, the player with all 4's will win 2/3 of the time.

To prepare for this game, you're investigating different ways of picking the numbers. To do this, write a program that will take an opponent's die and output some die which will win against it more than half the time. If no die satisfies the task requirements, return an empty list.

Input: An enemy's die as a sorted list of integers, one for each face of the opponent's die.

Output: Your die as a list of integers, one for each face of your die or an empty list.

  • winning_die([3, 3, 3, 3, 6, 6]) == [4, 4, 4, 4, 4, 4] # Or [3, 3, 4, 4, 5, 5]
  • winning_die([4, 4, 4, 4, 4, 4]) == [2, 2, 5, 5, 5, 5] # Or [5, 5, 2, 2, 5, 5]
  • winning_die([2, 2, 5, 5, 5, 5]) == [3, 3, 3, 3, 6, 6]
  • winning_die([1, 1, 3]) == [1, 2, 2]

How can I make this faster?

import itertools

def winning_die(enemy_die):
    upper = max(enemy_die) + 1
    comb = [i for i in itertools.product(range(1, upper+1), repeat=len(enemy_die)) 
            if sum(i)== sum(enemy_die)]

    for die in comb:
        if win(die, enemy_die):
            return list(die)
    return []

def win(player, enemy):
    return sum(1 if p > e else -1 if p < e else 0 
               for p in player for e in enemy) > 0
\$\endgroup\$
  • \$\begingroup\$ You need to implement a function similar to product which generates dice with the correct sum without wasting time generating dice that are nowhere near correct. For example if the enemy die is [1, 1, 5] then your die cannot contain a 5 or 6, and if it contains a 4 then the only other numbers allowed are 1 and 2. You'll need recursive backtracking. \$\endgroup\$ – Alex Hall Sep 7 '17 at 10:13
2
\$\begingroup\$
comb = [i for i in itertools.product(range(1, upper+1), repeat=len(enemy_die)) 
        if sum(i)== sum(enemy_die)]

for die in comb:
    if win(die, enemy_die):
        return list(die)
return []

There's an early return -- but it's after creating the entire list of possibilities. Changing comb to a generator expression will let you skip generating the rest of the comb after finding a winner:

enemy_die_sum = sum(enemy_die)  # Might as well cache this too

comb = (i for i in itertools.product(range(1, upper + 1), repeat=len(enemy_die))
        if sum(i) == enemy_die_sum)

You can then fold the win()-checking loop into the same expression, simplifying down to this (thanks @Mathias Ettinger):

def winning_die(enemy_die):
    upper_bound = max(enemy_die) + 1
    enemy_die_sum = sum(enemy_die)

    comb = (die for die in itertools.product(range(1, upper_bound + 1), repeat=len(enemy_die))
            if sum(die) == enemy_die_sum and win(die, enemy_die))

    return list(next(comb, []))

For me, this runs around 10-50x faster for your test cases.

\$\endgroup\$
  • 2
    \$\begingroup\$ If you add and win(i, enemy_die) at the end of the genexpr, you can then just return next(comb, []) without having to do the looping in Python and possibly gain some more time too. \$\endgroup\$ – Mathias Ettinger Sep 7 '17 at 8:20
  • \$\begingroup\$ Thank you very much, DenC and Mathias. But it is still not fast enough to pass the game :-(. \$\endgroup\$ – Tao Xu Sep 15 '17 at 3:40

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.