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) &gt; 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) &gt; 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?
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 -&gt; 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.