Accueil

Retour à Hanoï

Dans GNU/Linux Magazine 64 de septembre 2004, les Mongueurs de Perl ont écrit une Perle sur les tours de Hanoï. Il s'agissait d'écrire un script résolvant le problème des tours de Hanoï. Cela pouvait se faire au choix par des directives :

de 1 vers 3
de 1 vers 2
de 3 vers 2
de 1 vers 3
de 2 vers 1
de 2 vers 3
de 1 vers 3
soit en ASCII Art :
 =|=   |    |  
==|==  |    |  
XXXXXXXXXXXXXXX

  |    |    |  
==|== =|=   |  
XXXXXXXXXXXXXXX

  |    |    |  
  |   =|= ==|==
XXXXXXXXXXXXXXX

  |    |   =|= 
  |    |  ==|==
XXXXXXXXXXXXXXX
soit enfin en mode graphique : Wx, Perl/Tk, Gtk, etc.

Exemple de tours de Hanoï en Perl/Tk

J'ai participé à cette Perle en fournissant un programme qui fonctionnait en mode « directives » et en mode « ASCII Art », mais il y a eu deux problèmes. Pour des contraintes éditoriales, j'ai été obligé de supprimer tous les commentaires ainsi que le POD (documentation utilisateur). D'autre part, il y avait deux bugs : tout d'abord, comme l'a signalé BooK dans l'article, si l'on ne saisit ni l'option -d ni l'option -g, le programme n'affiche rien. Plus généralement, il n'y avait pas de vérification des paramètres. Le second, que BooK n'a pas remarqué, est que le choix entre les deux modes se faisait avec une option -d pour « directives » et -g pour « ASCII Art ». Donc, d'une part cela faisait croire qu'il s'agissait d'un mode graphique, d'autre part, l'opposition -g / -d était légèrement ambiguë puisqu'elle pouvait faire penser à la dichotomie gauche / droite.

