7
\$\begingroup\$

After answering Monty hall python simulation I wondered what the outcome were to be if there were more than three doors, say four or seven. And so I decided to modify the problem slightly to adjust for this.

There are \$x\$ amount of doors. Behind one door is a car, the others are goats. You pick a door, and the host reveals a goat in a different door. You're then given the choice to change from the selected door to any door except the open door, or the already selected door.

And so I decided to find out how many times a person is likely to win if they always pick a random door when asked if they want to switch door. And so programmed the following:

import random

def monty_hall(amount, doors=3):
    if doors < 3:
        raise ValueError(f'doors must be greater than three, not {doors}')

    wins = 0
    for _ in range(amount):
        player_choice = random.randrange(doors)
        car_placement = random.randrange(doors)
        other_doors = set(range(doors)) - {player_choice, car_placement}

        shown_door = random.choice(list(other_doors))
        swap_doors = set(range(doors)) - {player_choice, shown_door}
        final_choice = random.choice(list(swap_doors))

        wins += final_choice == car_placement
    return wins

print(monty_hall(1000000, 3))
print(monty_hall(1000000, 4))
print(monty_hall(1000000, 5))

I then decided to optimize the above code, and came up with the following ways to do this:

  1. Change player_choice to doors - 1. The first player choice doesn't have to be random.
  2. Change other_doors and swap_doors to account for (1). Rather than removing an item that will always be in the set, remove it from the range and the second set. And so other_doors becomes: set(range(doors - 1)) - {car_placement}.
  3. Remove player_choice as it's no longer used.
  4. Change shown_door to always be the first door. However if the car is the first door, show the second. shown_door = car_placement == 0.
  5. Remove other_doors as it's no longer used.
  6. Change swap_doors to be a list, rather then a set with an item being removed. This requires the use of an if else to manually split the list if the car is in the first door. And so can become:

    if car_placment == 0:
        swap_doors = [0] + list(range(2, doors - 1))
    else:
        swap_doors = list(range(1, doors - 1))
    final_choice = random.choice(swap_doors)
    
  7. Rather than making my code WET, as I did in (6), we can instead move the car to the second door if it's in the first, and use the else whatever the case.

  8. Finally we can merge all the code into a sum and a generator comprehension.

This resulted in the following code:

import random

def monty_hall(amount, doors=3):
    if doors < 3:
        raise ValueError(f'doors must be greater than three, not {doors}')

    rand = random.randrange
    return sum(
        max(rand(doors), 1) == rand(1, doors - 1)
        for _ in range(amount)
    )

print(monty_hall(1000000, 3))
print(monty_hall(1000000, 4))
print(monty_hall(1000000, 5))

Are there any improvements that I can make on either the optimized or non-optimized solutions? Also are there any issues with the optimized solution, as my method for optimization weren't exactly scientific. As far as I know it looks good.

Code is only runnable in Python 3.6+

\$\endgroup\$
  • \$\begingroup\$ What is the rationale for 1. (and thus 4.)? \$\endgroup\$ – Mathias Ettinger Apr 18 '17 at 9:51
  • \$\begingroup\$ @MathiasEttinger I decided to make it static as changing the first chosen door doesn't change the outcome of the problem, the randomness there comes from the random door that the car is behind. Say you were to manually model this, you'd always take the chosen door to be one door rather than any door. I chose the last door as it made the code a little nicer to read. \$\endgroup\$ – Peilonrayz Apr 18 '17 at 9:56
  • \$\begingroup\$ "I wondered what the outcome were to be if there were more than three doors, say four or seven" - as an aside: The probability that the contestant picked the car is 1/x. If they swap, it converts this probability to (x-1)/x. You should always swap, as it converts the probability that you didn't get it first time, into the probability that you did. With an increasing number of doors, swapping vastly improves the likelihood that you did win \$\endgroup\$ – Caius Jard Apr 18 '17 at 13:48
  • \$\begingroup\$ @CaiusJard you also have to take into account that the swap has a possible \$x-2\$ doors to move to, and so the chance to win becomes \$\frac{x-1}{x(x - 2)}\$, compared to \$\frac{1}{x}\$ if you don't swap. \$\endgroup\$ – Peilonrayz Apr 18 '17 at 14:00
  • \$\begingroup\$ While I believe your assertion to be correct, your modifications mean it's "no longer the Monty Hall problem"... \$\endgroup\$ – Caius Jard May 11 '17 at 16:41
5
\$\begingroup\$

I would have used an helper function in the first version so that your monty_hall function is:

def monty_hall(amount, doors=3):
    if doors < 3:
        raise ValueError(f'doors must be greater than three, not {doors}')

    return sum(player_wins_a_car(doors) for _ in range(amount))

This also applies to the second version but removes some of the speed optimizations you made there; so not sure if it’s worth keeping.

However, in the first version, I would use list-comprehensions to reduce a bit the memory needed. It would also exhibit the actions more like a real player would do. Since creating the set from range will already iterate over each elements, using the list-comp won't be much more costy:

import random

def player_wins_a_car(doors):
    player_choice = random.randrange(doors)
    car_placement = random.randrange(doors)
    shown_door = random.choice([door for door in range(doors)
                                if door not in (player_choice, car_placement)])
    final_choice = random.choice([door for door in range(doors)
                                  if door not in (player_choice, shown_door)])

    return final_choice == car_placement

For the second version, if you were to keep two functions that could lead to more explanatory stuff like:

def player_wins_a_car(doors):
    # Choose a door that hide a car. Car is never behind door 0,
    # if it were behind door 0, consider door 0 and 1 to be
    # swapped so that host always open door 0.
    car_placement = random.randrange(doors) or 1
    # Consider an initial choice of door `doors - 1` and host
    # showing door 0 unconditionaly. Always choosing a random
    # door out of these two.
    final_choice = random.randrange(1, doors-1)

    return car_placement == final_choice

I’m using or here as the only value triggering max would be 0, not sure which one performs better.

\$\endgroup\$
  • \$\begingroup\$ Nice, using a list comprehension and or both gave little performance improvements. But those little performance improvements aren't the selling point! I'm a little surprised by how little a performance cost using player_wins_a_car is as well. But speed isn't everything, nice answer! \$\endgroup\$ – Peilonrayz Apr 18 '17 at 10:56
  • \$\begingroup\$ @Peilonrayz In any case, you could make player_wins_a_car an inner function so that the name is local to monty_hall and resolve faster than a global lookup to try and reduce the performance cost even a tiny bit more. \$\endgroup\$ – Mathias Ettinger Apr 18 '17 at 11:03
  • \$\begingroup\$ IIRC global would be better, one time creation, one time move from global to local. But I'm more than happy to take the 7% performance hit, I thought it'd be more around 100%... \$\endgroup\$ – Peilonrayz Apr 18 '17 at 11:08
  • 2
    \$\begingroup\$ @Peilonrayz yes, that damn interpretter having so much overhead everywhere else that a function call in a tight loop seems like nothing ;) \$\endgroup\$ – Mathias Ettinger Apr 18 '17 at 11:10

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.