Attempt at Infinite Monkey theorem using Python

Question

So , I've been trying to implement the infinite monkey theorem using python.The problem statement is something like this.

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. The sentence is: “methinks it is like a weasel”

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.

import random,string

shakespeare = 'methinks it is a weasel'

def generate():
 char = string.ascii_lowercase+' '
 randchars = ''.join(random.choice(char) for _ in range(27))
 return randchars

def score():
 scorenum = 0
 randchars = generate()
 print randchars
 shake = shakespeare.split()
 randlist = randchars.split()
 for i,j in zip(shake,randlist):
  if i==j:
   scorenum = scorenum+1
  scorecount = (scorenum/27)*100
 return scorecount

def main():
 run = 0
 while not(score()==100):
  score()
  run = run + 1
  print run
  if run ==1000:
   print score()

if __name__ == '__main__':
 main()

So, the program is running fine, but I can see the randomized string appearing twice when I print it, and I've reached 3 million mark without reaching any success in terms of matching. I believe I've written the main function wrongly, but I'm not sure of the problem yet.

Thanks in advance if you can help me fix this. :)

Answer 1

my version short and simple

from random import choice

alphabets = [chr(i) for i in range(97, 123)]
alphabets.append(" ")
string = "methinks it is like a weasel"


def random_string():
    result = ""
    i = 0
    while i < len(string):
        result += choice(alphabets)
        i += 1
    return result


def score_n_match():
    score = 0
    i = 0
    match = ""
    while i < len(string):
        temp = random_string()
        if string[i] == temp[i]:
            print(f"{i + 1} match found.")
            match += temp[i]
            i += 1
        score += 1
    print(f"generated string: {match} after {score} loops")


score_n_match()

Answer 2

My solution:

import string
import random
import sys

#blind method
def generate(length):
    characters = string.ascii_lowercase+" "
    return "".join([random.choice(characters) for i in range(length)])

def score(test_string,target_string):
    test_list = zip([i for i in test_string],[i for i in target_string])
    return (sum([1 for test_letter, target_letter in test_list if test_letter == target_letter])/len(target_string))*100

def generate_and_score(phrase):
    counter = 0
    best_score = 0
    best_attempt = None
    while best_score < 100: 
        this_attempt = generate(len(phrase))
        this_score = score(this_attempt,phrase)
        counter += 1
        if this_score > best_score:
            best_score = this_score
            best_attempt = this_attempt
        if counter % 1000 == 0:
            print("Tries: {}; Best Guess: {} with a score of {}".format(counter, best_attempt, best_score))
    print("Success in {} guesses!".format(counter))

#hill-climbing method
def improved_generate(best_attempt,phrase):
    characters = string.ascii_lowercase+" "
    return "".join([random.choice(characters) if a != p else a for a,p in zip([i for i in best_attempt],[i for i in phrase])])

def generate_and_score_improved(phrase):
    counter = 0
    best_score = 0
    best_attempt = None
    while best_score < 100:
        this_attempt = improved_generate(best_attempt,phrase) if best_attempt else generate(len(phrase))
        this_score = score(this_attempt,phrase)
        counter += 1
        if this_score > best_score:
            best_score = this_score
            best_attempt = this_attempt
        if counter % 1000 == 0:
            print("Tries: {}; Best Guess: {} with a score of {}".format(counter, best_attempt, best_score))
    print("Success in {} guesses!".format(counter))

Answer 3

More Optimized version :), takes less than 100 iteration for complete match. I think this would help.

import string
import random

def randomGen(goalList):
    characters = string.ascii_lowercase+" "
    randString =""
    for i in range(len(goalList)):
        randString = randString+characters[random.randrange(len(characters))]
    randList = [randString[i] for i in range(len(randString))]
    return randList

def scoreRand(goalList,randList):
    numScore = 0
    for i in range(len(goalList)):
        if goalList[i] == randList[i]:
            numScore = numScore+1
    return numScore / len(goalList)

def common_elements(clist,list1, list2):
    for i in range(len(list1)):
        if list1[i] == list2[i]:
            clist[i] = list1[i]
    return clist

def main():
    goal = "methinks it is like a weasel"
    goalList = [goal[i] for i in range(len(goal))]
    clist = [' ' for i in range(len(goal))]
    randList = randomGen(goalList)
    clist = common_elements(clist,goalList, randList)
    score = scoreRand(goalList,clist)
    totalIteration = 0
    while(score < 1):
        newrandList = randomGen(goalList)
        newclist = common_elements(clist,goalList, randList)
        newscore = scoreRand(goalList,clist)
        score = newscore
        randList = newrandList
        clist = newclist
        totalIteration = totalIteration+1
        print(score," : ",''.join(clist))
    print("Total iterations: ",totalIteration)

main()

Answer 4

The following simulates multiple monkeys using (soft) Python threading.