Voici donc le programme corrigé, avec de nouveau les commentaires, plus un peu de couleurs pour la correction des bugs. Quant à la documentation utilisateur en POD, je n'ai pas repris l'ancienne, car j'ai adopté une idée utilisée entre autres par Platon, Galilée et Douglas Hofstadter : le dialogue à but didactique. Cela permet d'introduire des notions de manière progressive en commençant par un exemple, puis en donnant le cas général, puis les cas limites et les cas pathologiques. Dans les FAQ, chaque question doit être auto-suffisante et indépendante des autres (quoique je me souviens avoir lu une FAQ où un chapitre ressemblait à un dialogue). Alors que dans un dialogue, les questions et les réponses s'enchaînent, chaque réponse traitant une question et faisant surgir une autre question. Voici donc le programme avec commentaires et POD :

  #!/usr/bin/perl -s

  use strict;
  use vars qw/$d $a/;

  die "Il faut renseigner au moins une option -d ou -a"
    unless $d or $a;
  die "Merci d'indiquer le nombre de disques"
    unless @ARGV;
  warn "Arguments excédentaires ignorés"
    if @ARGV >= 2;

  my $n = $ARGV[0];
  my $ld = 2 * $n  + 1; # largeur maximale d'un disque
  my $l  = 3 * $ld;     # largeur du plateau, sans compter le caractère de saut de ligne
  my $ll = $l + 1;      # largeur du plateau, en comptant le caractère de saut de ligne

  my %s = qw/12 3 13 2 21 3 23 1 31 2 32 1/;  # initialisation pour les coups pairs
  @s{qw/1 2 3/} = $n % 2 ? qw/3 1 2/ : qw/2 3 1/; # puis les coups impairs

  # $j position de départ "1111" : tous les disques sur l'aguille 1
  # $k position d'arrivée "3333" : tous les disques sur l'aguille 3
  # Par la suite, $j contient la position courante, par exemple
  # "1123", les deux petits disques sur l'aguille 1, le presque grand
  # sur l'aiguille 2 et le grand sur la 3.
  # Et $v représente le vide.
  my ($j, $k, $v) = map { $_ x $n } ("1", "3", " ");

  # affichage de la directive ou du plateau de jeu, ou les deux
  # Si appelée sans argument, la fonction n'imprimera pas la directive,
  # seulement le plateau de jeu (et encore, à condition d'avoir demandé '-a')
  sub aff {
    printf "de %d vers %d\n", @_ if $d && @_;
    return unless $a;
    my $w = "$v|$v";
    # pour l'instant, trois aiguilles sans rien et le socle
    my $t = "$w$w$w\n" x $n . "X" x $l;
    my $p = - $ld;
    foreach (split '', $j)
      {
	# le disque gagne un peu en largeur
	$w =~ s/ ([=|]+) /=$1=/;
	# et il est placé sur la bonne aiguille, quoique pas forcément à la bonne hauteur
	substr($t, $p + $_ * $ld, $ld) = $w;
	$p += $ll;
      }
    local $_ = "$t\n";
    # les disques tombent morceau par morceau ; pour comprendre, essayez donc
    #     print while s/=(.{$l}) / $1=/gso;
    # avec 3 ou 4 disques
    1 while s/=(.{$l}) / $1=/gso;
    print;
  }
  # coup impair : déplacement du disque 1
  sub impair {
    $j =~ s/^(.)/$s{$1}/;
    aff $1, $s{$1};
  }
  # enchaînement d'un coup pair et d'un coup impair
  sub pairimp {
    $j =~ s/^(.)(\1*)(.)/$1$2$s{"$1$3"}/;
    aff $3, $s{"$1$3"};
    impair;
  }

  aff;
  impair;
  pairimp while $j ne $k;

  __END__

  =head1 NOM

  hanoi -- Tours de Hanoï en mode directives et art ASCII

  =head1 RÉSUMÉ

    hanoi [-d] [-a] nb

  =head1 DESCRIPTION

  Ce programme  résoud le problème des  Tours de Hanoï  sans utiliser de
  récursion.   L'affichage  est   une  liste   de  directives,   ou  une
  représentation  des  Tours de  Hanoï  en  art  ASCII, les  deux  étant
  compatibles.

  =head1 PARAMÈTRES

  =over 4

  =item l'utilisateur :

  -- Comment lance-t-on le programme ?

  =item le programmeur :

  -- Il se lance en ligne de commande, avec un paramètre obligatoire, le
  nombre de disques.

  =item l'utilisateur :

  -- Et on peut aller jusqu'à combien ?

  =item le programmeur :

  -- Il n'y a  pas de limite dans le programme  lui-même. Compte tenu du
  volume du résultat et du temps  pour traiter une tour de Hanoï avec de
  nombreux disques, tu craqueras avant le programme.

  =item l'utilisateur :

  -- Il y a d'autres paramètres ?

  =item le programmeur :

  -- Oui, il  y a  deux paramètres facultatifs,  C<-a> et C<-d>.  Il est
  possible  de les spécifier  simultanément. Mais  il faut  spécifier au
  moins l'un des deux.

  =item l'utilisateur :

  -- Attends, laisse moi deviner. C'est 
  départ / arrivée ?
  analogique / digital ? 
  attaquant / défenseur ?
  anticyclone / dépression ? 
  AC / DC ?
  AC-DC / Deep Purple ?
  AC-47 / DC-3 ?
  démarrage / arrêt ?
  augmentation / diminution ?
  ajouter / déduire ?
  addition / division ?
  décollage / atterrissage ?
  amélioration / détérioration ?
  ancêtre / descendant ?
  approcher / distancer ?
  alimentation / digestion ?
  accélération / décélération ?
  ascension / descente ?
  descendre / abattre ?
  abattre / dézinguer ?
  dézinguer / assassiner ?
  assassiner / dessouder ?
  averse / déluge ?
  doux / amer ?
  apéritif / digestif ?
  amuse-gueule / dessert ?
  avaler / déglutir ?
  désinfectant / alcool à 90 ?
  angélique / démoniaque ?
  apôtre / disciple ?
  digitaline / atropine ?
  appétit / dégoût ?
  aisé / difficile ?
  aimer / détester ?
  algarade / différend ?
  adulation / dévotion ?
  attentif / distrait ?
  assiduité / dilettantisme ?
  agglutiné / dispersé ?
  accidentel / délibéré ?
  aride / détrempé ?
  abrité / découvert ?
  anarchie / dictature ?
  allons enfants de la patrie / debout les damnés de la terre ?
  arrestation / détention ?
  adepte / dissident ?
  avidité / désintérêt ?
  amusant / déprimant ?
  astuce / débrouillardise ?
  doit / avoir ?
  assis / debout ?
  à genou / debout ?
  accroupi / debout ?
  allongé / debout ?
  à plat ventre / décubitus dorsal ?
  accusatif / datif ?
  anodin / dangereux ?
  affirmation / démenti ?
  accoutrement / déguisement ?
  droite / arabesque ?
  axone / dendrite ?
  déformation / anamorphose ?
  autocar / diligence ?
  antenne de TV / décodeur Canal + ?
  dé à coudre / aiguille à tricoter ?
  anorak / doudoune ?
  dais / auvent ?
  alambic / distillerie ?
  départementale / autoroute ?
  département / arrondissement ?
  aéroplane / dirigeable ?
  avion / drone ?
  aileron / dérive ?
  aviso / destroyer ?
  avant / derrière ?
  arrière / devant ?
  aujourd'hui / demain ?
  avant-hier / demain ?
  antan / dans quelques années ?
  autrefois / dans le futur ?
  arroser / déshydrater ?
  alcoolisme / delirium tremens ?
  accoutumance / dépendance ?
  abus / dangereux ?
  ardoise / dette ?
  alternatif / deux cent vingt ?
  ampérage / différence de potentiel ?
  décamètre / angström ?
  année-lumière / décimètre ?
  ASA 100 / DIN 21 ?
  amours / délices et orgues ?
  déclaration des revenus / avis d'imposition ?
  Défense (ministère de la) / Armées (ministère des) ?
  attention / danger ?

  =item le programmeur :

  -- Atchoum !

  =item l'utilisateur :

  À tes souhaits / Dieu te bénisse. Tu veux un Aspro ou un Doliprane ?
  Bon, je reprends :
  Atchoum / Dormeur ? 
  Amora (moutarde) / Dijon (moutarde de) ?
  Dépêche-toi, tu traînes / Attends un peu, tu vas trop vite ?
  Darwin / Awards ?
  dessin / animé ?
  apogée / déclin ?
  apostrophe / double-quote ?
  dollar / arrobase ?
  Acme::Anything / Devel::DProf ?
  DateTime::Calendar::FrenchRevolutionary / Acme::MetaSyntactic::soviet ?
  déclinaison / ascension droite ?
  aptère / diptère ?
  Aiguille du Midi (3842 m) / Dôme du Goûter (4304 m) ?
  Allemagne / Deutschland ?
  Artémis / Diane ?
  Abondance (corne d') / Danaïdes (tonneau des) ?
  Ases / Dises ?
  Airbus / Dassault ?
  Aéropostale / Didier Daurat ?
  Agathe / Diamant ?
  Ariane V / Delta IV ?
  Atlantis / Discovery ?
  Ariane / Dédale ? 
  Anouk Aimée / Danielle Darrieux ? 
  Dietrich (Marlene) / Ange Bleu (l') ?
  André Raimbourg, dit Bourvil / de Funès (Louis) ?
  Alain Chabat / Dominique Farrugia ?
  Anny / Duperrey ?
  Alain / Delon ?
  Djohnny / Alliday ?
  Anne-Aymone / Danièle ?
  Alexandre / Dumas ?
  Aramis / d'Artagnan ?
  Aurore / Dupin ?
  Alfred / de Musset ?
  Alfred / de Vigny ?
  Alfred / Dreyfus ?
  Alphonse / Daudet ?
  Alphonse Allais / Denis Diderot ?
  Arouet le jeune, dit Voltaire / Ducasse Isidore, dit Lautréamont ?
  Alexandre de Macédoine / Darius de Perse ?
  alexandrin / décasyllabe ?
  Alexandra David Néel l'exploratrice / Dora l'exploratrice ?
  Agnès Sorel / Diane de Poitiers ?
  duc / archiduc ?
  Argine / Dame de trèfle ?
  David, roi de pique / Alexandre, roi de trèfle ?
  Delenda est Carthago / Alea jacta est ?
  Aragorn, roi de Gondor / Dénéthor, intendant de Gondor ?
  Angband / Dol Guldur ?
  Anduril / Dard ?
  Anakin Skywalker / Darth Vader ?
  Arrakis / Dune ?
  Disque-monde / A'Tuin la grande ?
  Armageddon / Deep Impact ?
  Amicalement vôtre / Dangereusement vôtre ?
  Apocalypse Now / Deer Hunter ?
  Dungeons and Dragons Basic Set / Advanced Dungeons and Dragons ?
  Avalon Hill / Decision Games ?
  Austerlitz / Défieux (Jean-Pierre) ?
  Air Force / Dauntless ?
  Air Superiority / Desert Eagles ?
  Anvil / Dragoon ?
  Dieppe (août 1942) / Arromanches (juin 1944) ?
  Davout / Auerstädt ?
  active / demi-solde ?
  Andrea / Doria ?
  Diogène / Aristote ?
  autobus de la ligne S / dandy avec un long cou ?
  Disparition (la) / Anton Voyl et Amaury Conson ?
  Dac (Pierre) / A moëlle (l'Os) ?
  Drôles de dames / Angels (Charlie's) ?
  Avanies et Framboises / Destins (mamelles du) ?
  Dargaud Éditions / Albert-René Éditions
  Averell Dalton / Dead or Alive ?
  Douglas Hofstadter / Achille et la Tortue ?
  Douglas Adams / Arthur Dent ?
  ADN / DNA ?
  Don't Panic! / Aaaaaaaaaaah
                             h
                              h
                               h
                                h
                                 h
                                  h
                                   ! ?
  doigt / aurteil ?
  arrêt / darche ? 
  asculin / déminin ?
  affirmatif / dégatif ? 
  aoui / dnon ? 
  asel / dpoivre ? 
  aouvert / dfermé ? 

  =item le programmeur :

  -- Non, c'est « art ASCII » ou bien « directives ».

  =item l'utilisateur :

  -- Et l'ancienne codification C<-d> C<-g> était légèrement ambiguë ?

  =item le programmeur :

  -- Oui, l'ambiguïté de l'ancienne  codification avait le défaut d'être
  trop légère.

  =back

Et maintenant, comme pour un DVD du commerce, vous pouvez lire le bonus de la communication-éclair.

Texte diffusé sous la license CC-BY-NC-ND : Creative Commons avec clause de paternité, excluant l'utilisation commerciale et excluant la modification.

Accueil