# -*- coding: utf-8 -*-
##################################################################
##################################################################
# QUEENS EXAMPLE
# 	- Program Type: Demonstration of Evolutionary alogorithms
#	- Authour: Matthew Rollings
#	- Date: 08/05/09
##################################################################
##################################################################


# Import randint from the random module
from random import randint

# Creates a array I just use for convenience
board=[1,2,3,4,5,6,7,8]

##################################################################
# FUNCTIONS - I usually declare functions at the start as its a good policy, but you can define (def) them
#		anywhere you want aslong as you don't call them before you've defined them

# Function to check amount of attacking queens
def check(array):
	
	# Collisions represent number of attacking queens, starts at zero obv.
	collisions=0
	
	# Checks for duplicate numbers, wont ever happen but its always good to check.
	# range returns numbers from the first number to the second number - 1
	# in this case 1,2,3,4,5,6,7,8   but not 9!!!
	for i in range(1,9):
		# If i is not in the array then we have a problem
		if i not in array:
			print "DUPLICATE NUMBER ERROR - KILLING STUPID GENE"
			# Return finishes the function sending a result back.
			return 0

	# Total Collisions
	# For each queen in the array
	for i in range(0, 8):
		col=0
		# For every other queen in the array
		for j in range(0, 8):
			# avoids checking self vs self
			if i!=j:
				# if queen i is on a diagonal from queen j, then the
				# difference in magnitude x-cord will equal the difference in 
				# the magnitude of the y-coord
				if abs(board[i]-board[j])==abs(array[j]-array[i]):
					# Sets a variable to tell the next part that a collision was detected
					col=1
		# If a collision was detected add one to collisions
		if col==1:
			collisions+=1
	# Return 8-colllisions, so that 0 is bad (8 attacking queens) and 8 is good (no attacking queens)
	return 8-collisions


# The reproduce function, takes two arguements, the two parents
def reproduce(array1, array2):
	
	# FIRST BABY (mother first then father)
	# Takes first half of mothers gene
	baby=array1[0:4]
	# Can't just add two halves as I will get duplicate numbers
	for i in array2:
		# add fathers genes going in order of numbers left
		if i not in baby:
			baby.append(i)
	# Add a little variation by giving a percentage chance of mutation
	if randint(0,100)>20:
		baby=mutate(baby)
	# Add the baby to the population and add its corresponding fitness
	population.append(baby)
	fitness.append(check(baby))
	
	# SECOND BABY (arrays just swapped around, Father first then mother)
	baby=array2[0:4]
	for i in array1:
		if i not in baby:
			baby.append(i)
	if randint(0,100)>20:
		baby=mutate(baby)
	population.append(baby)
	fitness.append(check(baby))	
	

# Mutate the array given to the function
def mutate(array1):
	#Chooses two random places (WARNING CAN BE SAME POSITION)
	a=randint(0,7)
	b=randint(0,7)
	# Swaps the two over (temporary var must be used (c))
	c=array1[a]
	array1[a]=array1[b]
	array1[b]=c
	return array1


# Prints the population and corresponding fitness to the screen
# Only used for debugging
def printpop():
	# Prints the group
	for i in range(0, len(population)):
		print population[i],fitness[i]


##################################################################
# VARIABLES -  Its just convenient to place editable variables together if you want to change something
#		they of course can go anywhere you want.

# The size of the population (how many genes, more = faster convergance but more cpu + memory, fewer = opp.)
popsize=40
# The starting variation of the group because I havn't created a better method
# for starting off. I just add arrays of 1,2,3,4,5,6,7,8 to the population and 
# give them the number of mutations between the following two values to make 
# psudo random starting group
variation=[4,14]  
# How many of the genes to kill each time in percentage, each dead gene will be replaced by a new child :)
die=0.40 
# Kill limit is calculated from the above percentage
kill_limit=die*popsize

##################################################################
# MAIN PROGRAM

# Makes the population and corresponding fitness arrays
population=[]
fitness=[]
for i in range(0,popsize):
	population.append([1,2,3,4,5,6,7,8])
	a=0
	while a<randint(variation[0],variation[1]):
		a+=1
		population[i]=mutate(population[i])
	fitness.append(check(population[i]))



# defines two more vars to be used in the big loop
maxi=0
generations=1

# Big loop, each cycle represents the next generation
# For a useful method of understanding uncomment the lines between the ^^^^'s and vvvv's
while maxi!=8:
	
	# vvvvvv
	#print "Starting gene pool:"
	#printpop()
	# ^^^^^^
	
	# Picks top # in group to be parents, kills rest
	killed=0
	# starting at the lowest fitness (0 and increasing untill kill limit reached)
	x=0
	while killed<kill_limit:
		for i in range(0,popsize):
			# Try is here to catch any errors
			try:
				if fitness[i]==x:
					# This bit removes the crappy gene from the population and from fitness
					population.pop(i)
					fitness.pop(i)
					# increases the kill counter
					killed+=1
				# stops if kill counter is reached
				if killed==kill_limit:
					# break leaves the loop that we are inside (for loop)
					break
			# except excutes if try fails (an error occurs, but this prevents program crashing)
			# Very useful as a fail safe for a sketchy bit of code (and makes good code robust)
			except:
				break
		# increments fitness
		x+=1
	
	# vvvvvv
	#print "Survial of fittest", killed, "killed off (Removed from gene pool)"
	#printpop()
	# ^^^^^^
	
	babies=0 # how mnay babies have been created
	cpop=len(population)-1 #current population (lower than normal due to deaths, -1 as arrays are addressed from 0)
	while babies<killed:
		# produces two babies from two random parents (should prob give fittest parents preference)
		reproduce(population[randint(0,cpop)],population[randint(0,cpop)])
		# Reproduce adds two babies to the population
		babies+=2 
	
	# vvvvvv
	#print "Reproduced", babies, "babies (Added to gene pool)"
	# ^^^^^^

	# adds one to the generations
	generations+=1

	# Looks for highest fitness in the group and checks if any have won!
	maxi=0
	for i in range(0,popsize):
		if fitness[i]>maxi:
			maxi=fitness[i]
			if maxi==8:
				print population[i]
				# Breaks this loop,
				# main loop will also break as maxi now = 8
				break

	# vvvvvv
	#print "Fittest so far", maxi
	# printpop()
	# raw_input()
	# ^^^^^^
	
	
# Loop ends.
# Shows how many generations it took to find the answer (very intersting, try running a few times, varies greatly)
print "Took",generations,"generations"
# Program ends



# Hope this makes sence, its not my best program, and its quite an advanced topic for a first
# program in the language. I've commented UBER-heavily hope it helps. Just email me if something doesn't
# make sence.

# Mat