]>
Commit | Line | Data |
---|---|---|
0731742a XL |
1 | // Copyright 2018 Developers of the Rand project. |
2 | // Copyright 2013-2018 The Rust Project Developers. | |
b7449926 XL |
3 | // |
4 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
5 | // https://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
6 | // <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your | |
7 | // option. This file may not be copied, modified, or distributed | |
8 | // except according to those terms. | |
9 | ||
10 | //! ## Monty Hall Problem | |
11 | //! | |
12 | //! This is a simulation of the [Monty Hall Problem][]: | |
13 | //! | |
14 | //! > Suppose you're on a game show, and you're given the choice of three doors: | |
15 | //! > Behind one door is a car; behind the others, goats. You pick a door, say | |
16 | //! > No. 1, and the host, who knows what's behind the doors, opens another | |
17 | //! > door, say No. 3, which has a goat. He then says to you, "Do you want to | |
18 | //! > pick door No. 2?" Is it to your advantage to switch your choice? | |
19 | //! | |
20 | //! The rather unintuitive answer is that you will have a 2/3 chance of winning | |
21 | //! if you switch and a 1/3 chance of winning if you don't, so it's better to | |
22 | //! switch. | |
23 | //! | |
24 | //! This program will simulate the game show and with large enough simulation | |
25 | //! steps it will indeed confirm that it is better to switch. | |
26 | //! | |
27 | //! [Monty Hall Problem]: https://en.wikipedia.org/wiki/Monty_Hall_problem | |
28 | ||
416331ca | 29 | #![cfg(feature = "std")] |
b7449926 | 30 | |
b7449926 | 31 | use rand::distributions::{Distribution, Uniform}; |
416331ca | 32 | use rand::Rng; |
b7449926 XL |
33 | |
34 | struct SimulationResult { | |
35 | win: bool, | |
36 | switch: bool, | |
37 | } | |
38 | ||
39 | // Run a single simulation of the Monty Hall problem. | |
416331ca | 40 | fn simulate<R: Rng>(random_door: &Uniform<u32>, rng: &mut R) -> SimulationResult { |
b7449926 XL |
41 | let car = random_door.sample(rng); |
42 | ||
43 | // This is our initial choice | |
44 | let mut choice = random_door.sample(rng); | |
45 | ||
46 | // The game host opens a door | |
47 | let open = game_host_open(car, choice, rng); | |
48 | ||
49 | // Shall we switch? | |
50 | let switch = rng.gen(); | |
51 | if switch { | |
52 | choice = switch_door(choice, open); | |
53 | } | |
54 | ||
55 | SimulationResult { win: choice == car, switch } | |
56 | } | |
57 | ||
58 | // Returns the door the game host opens given our choice and knowledge of | |
59 | // where the car is. The game host will never open the door with the car. | |
60 | fn game_host_open<R: Rng>(car: u32, choice: u32, rng: &mut R) -> u32 { | |
0731742a XL |
61 | use rand::seq::SliceRandom; |
62 | *free_doors(&[car, choice]).choose(rng).unwrap() | |
b7449926 XL |
63 | } |
64 | ||
65 | // Returns the door we switch to, given our current choice and | |
66 | // the open door. There will only be one valid door. | |
67 | fn switch_door(choice: u32, open: u32) -> u32 { | |
68 | free_doors(&[choice, open])[0] | |
69 | } | |
70 | ||
71 | fn free_doors(blocked: &[u32]) -> Vec<u32> { | |
72 | (0..3).filter(|x| !blocked.contains(x)).collect() | |
73 | } | |
74 | ||
75 | fn main() { | |
76 | // The estimation will be more accurate with more simulations | |
77 | let num_simulations = 10000; | |
78 | ||
79 | let mut rng = rand::thread_rng(); | |
80 | let random_door = Uniform::new(0u32, 3); | |
81 | ||
82 | let (mut switch_wins, mut switch_losses) = (0, 0); | |
83 | let (mut keep_wins, mut keep_losses) = (0, 0); | |
84 | ||
85 | println!("Running {} simulations...", num_simulations); | |
86 | for _ in 0..num_simulations { | |
87 | let result = simulate(&random_door, &mut rng); | |
88 | ||
89 | match (result.win, result.switch) { | |
90 | (true, true) => switch_wins += 1, | |
91 | (true, false) => keep_wins += 1, | |
92 | (false, true) => switch_losses += 1, | |
93 | (false, false) => keep_losses += 1, | |
94 | } | |
95 | } | |
96 | ||
97 | let total_switches = switch_wins + switch_losses; | |
98 | let total_keeps = keep_wins + keep_losses; | |
99 | ||
100 | println!("Switched door {} times with {} wins and {} losses", | |
101 | total_switches, switch_wins, switch_losses); | |
102 | ||
103 | println!("Kept our choice {} times with {} wins and {} losses", | |
104 | total_keeps, keep_wins, keep_losses); | |
105 | ||
106 | // With a large number of simulations, the values should converge to | |
107 | // 0.667 and 0.333 respectively. | |
108 | println!("Estimated chance to win if we switch: {}", | |
109 | switch_wins as f32 / total_switches as f32); | |
110 | println!("Estimated chance to win if we don't: {}", | |
111 | keep_wins as f32 / total_keeps as f32); | |
112 | } |