4
\$\begingroup\$

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?

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Sep 30, 2016 at 6:43

1 Answer 1

Reset to default
4
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.