mc

import sys
import math
import numpy as np

# 0 - 3 Missionários lado esquerdo
# 1 - 3 Canibais do lado esquerdo
# 2 - 0 Missionários do lado direito
# 3 - 0 Canibais lado direito
# 4 - Lado da canoa 0 - Esq - 1 Dir
initial_state = [3, 3, 0, 0, 0]


# (1,0) - Atravessar 1 missionário
# (2,0) - Atravessar 2 missionários
# (1,1) - Atravessar 1 canibal e 1 missionário
# (0,2) - Atravessar 2 canibais
# (0,1) - Atravessar 1 canibal
operators = [(1, 0), (1, 1), (2, 0), (0, 2)]

board = []
visited_nodes = []


def deslocateBoat(state, numMiss=0, numCan=0):
    # Comporta apenas 2 no barco
    if numMiss + numCan > 2:
        return

    # Testa a última posição, se for 0 a canoa ta a esquerda
    # Se for 1 esta a esquerda
    print(numCan, numMiss)
    if state[-1] == 0:
        missionariesOrigin = 0
        cannibalsOrigin = 1
        missionariesDest = 2
        cannibalsDest = 3
    else:
        missionariesOrigin = 2
        cannibalsOrigin = 3
        missionariesDest = 0
        cannibalsDest = 1

    # Caso não haja oque transportar
    if state[missionariesOrigin] == 0 and state[cannibalsOrigin] == 0:
        return

    # Atualizar a posição da canoa

    # Se é 1 passa a ser 0 e se é 0 passa a ser 1
    state[-1] = 1 - state[-1]

    # Deslocamento dos missionários
    # Remove 1 missioário da origem e aumenta 1 no destino
    # Verifica se a quantitade de missionários é menor que a quantidade de missionários no estado
    for i in range(min(numMiss, state[missionariesOrigin])):
        state[missionariesOrigin] -= 1
        state[missionariesDest] += 1

    # Deslocamento Canibais
    for i in range(min(numCan, state[cannibalsOrigin])):
        state[cannibalsOrigin] -= 1
        state[cannibalsDest] += 1

    print("Range", range(min(numMiss, state[missionariesOrigin])))
    return state


def successors(estadoAtual):
    arraySucessors = []  # armazenar os sucessores

    # Par ordenado que informa a quantidade de canibais e missionários a serem transferidos
    for (i, j) in operators:
        # cópia do array, i  missionários e j canibais
        # Retorna um estado possivel a partir do estado original

        sucessor = deslocateBoat(estadoAtual[:], i, j)
        print("MOVE:", deslocateBoat(estadoAtual[:], i, j))
        print("Successor", sucessor)
        print(estadoAtual[:])
        if sucessor == None:  # se estiver vazio
            continue

        # Aplicando as regras do problema
        # O número de missionários não pode ser menor que o de canibais
        if(sucessor[0] < sucessor[1] and sucessor[0] > 0) or (sucessor[2] < sucessor[3] and sucessor[2] > 0):
            continue

        # Verifica sucessor gerado já foi visitado
        if sucessor in visited_nodes:
            continue  # verificação de ESTADOS REPETIDOS

        # Adiciona o sucessor ao array de sucessores
        arraySucessors.append(sucessor)

    print(arraySucessors)

    return arraySucessors


successors(initial_state)


def calculateCost(state):
    left = (state[0], state[1])
    right = (state[2], state[3])

    cost = math.dist(left, right)  # calculo euclidiano

    heuristic = state[0] + state[1]

    result = cost + heuristic
    return result


def getAdjacentNotVisited(stateToVerify):
    saveCosts = []
    adj = successors(stateToVerify)

    if len(adj) > 0:
        for x in adj:
            saveCosts.append(calculateCost(x))

            minValue = min(saveCosts)
            return adj[saveCosts.index(minValue)]
    else:
        return -1


# Verifica se os canibais e missionários foram transportados
def finalTest(finalState):
    if finalState[2] == 3 and finalState[3] == 3:
        return True
    else:
        return False


def search(initial_state):
    board.append(initial_state)
    while len(board) != 0:
        stateToCheck = board[len(board)-1]

        # Se encontrar a solução, para o loop
        if finalTest(stateToCheck):
            print("Solucao encontrada")
            break
        adjReturn = getAdjacentNotVisited(stateToCheck)
        if adjReturn == -1:  # se retorna -1, não existe então tira o elemento
            board.pop()
        else:  # se não retorna -1, adiciona aos visited_nodes e adiciona a board
            visited_nodes.append(adjReturn)
            board.append(adjReturn)
    else:
        print("Caminho não encontrado")
    return board  # se estado atual for a board, será listado o caminho do estado inicial ate o estado final


def showSolution():
    solution = search(initial_state)
    for i in range(1, len(solution)):
        missionariesRight = abs(solution[i][0] - solution[i-1][0])
        cannibalsRight = abs(solution[i][1] - solution[i-1][1])
        boat = solution[i][4] - solution[i-1][4]

        if boat == 1:
            s = "direita"
        else:
            s = "esquerda"
        print(solution[i-1],
              "({},{},{})".format(missionariesRight, cannibalsRight, s))


showSolution()