GAUCHE = 0
DROITE = 1

LOUP = 0
CHEVRE = 1
CHOU = 2
PASSEUR = 3
PROTAGONISTES = (LOUP, CHEVRE, CHOU, PASSEUR)

DESSINS = (chr(128058), chr(128016), chr(129388), chr(128578))

class Passeur():
    """Le passeur mémorise des états des rives gauche et droite
    et simule des traversées : quand l'état courant ie le dernier
    de la mémoire est égal à l'état final on stoppe et on affiche
    
    un état est représenté par une liste de 4 valeurs 0 ou 1...
    chaque valeur correspond à un des protagonistes"""
    def __init__(self):
        self.suivant = None
        self.memoire = [[GAUCHE] * len(PROTAGONISTES)]
        self.etat = self.memoire[-1]


    def affiche_solution(self):
        for config in self.memoire:
            rives = ['', '']
            for protagoniste in PROTAGONISTES:
                rives[config[protagoniste]] += DESSINS[protagoniste]
            print(rives[GAUCHE] + ' ~~~~~~~~~ ' + rives[DROITE])
        
    def fini(self):
        return self.etat == [DROITE] * len(PROTAGONISTES)
    
    def memorise(self):
        self.memoire.append(self.suivant.copy())
        self.etat = self.memoire[-1]

    def oublie(self):
        self.memoire.pop()
        self.etat = self.memoire[-1]
        
    def deja_vu(self):
        return self.suivant in self.memoire
    
    def danger(self):
        """l'état suivant est dangeureux si le loup et la chèvre sont
        sur la même rive, sans le passeur ou alors la chèvre et le chou"""
        loup_mange_chevre = self.suivant[CHEVRE] == self.suivant[LOUP] and self.suivant[LOUP] != self.suivant[PASSEUR]
        chevre_mange_chou = self.suivant[CHEVRE] == self.suivant[CHOU] and self.suivant[CHEVRE] != self.suivant[PASSEUR]
        return loup_mange_chevre or chevre_mange_chou
    
    def traverse(self, protagoniste):
        """Faire traverser le protagoniste ie faire une copie de
        l'état courant puis changer la valeur pour le protagoniste
        si ce dernier n'est pas le passeur il faut aussi faire
        traverser le passeur"""
        self.suivant = self.etat.copy()
        self.suivant[protagoniste] = 1 - self.suivant[protagoniste]
        if protagoniste != PASSEUR:
            self.suivant[PASSEUR] = 1 - self.suivant[PASSEUR]
        
    def resoud(self):
        if self.fini():
            return True
        else:
            for protagoniste in PROTAGONISTES:
                self.traverse(protagoniste)
                if not self.danger() and not self.deja_vu():
                    self.memorise()
                    if self.resoud():
                        return True
                    else:
                        self.oublie()
            return False
                
seb = Passeur()
if seb.resoud():
    seb.affiche_solution()
else:
    print('Pas de solution')