from random import randint, gauss, seed, uniform, random
from math import exp
from time import sleep
import numpy as np

M = 10
N = 10
E = 3

#Initializerer de to viktigste listene. En for aa passe paa om man kan plassere paa posisjonen, og en for aa holde om egg er plassert der. Samme stoerrelse.
canPlaceLookUp = []
hasEgg = []

for y in range(0,M):
    canPlaceLookUp.append([])
    hasEgg.append([])
    for x in range(0,N):
        canPlaceLookUp[y].append(True)
        hasEgg[y].append(False)

#1-dimensjonal liste med egg plassert.
placedEggs = []
#Energi og nedkjoeling.
energy = 1.0
cooling_rate = 0.0002
#Retninger til count_eggs
directions = [(-1,0),(-1,-1),(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,1)]

#Needs a bit of a clean up, but will stay a bit cluttered as long as it works.
def can_place(x, y):
    global hasEgg, canPlaceLookUp, E

    if not canPlaceLookUp[y][x]:
        return False

    #Check vertical and horizontal
    if egg_counter(hasEgg, 0,y,(1,0),0)>=E:
        canPlaceLookUp[y][x] = False
        return False
    if egg_counter(hasEgg,x,0,(0,1),0)>=E:
        canPlaceLookUp[y][x] = False
        return False
    #Check diagonals
    if (egg_counter(hasEgg,x,y,(-1,-1),0)+egg_counter(hasEgg,x+1,y+1,(1,1),0))>=E:
        canPlaceLookUp[y][x] = False
        return False
    if (egg_counter(hasEgg,x,y,(1,-1),0)+egg_counter(hasEgg,x-1,y+1,(-1,1),0))>=E:
        canPlaceLookUp[y][x] = False
        return False
    return True

#Teller alle eggene i en retning fra posisjon og returnerer antall egg. Rekursivt flytter seg i en retning. Enten vertikalt, horisontalt eller diagonalt, basert paa dv.
def egg_counter(array, startx, starty, dv, current_count):
    if startx == len(array[0]) or starty == len(array) or startx < 0 or starty < 0:
        return current_count
    if array[starty][startx]:
        current_count+=1
    return egg_counter(array, startx+dv[0], starty+dv[1], dv, current_count)

#Teller eggene i alle retninger fra en posisjon. Bruker egg_counter for tellingen. Her er ett lavt antall egg en god ting for å spre løsningen bedre utover brettet.
def count_eggs(pos):
    global hasEgg, directions
    counter = 0
    for dv in directions:
        counter += egg_counter(hasEgg, pos[0], pos[1], dv,counter)
    return counter

#Henter ut "naboer" av posisjonen. Henter ut ved en submatrise av samme stoerrelse som hovedmatrisen, men midstilt i punktet
def generate_neighbors(x,y):
    global M, N
    result = []
    n = max(M,N)
    for a in xrange(0,n):
        for b in range(0,n):
            xi = max(0,min((x+a-n/2),N-1))
            yi = max(0,min((y+b-n/2),M-1))
            if can_place(xi,yi):
                result.append((xi,yi))
    return result

#Hovedfunksjonen for aa finne egg og returnere det. Baserer seg paa funksjonen i skriptet gitt fra oevingsforelesningen
def step(lastPlaced, placedEggs, temperature):
    neighbors = generate_neighbors(lastPlaced[0], lastPlaced[1]) #Henter ut mulige "naboer" av egget som ble sist lagt til.
    num_neighbors = len(neighbors) #Antall "naboer"
    if num_neighbors == 0: #Hvis det ikke er noen naboer returnerer den None saa den kan starte funksjonen paa nytt og finne et annet egg.
        return None
    n_fitness = map(count_eggs, neighbors) #Mapper antall egg rundt naboposisjonen
    max_fitness = min(zip(n_fitness, neighbors)) #Finner den posisjonen som har flest egg rundt seg. (burde kanskje endre denne til min)

    q = (max_fitness[0] - count_eggs(lastPlaced))/count_eggs(lastPlaced)
    p = min(1,exp(-q/temperature))

    if random() > p:
        return max_fitness[1]
    else:
        return neighbors[randint(0,num_neighbors-1)]

#Seed for aa kontrollere tilfeldigheten.
seed()
#Lager det foerste egget og plasserer det i "esken"
firstx = randint(0,N-1)
firsty = randint(0,M-1)
placedEggs.append((firstx, firsty))
hasEgg[firsty][firstx] = True
canPlaceLookUp[firsty][firstx] = False

#Hovedloopen
while 1:
    #Henter ut egg basert paa det egget som ble sist laget.
    egg = step(placedEggs[len(placedEggs)-1],placedEggs, energy)
    if egg:
        #Plasserer egg
        placedEggs.append(egg)
        hasEgg[egg[1]][egg[0]] = True
        canPlaceLookUp[egg[1]][egg[0]] = False
    #Reduserer energien/temperaturen
    if energy-cooling_rate > 0:
        energy -= cooling_rate
    else:
        #Skriver div info til en outputfil og bryter loopen for aa stoppe skriptet. Strengt tatt ikke viktig for algoritmen
        f = open("output.txt", "w")
        f.write("Seed: 5 \n\n")
        for eggs in hasEgg:
            print eggs
            for egg in eggs:
                f.write(str(egg)[0:1] + "\t")
            f.write("\n")
        f.write("\nAntall egg: " + str(len(placedEggs)) + "\n\n")
        print len(placedEggs)
        for egg in placedEggs:
            f.write("x: " + str(egg[0]) + ", y:" + str(egg[1]) + "\n")
        f.close()
        print placedEggs

        break