The monkey's "typewriter" only contains the letters that exist in the target Shakespeare text (in the example t, o, b, e, r, space) so it is actually solving a much smaller problem than a monkey typing randomly on a full typewriter. Even so, the monkeys struggle to type more than 3 short words in a row.

import threading
import time
from random import choice
shakespeare = 'to be or'
max_length = max(50, len(shakespeare))
alphabet = list(set(shakespeare))
no_of_monkeys = 4


class Monkey(threading.Thread):
    def __init__(self, monkey_id):
        threading.Thread.__init__(self)
        self.writings = ''
        self.writings_length = 0
        self.monkey_id = monkey_id

    def run(self):
        while not shakespeare in self.writings:
            len_writings = len(self.writings)
            if len(self.writings) > max_length:
                self.writings = self.writings[:-max_length]
            self.writings += choice(alphabet)
            self.writings_length += 1


def ellipsis_quote(s, surround_size=20):
    shakespeare_at = s.index(shakespeare)
    start = max(0, shakespeare_at - surround_size)
    finish = min(shakespeare_at + surround_size, len(s))
    return '...' + s[start:finish] + '...'


monkeys = [Monkey(monkey_id) for monkey_id, monkey in enumerate(range(no_of_monkeys))]
[monkey.start() for monkey in monkeys]
monkey_literature = False
while not monkey_literature:
    print "Scanning..."
    for monkey_id, monkey in enumerate(monkeys):
        if shakespeare in monkey.writings:
            print ''
            print "Monkey {monkey_id} wrote Shakespeare!".format(monkey_id=monkey_id)
            pronoun = choice(['he', 'she'])
            print "Here's what {pronoun} wrote:".format(pronoun=pronoun)
            print ellipsis_quote(monkey.writings)
            print 'after typing {length} letters'.format(length=monkey.writings_length)
            monkey_literature = True
    time.sleep(2)

Example result:

/usr/bin/python2.7 /home/vagrant/code/monkeys/monkeys.py
Scanning...

Monkey 0 wrote Shakespeare!
Here's what she wrote:
... bbrtbr rto be or...
after typing 1031167 letters

Answer 5

Optimized version, stores history of what matched. Takes anywhere between 480 to 820 iterations for a 100% match.

import random

def generate(length):

    monkey_types = ""

    for x in range(length):
        monkey_types = monkey_types + random.choice('abcdefghijklmnopqrstuvwxyz ')

    return monkey_types

def score_me(monkey_pwd, pwd):

    score = 0

    if len(pwd) == 1:
        return (monkey_pwd[:1] == pwd[:1])

    for x in range(1,len(pwd)):
        if monkey_pwd[:x] == pwd[:x]:
            score = score + 1
    return (score)

def main():

    pwd = 'methinks it is like a weasel'
    score = best_score = count = 0
    best_guess = ""

    while(best_score < len(pwd)):
        iter = generate(len(pwd)-best_score)
        score = score_me(iter, pwd[best_score:])
        if score > 0:
            best_score += score
            best_guess += iter[:score]

        count = count+1
        print(best_guess)

    print("Total runs: ", count)

if __name__ == "__main__":

    main()

Answer 6

Each time you call score(), you will generate a new statement, which means within this loop...

while not(score()==100):
  score()
  run = run + 1
  print run
  if run ==1000:
      print score()

... you are generating the statement at least twice, and sometimes three times.

You could replace it with something like:

while not(score()==100):
  run = run + 1
  print run

The number of potential combinations is vast - the chances of you being able to run this for long enough to see anything close to a readable sentence, never mind one that matches the exact sentence you're looking for, are really remote!

Here's an example that generates matches (I've seen several 33% matches on a 3 character quote):

import random,string

# shakespeare = 'methinks it is a weasel'
shakespeare = 'abc'
quoteLen = len(shakespeare)

def generate():
 char = string.ascii_lowercase+' '
 randchars = ''.join(random.choice(char) for _ in range(quoteLen))
 return randchars

def score():
 scorenum = 0
 randchars = generate()
 shake = shakespeare.split()
 randlist = randchars.split()
 for i,j in zip(shake,randlist):
  if i==j:
   scorenum = scorenum+1
 scorecount = (scorenum / quoteLen) * 100
 return scorecount

def main():
 run = 0
 curScore = 0
 while not(curScore==100):
  curScore = score()
  if (curScore != 0):      
    print(run, " = ", curScore)
  run = run + 1;

if __name__ == '__main__':
 main()

Example output:

2246  =  33.33333333333333
56731  =  33.33333333333333 
83249  = 33.33333333333333 
88370  =  33.33333333333333 
92611  =  33.33333333333333 
97535  =  33.33333333333333 

Answer 7

Even if it's equally distributed, the chances of scoring 100 are 1/27^27 (number of letters in the alpha-bait + space). 3 millions retires is a very small number...

If you want to check that your code works run it on a smaller sample, say: 2-4 characters.