I'm trying to solve the Hackerrank challenge Game of Stones, a (shortened) problem statement of which is copied below.
I came up with the following solution:
# The lines below are for the Hackerrank submission
# T = int(raw_input().strip())
# ns = [int(raw_input().strip()) for _ in range(T)]
T = 8
ns = [1, 2, 3, 4, 5, 6, 7, 10]
legal_moves = [2, 3, 5]
if n <= 1:
return "Second" # First player loses
elif n in legal_moves:
return "First" # First player wins immediately
next_ns = map(lambda x: n - x, legal_moves)
next_ns = filter(lambda x: x >= 0, next_ns)
next_n_rewards = map(which_player_wins, next_ns) # Reward for opponent
if any(map(lambda x: x=="Second", next_n_rewards)): # Opponent enters a losing position
for n in ns:
It seems from the problem description that you are able to keep the intermediate and final results from each calculation to use in later calculations. If that is so, a recursive algorithm is not optimal. Instead, use a dynamic programming style.
In other words, keep a global array that stores the results from previous determinations of wins and losses. When you determine for a new value of
n, rather than recursing all the way to the end, use the previous determinations.
For example, when you get to
n=10, you see that the first player removing 3 stones leaves 7 stones, which you have already seen as a win for the second player. Therefore, 10 stones is a win for the first player.
I believe that your recursive algorithm would calculate all over again the result for
n=7 rather than using the previous work.