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?