# Infinite Monkey Theorem Python Comparison

I wrote code to demonstrate the Infinite Monkey Theorem which states that if a monkey types at a keyboard for an infinite amount of time it will almost surely type a given text such as William Shakespeare. Here I've replaced the monkey with Python code. I have a sentence and let Python choose from the 26 letters of the alphabet and a space and have it randomly try to generate the chosen sentence.

import string
import random

def genString():
letters = list(string.ascii_lowercase + " ")
testList = [random.choice(letters) for letter in letters]
testString = ''.join(testList)
return testString

def score(n):
score = 0
test = "methinksit is like a weasel"
if test == n:
score = 100
else:
for letter in range(len(test)):
if test[letter] == n[letter]:
score = 1/27 + score
else:
score = 0/27 + score
score = score * 100
return score

def test():
count = 0
localScore = 0
n = genString()
guessString = ""
while(localScore != 100):
if score(n) > localScore:
localScore = score(n)
guessString = n
if count%1000 == 0:
print(localScore)
print(guessString)
print(count)
n = genString()
count = count + 1


However, for the test function I had a previous version which was:

def test2():
count = 0
localScore = 0
n = genString()
guessString = ""
testList = [score(n)]
while(100 not in testList):
if max(testList) > localScore:
localScore = max(testList)
guessString = n
if count%1000 == 0:
print(localScore)
print(guessString)
print(count)
n = genString()
testList.append(score(n))
count = count + 1


However, after testing it out I realized it was super slow. I'm guessing that the problem is that test2 has a runtime of O(n2) because of the loop and the max function and my previous test has a runtime of O(n). Is this true? Or is there another reason why it's super slow?

• max is an issue, so is in both of which are O(n). Also, the append is only amortized O(1) not O(1) in general. – Dair Sep 30 '16 at 6:43

# Python naming conventions

PEP 8 says that functions and variables should use snake_case so getString should be get_string.

# Naming issues

localScore is the best score that you have for all the generations, name it best_score instead. Similarly: guessString -> best_string. I think count is ok. I would have used gen or generation but then again it's not really a genetic algorithm so there isn't really evolution so one could argue count is better than gen...

# gen_string

I would say that it is pretty lucky that letter and "methinksit is like a weasel" have the same length. Give gen_string a length parameter. You don't need to convert letters to a list, and you don't need so many temporary variables. (I also prefer keyboard to letters since " " isn't a letter). Ultimately I came up with:

def genString(length):
keyboard = string.ascii_lowercase + " "
return ''.join((random.choice(keyboard) for _ in range(length)))


# test

Keep your test information in test and don't let it leak out.

test = "methinksit is like a weasel"


Should be somewhere in your test function, not score. Pass a reference string to score.

I would advise printing out more information than just numbers, something like this, so you can tell what is going on:

        print("Iteration: " + str(count))
print("Best score: " + str(best_score))
print("Best strint: " + best_string)


# score

This:

        else:
score = 0/27 + score


Is unneeded. Just get rid of it. I believe also:

if test == n:
score = 100


Is unneeded. (Although, there might be some weird floating point thing I'm not taking into consideration. Regardless, you can adjust for this.)

Don't have:

1/27


What should be in place of 27?

n is often assumed to be an integer, yet you use it as a string.

# Organization

test doesn't really feel like a test, it feels like the main point of your application. Maybe just change it to main() and do something like:

if __name__ == "__main__":
main()


If you think it is a test maybe move it into a testing file like test.py.