51 lines
1.0 KiB
Python
51 lines
1.0 KiB
Python
from functools import cache
|
|
|
|
|
|
@cache
|
|
def remove(n: str, pos: int) -> str:
|
|
assert pos < len(n)
|
|
r = n[:pos] + n[pos + 1:]
|
|
r = r.lstrip("0")
|
|
return r
|
|
|
|
|
|
@cache
|
|
def player_wins(n: str) -> bool:
|
|
if len(n) == 1:
|
|
return True
|
|
for i in range(len(n)):
|
|
if not player_wins(remove(n, i)):
|
|
return True
|
|
return False
|
|
|
|
def w(n: int) -> int:
|
|
r = 0
|
|
xs = [("", 0)]
|
|
for _ in range(n):
|
|
nxs = []
|
|
for x, x_count in xs:
|
|
nxs.append(("0" + x, x_count))
|
|
nx, nx_count = "x" + x, x_count + 1
|
|
if player_wins(nx):
|
|
r += (9 ** nx_count)
|
|
nxs.append((nx, nx_count))
|
|
xs = nxs
|
|
return r
|
|
|
|
|
|
def euler_961():
|
|
assert remove("105", 0) == "5"
|
|
assert remove("105", 1) == "15"
|
|
assert remove("105", 2) == "10"
|
|
assert remove("10005", 0) == "5"
|
|
assert w(2) == 18
|
|
assert w(4) == 1656
|
|
return w(18)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
solution = euler_961()
|
|
print("e961.py: " + str(solution))
|
|
# assert(solution == 0)
|
|
|