Created
January 5, 2023 04:08
-
-
Save duruyao/67f317c7ddb5b1662a87417466625bc2 to your computer and use it in GitHub Desktop.
The game of getting balls.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import sys | |
def have_wining_strategy(*bags: int) -> bool: | |
if 0 == sum(bags): | |
return False | |
for i in range(len(bags)): | |
for n in range(bags[i]): | |
if not have_wining_strategy(*bags[:i], n, *bags[i + 1:]): | |
return True | |
return False | |
def have_failing_strategy(*bags: int) -> bool: | |
if 0 == sum(bags): | |
return True | |
for i in range(len(bags)): | |
for n in range(bags[i]): | |
if not have_failing_strategy(*bags[:i], n, *bags[i + 1:]): | |
return True | |
return False | |
print(have_wining_strategy(*[int(x) for x in sys.argv[1:]])) | |
print(have_failing_strategy(*[int(x) for x in sys.argv[1:]])) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import sys | |
cache = {} | |
def key(*args: int) -> str: | |
args = list(args) | |
args.sort() | |
return str(args) | |
def have_wining_strategy(*bags: int) -> bool: | |
if key(*bags) in cache: | |
return cache[key(*bags)] | |
if 0 == sum(bags): | |
cache[key(*bags)] = False | |
return False | |
for i in range(len(bags)): | |
for n in range(bags[i]): | |
if not have_wining_strategy(*bags[:i], n, *bags[i + 1:]): | |
cache[key(*bags)] = True | |
return True | |
cache[key(*bags)] = False | |
return False | |
def have_failing_strategy(*bags: int) -> bool: | |
if key(*bags) in cache: | |
return cache[key(*bags)] | |
if 0 == sum(bags): | |
cache[key(*bags)] = False | |
return False | |
for i in range(len(bags)): | |
for n in range(bags[i]): | |
if not have_failing_strategy(*bags[:i], n, *bags[i + 1:]): | |
cache[key(*bags)] = True | |
return True | |
cache[key(*bags)] = False | |
return False | |
print(have_wining_strategy(*[int(x) for x in sys.argv[1:]])) | |
print(have_failing_strategy(*[int(x) for x in sys.argv[1:]])) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment