import numpy as np
import random

file = 'input.txt'
generations = 1000


class world:
    __map = {}
    __totalGold = 0
    __goldPos = []
    __golds = []
    __collectedGold = 0
    __maxX = 0
    __maxY = 0
    __startX = 0
    __startY = 0
    __x = 0
    __y = 0
    __sequence = []

    def load(self, file):
        f = open(file, 'r')
        data = f.read().split('\n')
        f.close()
        self.__parse(data)

    def __parse(self, data):
        y = 0
        for line in data:
            self.__maxY = y
            x = 0
            for char in line:
                self.__maxX = max(self.__maxX, x)
                self.__map[(x,y)] = char
                if char == 'g':
                    self.__totalGold+=1
                    self.__goldPos.append([x,y])
                if char == 's':
                    self.__startX = x
                    self.__startY = y
                x+=1
            y+=1

    def createpop(self):
        indiv = []
        for i in range(20):
            ind = np.zeros(64)
            for n in range(16):
                ind[n] = np.random.randint(0,255)
            indiv.append(ind)
        return indiv

    def moveagent(self,direction):
        self.__sequence.append(direction)
        if direction == 'U':
            self.__y -= 1
        if direction == 'D':
            self.__y += 1
        if direction == 'R':
            self.__x += 1
        if direction == 'L':
            self.__x -= 1
        for gold in self.__golds:
            if [self.__x,self.__y] == gold:
                self.__collectedGold += 1
                self.__golds.remove(gold)

    def execute(self,virtmach):
        self.__golds = self.__goldPos.copy()
        self.__collectedGold = 0
        self.__x = self.__startX
        self.__y = self.__startY
        stepout = 0
        steps = 0
        address = 0
        self.__sequence = []

        while True:
            if steps >= 500:
                break
            if self.__y > self.__maxY or self.__x > self.__maxX or self.__y < 0 or self.__x < 0:
                stepout = 1
                break
            if self.__collectedGold == self.__totalGold:
                print ('Success!',self.__sequence)
                break

            val = int(virtmach[address])
            if (val >> 6) == 0:
                addr = val & 0b00111111
                virtmach[addr] = (virtmach[addr] + 1) % 256
                address = (address + 1) % 64
            elif (val >> 6) == 1:
                addr = val & 0b00111111
                if virtmach[addr] == 0:
                    virtmach[addr] = 255
                else:
                    virtmach[addr] -= 1
                address = (address + 1) % 64
            elif (val >> 6) == 2:
                address = val & 0b00111111
            elif (val >> 6) == 3:
                move = val & 0b00111111
                countones = (bin(move).count("1"))+2
                if countones <= 2:
                    self.moveagent('U')
                elif countones == 3 or countones == 4:
                    self.moveagent('D')
                elif countones == 5 or countones == 6:
                    self.moveagent('R')
                elif countones >= 7:
                    self.moveagent('L')
                address = (address + 1) % 64
            steps += 1
        fit = 1 + self.__collectedGold*2 - (steps*0.001) - (stepout*0.01)
        return fit

    def evalfit(self,indiv):
        fitarr = np.zeros(len(indiv))
        for i in range(len(indiv)):
            virtmach = indiv[i].copy()
            fitness = self.execute(virtmach)
            fitarr[i] = fitness
        return fitarr

    def tournament_selection(self,prevpop,fitvect,k):
        p = 0.8
        pop = prevpop.copy()
        selected = []
        elite = []
        elitpos = np.argpartition(fitvect,-3)[-3:]
        for i in range(len(elitpos)-1):
            elite.append(pop[elitpos[i]])

        for n in range(4):
            pos = []
            indi = []
            for i in range(k):
                pos.append(random.randint(0,len(pop)-1))
            for n in range(len(pos)):
                indi.append(fitvect[pos[n]])

            prob = np.random.uniform(0,1)
            if prob < p:
                sel1 = max(indi)
                pos1 = np.where(fitvect == sel1)[0][0]
            else:
                pos1 = random.randint(0,len(pop)-1)
            selected.append(pop[pos1])
            pop.pop(pos1)
            np.delete(fitvect,pos1)

        return selected,elite

    def crossover(self,parents,elite):
        kids = []
        for e in elite:
            kids.append(e)
        for k in range(20-len(elite)):
            shift = random.randint(1,len(parents[0])-2)
            m = random.randint(0,len(parents)-1)
            d = random.randint(0,len(parents)-1)
            while m == d:
                d = random.randint(0,len(parents)-1)
            kid = parents[m].copy()
            kid[0:shift] = parents[d][0:shift]
            kids.append(kid)
        return kids

    def mutation(self,pop):
        mute = []
        num = random.randint(8,len(pop))
        for n in range(num):
            mute.append(random.randint(0,len(pop)-1))
        for m in mute:
            indiv = pop[m]
            switch1, switch2 = random.randint(0,len(indiv)-1),random.randint(0,len(indiv)-1)
            indiv[switch1] += 1
            if indiv[switch2] == 0:
                    indiv[switch2] = 255
            else:
                indiv[switch2] -= 1
            pop[m] = indiv
        return pop

    def newpop(self,prevpop,fitvect):
        select = self.tournament_selection(prevpop,fitvect,6)
        parents = select[0]
        elite = select[1]
        newgen = self.crossover(parents,elite)
        new = self.mutation(newgen)
        return new,self.__collectedGold

w = world()
w.load(file)
population = w.createpop()
for g in range(generations):
    fitpop = w.evalfit(population)
    newp = w.newpop(population,fitpop)
    population = newp[0]
collected = newp[1]