Make a Deal program - using sets in Python

Question

Mostly because I didn't believe the outcome of the classic game play Make-a-Deal (see https://math.stackexchange.com/questions/608957/monty-hall-problem-extended) I made this little program... and indeed if there are 3 doors and the quiz-master opens a door and you then switch from your initial choice of door your chances go up from 33% to 67%! This program is the generalized version whereby you can choose the number of doors and how many doors the quiz-master will open, it calculates the chance for a price for the initial choice (basically 1 over the number of doors) and the chance if you change your selected door after the doors have been opened.

I was pleasantly taken by the elegant solution using Python sets, but I wonder if this is the most efficient way. Comparing with other methods it looks like it becomes relatively more efficient with more doors and doors to open.

Thank you for your input...

#!/usr/bin/env python
'''  application of Make a deal statistics
     application is using sets {}
     for reference:
 https://math.stackexchange.com/questions/608957/monty-hall-problem-extended
'''
import random


def Make_a_Deal(doors, doors_to_open):
    '''  Generalised function of Make_a_Deal. Logic should be self explanatory
         Returns win_1 for the option when no change is made in the choice of
         door and win_2 when the option to change is taken.'''

    win_1, win_2 = False, False

    doors_set = set(range(1, doors+1))
    price_set = set(random.sample(doors_set, 1))
    choice1_set = set(random.sample(doors_set, 1))
    open_set = set(random.sample(doors_set.difference(price_set).
                   difference(choice1_set), doors_to_open))
    choice2_set = set(random.sample(doors_set.difference(open_set).
                      difference(choice1_set), 1))
    win_1 = choice1_set.issubset(price_set)
    win_2 = choice2_set.issubset(price_set)

    return win_1, win_2


def main():
    '''  input:
         - throws: number of times to Make_a_Deal (must be > 0)
         - doors: number of doors to choose from (must be > 2)
         - doors_to_open: number of doors to be opened before giving the option
           to change the initial choice (must be > 0 and <= doors-2)'''

    try:
        throws = int(input('how many throws: '))
        doors = int(input('how many doors: '))
        doors_to_open = int(input('how many doors to open: '))
        if (throws < 1) or (doors < 3) or \
                (doors_to_open > doors-2) or (doors_to_open < 1):
            print('invalid input')
            return

    except Exception as e:
        print('invalid input: ', e)
        return

    number_of_wins_1, number_of_wins_2, counter = 0, 0, 0

    while counter < throws:
        win_1, win_2 = Make_a_Deal(doors, doors_to_open)

        if win_1:
            number_of_wins_1 += 1
        if win_2:
            number_of_wins_2 += 1

        counter += 1
        print('completion is {:.2f}%'.
              format(100*counter/throws), end='\r')

    print('number of wins option 1 is {:.2f}%: '.
          format(100*number_of_wins_1/counter))
    print('number of wins option 2 is {:.2f}%: '.
          format(100*number_of_wins_2/counter))


if __name__ == '__main__':
    main()

Answer 1

You can do this in \$O(1)\$ space and time, where you're doing it in \$O(n)\$ space and time. I cleaned your code and got roughly the same as Graipher's code:

def make_a_deal(doors, doors_to_open):
    doors = range(1, doors+1)
    price = set(random.choice(doors))
    choice_1 = set(random.choice(doors))
    doors = set(doors)
    open_doors = set(random.sample(doors - price - choice_1, doors_to_open))
    choice_2 = set(random.sample(doors - open_doors - choice_1, 1))
    return choice_1 <= price, choice_2 <= price

But there are some changes you can make to make it faster.

1. After generating price and choice_1 you can check if the user has won, and return True, False.
2. You don't need to randomly select price, this is as you can rotate the doors until price is the first, always. And so you can make price = 0.
3. Expanding on the above we now know that 0 is the only door with the price, and so \$1 \to n\$ are all loser doors. From this we know that one of the doors we picked was a loser door, and so we can remove that door, and shift all the other doors down. Which is the same as removing the last door.
4. Expanding on the above, you can remove \$k\$ more loser doors, as they are randomly selected.
5. And so the second choice has a range of \$0 \to n - k - 1\$.

