travessia.py

# -*- coding: utf-8 -*-

class Estado():
    def __init__(self, missionarios_esq, missionarios_dir, canibais_esq, canibais_dir, lado_rio):
        self.missionarios_esq, self.missionarios_dir, self.canibais_esq, self.canibais_dir = missionarios_esq, missionarios_dir, canibais_esq, canibais_dir
        self.lado_rio = lado_rio
        self.m_previo_esq, self.m_previo_dir, self.c_previo_esq, self.c_previo_dir = missionarios_esq, missionarios_dir, canibais_esq, canibais_dir
        self.pai = None
        self.filhos = []

    def __str__(self):
        if self.pai:
            if self.lado_rio == 'dir':
                barco = '{}{}'.format(abs(self.missionarios_esq - self.pai.missionarios_esq)*'m' , abs(self.canibais_esq - self.pai.canibais_esq)*'c' )
            else:
                barco = '{}{}'.format(abs(self.missionarios_dir - self.pai.missionarios_dir)*'m' , abs(self.canibais_dir - self.pai.canibais_dir)*'c' )
        else:
            barco=""
        return 'barco( {}{}{} )  | esquerda: {}{}{} | {}{}{} :direita'.format(
                '->' if self.lado_rio == 'dir' else '<-', barco, (3-len(barco))*' ',
                int(self.missionarios_esq)*'m', int(self.canibais_esq)*'c', (10-int(self.missionarios_esq)-int(self.canibais_esq))*' ',
                int(self.missionarios_dir)*'m', int(self.canibais_dir)*'c', (10-int(self.missionarios_dir)-int(self.canibais_dir))*' ',
        )

    def segue_regra(self):
        if ((self.missionarios_esq < 0) or (self.missionarios_dir < 0)
            or (self.canibais_esq < 0) or (self.canibais_dir < 0)):
            return False
        return ((self.missionarios_esq == 0 or self.missionarios_esq >= self.canibais_esq) and
                (self.missionarios_dir == 0 or self.missionarios_dir >= self.canibais_dir))

    def teste_meta(self):
        resultado_esq = self.missionarios_esq == self.canibais_esq == 0
        resultado_dir = self.missionarios_dir == self.canibais_dir == 3
        return resultado_esq and resultado_dir

    def gerar_filhos(self):
        novo_lado_rio = 'dir' if self.lado_rio == 'esq' else 'esq'
        movimentos = [
            {'missionarios': 2, 'canibais': 0},
            {'missionarios': 1, 'canibais': 0},
            {'missionarios': 1, 'canibais': 1},
            {'missionarios': 0, 'canibais': 1},
            {'missionarios': 0, 'canibais': 2},
        ]
        for movimento in movimentos:
            if self.lado_rio == 'esq':
                missionarios_esq = self.missionarios_esq - movimento['missionarios']
                missionarios_dir = self.missionarios_dir + movimento['missionarios']
                canibais_esq = self.canibais_esq - movimento['canibais']
                canibais_dir = self.canibais_dir + movimento['canibais']
            else:
                missionarios_dir = self.missionarios_dir - movimento['missionarios']
                missionarios_esq = self.missionarios_esq + movimento['missionarios']
                canibais_dir = self.canibais_dir - movimento['canibais']
                canibais_esq = self.canibais_esq + movimento['canibais']
            filho = Estado(missionarios_esq, missionarios_dir, canibais_esq,
                           canibais_dir, novo_lado_rio)
            filho.pai = self
            if filho.segue_regra():
                self.filhos.append(filho)


if __name__ == '__main__':
    fila_execucao = [Estado(3, 0, 3, 0, 'esq')]
    solucao = None
    for elemento in fila_execucao:
        if elemento.teste_meta():
            solucao = [elemento]
            while elemento.pai:
                solucao.insert(0, elemento.pai)
                elemento = elemento.pai
            break;
        elemento.gerar_filhos()
        fila_execucao.extend(elemento.filhos)
    print "      acao      |          estado"
    for estado in solucao:
        print estado