Working on the problem of sum game. Suppose we have consecutive numbers from 1 to n, and an expected sum number, there are two players, and each player tries to select one number in turn (once a number is selected by one player, the other player cannot select it again), and the selected numbers are summed together. The player who first get a sum which is >= expected sum wins the game. The question is trying to find if first player has a force win solution (means no matter what numbers 2nd player will choose each time, the first player will always win).
For example, if we have numbers from 1 (inclusive) to 5 (inclusive) and expected sum is 7, if the first player select 1, no matter what the 2nd player select, in the final the first player will always win.
Here is my code and my idea is, each player tries to see if select the largest number can win -- if not then selecting the smallest available (means not having been selected) number -- which gives the current player max chance to win in the following plays, and give the opponent player minimal chance to win in the following plays.
I think the above strategy is optimum for player 1 and player 2, if in this strategy, player 2 cannot win, it means player 1 could force win.
I want to review the code, and also if my thought of the algorithm (strategy) to resolve the problem is correct?
def try_best_win(numbers, flags, current_sum, expected_sum, is_first_player):
if current_sum + numbers[-1] >= expected_sum:
return is_first_player == True
else:
for i in range(len(flags)):
# find the next smallest number
if flags[i] == False:
flags[i] = True
return try_best_win(numbers, flags, current_sum+numbers[i], expected_sum, not is_first_player)
if __name__ == "__main__":
print try_best_win([1,2,3,4,5], [False]*5, 0, 6, True) #False
print try_best_win([1,2,3,4,5], [False]*5, 0, 7, True) #True
flag
becomesTrue
it staysTrue
forever, and recursion doesn't happen. \$\endgroup\$