And so you can get \$O(1)\$ space and time:

def make_a_deal(doors, doors_to_open):
    price = 0
    choice_1 = random.randrange(doors)
    if choice_1 == price:
        return True, False

    choice_2 = random.randrange(doors - 1 - doors_to_open)
    return False, choice_2 == price

Answer 2

I second @Graipher's answer in the use of an helper function for your sets sampling, but we could improve on its solution by using the following definition which automatically convert the returned value from random.sample into a set:

def random_choice(population, k=1):
    return {*random.sample(population, k)}

---

Your docstrings doesn't make much sense as they seem intended to the reader of the code. Instead, write your docstring for the user, document what the function/module is doing, not how.

---

You don't need to explicit the type of a variable in its name, choose names reflecting what is stored, not how.

---

I would separate input gathering from main. It's validation is good, even though a bit too much: if throws is not positive, there won't be any throws and the statistics will be 0, which is coherent. Make your main agnostic from where your data are coming/going to ease reusability and testing. If you trully want to report progression, you should instead accept a callback to make the behaviour optional and easily inter-changeable.

Having you input gathering separated from your main makes it easy to switch input to argparse for instance or any GUI for that matter.

---

Do not catch generic Exceptions here you only care about ValueErrors. It will avoid printing Invalid input for exceptions such as KeyboardInterrupt for instance.

You should also print your error messages to sys.stderr, and optionally exit your program with a non-zero return code using sys.exit().

---

Prefer using for loops over whiles with explicit counters.

---

Proposed improvements:

#!/usr/bin/env python3

"""Application of Make a deal statistics

Application is using sets {}

For reference:
    https://math.stackexchange.com/questions/608957/monty-hall-problem-extended
"""

import sys
import random


def random_choice(population, k=1):
    return {*random.sample(population, k)}


def make_a_deal(doors, doors_to_open):
    """Generalised function of Make a Deal.

    Returns a pair of boolean indicating:
     - wether the original choice was a win for the first element
     - wether the changed choice was a win for the second element
    """

    doors = set(range(doors))
    prize = random_choice(doors)
    original_choice = random_choice(doors)

    opened = random_choice(doors - prize - original_choice, doors_to_open)
    changed_choice = random_choice(doors - opened - original_choice)

    return original_choice <= prize, changed_choice <= prize


def main(throws, doors, doors_to_open, progression_callback=None):
    """Gather statistics about repeated simulations of Make a Deal game.

    Parameters:
     - throws: number of simulations to run
     - doors: number of doors to choose from (must be > 2)
     - doors_to_open: number of doors to be opened before giving the
    option to change the initial choice (must be > 0 and <= doors - 2)
    """
    if doors < 3:
        raise ValueError('doors must be at least 3')

    if not (0 < doors_to_open <= doors - 2):
        raise ValueError('doors to open mismatch the number of doors')

    original_wins = changed_wins = 0
    for throw in range(throws):
        original_win, changed_win = make_a_deal(doors, doors_to_open)

        if original_win:
            original_wins += 1

        if changed_win:
            changed_wins += 1

        if progression_callback is not None:
            progression_callback(throw / throws)

    return original_wins / throws, changed_wins / throws


def show_completion(ratio):
    print('Completion is {:.2%}'.format(ratio), end='\r')


if __name__ == '__main__':
    try:
        throws = int(input('How many throws: '))
        doors = int(input('How many doors: '))
        doors_to_open = int(input('How many doors to open: '))
        wins1, wins2 = main(throws, doors, doors_to_open, show_completion)
    except ValueError as e:
        print('Invalid input:', file=sys.stderr, end=' ')
        sys.exit(e)

    print('Number of wins without changing is {:.2%}'.format(wins1))
    print('Number of wins after changing is {:.2%}'.format(wins2))

