Game where two players take turns picking numbers until a target sum (part 2)

Question

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,

1. I think the use of first_player_initial_choice is a bit ugly, but I do not know how to remove it;
2. 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;
3. 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

Answer 1

About the algorithm

• If you want to check for a force win on the first turn, you just need to check what happens when player one picks the lowest number and player two picks the remaining highest number.

• If you want to check for a force win on the other turns you can repeat the check by removing numbers from the list and check the remaining highest and lowest numbers.

About the code

• It took me a while to get how your code worked, I think it's overly complicated. You have flags to determine if a number has been picked, but if you really want to keep a copy of the original numbers (which you don't actually need) you can just, well, copy it.
• I still don't really get the path variable. You use that to determine whose turn it is, but you don't need to know that, you only need to know if player one has a forced win.

This is how I'd go about it for a solution. Keep in mind that I didn't test every corner case, but it should give you an idea about what I mean:

def force_win(numbers, current_sum, expected_value):
    # Numbers are assumed to be positive integers
    # For simplicity I assume there are no duplicates
    # Otherwise be careful if min_value == max_value
    min_value = min(numbers)
    max_value = max(numbers)
    current_sum += min_value + max_value

    if (current_sum >= expected_value):
        return False

    numbers.remove(min_value)
    if (max_value in numbers):
        numbers.remove(max_value)
    if (len(numbers) == 0):
        return False

    if (min_value + max_value < expected_value):
        if ((current_sum + min_value) >= expected_value):
            return True
    force_win(numbers, current_sum, expected_value)

    return False

if __name__ == "__main__":
    print force_win([1,2,3,4,5], 0, 7)