CODEWITHSUNDEEP
python-3.xsimulation
papatri
papatri

Reputation: 11

Simulating flipping a coin using list comprehension and randomness, code works at first then hangs

Having problem with a coin flip simulation. This code should be counting the amount of flips on average it should take to flip a coin and get tails three times in a row (so a success = 3 't', 1 success satisfies the first experiment).

import random

experiments = [1, 10, 100, 1000, 10000, 100000]

for number in experiments:
    experiment = []
    success = 0
    while success < number:
        face = random.choice(['h','t'])
        experiment.append(face)
        success = ''.join(experiment).count('ttt')
    print(f'Experiments: {number}')
    print(f'Average flips: {len(experiment)/success}\n')

Output looks like this:

[evaluate troubleshooting.py]
Experiments: 1
Average flips: 27.0

Experiments: 10
Average flips: 6.4

Experiments: 100
Average flips: 14.39

Experiments: 1000

Upvotes: 0

Views: 142

Answers (1)

Nick Vitha
Nick Vitha

Reputation: 466

Well, I think the main problem is that success = ''.join(experiment).count('ttt') line will cause your program to search the entire list for each and every run through your while loop, which will be O(n^2) time complexity (AKA, BAD. Really really bad the more experiments you run).

I whipped up a (rudimentary) program that will do that part in linear (O(n)) time:

import random

experiment_size = [1,10,100,1000,10000,100000]

for number in experiment_size:
    last = False # track whether the last 3 flips were tails. False = don't care, 
                 # True = tails
    last_2 = False
    last_3 = False

    success = 0
    runs = 0
    while success < number:
        runs += 1
        last_3 = last_2 #bump the 3rd from last flip
        last_2 = last
        last = bool(random.getrandbits(1)) #get True or False, randomly
        if(last & last_2 & last_3): #if all are tails
            success += 1
            last, last_2, last_3 = False, False, False #reset so that you have to get 3
                                                       #in a row again
    print("Runs: " + str(runs) + "\nSuccesses: " + str(success) +"\nAverage: " + str(runs/success) + "\n")

Because we're not traversing an entire list for every repetition, it's a lot faster.

Upvotes: 1

Related Questions