Le loup 🐺, la chèvre 🐐 et la pomme 🍏

Ta mission, noble passeur, est de mener de l'autre côté de la rivière,

• Un loup 🐺
• Une chèvre 🐐
• Et une gigantesque pomme, de la taille d'un chou : 🍏

Mais ton frêle esquif 🚣‍ ne permet de transporter que l'un d'entre eux (maximum) à la fois. Et tu dois faire attention :

• 🐺 😋 🍴 🐐 si tu les laisses seuls sur une des deux rives
• 🐐 😋 🍴 🍏 si tu les laisses seuls sur une des deux rives

L'état actuel du jeu est (0,0,0).

Modélisation : chaque état du jeu est représenté par un point de l'espace :

1. Son abscisse est celle de 🐺 (0 si 🐺 est à gauche, 1 si 🐺 est à droite).
2. Son ordonnée est l'abscisse de 🐐 (0 si 🐐 est à gauche, 1 si 🐐 est à droite).
3. Sa hauteur est l'abscisse de 🍏 (0 si 🍏 est à gauche, 1 si 🍏 est à droite).

Le 🕸️ des états est un cube, dont les arêtes représentent des actions que tu peux mener :

Sur chacun des 8 ⭕ de ce cube, a été représentée la rive droite. Le jeu consiste à trouver un chemin dans ce 🕸️, allant du ⭕ vide au ⭕ portant 🐺🐐🍏. Mais

• Si une arête joint deux ⭕ portant 🐺🐐 (ou ne portant aucun des deux), c'est ⚰️ : sur un des deux ⭕, tu laisses 🐺🐐 seuls sans surveillance et ne peux empêcher le festin : tu as perdu !
• Si une arête joint deux ⭕ portant 🐐🍏 (ou aucun des deux) là encore tu laisses 🐐🍏 seuls sans surveillance et c'est là encore ⚰️.

Cela amène à enlever 4 arêtes du 🕸️ :

• ( )----( 🍏)
• (🐺🐐 )----(🐺🐐🍏)
• ( )----(🐺 )
• ( 🐐🍏)----(🐺🐐🍏)

Le 🕸️, une fois ces arêtes enlevées, est plus simple :

On y voit qu'il y a deux solutions :

• 🐐🐺🐐🍏🐐
• 🐐🍏🐐🐺🐐

Solution Python

Représentation ternaire d'un entier

Le nombre 0 s'écrit 0 en base 3.

def ternary(n):
        if n<3:
                return str(n)
        else:
                return ternary(n//3)+str(n%3)

Programmation objet

Dans la suite,

• loup est une variable globale, de type (ou de classe) L,
• chevre est une variable globale, de type (ou de classe) C,
• pomme est une variable globale, de type (ou de classe) P.

Le loup

Pour faire entrer le loup en scène, on utilise la fonction L() qui crée un objet de classe L et on le nomme, en faisant loup = L(). La définition de cette fonction se fait par

class L():
        def __init__(self):
                self.state = 0
        def go(self):
                if chevre.state != pomme.state:
                        self.state = 1-self.state

Autrement dit un loup (de classe L) est initialisé à l'état 0 (tous les personnages sont à gauche au début du jeu) et ne peut bouger (avec la méthode go()) que si la chevre et la pomme ne sont pas sur la même rive (dans le même état, ou state). Bouger veut dire changer d'état (ou de rive) en allant de gauche à droite (ou de 0 à 1), ou de droite à gauche (ou de 1 à 0).

La chèvre

La chèvre est plus facile à définir que le loup, parce qu'elle bouge plus facilement :

class C():
        def __init__(self):
                self.state = 0
        def go(self):
                self.state = 1-self.state

La pomme

Et la pomme est définie de manière similaire au loup :

class P():
        def __init__(self):
                self.state = 0
        def go(self):
                if loup.state != chevre.state:
                        self.state = 1-self.state

Solution du problème

243 = 3⁵ donc le script suivant essaye tous les programmes de longueur 5 (à 5 mouvements) maximum.

for n in range(243):
        programme = ternary(n)
        programme = programme.replace("0","loup.go();")
        programme = programme.replace("1","chevre.go();")
        programme = programme.replace("2","pomme.go();")
        exec("loup,chevre,pomme=L(),C(),P();"+programme)
        if loup.state+chevre.state+pomme.state==3:
                print(programme)

Par exemple, l'écriture de 42 en ternaire est 1120. Le script remplace les 0 par des loup.go(), les 1 par des chevre.go() et des 2 par des pomme.go() donc 1120 devient

chevre.go()
chevre.go()
pomme.go()
loup.go()

Ce programme n'est pas une solution au problème : la chèvre fait un aller-retour puis la pomme ni le loup ne peuvent bouger car cela viole la règle du jeu. Alors si on exécute le programme de numéro 42 (après avoir initialisé les variables loup, chevre et pomme) l'état final des trois variables n'est pas 1,1,1. On n'affiche donc pas le programme obtenu. On n'affiche que les programmes qui vont de l'état initial 0,0,0 à l'état final 1,1,1. On en trouve deux :

chevre.go();loup.go();chevre.go();pomme.go();chevre.go();
chevre.go();pomme.go();chevre.go();loup.go();chevre.go();