#!/usr/bin/env python
#
# Program to read and print a file 
#
import random
import math
import numpy


# evaluate a candidate solution
# inputs: weight array, value array,
# and boolean vector where 1 in position i indicates that item i
# will be taken.
# outputs: total weight taken in this choice and total value
def evalcand(myweights, myvalues, mychoices):
   sumweights = 0
   sumvalues = 0
   i = 0
   while(i < len(mychoices)):
	if(mychoices[i] == 1):
		sumweights+= myweights[i]
		sumvalues+= myvalues[i]
	i+=1
   return (sumweights, sumvalues)

# generate a candidate
# consisting of a boolean array of length mylen
# input: mylen
# ouput: the array
def gencand(mylen):
  arr = []
  i = 0
  while(i < mylen):
	x = random.random()
	if(x > 0.96): # this depends on application; for this knapsack problem
		# the total weight is much larger than weight that can be 
		# carried.
		arr.append(1)
	else:
		arr.append(0)
	i+=1
  return (arr)

		

  
  

# Mutate at each position with probability mutationprob
# In a setting where the probability of a 1 is a lot smaller than a 0,
# we may not want to be symmetric, because any mutation will tend to 
# produce more 1s.
# That was original algorithm. New algorithm just moves 1s around.
def mutate(arr):
  x = random.random()
  myarr = arr
  # print ("Sum of old array is: "), sum(myarr)
  i = 0
  while(i < len(myarr)):
	x = random.random()
	if((x <= mutationprob) & (1 == myarr[i])) :
		myarr[i] = 0
		# Put your code here
	elif((x <= mutationprob) & (0 == myarr[i])) :
		myarr[i] = 1 # is this right? Might create too many 1s
		# Put your code here
	i+=1
  # print ("Sum of new array is: "), sum(myarr)
  return (myarr)

# cross-over at random point with prob crossprob
def crossover(myarr1, myarr2):
  x = random.random()
  newarr1 = []
  newarr2 = []
  if(x <= crossprob):
	x = random.random()
	j = int(x * len(myarr1))
	newarr1 = myarr1[:j]
	newarr1+= myarr2[j:]
	# Put your code here
  	return (newarr1, newarr2)
  else:
	return(myarr1, myarr2)

# evolve a solution
def evolve(allscores, allarr, best, bestarr):
  flag = 1
  myallscores = allscores
  myallarr = allarr
  lastbest = best
  lastbestfit = fit(best)
  lastbestarr = bestarr
  mytries = 0
  while(1 == flag):
  	fitarr = []
  	i = 0
  	while(i < len(myallscores)):
		fitarr.append(fit(myallscores[i]))
		i+= 1
	fitmax = max(fitarr)
	fitmin = min(fitarr)
	spread = fitmax - fitmin
	print ("Spread is: "), spread
	nextgen =[]
 	i = 0
	# the more likely candidate is the one with the greatest fitness
	while(numcands >= len(nextgen)): # until we have filled 
		myprob = (0.01 + (fitarr[i] - fitmin)) / (0.01 + spread)
		x = random.random()
		if(x <= myprob):
			nextgen.append(myallarr[i])
		i+= 1
		if(i == numcands): 
			i = 0
	# mutations
	i = 0
	while(i < numcands):
		# print ("About to call mutate")
		nextgen[i] = mutate(nextgen[i])
		i+= 1
	# cross-over
	i = 0
	while(i < numcands):
		j=i+1
		while(j < numcands):
			pair = crossover(nextgen[i], nextgen[j])
			myallarr[i] = pair[0]
			myallarr[j] = pair[1]
			j+= 1
		i+= 1
	# evaluate
	if(mytries == numtries):
		flag = 0
	mytries+=1
 	myallscores = []
 	i = 0
	while(i < numcands):
		myallscores.append(evalcand(weights, values, myallarr[i]))
		# print ("Fit of candidate "), i, (" is: "), fit(myallscores[i])
		if((fit(myallscores[i])) > lastbestfit):
			print "Have a better fit"
			flag = 1
			lastbestfit = fit(myallscores[i])
			lastbest = myallscores[i]
			lastbestarr = myallarr[i]
    			print ("last best fit: "), lastbestfit
		i+= 1
  print ("final best fit: "), lastbestfit
	

	
		

# derive fitness of an array by using evalcand to get the weight and score
# and give the score if weight is under maxweight; otherwise give amount 
# by which weight is too high
def fit(pair):
  if(maxweight >= pair[0]):
	return pair[1]
  else:
	return maxweight - pair[0] # negative number

# DATA 
numcands = 40 # for genetic algorithm
numtries = 100 # number of generation of genetic algorithm
maxweight = 50
mutationprob = 0.01 # because most of the vector is 0, this will tend
	# to increase the number of 1s, so be careful
newcandprob = 10 * mutationprob # just generate a new candidate
	# instead of mutating
crossprob = 0.1

# EXECUTION 
   
file = open("knapinput","r")
text = file.readlines()
file.close()

print text[0]
totweight = int(text[0])

weights = []
values = []
i = 1
while(i < len(text)):
	x = text[i].split(" ")
	weights.append(float(x[0]))
	values.append(float(x[1]))
	i+=1

allarr= []
allscores = []
i = 0
while(i < numcands):
  myarr = gencand(len(weights))
  allarr.append(myarr)
  allscores.append(evalcand(weights, values, myarr))
  i+= 1

# Put code here maybe to get better initial candidate
best = allscores[0]
bestarr = allarr[0]
bestfit = fit(allscores[0])
print ("Sorting based on value/weight gives fitness: "), bestfit
i = 1
while(i < numcands):
  if (fit(allscores[i]) > bestfit):
	best = allscores[i]
	bestarr = allarr[i]
	bestfit = fit(allscores[i])
	print ("Best index is: "), i, (" and best fit score is: "), bestfit
	print ("Best fit weight is: "), allscores[i][0]
	print ("Best fit score is: "), allscores[i][1]
  i+= 1

print ("best fit after first generation: "), bestfit

evolve(allscores, allarr, best, bestarr)