2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ By "force win solution", do you mean "on the first turn" or "on any turn" ? \$\endgroup\$ – ChatterOne Nov 17 '16 at 8:29
  • \$\begingroup\$ I think he means "first-player-win", meaning that when both players play a perfect strategy, the starting player will always win after an arbitrary number of moves or turns. \$\endgroup\$ – vonludi Nov 17 '16 at 8:39
2
+25
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Nice solution ChatterOne, vote up. For your comments -- "you just need to check what happens when player one picks the lowest number and player two picks the remaining highest number", I do not quick get it, how select max/min only could determine if there is a force win situation (without full enumerate)? I ask this since each player could try their best to play -- they are not necessary always choose largest and/or smallest available number. \$\endgroup\$ – Lin Ma Nov 18 '16 at 8:14
  • 1
    \$\begingroup\$ The purpose of the game is to reach at least a specified number. When you pick a number you cannot lose: either you win, or the game continues. If pick the lowest possible number, you check if the other player can win by picking the highest. If he can, you return false immediately. Otherwise, he will also not win by picking one of the lowest numbers, so you may have a forced win, and you repeat the process. \$\endgroup\$ – ChatterOne Nov 18 '16 at 8:59
  • \$\begingroup\$ Thanks for the explanation ChatterOne, but I think this line is not correct -- numbers.remove(min_value), I think this line means you assume first player always choose the smallest number, actually the player may choose any number, always choose smallest number (under the condition of the first player cannot win in current step) -- is not optimal solution of player 1 and play 1 may lose force win opportunities. If I mis-understand your code of numbers.remove(min_value), please feel free to correct me. \$\endgroup\$ – Lin Ma Nov 19 '16 at 7:14
  • \$\begingroup\$ Hi ChatterOne, if you could clarify on my above question, it will be great. thanks. \$\endgroup\$ – Lin Ma Nov 25 '16 at 3:58
  • \$\begingroup\$ Hi ChatterOne, thanks for all the help and mark your reply as answer, start a new thread and we can continue to discuss open question there, thanks. codereview.stackexchange.com/questions/148147/… \$\endgroup\$ – Lin Ma Nov 26 '16 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.