title: Hill-climbing algorithm to generate a string using Levenshtein distance as heuristic in Python?
body: <p>I have been following this <a href="http://interactivepython.org/courselib/static/pythonds/Introduction/introduction.html" rel="nofollow">ebook</a> and I am stuck at one of their Self Check questions, which goes on like this:</p>
  
  <blockquote>
    <p><strong>Self Check</strong></p>
    
    <p>Here’s a self check that really covers everything so far. You may have
    heard of the infinite monkey theorem? 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. How long do you think it would take for a Python
    function to generate just one sentence of Shakespeare? The sentence
    we’ll shoot for is: “methinks it is like a weasel”</p>
    
    <p>You’re not going to want to run this one in the browser, so fire up
    your favorite Python IDE. 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.</p>
    
    <p>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.To make it easier to follow
    your program’s progress this third function should print out the best
    string generated so far and its score every 1000 tries.</p>
    
    <p><strong>Self Check Challenge</strong></p>
    
    <p>See if you can improve upon the program in the self check by keeping
    letters that are correct and only modifying one character in the best
    string so far. This is a type of algorithm in the class of ‘hill
    climbing’ algorithms, that is we only keep the result if it is better
    than the previous one.</p>
  </blockquote>
  
  <p>I wrote some code that does the first part of this challenge using Levenshtein distance between generated and needed strings.</p>
  
  <pre><code>import random, string, nltk
  
  def string_generator(length, collection):
      """
      takes all characters in collection and generates a string of size length.
      """
      return ''.join([random.choice(collection) for _ in xrange(length)])
  
  def string_tester(output, text):
      """
      compares strings given and returns the Levenshtein distance.
      """
      return nltk.metrics.edit_distance(output, text)
  
  if __name__ == '__main__':
      collection = [x for x in (string.ascii_lowercase + ' ')]
      longest_distance = 27
      best_string = None
      ctr = 0
      while True:
          random_string = string_generator(26, collection)
          distance = string_tester(random_string, "methinks it is like a weasel")
              ctr += 1
          ctr %= 1000
              if distance &lt; longest_distance:
              best_string = random_string
              longest_distance = distance
              # end if the string generated is same as the one given
          if longest_distance == 0:
              print best_string
              print longest_distance
              break
              # use the best string to generate a better string every 1000th time
          if ctr == 0:
              print longest_distance
              print best_string
              # TODO: optimization here
  </code></pre>
  
  <p>I have no idea how can I generate a better string - using the best string until that iteration and given methods - at the TODO.</p>
  
  <p><strong>tl;dr:</strong>  How can I write a hill climbing algorithm that uses Levenshtein distance as its heuristic until it generates a certain string? Please outline the process.</p>