32 lines
728 B
Python
32 lines
728 B
Python
from fractions import Fraction
|
|
from functools import lru_cache
|
|
|
|
|
|
@lru_cache
|
|
def expected_singles(sheets):
|
|
count = 0
|
|
if len(sheets) == 1 and sheets[0] == 5:
|
|
return 0
|
|
elif len(sheets) == 1:
|
|
count += 1
|
|
|
|
weight = Fraction(1, len(sheets))
|
|
for sheet in sheets:
|
|
nsheets = list(sheets)
|
|
nsheets.remove(sheet)
|
|
for nsheet in range(sheet, 5):
|
|
nsheets.append(nsheet + 1)
|
|
count += weight * expected_singles(tuple(sorted(nsheets)))
|
|
return count
|
|
|
|
|
|
def euler_151():
|
|
return round(float(expected_singles(tuple([2, 3, 4, 5]))), 6)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
solution = euler_151()
|
|
print("e151.py: " + str(solution))
|
|
assert(solution == 0.464399)
|
|
|