Answer 3

Python has an official style-guide, PEP8. It recommends using lower_case for variable and function names. There is also a style-guide for docstrings, PEP257, which recommends using triple double-quotes ("""So, like this""").

Your module docstring should maybe include a one sentence summary, like "Extended Monty-Hall problem with n doors, k of which are opened by the game master."

---

It is a pity that random.choice does not work on sets, because they are not indexable. However, you are using its alternative random.sample(x, 1) often enough that you might want to put it in a function:

def random_choice(x):
    return random.sample(x, 1)[0]

This also means you need to use {random_choice(x)}, instead of set(random_choice(x)), because this is now a single element and no longer a list with one element.

---

doors_set.difference(price_set).difference(choice1_set) is the same as doors_set - price_set - choice1_set, which is shorter and at least as readable.

Similarly, choice1_set.issubset(price_set) is equivalent to choice1_set <= price_set (even though here the more expressive version is probably easier to understand).

You don't need to declare a variable in Python, especially if you override its value anyways (win_1 and win_2).

I would also rename option_1 and option_2 to the easier to understand no_change and change.

Since you never use doors again, I would remove all the trailing _set from the names.

There is no difference if you enumerate your doors starting with zero or one, so I would use set(range(doors)) for simplicity.

With that, your make_a_deal function becomes:

def make_a_deal(doors, doors_to_open):
    '''  Generalised function of Make_a_Deal. Logic should be self explanatory
         Returns win_1 for the option when no change is made in the choice of
         door and win_2 when the option to change is taken.'''

    doors = set(range(doors))
    price = {random_choice(doors)}
    choice1 = {random_choice(doors)}
    open_doors = set(random.sample(doors - price - choice1, doors_to_open))
    choice2 = {random_choice(doors - open_doors - choice1)}
    no_change = choice1 <= price
    change = choice2 <= price

    return no_change, change

Answer 4

I think it's a good idea to test a problem yourself if you don't agree with the solution, so I commend you for that. However, since what you're doing is a simulation of a statistical problem, the unfortunate solution to optimizing this and making it better is to simply use math to calculate formulas for the probabilities.

For this, I'll generalize it even further: there can be more than one prize. However, the host cannot open a door with a prize behind, so this limits the number of doors they can open.

If we have \$n\$ doors, \$p\$ prizes, and the host opens \$d\$ doors, then the probability of winning without switching doors is simply \$\frac{p}{n}\$, since what the host does with the doors does not affect our initial choice. Also note that for the game to progress, the host cannot open more than \$n-p-1\$ doors, as he could be forced to open a door with a prize behind otherwise.

To calculate the probability of winning by switching, we divide the scenario in to the two cases:

1. We were correct in our first guess
2. We didn't pick a prize with our first guess

We know that \$(1)\$ occurs with probability \$\frac{p}{n}\$, and inversely \$(2)\$ occurs with probability \$\frac{n-p}{n}\$.

For case \$(1)\$, there is a prize behind the door we picked first, so there are \$p-1\$ prizes behind the rest of the closed doors. Since the host has opened \$d\$ doors, there are \$n-d-1\$ doors to switch to.

For case \$(2)\$, there are \$p\$ prizes behind the doors that we can switch to, and there are still \$n-d-1\$ doors to choose from.

By multiplying the probabilities, we get:

$$ P(winning\ by\ switching) = \frac{p}{n}\frac{p-1}{n-d-1} + \frac{n-p}{n}\frac{p}{n-d-1} = \frac{p}{n}\frac{n-1}{n-d-1} $$

Considering this, my python implementation would be:

def get_win_percentage(n, d, p, switching):
    if d > n-p-1:
        return 0
    if not switching:
        return p/n
    return (p/n)*(n-1)/(n-d-1)

I know that this doesn't answer your question directly, but since you've gotten a lot of good feedback from other users, I thought I'd contribute this way.