Valérie s’est lancée dans une suite de joutes Facebookestes à grands coups de Scramble. Un tableau de 4×4 ou 5×5 avec des lettres, le but du jeu est de dénombrer tous les mots que l’on trouve dedans.
En anglais avec des amies anglophones, bonjour les corrections sur les premières parties.
Petit à petit, Valérie comble son handicap.
Finalement, qu’est-ce que jeu sinon regarder une case, puis ses voisines récursivement ? Ah oui, il ne faut pas repasser deux fois par la même case. Et à la fin il faut vérifier que les mots existent.
Bon.
On sort son Perl favori, et on précise que ce logiciel est sous GPL v3.
Pour vérifier que les mots existent, il existe des listes qui améliorent l’ordinaire du /usr/share/dict/words. Dans ce cas particulier de la liste TWL06.zip, un dos2unix permet d’enlever des sauts de lignes peu linuxiens.
On met les mots en mémoire avec un
open DICT,"< TWL06.txt";
my $dict;
while (<DICT>) {
chomp($_);
$dict->{$_}=0;
}
close(DICT);
Il reste un gros bout : parcourir le tableau pour dénombrer les mots candidats.
On commence par récupérer depuis la ligne de commande tapée par l’utilisateur le tableau en question, sous forme d’une chaîne de caractères unique.
my $string = uc(shift());
Avoir la dimension du tableau (combien de lignes = combien de colonnes) est utile par la suite :
my $dimension = int(sqrt(length($string)));
Le Scramble se joue en s’intéressant aux cases adjacentes, on définit donc la métrique (distance entre deux cases) :
sub distance {
my $x = shift();
my $y = shift();
my $dx = abs($x->[0]-$y->[0]);
my $dy = abs($x->[1]-$y->[1]);
return ($dx>$dy) ? $dx : $dy;
}
Dans ces conditions, deux cases sont adjacentes si la distance qui les sépare vaut 1. On peut alors créer un hash qui donne donne tous les voisins ($i,$j) de la case ($i0,$j0) :
sub neighbors {
my $nei;
for (my $i0=0 ; $i0<$dimension ; $i0++) {
for (my $j0=0 ; $j0<$dimension ; $j0++) {
my @a=($i0,$j0);
for (my $i=0 ; $i<$dimension ; $i++) {
for (my $j=0 ; $j<$dimension ; $j++) {
my @b=($i,$j);
$nei->{$i0.$j0}->{$i.$j}=1 if (distance(\@a,\@b)==1);
}
}
}
}
return $nei;
}
my $neighbors=neighbors();
Il nous manque encore la possibilité d’extraire la lettre d’une case donnée. On donne deux entrées possibles à cette fonction, par coordonnées (x puis y) ou en format concaténé (xy) :
sub get_str {
my $a = shift();
my $b;
unless ($b = shift()) { $b=substr($a,1,1); $a=substr($a,0,1); }
my $res = substr($string,$a+$b*$dimension,1);
$res=$res."U" if ($res eq "Q");
return ($res);
}
Au passage, on s’occupe du cas du "Q" qui apparaît toujours sous la forme "QU".
La partie récursive maintenant, celle qui se baladera dans le tableau.
my @allwords;
sub get_neighbors {
my $a = shift();
my $b = shift();
my $depth = shift();
my $word = shift();
$word->{$a.$b}=$depth;
if ($depth==0) {
push @allwords,$word;
} else {
foreach my $nei0 (keys %{$neighbors->{$a.$b}}) {
next if defined($word->{$nei0});
my $word0={};
%$word0=%$word;
my ($a0,$b0)=(substr($nei0,0,1),substr($nei0,1,1));
get_neighbors($a0,$b0,$depth-1,$word0);
}
}
return;
}
Si le mot candidat a la longueur souhaitée ($depth à 0), alors on le stocke dans le tableau @allwords en référençant sa taille, pour aider au tri plus tard).
Sinon, on s’intéresse récursivement à ses voisins.
On peut alors lancer la balade dans le tableau à partir de toutes les cases une par une, et pour toutes les longueurs de mots désirées.
Si un mot candidat est référencé dans le hash %$dict, alors on l’imprime à l’écran.
for (my $wordsize=7 ; $wordsize>2 ; $wordsize–) {
for (my $i0=0 ; $i0<$dimension ; $i0++) {
for (my $j0=0 ; $j0<$dimension ; $j0++) {
@allwords=();
my $word;
get_neighbors($i0,$j0,$wordsize,$word);
foreach my $myword ( @allwords ) {
my @thewords;
@thewords=sort { $myword->{$b} <=> $myword->{$a} } keys %$myword;
my $myword = join("",map { get_str($_) } @thewords);
print($myword,"\n") if (defined($dict->{$myword}));
}
}
}
}
Si on appelle ce script break_scramble, alors on peut trouver les mots anglais entre 3 et 7 lettres compris dans le tableau
| a | b | c | d |
| e | f | g | h |
| i | j | k | l |
| m | n | o | p |
$ ./break_scramble abcdefghijklmnop
KNIFE
PLONK
MINK
FINK
FINO
JINK
GLOP
KNOP
KOJI
Des optimisations possibles ? Oui, plein. Pour commencer, éviter de repasser par toutes les tailles de mots possibles et imaginables.
Mais en attendant, il devient difficile de perdre les duels Scramble même avec les 30 secondes d’exécution sur un pauvre Pentium 4 HT.
