Solution alzheimerienne des tours de Hanoï

Comme promis, voici le deuxième article du mois. Ça fait un certain nombre de fois que je publie des articles courts, donc je voulais me rattraper.

Par contre, j’ai jamais promis que ce deuxième article serait intéressant.

Il s’agit céans d’un petit bout de code en python, résolvant le problème des tours de Hanoï de manière alzheimerienne.

Je vous en avais parlé il y a quelques années.

La manière alzheimerienne impose de ne pas se souvenir des coups joués précédemment, et de ne pas partir dans des trips de récursivité sous acide.

Le coup à jouer est déduit uniquement de la situation courante, c’est à dire la position des disques. Vous pouvez donc appliquer cet algorithme même si vous êtes atteint de la maladie d’Alzheimer. Ha ha ha.

J’ai pris le temps de remettre le code au propre, en PEP-8, avec des commentaires corrects. Le tout est sur mon github.

Explication de l’algorithme

Elle est dans la docstring du fichier python. Je vous la remets ici.

Il faut d’abord déterminer le nombre de « coupures » dans l’ordre des disques.

Lorsque deux disques de taille N-1 et N sont empilés sur un même poteau, il n’y a pas de coupure entre eux. Lorsqu’ils sont sur deux poteaux différents, on compte une coupure.

De plus, lorsque le gros disque du bas n’est pas sur le poteau de fin, on compte également une coupure.

Exemple :

• Le disque 1 (le plus petit) est sur le poteau de départ.
• Les disques 2 et 3 sont sur le poteau intermédiaire.
• Le disque 4 (le plus gros) est aussi sur le poteau de départ.

 

      |           |           |
      |           |           |
      |           |           |
     +++        -----         |
  ---------    +++++++        |
  .................................

 

On compte les coupures en partant du plus gros disque vers le plus petit (mais on aurait pu compter dans l’autre sens).

• Le 4 n’est pas sur le poteau de fin. +1 coupure
• Le 4 et le 3 ne sont pas sur le même poteau. +1 coupure
• Le 3 et le 2 sont sur le même poteau. OK
• Le 2 et le 1 ne sont pas sur le même poteau. +1 coupure

Total : 3 coupures.

Cette dame s’appelle Miss Twin Towers, soit l’équivalent de deux tiers d’un jeu de tour de Hanoï

Si le nombre de coupures est impair, il faut déplacer le disque 1 (le petit).

Pour déterminer son poteau de destination :

Si le nombre total de disque est pair, le petit disque doit se déplacer vers l’avant :

poteau de départ -> poteau intermédiaire -> poteau de fin -> poteau de départ -> etc.

Si le nombre total de disque est impair, il doit se déplacer vers l’arrière :

poteau de fin -> poteau intermédiaire -> poteau de départ -> poteau de fin -> etc.

Si le nombre de coupures est pair, il faut déplacer un disque autre que le petit disque. Dans ce cas, il n’y a toujours qu’un seul mouvement possible.

Parmi les deux poteaux ne contenant pas le petit disque, l’un d’eux est vide. Il faut alors déplacer un disque du poteau non vide vers le poteau vide.

Parmi les deux poteaux ne contenant pas le petit disque, aucun n’est vide. Il faut prendre le plus petit disque parmi ces deux poteaux, et le déplacer vers l’autre.

Lorsque le nombre de coupures vaut 0, le jeu est terminé. Tous les disques sont sur le poteau de fin, dans le bon ordre.

Il faudrait une vraie démonstration mathématique pour prouver que cet algo fonctionne, mais je ne sais pas la faire. Ça semble fonctionner quel que soit le nombre de disques.

Les tours c’est fun

Pour finir, voici une image d’un vieux jeu que j’avais beaucoup aimé : Mystic Towers. Je n’ai pu profiter que de la version shareware, mais c’était quand même chouette

Oh, et il semblerait qu’on arrive déjà à la fin du mois. Il faut que je démarre un nouvel article. Diantre.