Detect all certain substrings in Python sequence

Question

The code below demonstrates Penney's Game - the probability of one sequence of heads and tails appearing before another. In particular, I wonder about the efficiency of while not all(i in sequence for i in [pattern1, pattern2]):, and more globally about coding this optimally in Python. Is this a reasonable attempt in Python, or is the a better more efficient way. The more I think I know about Python, the more I believe there's always a better way!

import random

pattern1 = 'TTT'
pattern2 = 'HTT'

pattern1Wins = 0
pattern2Wins = 0

trials = 1000

for _ in range(trials):

    sequence = ''

    while not all(i in sequence for i in [pattern1, pattern2]):
        sequence += random.choice(['H','T'])

    if sequence.endswith(pattern1):
        pattern2Wins += 1
    else:
        pattern1Wins += 1

print pattern1, 'wins =', pattern1Wins
print pattern2, 'wins =', pattern2Wins

print str((max([pattern1Wins, pattern2Wins]) / float(trials) * 100)) + '%'

@Kasra, really my question is, is this a reasonable attempt in Python, or is the a better more efficient way. The more I think I know about Python, the more I believe there's always a better way! — peedurrr
– peedurrr, Commented Apr 28, 2015 at 11:18
while not sequence[-3:] in {pattern1,pattern2} would be more efficient — Padraic Cunningham
– Padraic Cunningham, Commented Apr 28, 2015 at 11:28

Padraic Cunningham · Accepted Answer · 2015-04-28 12:01:15Z

Create your sequence with three calls to choice originally then just add the last two and a new choice looping until one of the patterns appears:

pattern1 = 'TTT'
pattern2 = 'HTT'
trials = 1000
d = {pattern1: 0, pattern2: 0}

for _ in range(trials):
    sequence = random.choice("HT") + random.choice("HT") + random.choice("HT")
    while sequence not in {pattern1, pattern2}:
        sequence = sequence[-2:] + random.choice("HT")
    d[sequence] += 1

print pattern1, 'wins =', d[pattern1]
print pattern2, 'wins =', d[pattern2]
print str((max([d[pattern1], d[pattern2]]) / float(trials) * 100)) + '%'

Some timings with random.seed:

In [19]: import random
In [20]: random.seed(0)
In [21]: %%timeit
   ....: pattern1 = 'TTT'
   ....: pattern2 = 'HTT'
   ....: trials = 1000
   ....: patterns = {'TTT': 0, 'HTT': 0}
   ....: for _ in range(trials):
   ....:     sequence = ''
   ....:     while True:
   ....:         sequence += random.choice('HT')
   ....:         for pattern in patterns:
   ....:             if sequence.endswith(pattern):
   ....:                 patterns[pattern] += 1
   ....:                 break
   ....:         else:
   ....:             continue
   ....:         break
   ....: 
100 loops, best of 3: 7.28 ms per loop

In [22]: %%timeit
   ....: pattern1 = 'TTT'
   ....: pattern2 = 'HTT'
   ....: trials = 1000
   ....: d = {pattern1: 0, pattern2: 0}
   ....: for _ in range(trials):
   ....:     sequence = random.choice("HT") + random.choice("HT") + random.choice("HT")
   ....:     while sequence not in {pattern1, pattern2}:
   ....:         sequence = sequence[-2:] + random.choice("HT")
   ....:     d[sequence] += 1
   ....: 
100 loops, best of 3: 4.95 ms per loop

In [23]: %%timeit
pattern1 = 'TTT'
pattern2 = 'HTT'
pattern1Wins = 0
pattern2Wins = 0
trials = 1000
for _ in range(trials):
    sequence = ''                              
    while True:                                       
        sequence += random.choice('HT')
        if sequence.endswith(pattern1):
            pattern2Wins += 1         
        elif sequence.endswith(pattern2):
            pattern1Wins += 1
        else:
            continue
        break
   ....: 
100 loops, best of 3: 6.65 ms per loop

jonrsharpe · Accepted Answer · 2015-04-28 11:26:57Z

Given that you only care about the last three characters being one of two substrings, I would go with something like:

sequence = ''
while True:
    sequence += random.choice('HT')
    if sequence.endswith(pattern1):
        pattern2Wins += 1
    elif sequence.endswith(pattern2):
        pattern1Wins += 1
    else:
        continue
    break

endswith is much more efficient than in, because it doesn't check through the whole string for matches (where you already know there won't be any).

Alternatively, you could factor out pattern1 and pattern2 to a dictionary {pattern: wins}:

patterns = {'TTT': 0, 'HTT': 0}

...

sequence = ''
while True:
    sequence += random.choice('HT')
    for pattern in patterns:
        if sequence.endswith(pattern):
            patterns[pattern] += 1
            break
    else:
        continue
    break

Finally, string concatenation with + isn't terribly efficient; strings are immutable, so a new string is created each time. Instead, consider putting the results into a list, and checking the last three items of it:

sequence = []
while True:
    sequence.append(random.choice('HT'))
    if sequence[-3:] == ['H', 'T', 'T']:
        ...

Collectives™ on Stack Overflow

Detect all certain substrings in Python sequence

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related