Infinite monkey theorem demonstration in Python

Question

This was the assignment:

Here’s a self check that really covers everything so far. You may have heard of the infinite monkey theorem? The theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type a given text, such as the complete works of William Shakespeare. Well, suppose we replace a monkey with a Python function. How long do you think it would take for a Python function to generate just one sentence of Shakespeare? The sentence we’ll shoot for is: “methinks it is like a weasel”

You’re not going to want to run this one in the browser, so fire up your favorite Python IDE. The way we’ll simulate this is to write a function that generates a string that is 27 characters long by choosing random letters from the 26 letters in the alphabet plus the space. We’ll write another function that will score each generated string by comparing the randomly generated string to the goal.

A third function will repeatedly call generate and score, then if 100% of the letters are correct we are done. If the letters are not correct then we will generate a whole new string.To make it easier to follow your program’s progress this third function should print out the best string generated so far and its score every 1000 tries

Soo i have created a python program which generates the string provided, i am in learning phase, can someone please suggest any improvement or any tips or corrections.

Note: I know i have not did the exact method said in that question, but i have created the expected result.
makeRandSent: This will give me random character.
compare: This will give me final result by comparing each user character with randomly generated character and it will only change those chracter which are not match.

def makeRandSent(userSent):
    counter = 0
    randSent = [""] * (len(userSent) - 1)
    randSent.clear()
    while counter < len(userSent):
        counter = counter + 1
        randSent.append(myalphlist[random.randrange(0,len(myalphlist) - 1)])
    return randSent

def compare(userSent):
    myBoolList = [False] * len(userSent)
    myRandSent = makeRandSent(userSent)
    print("random sent: ",myRandSent)
    myFinalList = [""] * len(userSent)
    while myBoolList.count(False) > 0:
        counter = 0
        myRandSent = makeRandSent(userSent)
        for char in myRandSent:
            if char == userSent[counter]:
                myBoolList[counter] = True
                myFinalList[counter] = char
            counter = counter + 1
        print(myBoolList," Final: ",myFinalList)    
    return myBoolList

E.G:
Input:
compare("pratik")
Output after several automatic attempts by program:
[True, True, True, True, True, True] Final: ['p', 'r', 'a', 't', 'i', 'k']

Answer 1

In Python you don't need to declare your variables. So the randSent = [""] * (len(userSent) - 1); randSent.clear() part is completely unnecessary.

Second, Python has an official style-guide, PEP8, which programmers are encouraged to adhere to. It recommends using lower_case_with_underscores as variable and function names.

Python also has a built-in module called string, which has all lowercase characters. With it, generating a random sentence becomes a lot easier. I renamed this function generate, to adhere more closely to the requirements. It uses random.choice, which just chooses a random element from a sequence and _ as a placeholder for the unused loop variable.

import random
import string

ALLOWED_CHARS = string.ascii_lowercase + " "


def generate(n):
    return "".join(random.choice(ALLOWED_CHARS) for _ in range(n))

The requirements also mention a score function, which you have kind of implemented in your main function. I would implement it using sum and iterating over both sentences simultaneously:

def score(user_sentence, sentence):
    return sum(user_char == char for user_char, char in zip(user_sentence, sentence))

Alternatively, you could use the Levenshtein distance as score:

$ pip install python-Levenshtein

Which you can then use like this:

import Levenshtein

def score(user_sentence, sentence):
    return len(user_sentence) - Levenshtein.distance(user_sentence, sentence)

When testing these two score functions, the Levenshtein seems to be about twice as fast:

In [8]: s1 = generate(27)
In [9]: s2 = generate(27)
In [10]: %timeit score(s1, s2)
100000 loops, best of 3: 3.47 µs per loop

In [11]: %timeit score_levenshtein(s1, s2)
1000000 loops, best of 3: 1.75 µs per loop

The actual main function can be a lot simpler, I use itertools.count to have a loop that runs infinitely long and keeps track of how many iterations it has gone through.

I think your code has a bug, in that it seems to set a position as True if you ever found a string that has the correct character in that position. The requirements are quite clear that you should generate new sentence each time and discard the old characters (even if some were correct). I also implemented the output every 1000 iterations. I call the code with a if __name__ == "__main__": guard to allow importing parts of this script from another script.

import itertools


def compare(user_sentence):
    n = len(user_sentence)
    max_score = 0
    best_fit = " " * n

    sentence = generate(n)
    for i in itertools.count():
        if sentence == user_sentence:
            # We are done
            print i
            break

        # Calculate score of current sentence and update best score if necessary
        current_score = score(user_sentence, sentence)
        if current_score > max_score:
            max_score = current_score
            best_fit = sentence

        # Output every 1000 iterations
        if i % 1000 == 0:
            print i, best_fit, max_score

        # Get a new random sentence
        sentence = generate(n)


if __name__ == "__main__":
    compare("methinks it is like a weasel")

As alluded to in the problem statement, this takes quite a long time to run. Mine has been running about 10 minutes now and has gone through about 32 million iterations and has a maximum score of 11/27. But considering that there are \$27^{27} = 443426488243037769948249630619149892803\$ permutations for a 27 character long string with 27 possible characters at each position, this could take quite a bit longer...