target_word = "hello world"
target_size = len(target_word)
alphabet = "abcdefghijklmnopqrstuvwxyz "
def make_guess(alphabet,size):
return "".join(random.choice(alphabet) for _ in range(size))
guess = make_guess(alphabet,target_size)
for i in itertools.count(0):
if guess == target_word:
break;
if not i % 1000:
print "Best So Far:",guess
#climb hill and replace our guess if our next guess is better
guess = min(guess,make_guess(alphabet,target_size),key=lambda _guess:levenstein(_guess,target_word))
print "Final Guess:",guess
this is called hill climbing because the potential solution only gets replaced if the next potential solution is better. this can lead to problems in other types of problem statements, where you will find local maxima or minima, that performs relatively well, but you will miss the global maxima or minima