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.

Une réponse à “Solution alzheimerienne des tours de Hanoï

  1. Atelier de démo des tours de Hanoï
    http://recher.pythonanywhere.com/urluth/?u=aaa
    https ://en.wikipedia.org/wiki/Tower_of_Hanoi#/media/File:UniversumUNAM34.JPG

    Voilà qui est amusant. Alors, je voudrais pas faire mon mec qui me la pète, mais… Ouais nan, ça allait être de la merde ce que j’allais dire. Comme vous l’aurez vu, il y a en avant-plan une pile de disques où ils sont tous à l’envers. Blargle ! Mais c’est pas grave. Et la tour derrière est vraiment géante. Combien y’a-t-il de disques ? Comptez-les ! Ou nan. Les comptez pas en fait. On s’en fout non ? Et sinon ils ont tous des chapeaux bizarres dans cette photo, mais c’est pas grave non plus. Peut-être qu’ils voulaient jouer aux tours de Hanoï avec leurs chapeaux. Mais pas avec des soutien-gorges, car il faudrait le couper en deux pour avoir deux disques, sauf que ça fait des disques de la même taille. Ou alors il faudrait des soutien-gorges de femme ayant des seins asymétriques. Au fait, on dit « des soutien-gorges », « des soutiens-gorge » ou « des soutiens-gorges » ?

    Miss Twin Towers et deux amis à elle
    http://recher.pythonanywhere.com/urluth/?u=aab
    https ://zbporn.com/albums/429621/plumper-miss-twin-towers/

    Cool. Des boobs, sans soutien[s]-gorge[s]. C’est chouette. J’ai pas regardé la date de création de la vidéo, mais vu la qualité et le style vestimentario-tronchial des mecs, je dirais que ça date un peu. Est-ce que ça a été fait avant ou après l’attentat sur les Twin Towers ? J’en sais rien. Dans tous les cas, je propose qu’on remplace les Twin Towers détruites par une statue géante de cette dame. Et bon sang, ces aréoles géantes. Encore plus étendues que celles de Melonie Rose. Vous m’excusez un instant, je vais allez m’isoler 10 petites minutes et je reprendrais l’écriture de ces commentaires un peu plus tard.

    Screenshot du jeu Mystic Towers
    http://recher.pythonanywhere.com/urluth/?u=aac
    http ://www .mobygames.com/game/mystic-towers/promo/imageType,1/promoImageId,61695/

    Ah, ça va mieux. De quoi on parle maintenant ? Ah, Mystic Towers. Super chouette ce jeu. J’y ai retrouvé plein de petits éléments que j’aime en général dans les jeux. 1) la 3D isométrique. 2) Des décors d’intérieur très détaillé (pour l’époque, ça faisait très détaillé), il y a des tableaux au mur, des tables sur lesquels sont posés les objets, des sols différents et des alcôves avec des objets dedans. J’adore les alcôves. À ce titre, le jeu Cadaver des Bitmap Brothers, j’ai adoré, même si j’ai jamais pris le temps de m’y plonger à fond dedans. Et pour finir : 3) un sentiment de « nettoyage », car le but du jeu est tout simplement de tuer tous les monstres d’une tour (pensez à détruire préalablement le générateur, sinon ça servira à rien). Voilà. Et sinon il fallait gérer les valeurs de « faim », « soif » et « point de vie », et ça c’est plutôt sympa aussi. En plus il y avait plein d’objets de bouffe et de boissons différents, qui est une autre chose que j’aime dans les jeux : la multitude d’objets.

Répondre

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l'aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s