Hello, Lifeforms!

UmS6D0aW62+q!'%S2 (perfection:   0%) Evolving        2nd generation.
aUKahChc.5,e&8:?1 (perfection:   0%) Evolving        3rd generation.
bYJo$F?O2;aTV'q'? (perfection:   0%) Evolving        4th generation.
P]N0+dC=p-GVh<p1E (perfection:   0%) Evolving        5th generation.
P]N0+dC=p-GPQ>+6b (perfection:   0%) Evolving        6th generation.
Q?T1LHOp=LSj*VUr0 (perfection:   0%) Evolving        7th generation.
ob3<2Ih=p-CO^f#`5 (perfection:   0%) Evolving        8th generation.
dK8:SCn^omSj*VO ` (perfection:   0%) Evolving        9th generation.
X@Z'H<f.)T?f&(i6. (perfection:   6%) Evolving       10th generation.
g&H0+)DG^J%GV(\(l (perfection:   0%) Evolving       11th generation.
dK9K3Vf.)T?f&`Kfq (perfection:   6%) Evolving       12th generation.
8@Zm`,jZ-*jf38":; (perfection:  12%) Evolving       13th generation.
g&l:7O^q0jGA2r2,& (perfection:  12%) Evolving       14th generation.
j^4'N.:L0fV.9_Psi (perfection:  18%) Evolving       15th generation.
co2sL:BLffGA2((Y! (perfection:  18%) Evolving       16th generation.
MHX<oUL$EP`<o(\si (perfection:  18%) Evolving       17th generation.
g9l#bkrL$+e &>Tsr (perfection:  24%) Evolving       18th generation.
Pibho,MYilkEo(.sj (perfection:  29%) Evolving       19th generation.
cel/opLRP2aEerTs! (perfection:  35%) Evolving       20th generation.
HR(so ELrfef/\-s& (perfection:  41%) Evolving       21st generation.
ce>l9dr3iPef?r2sc (perfection:  41%) Evolving       22nd generation.
HRl#) EaibkforTs! (perfection:  47%) Evolving       23rd generation.
Ho9ho, LJ-?fY>ms! (perfection:  53%) Evolving       24th generation.
He^j`,YLrfeHFlms! (perfection:  53%) Evolving       25th generation.
HRli*/ Lrfe &rms! (perfection:  59%) Evolving       26th generation.
HelBNd Lrfe &rms! (perfection:  65%) Evolving       27th generation.
HeGlo,jLifGf&rm]! (perfection:  71%) Evolving       28th generation.
ce4lod >iWeforms! (perfection:  71%) Evolving       29th generation.
H&lho, Lif@forms! (perfection:  82%) Evolving       30th generation.
HRllo, >ifeforms! (perfection:  88%) Evolving       31st generation.
Hello,:Lif@forms! (perfection:  88%) Evolving       32nd generation.
He9lo, Lifeforms! (perfection:  94%) Evolving       33rd generation.
Hello, LifeformN! (perfection:  94%) Evolving       34th generation.
HelloV Lifeforms! (perfection:  94%) Evolving       35th generation.
Hello, LifefKrms! (perfection:  94%) Evolving       36th generation.
Evolved to 100% perfection. Concluding.
 
35,000 individuals sacrificed their lives
so that their species could eventually say:
 
        Hello, Lifeforms!

#!/usr/bin/env python2.6
#
# Copyright (c) 2009 Lee Braiden <lee.b@irukado.org>
# Released under the GNU General Public License, version 3.
# http://www.gnu.org/licenses/gpl.html for details.
#
 
import sys
from random import randint, sample
 
class Mirror:
	"""Stores certain details that individuals must analyse
	and evolve themselves against.  Named after the
	psychology concept of being a mirror for an individual's
	own thoughts."""
	def __init__(self, destiny):
		"""Takes a string, 'destiny', which creatures must
		evolve to say."""
		self.UPPER = max([ ord(x) for x in destiny ])
		self.LOWER = min([ ord(x) for x in destiny ])
		self.destiny = destiny
 
	def chromosome_len(self):
		"""Returns the number of chromosomes in an individual's
		genes.  In other words, this is the length of the message
		characters should evolve to say."""
		return len(self.destiny)
 
	def range(self):
		"""A quick (readability-)helper function, which allows looping
		over each gene."""
		return range(0, self.chromosome_len())
 
class Individual:
	"""Represents an individual beastie which will be created, can
	breed, can mutate, can attempt to solve the problem at hand,
	and can be tested for fitness, among other things."""
	def __init__(self, chromosome_len, mutation_rarity):
		self._genes =  " " * chromosome_len
		self.fitness = 0
		self.mutation_rarity = mutation_rarity
 
	def _gene_val(self, mirror):
		"""Create a random gene value"""
		return chr(randint(mirror.LOWER, mirror.UPPER))
 
	def _randomise_genes(self, mirror):
		"""Initialise all of the individual's genes randomly.  Used
		during creation, rather than breeding"""
		self._genes = "".join([ self._gene_val(mirror) for idx in mirror.range() ])
 
	def _choose_gene(self):
		"""Choose an individual gene to target."""
		return randint(0, len(self._genes)-1)
 
	def _freaky(self):
		"""Roll a dice, and see if this individual is (un)lucky enough
		to gain a mutation."""
		return randint(0, self.mutation_rarity) == 0
 
	@classmethod
	def conjure(cls, mirror, mutation_rarity):
		"""Create an individual from scratch."""
		i = cls(len(mirror.destiny), mutation_rarity)
		i._randomise_genes(mirror)
		return i
 
	@classmethod
	def breed(cls, mirror, mom, dad):
		"""Breed an individual from two parents."""
		mutation_rarity = float(mom.mutation_rarity + dad.mutation_rarity) / 2.0
		kid = cls(len(mirror.destiny), mutation_rarity)
		x = kid._choose_gene()
		kid._genes = "".join(mom._genes[:x]) + "".join(dad._genes[x:])
		if kid._freaky():
			kid._mutate(mirror)
		return kid
 
	def _mutate(self, mirror):
		"""Mutate a random gene"""
		orig_genes = self._genes
		idx = self._choose_gene()
		els = [ x for x in self._genes ]
		els[idx] = self._gene_val(mirror)
		self._genes = "".join(els)
 
	def self_evaluate(self, mirror):
		"""Evaluate 'fitness', or the ability to solve the given
		problem.  In other words, measure how close the individual
		is to the correct message text, and assign a score
		accordingly."""
		fitness = max_fitness = float(len(self._genes))
 
		for idx in range(0, len(self._genes)):
			if self._genes[idx] == mirror.destiny[idx]:
				continue
			else:
				fitness -= 1
 
		self.fitness = 100.0 * (fitness / max_fitness)
 
	def __cmp__(self, competitor):
		"""Comparison function, used for sorting populations to find
		the fittest."""
		if self.fitness > competitor.fitness:
			return 1
		elif self.fitness == competitor.fitness:
			return 0
		else:
			return -1
 
class World:
	"""Represents a world populated by Individuals, which breed
	together, subject to natural selection, to reach an evolutionary
	goal."""
	def __init__(self, mirror, population_size=1000, mutation_rarity=1000, fitness_required=100.0):
		"""Initialise a population of population_size members, mutating
		one in every mutation_rarity breeds.  Evolution will stop when
		fitness reaches fitness_required percent."""
		self._mirror = mirror
		self._population = [ Individual.conjure(mirror, mutation_rarity) for i in range(0, population_size) ]
		self.sacrifice_count = 0
		self._fitness_required = 100.0
		self._mutation_rarity = mutation_rarity
 
	def _natural_select(self, exclusion_list=[]):
		"""Select two individuals from a population, choosing the most
		'fit' for breeding."""
		a,b = sample(self._population, 2)
		if (a > b):
			return a
		else:
			return b
 
	def _breeding_pairs(self):
		"""Select enough breeding pairs from a population to create a
		new population of equal size, assuming one child per couple."""
		bp = []
		pop_size = len(self._population)
 
		for i in range(0, pop_size):
			mom = self._natural_select()
			dad = self._natural_select([mom])
			bp.append((mom,dad))
 
		return bp
 
	def _breed_new_generation(self, mirror):
		"""Create a new generation, breeding it from the older
		generation using natural selection."""
		new_gen = []
		bp = self._breeding_pairs()
		for mom,dad in bp:
			kid = Individual.breed(mirror, mom,dad)
			new_gen.append(kid)
 
		self.sacrifice_count += len(self._population)
		self._population = new_gen
 
	def _analyse_population(self):
		"""Evaluate the genetic fitness of the entire population."""
		for i in self._population:
			i.self_evaluate(self._mirror)
 
		self._population.sort()
		most_civilised = self._population[0]
 
		return most_civilised
 
	def evolve_civilisation(self):
		"""Evolve this civilisation until the required fitness_level
		is reached."""
		generation_count = 1
		last_str_len = 0
		while(generation_count):
			most_civilised = self._analyse_population()
			gen_ord = ordinal(generation_count + 1)
 
			if most_civilised.fitness >= self._fitness_required:
				print "Evolved to %3.0f%% perfection. Concluding." % most_civilised.fitness
				return most_civilised
			else:
				print "%s (perfection: %3.0f%%) Evolving % 10s generation." % (most_civilised._genes, most_civilised.fitness, gen_ord)
				self._breed_new_generation(self._mirror)
 
			generation_count += 1
 
# a couple of helper functions #############
 
def ordinal(n):
	"""borrowed from John Machin's python-list post.  Appends an
	ordinal suffix to a number.  For example, 1 becomes 1st,
	2 becomes 2nd, etc."""
	if 10 <= n % 100 < 20:
		return str(n) + 'th'
	else:
		return  str(n) + {1 : 'st', 2 : 'nd', 3 : 'rd'}.get(n % 10, "th")
 
 
def PrintLargeNumber(n,width=2,delim=',',decimal='.'):
	"""Converts a float to a string with appropriately placed commas.
 
	Floats will be shown with 'width' digits right of the decimal.
	'delim' specifies the thousands delimiter.
	'decimal' specifies the decimal character.
 
	Copyright 2007 Regents of the University of California
	Written by David Isaacson at the University of California,
	Davis BSD License"""
	if width >= 0: s = "%.*f" %(width,n)
	else: s = str(n)
	dec = s.find(decimal)
	if dec == -1: dec = len(s)
	threes = int((dec-1)/3) # we don't need a comma at the start
	for i in xrange(threes):
		loc = dec-3*(i+1)
		s = s[:loc] + delim + s[loc:]
	return s
 
############################################
 
def evolve_from_nothingness(msg):
	"""Evolve an individual capable of saying the given msg."""
	world = World(Mirror(msg))
	greeter = world.evolve_civilisation()
 
	large_num_str = PrintLargeNumber(world.sacrifice_count, width=0)
 
	print "\n%s individuals sacrificed their lives\nso that their species could eventually say:\n\n\t%s\n\n" % (large_num_str, greeter._genes)
 
 
if __name__ == "__main__":
	evolve_from_nothingness("Hello, Lifeforms!")
 
	sys.stdout.write("Press return: ")
	sys.stdout.flush()
	sys.stdin.readline()