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.

Que devient le groupe de musique Lonah ?

C’était il y a quelques années.

Je vous propose de faire mon vieux de la veille et de vous raconter ça comme si c’était une lointaine époque dont je serais le seul survivant à me souvenir. Ça fait toujours super classe.

[Disgression : ça me rappelle une autre époque, pas si lointaine, où, dès que j’utilisais l’expression « ca me rappelle », il se trouvait un petit trou du cul de connard pour se foutre de ma gueule et m’imiter comme si j’étais quelqu’un de très vieux qui se rappelait une ancienne époque. Ce n’était pas uniquement de la moquerie, c’était aussi un acte réducteur de ma personne : le petit trou du cul sous-entendait que j’étais un jeune petit trou du cul qui voulait se donner l’impression qu’il avait une histoire, alors qu’il n’en n’a pas car il est trop jeune. Même à l’age de trois ans, j’avais déjà une histoire, trou du cul. L’histoire de millions d’autres enfants. Mais ce n’est pas le moment de parler de ça.]

En ces temps très très anciens, les licences libres logicielles (GPL, BSD, Apache, …) étaient relativement connues, mais les licences libres artistiques n’en étaient qu’à leurs blablabutiements. Les œuvres apparentées étaient donc assez rares, et souvent d’une qualité et d’un intérêt douteux. Les chantres du Libre devaient donc user d’un peu de mauvaise foi pour les défendre, et lorsqu’ils citaient des exemples, retombaient souvent sur les mêmes :

• Elephant’s dream pour les films d’animation,
• Mastoc Studio pour les dessins animés,
• Gonzolero pour la bande dessinée,
• Inlibroveritas pour les écrits,
• TuxRacer, Quake, XBill pour les jeux vidéos,
• Le site culturelibre.net, qui n’existe plus,
• Les trucs de Ehma, Lacrymosa Industry, LL De Mars, etc.

Je mets les liens grisés ici, car si je les intègre dans la liste, ce sera illisible :

• https ://orange .blender.org/background/
• https ://www .youtube.com/user/MastocStudio/videos?sort=dd&view=0&shelf_id=0
• http ://art9libre .tuxfamily.org/archives/author/eldreammachine
• http ://www .inlibroveritas.net/
• http ://tuxracer .sourceforge.net/
• https ://en .wikipedia.org/wiki/Quake_III_Arena
• http ://www .xbill.org/
• http ://web .archive.org/web/20060619144448/http://culturelibre.net:80/article.php3?id_article=330
• https ://fr .wikipedia.org/wiki/Ehma
• https ://lacrymosa .tuxfamily.org/
• http ://www .le-terrier.net/index2.html

Les terres de l’Art Libre étaient encore vierges, il suffisait donc d’y produire une œuvre pas trop dégueu pour avoir un tout petit public conquis dès le départ. C’est à cette occasion que j’ai essayé de devenir riche et célèbre avec mon dessin animé Pru-Pra-Prok. Je vous ai déjà raconté cela.

L’art de la musique était un peu plus avancé que les autres dans la découverte des bouleversements interneto-générés. Un paquet de pop-corn à la main, nous assistions aux échauffourées entre les vilaines maisons de disques soutenues par la méchante Sacem, et les héros robin-des-boisesques qu’étaient Napster et autres eMule. C’est dans ce contexte qu’apparut Jamendo, une plate-forme d’écoute et de téléchargement de musique. Son positionnement par rapport au « Libre » est source de débats et d’analyses diverses (https:// framablog.org/2011/10/04/librologie-jamendo/). De son côté, Mano Solo tentait un truc, se planta, puis mourut un petit peu.

Jamie Lopez n’est pas sur Jamendo, malgré les 3 lettres initiales en commun.

Le groupe de musique Lonah, composé de gens (retrouvez les noms vous-mêmes) était un « early adopter » de Jamendo. Leur premier album « Pièces » est un joli petit concentré patchworkesque de choses belles, étranges, oniriques, volantes, interrogatives, safranées, piscinesques. Je l’aime beaucoup.

J’étais allé les voir en concert, dans un quelconque bar-salle parisien. Le petit dépliant du planning indiquait « Lionah ». Woups, boulette.

Puis ils ont sorti deux autres albums, tout aussi bien. De mon côté, j’étais parti vers d’autres choses. C’est à peu près à cette époque que j’ai commencé ce blog. La suite de cette histoire est dans mes articles.

Récemment, je suis allé traîner sur leur site, le dernier message date de 2012. On y trouve également une photo de chien-loup, à moins que ce soit un choux-lien.

Est-ce qu’ils sont partis en tournée mondiale et n’ont plus le temps de donner de leurs nouvelles ? Est-ce qu’ils se sont séparés ? Est-ce que leur gloire naissante s’est embrasée au contact trop proche d’un soleil trop attirant ? Est-ce que ça leur a finalement semblé mieux et plus jucraciel de devenir trader en cokaïne à Dubaï ? Si vous avez des infos ou si un membre du groupe me lit, ça me ferait très plaisir d’avoir un petit commentaire.

En attendant, j’ai un petit cadeau pour vous. Le groupe avait créé un très beau morceau intitulé « le roi se meurt », inspiré de la pièce de théâtre éponyme de Ionesco. Même que j’avais acheté et lu le texte de la pièce suite à la découverte de cette chanson.

Celle-ci ne semble pas présente sur leur compte Jamendo. Elle est écoutable sur leur blog (http:// www. lonah.net/?q=node/24), mais il faut activer le flash, et c’est difficilement (voire impossiblement) téléchargeable.

Heureusement, j’avais récupéré le mp3 à une époque où il était disponible (je ne sais plus où). Voici donc, chers lecteurtrices/auditeurtrices, un petit trésor : Le roi se meurt en mp3 (https:// www. dropbox.com/s/itnirgtpwhec6xj/12%20Le%20roi%20se%20meurt.mp3?dl=0).