Solve a whole game by search with memoization.
What to build
A program that decides who wins a take-away game with perfect play, and gives a winning first move.
Requirements
- There are several heaps of stones and a set of allowed takes. A move removes an allowed number of stones from one heap that has at least that many. Players alternate; a player who cannot move loses.
- Print
first player wins: take T from heap Hfor the first winning move (smallest heap number from 1, then smallest take), orsecond player wins.
Input
Line 1: the heap sizes. Line 2: the allowed takes.
Output
One line.
Constraints
At most 3 heaps of at most 15 stones; takes between 1 and 15.
Example
Input:
5
1 2 3
Output:
first player wins: take 1 from heap 1
Why it works
With perfect play every position is either a win or a loss for the player to move, and search with memoization labels each position once, from the end of the game backwards.
Examples
5 1 2 3
first player wins: take 1 from heap 1
4 1 2 3
second player wins
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
A position is winning for the player to move if some move leads to a position that is losing for the opponent; a position with no moves is losing.
Hint 2
Memoize the result for each tuple of heap sizes, or the search repeats the same positions many times.
Solution
Show one correct solution (try it yourself first)
from functools import lru_cache
heaps = tuple(map(int, input().split()))
takes = sorted(set(map(int, input().split())))
def moves(state):
for h, size in enumerate(state):
for t in takes:
if t <= size:
yield h, t, state[:h] + (size - t,) + state[h + 1:]
@lru_cache(maxsize=None)
def wins(state):
return any(not wins(nxt) for _, _, nxt in moves(state))
for h, t, nxt in moves(heaps):
if not wins(nxt):
print(f"first player wins: take {t} from heap {h + 1}")
break
else:
print("second player wins")