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_choice
is a bit ugly, but I do not know how to remove it; - I check
len(path) == 1
to 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[0] in first_player_initial_choice
to 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.
My code,
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[0] in first_player_initial_choice:
final_result.append(result)
print final_result