Here is a continued discussion (Game where two players take turns picking numbers until a target sum) from here since my previous code has bug, I fixed it with totally new algorithm implementation.
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), and also try to find all possible force win solutions of player 1.
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.
Areas which I want to improve, but do not know how in my below code, asking for advice,
- I think the use of
first_player_initial_choiceis a bit ugly, but I do not know how to remove it;
- I check
len(path) == 1to see if it is first choice by player 1, so that I can record when player 1 force win, what is the first selected number -- which could be used for further filter purpose, it seems a bit ugly as well;
- I tried to find all possible winning solution of player 1, when try to filter (by using
if result in first_player_initial_choiceto see if winning soluton of player 1 is actually a player 1 force win solution.) It seems a bit ugly as well, but I cannot figure out a way which pick-up only player 1 force win solution only in an efficient recursive solution way.
results =  first_player_initial_choice = set() def force_win(numbers, flags, current_value, expected_value, path): current_win = False for i in range(len(flags)): if not flags[i]: if numbers[i] + current_value >= expected_value: path.append(numbers[i]) if len(path) % 2 != 0: results.append(path[:]) if len(path) == 1: first_player_initial_choice.add(numbers[i]) path.pop(-1) current_win = True else: flags[i] = True path.append(numbers[i]) opponent = force_win(numbers, flags, current_value+numbers[i], expected_value, path) if len(path) == 1 and not opponent: first_player_initial_choice.add(numbers[i]) path.pop(-1) flags[i] = False if not opponent: current_win = True # for return current_win if __name__ == "__main__": win = force_win([1,2,3,4,5],[False]*5, 0, 8, ) print win if win: final_result =  print results print first_player_initial_choice for result in results: if result in first_player_initial_choice: final_result.append(result) print final_result