Solveur de Scrabble

Né d'un pari un peu fou avec Gnieark, ce solveur de Scrabble est écrit entièrement en Bash.

Par solveur de Scrabble, j'entends un programme qui, étant données une liste de lettres (avec ou sans lettres blanches), va retourner la liste de tous les mots possibles. Il n'est donc pas question ici de reproduire un plateau de Scrabble ou de présenter un calcul des points en fonction des lettres.

Ce billet a pour but d'expliquer le fonctionnement de ce programme.

Téléchargement

Télécharger ScrabbleSolver

Attention : voir les pré-requis ci-dessous.

Pré-requis

Ce programme nécessite l'utilitaire dialog. Il est possible de l'installer sous Debian via la commande apt-get install dialog.

Hormis cette contrainte, il utilise également les outils grep, sed, tr et cut. S'agissant d'outils standard, il sont généralement déjà installés sur votre machine (si c'est un GNU Linux bien sûr).

Dernier point : s'agissant d'un script Bash, celui ne fonctionnera pas si vous cherchez à l'exécuter en tapant sh scrabblesolver.

Copies d'écran

Les 2 copies d'écrans suivantes présentent la saisie des lettres et l'affichage des resultats.

Interface de saisie des lettres

Interface d'affichage des résultats

Préparation du fichier ODS6.txt

Pour disposer de temps de réponse très bas de la part d'un script Bash, il faut se reposer sur un nombre de processus réduit et des utilitaires performants. Dans le cas présent, tout le travail de recherche est confié à l'utilitaire egrep. Il faudra donc lui donner la chaîne de recherche correspondant aux lettres fournies par l'utilisateur et préparer le fichier ODS6.txt.

Ce fichier contient la liste de tous les mots possibles et autorisés au Scrabble français :

Afin de faciliter et optimiser la recherche, le script utilisera des séquences de lettres dans l'ordre alphabétique. Par exemple, ELEPHANT sera traité sous la forme AEEHLNPT. Le script Bash suivant permet de générer la liste préparée :

cat ODS6.txt | while read ligne
do
    printf '%s' "$ligne" | sed 's/\(.\)/\1\n/g' | sort | tr -d '\n'
    echo
done

Attention : l'exécution de ce script peut prendre de 1 heure à 2 heures. Cela est dû à l'utilisation de plusieurs processus pour le traitement d'une seule ligne.

La ligne cat ODS6.txt | while read ligne lit le fichier ODS6.txt ligne par ligne dans la variable ligne.

La ligne printf '%s' "$ligne" | sed 's/\(.\)/\1\n/g' | sort | tr -d '\n' réalise les opérations suivantes :

La ligne echo insère un retour chariot.

Ainsi la chaîne ELEPHANT subit le traitement suivant (\n doit être compris comme un retour chariot et non comme deux caractères) :

Ce n'est malheureusement pas suffisant pour notre solveur. Si cette forme permet de retrouver rapidement les mots contenants certaines lettres, elle ne permet pas de retrouver le mot lui-même ! Pour cela, il faut fusionner la liste originale et la liste préparée. À ce titre la commande paste se révèle particulièrement utile. Par exemple :

paste -d '=' file1 file2

Si file1 contient les lignes :

A
B
C

Et file2 les lignes :

1
2
3

L'exemple produira la sortie suivante :

A=1
B=2
C=3

Cela nous permet de créer le fichier ODS6.prep.txt qui contiendra des lignes de la forme :

AEEHLNPT=ELEPHANT

Le fichier ODS6.prep.txt ainsi produit est directement utilisable par le script scrabblesolver.

Explications du script

La fonction addchar

La fonction addchar prend une chaîne de caractère et ajoute un caractère après chaque caractère de cette chaîne.

Exemple :

addchar "abc" "=" # Retourne la chaîne "a=b=c="

Cette opération est utile dans le cadre de ce programme car sa principale activité va être de constituer une chaîne de caractère à destination de la commande grep.

Elle pourrait être écrite avec une commande sed mais elle fait partie du processus d'optimisation.

La boucle principale parcourt la chaîne caractère après caractère. Pour chaque caractère rencontré, elle affiche le caractère lu concaténé au caractère passé en paramètre. La boucle repose complètement sur des fonctionnalités de Bash.

La boucle for fait varier $i de 0 au nombre de caractères de la chaîne (${#string}). Pour extraire le caractère de la chaîne, elle utilise la construction ${string:start:length} qui exrait une sous-chaîne d'une chaîne de caractères. Voici la boucle :

for ((i=0; i<${#string}; i++))
do
    printf '%s' "${string:$i:1}$char"
done

Je parlais d'optimisation tout à l'heure : cette fonction n'utilise aucun processus supplémentaire pour s'exécuter car elle repose uniquement sur des fonctionnalités embarquées de Bash.

Utilisation de dialog

Le script utilise dialog pour proposer une interface utilisateur. Cela représente deux appels distincts, l'un pour demander les lettres à l'utilisateur, l'autre pour afficher les résultats de la recherche :

La ligne suivante affiche une boîte de dialogue demandant à l'utilisateur de saisir les lettres/joker. L'utilitaire dialog envoie la saisie de l'utilisateur sur la sortie d'erreur que l'on redirige dans un fichier answer. Cela a pour effet secondaire de n'afficher aucun message d'erreur en cas d'absence de dialog sur le système :

dialog --title "Scrabble solver" \
    --inputbox "Entrez les lettres (joker=*)" 16 51 2> answer

La ligne suivante affiche la liste des résultats contenus dans un fichier results. Elle permet à l'utilisateur d'utiliser les touches fléchées pour parcourir la liste :

dialog --title "Résultats" \
    --fixed-font \
    --textbox results 0 0 2> /dev/null

Transformation de la saisie utilisateur

Tout le travail du script consiste à transformer la saisie de l'utilisateur en une expression rationnelle utilisable par egrep.

Nettoyage et préparation

La première étape nettoie et prépare la liste des lettres. Elle ne garde que les caractères alphabétiques non accentués qu'elle passe en majuscule au besoin. De plus, les joker "*" sont remplacés par "{A..Z}" :

answers=$(cat answer | \
    tr 'a-z' 'A-Z' | # Convert letters to uppercase
    tr -d --complement 'A-Z*' | # Delete non alphabetic letters or *
    sed 's/[*]/{A..Z}/g' # Handle jokers
)

Explications :

Exemple de traitement d’une chaîne :

Création d’un motif pour egrep

Pour rechercher une chaîne composée d’une ou plusieurs lettres avec une expression rationnelle, il suffit d’ajouter un point d’interrogation ? après chaque lettre. Par exemple, en transformant ABC en A?B?C?, les mots suivants seront reconnus : A, B, C, AB, AC, BC, ABC. Cette expression rationnelle ne semble pas prendre en compte les chaînes BA, CA, CB, BAC, BCA ou CBA. Ce n’est pas un problème car, à ce stade, nous ne travaillons qu’avec des lettres triées dans l’ordre alphabétique.

Pour la gestion des jokers, le script utilise une facilité de Bash : les séquences. Si vous tapez la ligne suivante en Bash :

echo A{A..Z}C

Bash produira la sortie suivante :

AAC ABC ACC ADC AEC AFC AGC AHC AIC AJC AKC ALC AMC
ANC AOC APC AQC ARC ASC ATC AUC AVC AWC AXC AYC AZC

Ainsi Bash produit toutes les combinaisons possibles de chaînes pour la séquence donnée. La chaîne peut contenir plusieurs séquences. Cela implique qu’elles doivent être utilisées avec parcimonie. Le motif {A..Z}{A..Z} produira 676 (26×26) combinaisons !

Pour chacune des combinaisons produites il faudra intercaler un |. Dans le cadre des expressions rationnelles ce caractère indique un choix alternatif. Par exemple A|B|C sera valide pour les chaînes A, B et C.

Ces traitements mis ensembles, cela donne le code suivant :

nl=$'\n'
patterns=$(for answer in $(eval echo $answers)
do
    # Put one character per line and sort the lines
    pattern=$(sort <<< "$(addchar "$answer" $'\n')")

    # Join back the sorted lines
    pattern="$(addchar "${pattern//$nl}" '?')"
    printf '%s|' "$pattern"
done)

Explications :

Exemple de traitement d’une chaîne :

Recherche des solutions

Maintenant que l’expression rationnelle est construite, il faut la transmettre à egrep. Le fichier dans lequel rechercher se nomme ODS6.prep.txt et contient des lignes de la forme <séquence triée>=<mot>. La recherche se fait en une seule commande :

egrep "^(${patterns%|})=" ODS6.prep.txt | \
    cut -d '=' -f 2 > results

Explications :