#(b, nm1,nc1,bp,nm2,nc2)
import random
import math
import time
import copy

"""
b-boat capacity (de ce e p acolo nimeni nu stie )
nm1+nm2 = nm
nc1+nc2 = nc
bp - boat position
asta e tot . voiallla :))
"""

class State:
    def __init__(self,b,nm1,nc1,bp,nm2,nc2):
        self.b=b
        self.nm1=nm1
        self.nc1=nc1
        self.bp=bp
        self.nm2=nm2
        self.nc2=nc2

def initialize(nm,nc,b):
    return State(b,nm,nc,1,0,0)

def isFinal(state):
    if state.nm1==0 and state.nc1==0 and state.bp == 2 :
        return True
    return False

def transition(state,nm,nc):
    return State (state.b,state.nm1+nm,state.nc1+nc,3-state.bp,state.nm2-nm,state.nc2-nc)

def validation(state,mm,cm):
    tempState = transition(state,mm,cm)
    if tempState.nm1>0 and tempState.nm1<tempState.nc1 :
        return False
    elif tempState.nm2>0 and tempState.nm2<tempState.nc2 :
        return False
    elif abs(mm+cm) > tempState.b :
        return False
    elif mm+cm > 0 and mm >= 0 and cm >= 0 and tempState.bp == 2 :
        return False
    elif mm + cm < 0 and mm <= 0 and cm <= 0 and tempState.bp == 1:
        return False
    elif tempState.nm1<0 or tempState.nm2<0 or tempState.nc1<0 or tempState.nc2<0:
        return False
    return True;

"""
s = initialize(10,10,5)

if(validation(s,-2,-3)):
    s=transition(s,-2,-3)
    print(s.b,s.nm1,s.nc1,s.bp,s.nm2,s.nc2)
else :
    print("not valid dude")
"""

def randomeStrategy(s):
    stari = []
    counter = 0
    while isFinal(s) == False :
        nm = s.nm1+s.nm2
        nc = s.nc1+s.nc2
        if s.bp == 1:
            mm=random.randint(-nm,0)
            cm=random.randint(-nc,0)
        else :
            mm = random.randint(0, nm)
            cm = random.randint(0, nc)

        if validation(s,mm,cm) and (transition(s,mm,cm) in stari) == False :
            counter=counter + 1
            s=transition(s,mm,cm)
            stari.append(s)
            #print(s.b,s.nm1,s.nc1,s.bp,s.nm2,s.nc2
            #(math.ceil((s.nm1+s.nm2 +s.nc1+s.nc2)/s.b))*2

        if counter == 100:
            counter = 0
            stari.clear()
            s=initialize(s.nm1+s.nm2,s.nc1+s.nc2,s.b)
    #for s in stari :
      # print(s.b, s.nm1, s.nc1, s.bp, s.nm2, s.nc2)
    #print("Acest algoritm a ajuns la solutie in ",len(stari)," pasi ",end="")
    #if len(stari)==(math.ceil((s.nm1+s.nm2 +s.nc1+s.nc2)/s.b))*2-1:
    #    print("(solutie optima)")
    #else:
     #   print("(solutie neoptima , se putea in ",(math.ceil((s.nm1+s.nm2 +s.nc1+s.nc2)/s.b))*2-1, " pasi")
    return len(stari)
# pentru valorile 4,4,2 . pasii parcursi minim sunt (nm+nc/b )* 2 - 1   care este ((4+4)/2)*2 -1  = 7
# daca counterul este 6 atunci algoritmul ruleaza la infinit deoarece nu exista  6 pasi care sa se termine in starea finala
#s=initialize(4,4,2)
#randomeStrategy(s)


def backtracking(state,list_state):
    for mm in range(-state.b,state.b):
        for cm in range(-state.b,state.b):
            if validation(state,mm,cm):
                new_state=transition(state,mm,cm)
                if isFinal(new_state):
                    list_state.append(new_state)
                    #for s in list_state:
                     #   print(s.b, s.nm1, s.nc1, s.bp, s.nm2, s.nc2)
                    return len(list_state)
                elif (new_state in list_state) == False:
                    list_state.append(new_state)
                    if backtracking(new_state,list_state):
                        return len(list_state)
                    else :
                        del list_state[-1]
#s=initialize(4,4,2)
#backtracking(s,[])
def validStates(state):
    stari = []
    if state.bp == 1 :
        for mm in range(-state.b, 1):
            for cm in range(-state.b, 1):
                if validation(state, mm, cm):
                    stari.append(transition(state,mm,cm))
    else:
        for mm in range(0,state.b+1):
            for cm in range(0, state.b+1):
                if validation(state, mm, cm):
                    stari.append(transition(state,mm,cm))

    return stari

def heuristic(stare,initialState):
    return ((initialState.nc1+initialState.nm2)-(stare.nc2+stare.nm2))

"""
print(heuristic(validStates(initialize(4,4,2))[2],initialize(4,4,2)))
x = validStates(initialize(4,4,2))[2]
print(x.nc1,x.nm1)
"""
def aStaaaar(stareInitiala):
    incState = copy.copy(stareInitiala)
    d = 999999
#afisez starea initiala
    #print(stareInitiala.nc1,stareInitiala.nm1)
    pas=0
#fac while nu am ajuns la starea fi
    while isFinal(incState) == False:
        toateStarile = validStates(incState)
        for stare in toateStarile :
#cand barca se intoarce atunci nu o sa existe o valoare heuristica care sa fie mai mica sau egala decat d
# pentru cazul in care barca se poate intoarce singura totul este ok .

            if heuristic(stare,stareInitiala) <= d:
                d=heuristic(stare,stareInitiala)
                pas +=1
                incState = copy.copy(stare)
        #print(incState.nc1, incState.nm1,incState.nc2,incState.nm2)
    return pas
#aStaaaar(initialize(3,3,5))
#8,2,5 toate valorile cu 5


def statistici():
    start = time.time()
    sumaRandome = 0
    counterRandome = 0
    for e in range(2,10):
        for j in range (2,10):
            for k in range (5,10):
                if e >=j:
                    sumaRandome+=randomeStrategy(initialize(e,j,k))
                    counterRandome+=1
    print("Random are o medie de " , sumaRandome/counterRandome," pasi pe executie - durata medie executie ",(time.time()-start)/counterRandome)
    start = time.time()
    sumaBacktracking = 0
    counterBacktracking = 0
    for e in range(2, 10):
        for j in range(2, 10):
            for k in range(5, 10):
                if e >= j:
                    sumaBacktracking += backtracking(initialize(e, j, k),[])
                    counterBacktracking += 1
    print("Backtracking are o medie de ", sumaBacktracking / counterBacktracking, " pasi pe executie  - durata medie executie ",(time.time()-start)/counterBacktracking)

    sumaStar= 0
    counterStar = 0
    for e in range(2, 10):
        for j in range(2, 10):
            for k in range(5, 10):
                if e >= j:
                    sumaStar += aStaaaar(initialize(e, j, k))
                    counterStar += 1
    print("a* are o medie de ", sumaStar / counterStar, " pasi pe executie - durata medie executie ",(time.time()-start)/counterStar)
statistici()