import random
import math
from string import ascii_lowercase

children = 12 #must be an even number
word = "heijeasfsa" #Only small letters
chanse_of_mutation = 12 #The closer to 12, the better chanche of faster results




def ArrayOfString(string):
	array = []
	for i in string:
		array.append(i)
	return array;

def sort(doubleArray):
	buckets = []
	for i in range(0,len(doubleArray[0][0]) + 1):
		buckets.append([])
	for x in range(0,len(doubleArray)):
		buckets[doubleArray[x][1]].append(doubleArray[x])
	newArray = []
	for x in reversed(buckets):
		for c in x:
			if(c != ""):
				newArray.append(c)
	return newArray

def fitness(string,d):
	fit = 0;
	for i in range (0, len(string)):
		if (d[i] == string[i]):
			fit += 1;
	return fit;


def kill(doubleArray):
	b = math.floor(children/2)
	return doubleArray[:b]

string = ArrayOfString (word);
alfabet = []
random_words = []

def splitt(doubleArray):
	newArray = []
	for parent in doubleArray:
		for child in range(0,2):
			word = ""
			for letter in parent[0]:
				tall = random.randint(0,chanse_of_mutation)
				if tall == 0:
					word += alfabet[random.randint(0, len(alfabet) - 1)]
				else:
					word += letter
			newArray.append([word,0])
	return newArray




for c in ascii_lowercase:
	alfabet.append(c)

for i in range (0,children):
	key = ""
	for c in range(0, len(string)):
		key += alfabet[random.randint(0, len(alfabet) - 1)]
	random_words.append([key,0])

final_form = False
generation = 1;
most_fit = 0;
while not final_form:
	for c in range(0, len(random_words)):
		random_words[c][1] = fitness(string, ArrayOfString(random_words[c][0]))
	print(" ##########################", "\n", "Generation ",generation,"\n","##########################", "\n")
	random_words = sort(random_words)
	print(random_words, "\n")

	if(random_words[0][1] == len(string)):
		final_form = True
	else:
		print(" ##########################", "\n", "Fittest of Generation ",generation,"\n","##########################", "\n")
		random_words = kill(random_words)
		print(random_words, "\n")
		random_words = splitt(random_words)
	generation = generation +1