Evolve some text

We start with a target string. We then generate ten random candidates each of the same length as the target, and assign each one a score based on how many correct characters it has. The highest-scoring candidate then becomes the father of the next generation: we spawn ten clones of the winner, with the correct members of each retained and the other members randomised. Then we score each of these, and go round and round again until we get to the target string.

Happy Birthday Darwin. And Python rocks.

#!/usr/bin/env python

import sys
import string
import random
import copy

# the string we will work towards
try:
    target = sys.argv[1]
except:
    target = "from so simple a beginning endless forms most beautiful and most wonderful have been, and are being, evolved."
winningscore = len(target)

# get ascii character set
chars = []
for i in range(32, 127):
    chars.append(chr(i))
chars.append("\n")

# how many candidates will we spawn in each generation
selectees = 10

# a list to hold our candidates
candidates = []

# class representing a character in our candidate
class member():
    def __init__(self, char = ""):
        self.character = char
        # fixity will be set if this character is correct
        self.fixity = False

    # set to a new, random character
    def randomize(self):
        # unless this one has been fixed
        if not self.fixity:
            a = chars[int(random.random() * len(chars))]
            self.character = a

    # string representation    
    def __str__(self):
        return self.character

# class representing a generated candidate (it's basically a list)
class candidate(list):
    # we start with a score of 0
    grade = 0
    size = 0

    # create a new list
    def __init__(self, length):
        self.size = length
        # and populate and score it
        self.populate()
        self.score()

    # fill the array with randomness to start
    def populate(self):
        for i in range(0, self.size):
            m = member()
            m.randomize()
            self.append(m)

    # represent as a string (this is an ugly hack, I think)
    def __str__(self):
        a = []
        for i in self:
            a.append(i.__str__())
        return "".join(a)

    # count how many correct members we have
    def score(self):
        self.grade = 0
        for i in range(0, len(self)):
            # if its a match with the target string
            if self[i].character == target[i]:
                # then we fix this member in place and score 1 point
                self[i].fixity = True
                self.grade += 1

    # randomize ourself    
    def shuffle(self):
        for a in self:
            # members with fixity set will not be randomized
            a.randomize()
        # and work out our new score
        self.score()

# find the candidate with the best score
def getwinner():
    bestgrade = 0
    # assume the first one is the winner for now
    winner = candidates[0]

    # now for each candidate
    for c in candidates:
        # if we're better than the best so far
        if c.grade > bestgrade:
            # hold on to the leader
            winner = c
            # and raise the bar
            bestgrade = c.grade
    # this method will pick the first candidate from the set of possible winners

    # if all of our members are correct
    if bestgrade == winningscore:
        # we've solved it!
        global unsolved
        unsolved = 0
    # send back the winner
    return winner

# real live code starts here

# generate an initial set of random candidates
for i in range(0, selectees):
    candidates.append(candidate(len(target)))

# assume we've not solved it yet
unsolved = True

# how may turns do we take?
iterations = 0

# while we have not the answer
while (unsolved):
    iterations += 1
    
    # find our winner
    winner = getwinner()
    # and show it
    print winner

    # set all of our candidates to the winner
    for i in range(0, len(candidates)):
        candidates[i] = copy.copy(winner)
        # then shuffle each one
        candidates[i].shuffle()

# and when we're finished, print some stats
print "%d-character string, %d iterations" % (len(target), iterations)