Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Memoization solution in Clear category for Battle Dice by sawako.oono
from functools import lru_cache
@lru_cache(maxsize=1000)
def one_time_prob(dice_description,units):
if units<=0:
return {(0,0):1}
prob_={}
for i in dice_description:
attack=i.count("A")
defence=i.count("D")
prob_[(attack,defence)]=prob_.get((attack,defence),0)+round(1/len(dice_description),10)
prob={}
for (attack,defence), i in prob_.items():
for (attack2,defence2),j in one_time_prob(dice_description,units-1).items():
prob[(attack+attack2,defence+defence2)]=prob.get((attack+attack2,defence+defence2),0)+round(i*j,10)
return prob
def one_battle(prob1,prob2,units_one,units_two):
prob={}
for (one_attack,one_defence),i in prob1.items():
for (two_attack,two_defence),j in prob2.items():
units_one_copy=max(units_one-max((two_attack-one_defence),0),0)
units_two_copy=max(units_two-max((one_attack-two_defence),0),0)
prob[(units_one_copy,units_two_copy)]=prob.get((units_one_copy,units_two_copy),0)+round(i*j,10)
return prob
def battle_probability(dice_description, units_one, units_two):
@lru_cache(maxsize=1000)
def sub_battle_probability(units_one, units_two,dice=tuple(dice_description)):
var=1
prob1,prob2=one_time_prob(dice,units_one),one_time_prob(dice,units_two)
prob=one_battle(prob1,prob2,units_one,units_two)
results=[]
for (units_one_copy,units_two_copy), p in prob.items():
if units_one_copy==units_one and units_two_copy==units_two:
var-=p
elif units_one_copy>0 and units_two_copy>0:
results.append(0 if p==0 else sub_battle_probability(units_one_copy, units_two_copy)*p)
elif units_one_copy<=0 and units_two_copy<=0:
results.append(0)
elif units_one_copy>0:
results.append(1*p)
else:
results.append(0)
return round(sum(results)/var,4)
return sub_battle_probability(units_one, units_two)
if __name__ == '__main__':
#These are only used for self-checking and are not necessary for auto-testing
def almost_equal(checked, correct, significant_digits=4):
precision = 0.1 ** significant_digits
return correct - precision < checked < correct + precision
assert(almost_equal(battle_probability(['A', 'D'], 3, 3), 0.0000)), "Always ties, nobody wins"
assert(almost_equal(battle_probability(['A', 'D'], 4, 3), 1.0000)), "Always win"
assert(almost_equal(battle_probability(['AA', 'A', 'D', 'DD'], 3, 4), 0.0186)), "You can win"
assert(almost_equal(battle_probability(['AA', 'A', 'D', 'DD'], 4, 4), 0.4079)), "Ready to fight"
assert(almost_equal(battle_probability(['AA', 'A', 'D', 'DD'], 5, 4), 0.9073)), "I have good chance"
July 15, 2021
