#!/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)
