CNSemDist

import math
# coding: utf-8 #


class State():
    def __init__(self, leftMiss, rightMiss, leftCann, rightCann, boatSide):
        self.node = None
        self.childrens = []
        self.leftMiss = leftMiss
        self.rightMiss = rightMiss
        self.leftCann = leftCann
        self.rightCann = rightCann
        self.boatSide = boatSide

    def __repr__(self):
        from pprint import pformat
        return pformat(vars(self), indent=4, width=1)

    def validState(self):
        # Não permitir missionarios ou canibais negativos
        if ((self.leftMiss < 0)
            or (self.leftCann < 0)
            or (self.rightMiss < 0)
                or (self.rightCann < 0)):
            return False

        # Não permitir mais canibais que missionários
        if((self.leftMiss == 0 or self.leftMiss >= self.leftCann) and
           (self.rightMiss == 0 or self.rightMiss >= self.rightCann)):
            return True

    def createChildren(self):
        possible_moves = [
            [1, 0], [1, 1], [0, 2], [2, 0], [0, 1]
        ]

        # Gera os possíveis estados e armazena apenas os válidos no estado atual
        for move in possible_moves:
            if self.boatSide == 0:
               # Barco na esquerda, ambos saem da esquerda pra direita

                # movimentação dos missionarios da direita para a esquerda
                leftMiss = self.leftMiss - move[0]
                rightMiss = self.rightMiss + move[0]

                # movimentação dos cannibais da direita para a esquerda
                leftCann = self.leftCann - move[1]
                rightCann = self.rightCann + move[1]

                # Criação do estado do filho
                children = State(leftMiss, rightMiss,
                                 leftCann, rightCann, 1)
            else:
               # Barco na direita, ambos saem da direita pra esquerda

                # movimentação dos missionarios da esquerda para a direita
                rightMiss = self.rightMiss - move[0]
                leftMiss = self.leftMiss + move[0]

                # movimentação dos cannibais da esquerda para a direita
                rightCann = self.rightCann - move[1]
                leftCann = self.leftCann + move[1]

                # Criação do estado do filho
                children = State(leftMiss, rightMiss,
                                 leftCann, rightCann, 0)

            # adiciona a lista
            children.node = self

            # validação de estado
            if children.validState():
                # adiciona como filhos do pai
                self.childrens.append(children)

    def finalState(self):
        if ((self.rightMiss and self.rightCann) == 3 and
           (self.leftMiss and self.leftCann) == 0):
            return True
        else:
            return False

    def calculateEuclidianDistance(self):
        left = (self.leftMiss, self.leftCann)
        right = (self.rightMiss, self.rightCann)

        cost = math.dist(left, right)

        heuristic = self.leftMiss + self.rightMiss
        result = cost + heuristic
        return result


class Tree():
    def __init__(self):
        self.state = [State(3, 0, 3, 0, 0)]
        self.solution = None

    def resolveProblem(self):
        for element in self.state:
            if element.finalState():
                # Se o elemento for o final, armazena o caminho
                self.solution = [element]
                while element.node:
                    self.solution.insert(0, element.node)
                    element = element.node
                break

            # Se o elemento nao solucionar gera os filhos no state
            element.createChildren()

            self.state.extend(element.childrens)


problem = Tree()
problem.resolveProblem()

i = 0
for state in problem.solution:

    i += 1
    print(
        "Passo", i,
        '\nLeft Miss', state.leftMiss, 'Right Miss', state.rightMiss, '\n'
        'Left Cann:', state.leftCann,  'Right Cann', state.rightCann, '\nBoat side:', state.boatSide, '\n', 50*'--'
    )