Monty Hall Problem
The Monty Hall Problem is a mind blowing puzzle in that the answer seems so counterintuitive it almost does not make sense. Although, it can be demonstrated to be true, as seen in this example. The motivation to solve this problem came from a company that wanted people to write a program that shows the solution is correct and to write a simple explanation. I chose to write this in Rust as I am still learning the language and wanted to get better.
Problem
Suppose you're on a game show. You have to choose one of three doors. Behind one of the doors is a car; behind the others, goats. You pick a door, lets say No. 1. The host, who knows what's behind the doors, opens one of the other doors, say No. 3, and reveals a goat beind it. He then says: "Do you want to pick door No. 2 or stick with your original choice?" Is it to your advantage to switch your choice?
The well known answer to this famous problem is that you should always switch and choose the other door. Switching improves your odds of winning from the original 1/3 to 2/3. The answer might seem like weird math, so much so that it borders on the absurd. It is nevertheless demonstrably true.
How would you show this programatically?
Explanation
The program is basically a simulation of the problem with random generator numbers. As the number of runs approaches infinity, we can see that the probabilities of winning a car in case of door switching approaches 2/3 and 1/3 otherwise. I think the code is readable and has some comments when it is not obvious what it is doing. The most difficult thing to graps may be this expressions:
!(presenter_door | chosen_door) & 0x3
What this is doing is taking advantage of the 2-bit representation of the possible doors.
If the presenter and chosen door are 1 and 2, they are represented as 01
and 10
respectively. So we OR them obtaining 11
and apply the NOT operation, getting 00
which is the missing door.
This is demonstrably true for the other two cases.