Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
O(n) solution in Speedy category for Unfair Dice by coells
from collections import Counter
def cost(dice, c):
prev, loss, bank, pos = 1, 0, 0, 0
for i, v in enumerate(dice):
if v > prev:
new_v = prev
if c[new_v] and new_v + 1 < v:
new_v += 1
new_loss, new_bank = c[v] + c[new_v], v - new_v
if new_bank*loss >= bank*new_loss:
loss, bank, pos = new_loss, new_bank, i
prev = v
dice[pos] -= bank
return -loss, bank
def gain(dice, c):
gain, pos = max((c[v]+c[v+1], i) for i, v in enumerate(dice))
dice[pos] += 1
return gain
def winning_die(dice):
c = Counter(dice)
loss, bank = cost(dice, c)
while bank:
loss, bank = loss + gain(dice, c), bank - 1
return dice if loss > 0 else []
if __name__ == '__main__':
#These are only used for self-checking and not necessary for auto-testing
def check_solution(func, enemy):
player = func(enemy)
total = 0
for p in player:
for e in enemy:
if p > e:
total += 1
elif p < e:
total -= 1
return total > 0
assert check_solution(winning_die, [3, 3, 3, 3, 6, 6]), "Threes and Sixes"
assert check_solution(winning_die, [4, 4, 4, 4, 4, 4]), "All Fours"
assert check_solution(winning_die, [1, 1, 1, 4]), "Unities and Four"
assert winning_die([1, 2, 3, 4, 5, 6]) == [], "All in row -- No die"
June 24, 2014
