Trichons au jeu des anagrammes vivants

L'auteur de ce sujet a trouvé une solution à son problème.
Staff
Auteur du sujet

Atelier : Trichons au jeu des anagrammes vivants !

Avez-vous vu le jeu "Les anagrammes vivants", dans le BàS ?

Si non, voici un petit rappel des règles :

J'ai un petit jeu à vous proposer dont le principe est très simple. L'idée étant que je donne un mot de départ et un mot d'arrivée, et vous devez trouver le chemin entre les deux.

Exemple :

Mot de départ : MOT
Mot d'arrivée : ZESTE
CHEMIN : MOT -> MET -> METS -> TEST -> ZESTE

Les règles.

Comme vous l'avez vu dans l'exemple, pour chaque changement vous avez le droit d'effectuer une seule des actions suivantes sur votre mot.

  • changer une des lettres du mot par une lettre de l'alphabet Français
  • ajouter une lettre en plus dans le mot
  • enlever une lettre du mot

La seule condition à respecter est de s'assurer que chaque mot est un mot de la langue Française (conjugaison, infinitif, nom propres et non communs autorisés), et pour cela vous avez la possibilité à chaque tour de remplacer un mot pas son anagramme (cf. le passage de "METS" à "TEST" dans l'exemple).

Et si on trichait ?

Ce jeu n'est pas spécialement simple, et on se pose toujours la question de savoir s'il y a une meilleure solution ou non.

Alors pourquoi ne pas tricher et faire un programme qui découvre les solutions pour nous ? En plus, ça fait un bon exercice et la variété de solutions possibles en fait un choix parfait pour comparer les différentes idées !

Pour commencer, il nous faut une liste de mots

Je vous propose d'utiliser ce fichier, qui est tirée de ce site mais qui a été ré-enregistrée en UTF-8.

Ensuite, que faire ?

Eh bien, réfléchir au problème. Qu'est-ce qu'on a besoin de faire ici ? En fait, répondre à plusieurs problèmes ?

  1. Comment déterminer les mots autorisés à partir d'un mot donné ? (ce qui correspond à avancer d'une étape sur le chemin)
  2. Comment trouver un chemin valide ? (qui ne contient que des mots existants)
  3. Comment trouver le plus court chemin ? (ou plus exactement, un plus court chemin, puisqu'il en existe vraisemblablement plusieurs)
  4. Comment faire tout ceci dans un temps raisonnable ?
  5. Et bien sûr, comment récupérer les mots voulus et afficher le résultat à l'utilisateur ?

Attention aux subtilités !

Dans le désordre :

  • Le fichier contient des majuscules et des accents, or dans le jeu majuscules et accents ne comptent pas
  • Le fichier contient 336531 entrées, ce qui fait qu'il va falloir soigner un minimum l'algorithme pour réussir à calculer ça dans un temps raisonnable.
  • L'autorisation des anagrammes complique sensiblement la recherche des mots possibles
  • Il y a très probablement plusieurs "plus courts chemins" possibles. Un seul suffit.

Sisi, c'est possible !

Parce que je n'aime pas lancer un atelier sans avoir d'abord vérifié la faisablilité… je vous annonce que c'est faisable !

Démonstration avec une solution théorique à la très belle réponse de Ishimaru Chiaki :

1
2
Chemin trouvé : [adherence, deracinee, decernai, decornai, caliorne, clouerai, aquicole, coquille]
Calculé en 25105 ms

Je posterai ma réponse un peu plus tard, il faut que je la nettoie et j'ai un problème de performances bizarre quand la solution n'est pas rapide à trouver.

Pour ceux qui veulent un challenge, ou tout simplement tester les limites de leur programme, essayez de trouver un chemin entre ire et hydrothérapique. Il en existe un dans le fichier que j'ai donné, d'une longueur minimale de 26 !

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
ire
aire
seria
caries
criames
miracles
morcelais
compileras
compulserai
compliqueras
compliquates
cytoplasmique
spasmolytique
asymptotiques
hypostatiques
hypostatique
hypothequais
hypothequas
hypotheques
hypothequees
deshypotheque
deshypothequer
deshypothequera
deshypothequerai
hydrotherapiques
hydrotherapique

Des questions !

Je suis débutant, je peux participer quand même ?

Bien sûr ! La liste dans le paragraphe "Ensuite, que faire ?" donne des pistes de trucs à faire, à peu près par difficulté progressive.

L'important reste de participer et d'apprendre !

On fait ça en quel langage ?

Celui que vous voulez ! Cela dit, ça risque d'être délicat à faire dans certains langages un peu trop exotiques ou consommateurs en ressources. C'est vous qui voyez.

Édité par SpaceFox

Staff

J'ai un algorithme je crois linéaire (oui vers 4h du matin j'ai des doutes) que je n'ai pas encore implémenté :

Soit $d$ le mot de départ et $a$ le mot d'arrivé. Pour chaque mot $x$, calculer la distance de $x$ par à $d$. C'est à dire le nombre d'échange minimal qu'il faudrait pour passer de $x$ à $d$. Puis à partir de $d$ faire un DFS sur le graphe généré où les mots sont les sommets et il y a une arrête entre deux mots si la longueur vaut $1$. C'est algo est pas génial si le mot que l'on suit s'éloigne du mot d'arrivé $a$. Je pense qu'il faut donc utiliser une heuristique, donc calculer la distance de chaque mots par rapport à $a$ et prendre un chemin qui réduit cette distance en priorité. Cela demande donc de faire une passe sur la liste de mot pour calculer les distances, ce qui devrait être assez rapide puis de faire le parcours associé. Avec environ $330000$ mots, je pense qu'on peut rusé un peu sur le DFS pour pas s'encombrer avec des mots inutiles. A implémenter…

+0 -0

Hello!

Très bonne idée que ce petit jeu. Avant de me lancer dans la réalisation de mon idée, je voulais savoir si ce n'était pas "tricher" (ton jeu, tes règles) que d'agir ainsi:

-Lancer un programme UNE fois sur la liste des mots qui créera un graphe mettant en relation tous les mots où la distance Levenshtein est de 1. Avec un complexité O(n^2), très parallélisable et donc potentiellement rapide, ce programme crée n (avec n: nombre de mots) noeuds qui contiennent chacun la topologie complète du réseau. Je souligne que ce programme sera lancé une fois par liste de mots et prendra, une estimation du pouce fois l'articulation, environ 15 [s].

-A chaque nouvelle requête, faire une recherche dans le graphe. (Vu que chaque noeud contient la topologie du réseau, chaque requête devrait être extrêmement rapide.)

Cela reprend l'idée de Saroupille, mais sépare juste la tâche création graphe/recherche. (Car le graphe est tout à fait indépendant de la requête.)

Édité par Tom Tenv

D.W. "All problems in CS can be solved by another level of indirection" K.H. "…except for the problem of too many layers of indirection."

+0 -0
Staff

Hello!

Très bonne idée que ce petit jeu. Avant de me lancer dans la réalisation de mon idée, je voulais savoir si ce n'était pas "tricher" (ton jeu, tes règles) que d'agir ainsi:

-Lancer un programme UNE fois sur la liste des mots qui créera un graphe mettant en relation tous les mots où la distance Levenshtein est de 1. Avec un complexité O(n^2), très parallélisable et donc potentiellement rapide, ce programme crée n (avec n: nombre de mots) noeuds qui contiennent chacun la topologie complète du réseau. Je souligne que ce programme sera lancé une fois par liste de mots et prendra, une estimation du pouce fois l'articulation, environ 15 [s].

-A chaque nouvelle requête, faire une recherche dans le graphe. (Vu que chaque noeud contient la topologie du réseau, chaque requête devrait être extrêmement rapide.)

Cela reprend l'idée de Saroupille, mais sépare juste la tâche création graphe/recherche. (Car le graphe est tout à fait indépendant de la requête.)

Tom Tenv

J'y ai pensé, mais ce qui m'a paru étrange c'est le faite de stocker à la louchent $350000^2$ entiers. En supposant que tu stockes ça dans un char par exemple, ça fait tout de même 122Go de données.

C'est juste ensuite impossible de créer ce graphe. C'est pour ça que je proposais un prétraitement un peu moins lourd. Mais déjà assez volumineux.

Edit : SpaceFox, tu as utilisé quelle approche ?

Édité par Saroupille

+0 -0
Staff

Bon j'ai implémenté une solution naïve en python avec une simple optimisation. ça marche, mais forcément les chaines trop longues sont plus difficiles (voire impossibles sur un faible ordi).

Code :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
# coding: utf-8
import operator
import time
import unicodedata

depart = "mot"
arrive = "zeste"
fichier = 'liste.de.mots.txt'

liste_lettre = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q','r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
nbre_anag=0
nbre_leven=0
nbre_getc=0
load = []
#charger le dictionnaire en mémoire
print("debut du chargement du dictionnaire")
source = open(fichier, "r")
for f in source.readlines():
  ch = f.lower().strip()
  load.append(unicodedata.normalize('NFKD', ch.decode("utf-8")).encode('ascii', 'ignore'))
print("fin du chargement")

def levenshtein(s1, s2):
  if len(s1) < len(s2):
      return levenshtein(s2, s1)
  if len(s2) == 0:
      return len(s1)

  previous_row = xrange(len(s2) + 1)
  for i, c1 in enumerate(s1):
      current_row = [i + 1]
      for j, c2 in enumerate(s2):
          insertions = previous_row[j + 1] + 1
          deletions = current_row[j] + 1
          substitutions = previous_row[j] + (c1 != c2)
          current_row.append(min(insertions, deletions, substitutions))
      previous_row = current_row

  return previous_row[-1]

def anagrammes(mot):  
  anags = ['']; m = 0
  for c in set(mot):
      for _ in range(mot.count(c)):
          anags = [s[:k+1]+c+s[k+1:] for s in anags for k in range(s.rfind(c),m)]
          m += 1
  fin = []
  for anag in anags:
    if anag.lower() in load:
      fin.append(anag)
  return fin

def get_child(mot_depart, mot_arrive, chemin=[]):
  #ajout d'une lettre
  add_list=[]
  for lettre in liste_lettre:
    for i in range(0,len(mot_depart)+1):
      ch = "{}{}{}".format(mot_depart[:i],lettre,mot_depart[i:])
      if ch.lower() in load:
        add_list.append(ch)
  #retrait d'une lettre
  sup_list=[]
  for lettre in liste_lettre:
    for i in range(0,len(mot_depart)):
      ch = "{}{}".format(mot_depart[:i],mot_depart[i+1:])
      if ch.lower() in load:
        sup_list.append(ch)
  #modification d'une lettre
  maj_list=[]
  for lettre in liste_lettre:
    for i in range(0,len(mot_depart)):
      ch = "{}{}{}".format(mot_depart[:i],lettre,mot_depart[i+1:])
      if ch.lower() in load:
        maj_list.append(ch)
  
  #merge des enfants possibles
  list_trait = add_list + sup_list + maj_list
  
  #anagrammes sur toutes les combinaisons
  childs = []
  for word in list_trait:
    ang = anagrammes(word)
    if len(ang) > 0:
      childs=childs+ang
  childs = list(set(childs))
  
  #evite de repasser par un chemin deja explore
  for ch in chemin:
    if ch in childs:
      childs.remove(ch)
  
  #tri par distance de levenstein
  dcs = {}
  for child in childs:
    d = levenshtein(child, mot_arrive)
    dcs[child]=d
  dcs = sorted(dcs.iteritems(), key=operator.itemgetter(1))
  
  #recursivite
  for (child, d) in dcs:
    chemin.append(child)
    if mot_arrive.lower() != child:
      print(chemin)
      return get_child(child, mot_arrive, chemin)
    break
  return chemin

if depart.lower() in load:
  if arrive.lower() in load:
    tps1 = time.clock() 
    print get_child(depart,arrive,["mot"])
    tps2 = time.clock()
    print("Temps d'execution : {} sec".format(str(tps2 - tps1)))
  else:
    print "Le mot d'arrivee n'est pas dans le dictionnaire"
else:
  print "Le mot de depart n'est pas dans le dictionnaire"

Résultat :

1
2
3
4
5
6
7
8
9
firm1@firm-station:~/Bureau$ python vive.py
debut du chargement du dictionnaire
fin du chargement
['mot', 'met']
['mot', 'met', 'est']
['mot', 'met', 'est', 'lest']
['mot', 'met', 'est', 'lest', 'leste']
['mot', 'met', 'est', 'lest', 'leste', 'zeste']
Temps d'execution : 24.84248 sec

Voila, juste histoire d'être le premier a poster un code fonctionnel. Je mettrait à jour après optimisation.

EDIT : Tom, pour info, vu la taille du dictionnaire, je crois que tu auras du mal à arriver à quelque chose en tenant le coup d'une matrice en mémoire.

Édité par firm1

Coucou,

Pour inaugurer un peu cet atelier, je propose un premier jet. Un premier jet lent, mais un premier jet quand même. L'idée repose sur un graphe de 300K nœuds et de l'ordre de $M^2$ ($M$ = nombre de caractères dans l'alphabet, et accessoirement, à une unité près, la longueur max d'une chaîne) transitions (on choisit éventuellement un caractère à supprimer et éventuellement un caractère à ajouter).

À cela on rajoute un facteur $\log{N}$ ($N$ = taille du dico) pour pouvoir trouver, pour chaque transition, si le mot qu'on crée existe effectivement (dichotomie dans le dictionnaire pour ça). Ça doit pouvoir s'améliorer avec un coup de hash, à voir. Pour gérer correctement les anagrammes, on se débrouille pour garder des chaînes triées (par exemple ZESTE devient EESTZ), et on stocke une version du dictionnaire normalisée de cette manière.

Enfin, pour trouver un plus court chemin d'un mot A à un mot B, on fait un parcours en largeur, et on stocke, à chaque découverte d'un nœud, un identifiant de précédent pour pouvoir reconstruire le chemin à la fin.

La seule partie un peu ad-hoc dans l'algo est sans doute la gestion des transitions. Pour éviter les gérer en $M^3$ (algo qui consisterait à effectuer réellement la construction d'une nouvelle chaîne en supprimant et en insérant les caractères voulus), on fait ça en amorti de la manière suivante :

  • Pour chaque position du caractère à supprimer (on aura un cas particulier, dans lequel on ne veut en supprimer aucun).
  • On crée une chaîne, en supprimant ledit caractère Ensuite, on parcourt en parallèle la chaîne elle-même et les caractères à ajouter dans l'ordre alphabétique, en décalant d'une lettre vers la gauche à chaque fois pour garder la chaîne triée.

Prenons « AEGHI ». Par exemple, les transitions pour EGHI (soit AEGHI auquel on a supprimé un A) : AEGHI ; BEGHI ; CEGHI ; DEGHI ; EEGHI; EFGHI (on décale le « E » d'une position vers la gauche car F > E) ; EGGHI ; EGHHI (on décale le « G ») ; EGHII (on décale le « I ») ; EGHIJ ; EGHIK ; etc.

Bref, version en C, pas très élégante (c'est surtout pour l'algo, le reste faut pas trop regarder).

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NOM_DIC "out"

enum {
  N = 323603,
  M = 27
};

static struct Paire {
  char init[M], triee[M];
} dic[N];

static int file[N], deb, fin;
static int prec[N];

static int comparer_caracteres(const void *p, const void *q) {
  char a = *(const char *)p, b = *(const char *)q;
  return a < b ? -1 : (a > b);
}

static int comparer_paires(const void *p, const void *q) {
  const struct Paire *a = p, *b = q;
  return strcmp(a->triee, b->triee);
}

static void inserer_element(int v) {
  file[fin] = v;
  fin = (fin + 1) % N;
}

static int recuperer_element() {
  int v = file[deb];
  deb = (deb + 1) % N;
  return v;
}

static int trouver_id(const char *s) {
  int bas = 0, haut = N - 1;
  
  while (bas <= haut) {
      int mil = (bas + haut) / 2;
      int res = strcmp(dic[mil].triee, s);
      if (res < 0) bas = mil + 1;
      else if (res > 0) haut = mil - 1;
      else return mil;
  }
  
  return -1;
}

static void ajouter_transition(const char *s, int p) {
  int id = trouver_id(s);
  if (id == -1 || prec[id] != -2) return;
  prec[id] = p;
  inserer_element(id);
}

static void generer_transitions(int id) {
  char t[M]; 
  char *s = dic[id].triee;
  size_t n = strlen(s), i;
  
  for (i = 0; i <= n; ++i) {
      size_t m = 1, j;
      int c;
      t[0] = ' ';
      
      for (j = 0; j < n; ++j)
          if (j != i) t[m++] = s[j];
      
      t[m] = '\0';
      j = 0;

      for (c = 'a'; c <= 'z'; ++c) { // ASCII-compatible
          if (c == s[i]) continue;
      
          while (j != m - 1 && c > t[1 + j]) {
              t[j] = t[1 + j];
              ++j;
          }
          
          t[j] = c;
          ajouter_transition(t, id);
      }
      
      if (i != n) {
          t[m - 1] = '\0';
          ajouter_transition(t, id);
      }
  }
}

static void lire_dictionnaire() {
  FILE *fdic = fopen(NOM_DIC, "r");
  char s[M];
  size_t n = 0;
  
  if (fdic == NULL) return;
  
  while (fgets(s, sizeof s, fdic) != NULL) {
      size_t m = strlen(s);
      s[m - 1] = '\0';
      strcpy(dic[n].init, s);
      qsort(s, m - 1, 1, comparer_caracteres);
      strcpy(dic[n++].triee, s);
  }
  
  fclose(fdic);
  qsort(dic, N, sizeof *dic, comparer_paires);
}

static void ecrire_resultat(int id, const char *src, const char *dst) {
  static int resultat[N];
  size_t n = 0, i;
  
  while (id != -1) {
      resultat[n++] = id;
      id = prec[id];
  }
  
  puts(src);
  for (i = n - 2; i > 0; --i) puts(dic[resultat[i]].init);
  puts(dst);
}

static void generer_version_triee(char *triee, const char *src) {
  strcpy(triee, src);
  qsort(triee, strlen(triee), 1, comparer_caracteres);
}

int main(void) {
  char src[M], dst[M], srctriee[M], dsttriee[M];
  int i, id = 0, trouve = 0;
  
  lire_dictionnaire();    
  scanf("%s %s", src, dst);
  generer_version_triee(srctriee, src);
  generer_version_triee(dsttriee, dst);

  for (i = 0; i < N; ++i) prec[i] = -2;
  ajouter_transition(srctriee, -1);

  while (deb != fin) {
      id = recuperer_element();
      
      if (strcmp(dic[id].triee, dsttriee) == 0) {
          trouve = 1;
          break;
      }
      
      generer_transitions(id);
  }
  
  if (trouve)
      ecrire_resultat(id, src, dst);
  else
      puts("Aucun chemin");
      
  return 0;
}

Ah, et pour les accents, comme c'est un peu soulant en C, le fichier est d'abord passé par la phase prétraitement :

1
2
3
4
5
6
7
#!/bin/bash
declare -a SRC=( é è ê ô î ù â à ç )
declare -a DST=( e e e o i u a a c )
for i in {0..8}
do
  sed -i 's/'"${SRC[$i]}"'/'"${DST[$i]}"'/g' in
done

Pour ce qui est des perfs, c'est pas génial. Il faut environ 40s pour parcourir le graphe entier sur mon ordi (ce qui se produit si jamais il n'y a pas de chemin entre A et B). Comptez également 20s pour le « adherence/coquille » et 1s pour le « mot/zeste » (évidemment, plus le plus court chemin est long, plus le BFS met du temps à le trouver).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
$ time ./a.out < in
mot
ote
tee
etes
zeste

real    0m1.088s
user    0m1.056s
sys 0m0.028s

Par ailleurs, il y aurait mieux que proposé sur le sujet initial pour « Sobre -> Ivre ».

1
2
3
4
5
6
7
8
9
$ time ./a.out < in
sobre
rosie
rives
ivre

real    0m1.506s
user    0m1.476s
sys 0m0.024s

(Ne me demandez pas ce qu'est « rosie », mot que je n'ai trouvé nulle part ailleurs que dans le fichier texte fourni.)

ÉDIT : Ah bah zut, ce n'est plus une inauguration maintenant.

Édité par Lucas-84

Est-ce que l'on compte un éventuel temps de création d'un dictionnaire alternatif1 dans le temps de réponse ? :p (Si on veut le faire en deux programmes ?)

En plus, du coup, pour l'algo du plus court chemin, on peut carrément utiliser les maths ^^


  1. dictionnaire d'anagrammes, voir, si on est taré : lier tous les mots entre eux selon les 3 règles. Un joli automate, quoi ^^ 

Édité par SylafrsOne

C'est en se plantant qu'on devient cultivé.

+0 -0

EDIT : Tom, pour info, vu la taille du dictionnaire, je crois que tu auras du mal à arriver à quelque chose en tenant le coup d'une matrice en mémoire.

firm1

C'est vrai.

J'y ai pensé, mais ce qui m'a paru étrange c'est le faite de stocker à la louchent 3500002 entiers. En >supposant que tu stockes ça dans un char par exemple, ça fait tout de même 122Go de données.

C'est juste ensuite impossible de créer ce graphe. C'est pour ça que je proposais un prétraitement un peu >moins lourd. Mais déjà assez volumineux.

Saroupille

Toutafè.

Une option viable et de stocker chaque noeud et tous ces anagrammes d'ordre '1' (Avec une distance de Levenshtein < 2). Le fichier reste d'une taille convenable et il ne reste plus qu'à faire une BFS. (Ou DFS, j'ai pas encore très bien réfléchi à ce qui était le plus rapide.)

Ce qui est très long avec cette approche, c'est de produire le graphe et… J'ai pas la patience d'attendre tout ce temps. (Il a fallu 30 minutes pour faire 5% du dictionnaire pour produire un fichier de 1 MB. Donc une taille totale estimée de 20 MB, ce qui reste relativement faible et tout à fait chargeable dans la mémoire principale pour les futures computations, pour un temps de création de 10 heures, ce qui, pour moi est mon ordi, est beaucoup-beaucoup-beaucoup trop.)

Bravo à nos deux amateurs de lettres! =D

Édité par Tom Tenv

D.W. "All problems in CS can be solved by another level of indirection" K.H. "…except for the problem of too many layers of indirection."

+0 -0

firm1 j'ai un petit souci avec ton code : au chargement du dictionnaire, le code plante car il ne trouve pas le fichier.
Pourtant le fichier est dans le même répertoire du code et a le même nom.

Merci à toi.

Je te met l'erreur si ça peut t'aider :

1
2
3
4
5
debut du chargement du dictionnaire
Traceback (most recent call last):
  File "C:\Users\Baptiste\Desktop\Algo\Algo.py", line 17, in <module>
    source = open(fichier, "r")
FileNotFoundError: [Errno 2] No such file or directory: 'listedemots.txt'

Édité par baptisteguil

Portfolio photo : http://pixle-photographie.blogspot.fr/ | Tapé en bépo

+0 -1

Très sympa, j'avais pas vu le jeu dans le BàS, je vais aller y faire un tour.

Et c'est plutôt marrant, parce que je cherche à améliorer mes compétences en shell, et je trouve que cet exercice s'y prête particulièrement bien, quoique les perds risquent de ne pas être au rendez-vous.

Je m'y mets si j'ai le temps, je poste si j'aboutis à quelque chose. :)

(P.S. : Sympa de le proposer quelque soit le langage :) )

Staff
Auteur du sujet

C'est amusant, Lucas-84, on a des idées qui se ressemblent !

Attention, spoiler d'une solution qui marche !


Voici une solution implémentée en Java 8. Elle est sans doute améliorable, mais elle me garantit le plus court chemin dans un temps raisonnable (moins d'une minute pour trouver qu'il n'y en a pas).
J'ai la flemme de l'améliorer, je l'implémenterai plutôt en Ceylon, pour voir ce que vaut ce langage.

Personnellement j'ai découpé le problème en 2 sous-problèmes distinctes :

  1. Comment trouver les mots autorisés ?
  2. Comment trouver le plus court chemin entre 2 mots ?

Trouver les mots autorisés

Le problème, c'est la gestion des anagrammes.

Une solution simple et efficace est de se rendre compte que 2 anagrammes sont identiques si on trie les lettres des mots par ordre alphabétique (exemple : chien et niche donnent cehin). J'ai donc une classe qui me permet de garder cette information, et de retrouver tous les anagrammes possibles d'un mot en entrée :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package info.kisai.anagrams;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;


public class Anagrams {

  private Map<String, Set<String>> data = new HashMap<>();

  public void add(String word) {

      String key = toKey(word);

      if (!data.containsKey(key)) {
          data.put(key, new HashSet<String>());
      }

      data.get(key).add(word);
  }

  public Set<String> getAnagramsOf(String word) {
      return data.get(toKey(word));
  }

  private static String toKey(String in) {

      char[] chars = in.toCharArray();
      List<Character> list = new ArrayList<>(chars.length);
      StringBuilder sb = new StringBuilder(chars.length);

      for (char c : chars) {
          list.add(c);
      }

      Collections.sort(list);

      for (Character c : list) {
          sb.append(c);
      }
      return sb.toString();
  }
}

Oui, la méthode toKey est très sale, mais ça marche et j'ai la flemme de trouver plus optimisé. D'autant plus qu'à priori c'est pas le point bloquant.

Ensuite, trouver tous les mots possibles à partir d'un mot donné (ce qui revient à "avancer d'une étape" dans le jeu). Les règles nous disent que tous les mots autorisés sont :

  1. Les anagrammes simples
  2. Les anagrammes du mot avec une lettre en plus
  3. Les anagrammes du mot avec une lettre en moins
  4. Les anagrammes du mot avec une lettre modifiée, n'importe la quelle

OK, implémentons ceci de la manière la plus stupide qui soit, ou presque. On remarque simplement que dans le cas de "une lettre en plus", comme on récupère tous les anagrammes, on peut se contenter de rajouter la lettre au mot.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
  private Set<String> findPossibleWords(String word) {

      Set<String> out = new AcceptNullHashSet<>();
      char[] chars = word.toCharArray();

      // Simple anagrams
      out.addAll(anagrams.getAnagramsOf(word));

      add1Char(word, out);
      remove1Char(chars, out);
      replace1Char(chars, out);

      // Avoid infinite loops...
      out.remove(word);

      return out;
  }

  private void add1Char(String word, Set<String> out) {
      for (char c = 'a'; c <= 'z'; c++) {
          out.addAll(anagrams.getAnagramsOf(word + c));
      }
  }

  private void remove1Char(char[] chars, Set<String> out) {

      int length = chars.length;
      StringBuilder sb;

      // Loop : remove letter at position i
      for (int i = 0; i < length; i++) {
          sb = new StringBuilder(length - 1);
          for (int j = 0; j < length; j++) {
              if (i != j) {
                  sb.append(chars[j]);
              }
          }
          out.addAll(anagrams.getAnagramsOf(sb.toString()));
      }
  }

  private void replace1Char(char[] chars, Set<String> out) {

      int length;
      length = chars.length;
      char[] tmpCarArray;

      for (int i = 0; i < length; i++) {
          for (char c = 'a'; c <= 'z'; c++) {
              tmpCarArray = Arrays.copyOf(chars, length);
              if (tmpCarArray[i] != c) {
                  tmpCarArray[i] = c;
                  out.addAll(anagrams.getAnagramsOf(new String(tmpCarArray)));
              }
          }
      }
  }

Remarques sur ce code :

  • L'utilisation d'un Set permet d'éviter les duplications de mots (si un mot est trouvé 2 fois, il ne sera stocké qu'une seule fois)
  • Les méthodes modifient directement le Set out
  • Dans les mots autorisés, il y a le mot de départ lui-même. On le supprime pour éviter les boucles infinies.
  • Comme la méthode getAnagramsOf de la classe Anagrams peut renvoyer null et que la méthode addAll des Set n'accepte pas null en entrée, j'ai une implémentation spéciale d'un Set qui est aussi stupide que ça :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
package info.kisai.anagrams;

import java.util.Collection;
import java.util.HashSet;

public class AcceptNullHashSet<E> extends HashSet<E> {

  @Override
  public boolean addAll(Collection<? extends E> c) {
      if (c == null) {
          return false;
      }
      return super.addAll(c);
  }
}

OK, maintenant je sais trouver tous les mots autorisés à partir d'un mot donné. Comment je trouve le plus court chemin s'il existe ?

Le problème du plus court chemin

Étude algorithmique

Les algorithmes standard de recherche de chemin dans un graphe nécessitent de connaître le graphe à l'avance, ce qui n'est pas le cas ici. Le générer nous prendrait beaucoup trop de temps.

Par contre, on a énormément de contraintes qui nous simplifient la vie : tous les chemins ont le même poids, on se contente d'un seul "plus court chemin" (le premier trouvé nous va très bien).

Supposons que l'on travaille comme des grosses brutes, et que l'on parcoure tout l'arbre en largeur :

1
2
3
4
À partir du mot de départ, je trouve tous les mots possibles. Je les enregistre dans une liste "de profondeur 1" (ce sont les mots donnés par le mot de départ).
Est-ce que le mot recherché est dans la liste ?
    Si oui, j'ai trouvé un plus court chemin.
    Si non, je parcours tous les mots possibles de ma liste de profondeur 1, et refais le même processus sur chacun d'eux

Ce qui nous donne, en version générale :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
profondeur = 0
mots à la profondeur 0 : mot de départ
Boucle infinie !
    Incrémenter la profondeur
    Pour chaque mot de la profondeur courante :
         Calculer tous les mots suivants possibles
         Les ajouter à l'ensemble des mots de la profondeur courante
    Est-ce qu'on a au moins un mot dans l'ensemble des mots de la profondeur courante ?
         Non : il n'y a pas de chemin possible. On sort de la boucle
    Est-ce que le mot cible est dans la liste des mots de la profondeur courante ?
         Oui : On a trouvé un plus court chemin ! On sort de la boucle
         Non : Dommage... on doit chercher encore plus profond, c'est parti pour un nouveau tour de boucle

OK, ça marche, ça nous garanti de trouver le plus court chemin (puisque la seule chose possible est d'agrandir le chemin en augmentant la profondeur et qu'on parcourt tous les cas possibles). Par contre, cet algorithme a deux problèmes majeurs !

  1. Comment retrouver le plus court chemin qu'on a trouvé ? On sait que c'est une combinaison d'un mot de la profondeur 1, puis de la profondeur 2, etc… jusqu'à la dernière trouvée. Mais lesquels ?
    Pour ça le plus simple est de stocker l'information "tel mot a tel autre mot pour parent", information que l'on peut récupérer dans la boucle de calcul des mots enfants mais que l'on perds après.
    L'information est à conserver indépendamment pour chaque profondeur, afin d'éviter les boucles1
  2. C'est atrocement lent. En particulier, implémenté tel quel, on teste des centaines, des milliers de fois les mêmes mots : dès qu'on arrive à la profondeur 2, on a plusieurs mots sources, qui peuvent donc nous donner plusieurs fois les mêmes mots résultats. Il faut trouver une astuce pour les tester une seule fois.
    Ici le constat est simple : si on a déjà vu le mot avant, ça ne sert à rien de le remettre dans l'ensemble des mots à tester. En effet, si on l'a déjà rencontré, ça implique qu'il existe un chemin plus court pour y accéder et donc que le chemin que l'on vient de trouver n'est pas optimal.
    Ceci se fait simplement à l'aide d'une soustraction d'ensembles : on garde l'ensemble des mots déjà rencontrés, et on les enlève des mots possibles à chaque tour de boucle.

Notre algorithme devient donc :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
profondeur = 0
mots à la profondeur 0 : mot de départ
mots parents à la profondeur 0 : aucun
Boucle infinie !
    Incrémenter la profondeur
    mots parents à la profondeur courante : aucun
    Pour chaque mot de la profondeur courante :
         Calculer tous les mots suivants possibles
         Les ajouter à l'ensemble des mots de la profondeur courante
         Définir les mots parents pour la profondeur courante
    Soustraire l'ensemble des mots déjà connus
    Est-ce qu'on a au moins un mot dans l'ensemble des mots de la profondeur courante ?
         Non : il n'y a pas de chemin possible. On sort de la boucle
    Est-ce que le mot cible est dans la liste des mots de la profondeur courante ?
         Oui : On a trouvé un plus court chemin ! On sort de la boucle
         Non : Dommage... on doit chercher encore plus profond, c'est parti pour un nouveau tour de boucle
    Ajouter les mots de la profondeur courante à l'ensemble des mots déjà connus

et

1
2
3
4
5
6
Calcul du chemin :
mot courant = mot de fin
Boucle sur les profondeurs, de la longueur du chemin trouvé jusqu'à 0 :
    Ajouter le mot courant au chemin
    Nouveau mot courant = mot parent du mot courant pour la profondeur courante
Le chemin calculé est inversé (cible en premier), il faut l'inverser pour l'avoir dans l'ordre demandé

Remarque sur les performances

On remarque 2 phénomènes en fonction de la profondeur. En excluant les cas spéciaux des mots qui ne mènent à rien (comme "zygomatique") :

  • On multiplie le nombre de mots possibles à chaque profondeur…
  • Mais on multiplie aussi le nombre de mots déjà connus à chaque profondeur

Conséquence : le nombre de mots à traiter à chaque profondeur va augmenter, puis attendre un maximum (on a plein de mots inconnus et pas encore trop de mots déjà connus). Comme le nombre total de mots connus est fini, au bout d'un moment on aura tellement de mots déjà connus que la plupart des nouveaux mots trouvés vont être éliminés parce que déjà traités. Donc le nombre de mots va ensuite diminuer selon la profondeur, jusqu'à atteindre 0 (tous les mots possibles sont déjà connus) s'il n'y a pas de chemin.

Ceci a deux implications :

  1. Si on arrive à traiter "le nombre maximal de mots à une profondeur donnée" dans un temps raisonnable, l'algorithme ne va jamais tomber dans un cas incalculable : il garantit un résultat dans un temps fini et "raisonnable" (celui, théoriquement, de vérifier l'ensemble des mots du dictionnaire, une seule fois chacun).
  2. On voit que la portion de code qui fait la soustraction d'ensemble est critique puisque c'est elle qui va devoir gérer la soustraction de 2 ensembles potentiellement grands (cas limite : on connaît déjà presque tous les mots du dictionnaire, et les mots possibles à partir des mots connus sont "tous les mots du dictionnaire" – ce qui revient à soustraire le dictionnaire à lui-même, donc à soustraire deux listes de + de 300000 entrées).
    Heureusement Java fournit une méthode pour ce faire sur ses collections : removeAll.

Implémentation

Calcul des mots possibles pour la profondeur courante :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
  private Set<String> computeDepthWords(int depth, Set<String> previousDepthWords) {

      int nbWords;
      Set<String> depthWords = new HashSet<>();

      for (String previousLevelWord: previousDepthWords) {

          Set<String> possibleWords = findPossibleWords(previousLevelWord);

          for (String possibleWord : possibleWords) {
              previous.get(depth).put(possibleWord, previousLevelWord);
          }

          depthWords.addAll(possibleWords);
      }

      // Remove words known from previous level
      depthWords.removeAll(alreadTestedWords);
      return depthWords;
  }

Recherche du plus court chemin :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
  public List<String> findPath(String start, String end) throws Exception {

      long tStart = System.currentTimeMillis();

      System.out.println("Recherche d'un chemin entre " + start + " et  " + end);

      // Initialize variables
      int depth = 0;
      alreadTestedWords = new HashSet<>();
      previous = new HashMap<>();
      previous.put(0, new HashMap<String, String>());
      Set<String> previousDepthWords = new HashSet<>();
      Set<String> depthWords;
      List<String> path = new LinkedList<>();

      previousDepthWords.add(start);

      // Loop: while word is not found
      do {
          // 1. Set depth
          long startLoop = System.currentTimeMillis();
          depth++;
          previous.put(depth, new HashMap<String, String>());

          System.out.println("Calcul des possibilités de profondeur " + depth);

          // 2. Compute all words available at this level
          depthWords = computeDepthWords(depth, previousDepthWords);

          // 3. Is one of these words the final one ?
          if (depthWords.size() == 0) {
              System.out.println("Aucun chemin possible !");
              break;
          }
          if (depthWords.contains(end)) {
              System.out.println("Chemin trouvé !");
              break;
          }

          // 4. Update data
          alreadTestedWords.addAll(depthWords);
          previousDepthWords = depthWords;

          System.out.println("    Profondeur explorée en " + (System.currentTimeMillis() - startLoop) + " ms");

      } while (true);

      if (depthWords.size()  > 0) {
          path = extractPath(end, depth);
      }

      System.out.println("Calculé en " + (System.currentTimeMillis() - tStart) + " ms");

      return path;
  }

Récupération du chemin une fois qu'il a été trouvé :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
  private List<String> extractPath(String end, int depth) {

      List<String> path = new LinkedList<>();
      String previousWord = end;

      for (int i = depth; i >= 0; i--) {
          path.add(previousWord);
          previousWord = previous.get(i).get(previousWord);
      }

      Collections.reverse(path);
      return path;
  }

Implémentation générale

On a déjà les classes complètes Anagrams et AcceptNullHashSet. On y ajoute la classe qui permet de gérer le jeu lui-même (et qui rajoute des broutilles par rapport aux codes ci-dessus : nettoyage en entrée, stats) :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
package info.kisai.anagrams;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Locale;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class LiveAnagrams {

  private Set<String> words = new HashSet<>();
  private Anagrams anagrams = new Anagrams();

  private Set<String> alreadTestedWords = new HashSet<>();
  private Map<Integer, Map<String, String>> previous = new HashMap<>();

  public void loadWords(File dictionary) throws FileNotFoundException {

      System.out.println("Chargement du dictionnaire...");

      long start = System.currentTimeMillis();

      try (Scanner scanner = new Scanner(dictionary, "UTF8")) {
          String word = null;
          while (scanner.hasNextLine()) {
              word = clean(scanner.nextLine());
              words.add(word);
              anagrams.add(word);
          }
      }
      System.out.println("Chargement OK, " + words.size() + " mots en " + (System.currentTimeMillis() - start) + " ms");
  }

  private static String clean(String word) {
      return word.toLowerCase(Locale.FRANCE)
              .replace("à", "a")
              .replace("â", "a")
              .replace("ä", "a")
              .replace("é", "e")
              .replace("è", "e")
              .replace("ê", "e")
              .replace("ë", "e")
              .replace("î", "i")
              .replace("ï", "i")
              .replace("ô", "o")
              .replace("ö", "o")
              .replace("û", "u")
              .replace("ü", "u")
              .replace("ù", "u");
  }

  public List<String> findPath(String rawStart, String rawEnd) throws Exception {

      long tStart = System.currentTimeMillis();

      String start = clean(rawStart);
      String end = clean(rawEnd);
      if (!words.contains(start)) {
          throw new Exception("Le mot " + rawStart + " est inconnu");
      }
      if (!words.contains(end)) {
          throw new Exception("Le mot " + rawEnd + " est inconnu");
      }

      System.out.println("Recherche d'un chemin entre " + start + " et  " + end);

      // Initialize variables
      int depth = 0;
      alreadTestedWords = new HashSet<>();
      previous = new HashMap<>();
      previous.put(0, new HashMap<String, String>());
      Set<String> previousDepthWords = new HashSet<>();
      Set<String> depthWords;
      List<String> path = new LinkedList<>();

      previousDepthWords.add(start);

      // Loop: while word is not found
      do {
          // 1. Set depth
          long startLoop = System.currentTimeMillis();
          depth++;
          previous.put(depth, new HashMap<String, String>());

          System.out.println("Calcul des possibilités de profondeur " + depth);

          // 2. Compute all words available at this level
          depthWords = computeDepthWords(depth, previousDepthWords);

          // 3. Is one of these words the final one ?
          if (depthWords.size() == 0) {
              System.out.println("Aucun chemin possible !");
              break;
          }
          if (depthWords.contains(end)) {
              System.out.println("Chemin trouvé !");
              break;
          }

          // 4. Update data
          alreadTestedWords.addAll(depthWords);
          previousDepthWords = depthWords;

          System.out.println("    Profondeur explorée en " + (System.currentTimeMillis() - startLoop) + " ms");

      } while (true);

      if (depthWords.size()  > 0) {
          path = extractPath(end, depth);
      }

      System.out.println("Calculé en " + (System.currentTimeMillis() - tStart) + " ms");

      return path;
  }

  private Set<String> computeDepthWords(int depth, Set<String> previousDepthWords) {

      int nbWords;
      Set<String> depthWords = new HashSet<>();

      for (String previousLevelWord: previousDepthWords) {

          Set<String> possibleWords = findPossibleWords(previousLevelWord);

          for (String possibleWord : possibleWords) {
              previous.get(depth).put(possibleWord, previousLevelWord);
          }

          depthWords.addAll(possibleWords);
      }

      // Remove words known from previous level
      depthWords.removeAll(alreadTestedWords);

      nbWords = alreadTestedWords.size() + depthWords.size();
              System.out.println("    " + depthWords.size() + " mots trouvés à cette profondeur / total : "
              + nbWords + " / " + words.size() + " soit " + ((double) nbWords / (double) words.size()) * 100
              + "%");
      return depthWords;
  }

  private List<String> extractPath(String end, int depth) {

      List<String> path = new LinkedList<>();
      String previousWord = end;

      for (int i = depth; i >= 0; i--) {
          path.add(previousWord);
          previousWord = previous.get(i).get(previousWord);
      }

      Collections.reverse(path);
      return path;
  }

  private Set<String> findPossibleWords(String word) {

      Set<String> out = new AcceptNullHashSet<>();
      char[] chars = word.toCharArray();

      // Simple anagrams
      out.addAll(anagrams.getAnagramsOf(word));

      add1Char(word, out);
      remove1Char(chars, out);
      replace1Char(chars, out);

      // Avoid infinite loops...
      out.remove(word);

      return out;
  }

  private void add1Char(String word, Set<String> out) {
      for (char c = 'a'; c <= 'z'; c++) {
          out.addAll(anagrams.getAnagramsOf(word + c));
      }
  }

  private void remove1Char(char[] chars, Set<String> out) {

      int length = chars.length;
      StringBuilder sb;

      // Loop : remove letter at position i
      for (int i = 0; i < length; i++) {
          sb = new StringBuilder(length - 1);
          for (int j = 0; j < length; j++) {
              if (i != j) {
                  sb.append(chars[j]);
              }
          }
          out.addAll(anagrams.getAnagramsOf(sb.toString()));
      }
  }

  private void replace1Char(char[] chars, Set<String> out) {

      int length;
      length = chars.length;
      char[] tmpCarArray;

      for (int i = 0; i < length; i++) {
          for (char c = 'a'; c <= 'z'; c++) {
              tmpCarArray = Arrays.copyOf(chars, length);
              if (tmpCarArray[i] != c) {
                  tmpCarArray[i] = c;
                  out.addAll(anagrams.getAnagramsOf(new String(tmpCarArray)));
              }
          }
      }
  }

}

Et bien entendu, une interface pour pouvoir gérer tout ça :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package info.kisai.anagrams;

import java.io.File;
import java.util.List;
import java.util.Scanner;

public class CLI {

  public static void main(String... args) throws Exception {
      LiveAnagrams anagrams = new LiveAnagrams();
      anagrams.loadWords(new File("liste.de.mots.francais.frgut.txt"));

      try (Scanner in = new Scanner(System.in)) {
          String words = null;
          List<String> path = null;

          do {
              System.out.println("Entrez les 2 mots séparés par une espace (ou rien pour quitter) :");
              words = in.nextLine();

              if (words == null || words.trim().equals("")) {
                  break;
              }
              words = words.trim();

              if (words.contains(" ")) {
                  String[] wArray = words.split(" ");
                  if (wArray.length == 2) {
                      path = anagrams.findPath(wArray[0], wArray[1]);
                      System.out.println("Chemin trouvé :  " + path + " (" + path.size() + " étapes)");
                  } else {
                      System.out.println("Vous devez entrer 2 mots séparés par une espace.");
                  }
              }
          } while (true);
      }
  }
}

Résultats

Ca fonctionne comme prévu !

Dans le pire des cas le calcul d'une étape dépasse rarement les 10 secondes ; donc on peut trouver un résultat très compliqué en 1 minutes.
Le programme lui-même mange jusqu'à 1.4 Go de RAM (parce que c'est ce que je lui ai autorisé, une étude rapide montre qu'on pourrait diminuer ça de beaucoup, à voir l'impact sur les performances) et s'exécute sous Java 8 x64 / Windows 8.1 / Intel Core i5-3570.

Une étude rapide montre aussi que dès que la solution n'est pas évidente (calculs sur plus de quelques dizaines de mots), plus de la moitié du temps est passée dans la soustraction d'ensembles (méthode removeAll des Set de Java).

Exemple avec zeste et savoir :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
Recherche d'un chemin entre zeste et  savoir
Calcul des possibilités de profondeur 1
    63 mots trouvés à cette profondeur / total : 63 / 323590 soit 0.019469081244785066%
    Profondeur explorée en 3 ms
Calcul des possibilités de profondeur 2
    941 mots trouvés à cette profondeur / total : 1004 / 323590 soit 0.310269167774035%
    Profondeur explorée en 10 ms
Calcul des possibilités de profondeur 3
    5753 mots trouvés à cette profondeur / total : 6757 / 323590 soit 2.0881362217621064%
    Profondeur explorée en 104 ms
Calcul des possibilités de profondeur 4
    17793 mots trouvés à cette profondeur / total : 24550 / 323590 soit 7.586761024753547%
    Profondeur explorée en 653 ms
Calcul des possibilités de profondeur 5
    32955 mots trouvés à cette profondeur / total : 57505 / 323590 soit 17.770944713989927%
Chemin trouvé !
Calculé en 2919 ms
Chemin trouvé :  [zeste, ester, verts, versa, rivas, savoir] (6 étapes)

Autre exemple avec renard et espace :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
Recherche d'un chemin entre renard et  espace
Calcul des possibilités de profondeur 1
    83 mots trouvés à cette profondeur / total : 83 / 323590 soit 0.02564974195741525%
    Profondeur explorée en 0 ms
Calcul des possibilités de profondeur 2
    1419 mots trouvés à cette profondeur / total : 1502 / 323590 soit 0.46416761951852653%
    Profondeur explorée en 12 ms
Calcul des possibilités de profondeur 3
    8881 mots trouvés à cette profondeur / total : 10383 / 323590 soit 3.2086900089619577%
    Profondeur explorée en 189 ms
Calcul des possibilités de profondeur 4
    26605 mots trouvés à cette profondeur / total : 36988 / 323590 soit 11.430513921938255%
Chemin trouvé !
Calculé en 1410 ms
Chemin trouvé :  [renard, cendra, rances, recase, espace] (5 étapes)

Avec un chemin impossible :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
Recherche d'un chemin entre zeste et  zygomatique
Calcul des possibilités de profondeur 1
    63 mots trouvés à cette profondeur / total : 63 / 323590 soit 0.019469081244785066%
    Profondeur explorée en 4 ms
Calcul des possibilités de profondeur 2
    941 mots trouvés à cette profondeur / total : 1004 / 323590 soit 0.310269167774035%
    Profondeur explorée en 11 ms
Calcul des possibilités de profondeur 3
    5753 mots trouvés à cette profondeur / total : 6757 / 323590 soit 2.0881362217621064%
    Profondeur explorée en 113 ms
Calcul des possibilités de profondeur 4
    17793 mots trouvés à cette profondeur / total : 24550 / 323590 soit 7.586761024753547%
    Profondeur explorée en 679 ms
Calcul des possibilités de profondeur 5
    32955 mots trouvés à cette profondeur / total : 57505 / 323590 soit 17.770944713989927%
    Profondeur explorée en 2223 ms
Calcul des possibilités de profondeur 6
    47239 mots trouvés à cette profondeur / total : 104744 / 323590 soit 32.36935628418678%
    Profondeur explorée en 4806 ms
Calcul des possibilités de profondeur 7
    53397 mots trouvés à cette profondeur / total : 158141 / 323590 soit 48.870793287802464%
    Profondeur explorée en 7360 ms
Calcul des possibilités de profondeur 8
    48665 mots trouvés à cette profondeur / total : 206806 / 323590 soit 63.90988596680985%
    Profondeur explorée en 8749 ms
Calcul des possibilités de profondeur 9
    36970 mots trouvés à cette profondeur / total : 243776 / 323590 soit 75.33483729410673%
    Profondeur explorée en 8576 ms
Calcul des possibilités de profondeur 10
    24563 mots trouvés à cette profondeur / total : 268339 / 323590 soit 82.9256157483235%
    Profondeur explorée en 7194 ms
Calcul des possibilités de profondeur 11
    14675 mots trouvés à cette profondeur / total : 283014 / 323590 soit 87.4606755462159%
    Profondeur explorée en 5269 ms
Calcul des possibilités de profondeur 12
    8139 mots trouvés à cette profondeur / total : 291153 / 323590 soit 89.97589542322075%
    Profondeur explorée en 3448 ms
Calcul des possibilités de profondeur 13
    4276 mots trouvés à cette profondeur / total : 295429 / 323590 soit 91.29732068358108%
    Profondeur explorée en 2068 ms
Calcul des possibilités de profondeur 14
    2224 mots trouvés à cette profondeur / total : 297653 / 323590 soit 91.98461015482555%
    Profondeur explorée en 1156 ms
Calcul des possibilités de profondeur 15
    1069 mots trouvés à cette profondeur / total : 298722 / 323590 soit 92.31496646991563%
    Profondeur explorée en 671 ms
Calcul des possibilités de profondeur 16
    537 mots trouvés à cette profondeur / total : 299259 / 323590 soit 92.48091721004975%
    Profondeur explorée en 336 ms
Calcul des possibilités de profondeur 17
    265 mots trouvés à cette profondeur / total : 299524 / 323590 soit 92.5628109644921%
    Profondeur explorée en 170 ms
Calcul des possibilités de profondeur 18
    148 mots trouvés à cette profondeur / total : 299672 / 323590 soit 92.60854785376557%
    Profondeur explorée en 90 ms
Calcul des possibilités de profondeur 19
    67 mots trouvés à cette profondeur / total : 299739 / 323590 soit 92.62925306715289%
    Profondeur explorée en 51 ms
Calcul des possibilités de profondeur 20
    32 mots trouvés à cette profondeur / total : 299771 / 323590 soit 92.63914212429309%
    Profondeur explorée en 23 ms
Calcul des possibilités de profondeur 21
    22 mots trouvés à cette profondeur / total : 299793 / 323590 soit 92.64594085107699%
    Profondeur explorée en 11 ms
Calcul des possibilités de profondeur 22
    13 mots trouvés à cette profondeur / total : 299806 / 323590 soit 92.64995828054019%
    Profondeur explorée en 6 ms
Calcul des possibilités de profondeur 23
    9 mots trouvés à cette profondeur / total : 299815 / 323590 soit 92.65273957786087%
    Profondeur explorée en 4 ms
Calcul des possibilités de profondeur 24
    8 mots trouvés à cette profondeur / total : 299823 / 323590 soit 92.65521184214592%
    Profondeur explorée en 3 ms
Calcul des possibilités de profondeur 25
    4 mots trouvés à cette profondeur / total : 299827 / 323590 soit 92.65644797428845%
    Profondeur explorée en 3 ms
Calcul des possibilités de profondeur 26
    1 mots trouvés à cette profondeur / total : 299828 / 323590 soit 92.65675700732409%
    Profondeur explorée en 2 ms
Calcul des possibilités de profondeur 27
    0 mots trouvés à cette profondeur / total : 299828 / 323590 soit 92.65675700732409%
Aucun chemin possible !
Calculé en 53028 ms
Chemin trouvé :  [] (0 étapes)

On remarque grâce aux stats que j'ai affiché dans les boucles que la plupart des mots sont reliés entre eux ; et qu'à partir d'une profondeur de 7 ou 8 on atteint la moitié du dictionnaire. Regardez le dernier exemple : on y voit que "zeste" est relié à potentiellement 299828 mots différents, soit 92.66% du dictionnaire.

PS : Le code est là https://github.com/SpaceFox/anagrams-java

L'algorithme est semi-déterministe, c'est assez étrange. Sur un même OS,j'aurai toujours le même chemin, par contre si je change d'OS / de machine, j'aurai toujours un plus court chemin de même longueur mais avec des mots différents. Ca doit venir de la manière de calculer les hash.


  1. Il y a sans doute plus optimal, mais bon… ça marche et ce n'est pas là qu'on perds du temps. 

Édité par SpaceFox

Staff
Auteur du sujet

Marrant, j'ai essayé avec un dictionnaire anglais, les mots sont beaucoup moins bien connectés (un mot au hasard pas trop compliqué est relié à environ 80% du dictionnaire). Sans doute parce qu'il y a beaucoup moins de mots (1/3 du français) donc beaucoup moins de chemins.

firm1 j'ai un petit souci avec ton code : au chargement du dictionnaire, le code plante car il ne trouve pas le fichier.
Pourtant le fichier est dans le même répertoire du code et a le même nom.

Merci à toi.

Je te met l'erreur si ça peut t'aider :

1
2
3
4
5
debut du chargement du dictionnaire
Traceback (most recent call last):
  File "C:\Users\Baptiste\Desktop\Algo\Algo.py", line 17, in <module>
    source = open(fichier, "r")
FileNotFoundError: [Errno 2] No such file or directory: 'listedemots.txt'

baptisteguil

Psst, ça serait mieux avec le mot-clé with:

17
18
with open(fichier, 'r') as source:
    ...
+0 -0

On calcule un la distance de Levenshtein entre tous les mots. Ca donne n^2 arrêtes, avec n nombre de mots. On ne garde que les arrête où la distance est 1, ce qui donne un graphe sur lequel on peut lancer un A*.

D'autant plus qu'on doit calculer le graphe qu'une seule fois et que ca se parallélise très bien. Il est où le soucis ?

Edit : bon, en fait jai le même algo que les gens au dessus =/

Édité par Davidbrcz

+0 -0

Marrant, j'ai essayé avec un dictionnaire anglais, les mots sont beaucoup moins bien connectés (un mot au hasard pas trop compliqué est relié à environ 80% du dictionnaire). Sans doute parce qu'il y a beaucoup moins de mots (1/3 du français) donc beaucoup moins de chemins.

SpaceFox

C'est pas vraiment étonnant. La conjugaison anglaise ne propose que très peu de formes différentes pour un même verbe, contrairement au français. Si en plus tu considères que tous les adjectifs sont invariables, ça fait encore chuter le nombre de mots.

Bonsoir,

En voilà un exercice intéressant, et pas si simple qu'il n'en a l'air !

Bon, apparament mon algo n'est pas le plus rapide, et il ne trouve visiblement pas toujours le meilleur chemin. Mais il en trouve un, c'est déjà pas mal comme début je pense.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
323573 mots dans le dictionnaire
Chargement du dictionnaire effectué en 4586.3945ms
Le chemin entre adherence et coquille a été déterminé : 
0. adherence
1. decharnee
2. decharne
3. echarne
4. echarpe
5. pechera
6. pecher
7. perche
8. perce
9. perle
10. pelle
11. pille
12. oille
13. ouille
14. couille
15. coquille
Chemin trouvé en 66.6601ms

J'ai séparé le processus en trois parties. Les deux premières sont très lentes et probablement encore optimisables, mais à n'exécuter qu'une seule fois.

  1. Organisation du dictionnaire en un graphe (Aka tries)
  2. Création du graphe représentant l'espace des mots
  3. Recherche de chemin dans le graphe des mots

A l'étape 1, j'ouvre le fichier texte du dictionnaire, et je le restructure en un trie. Ceci permettra un accès beaucoup plus rapide à la deuxième phase. Partie pas forcément hyper intéressante mais indispensable !

A la fin de cette étape, j'ai un dictionnaire sous forme de trie, enregistré dans un fichier (qui pèse environ 600 Ko, et généré en 75sec)

A la deuxième étape, je rouvre mon trie précédemment créé, et j'établis le graphe de transition entre les mots. Je prends les mots un par un, et à partir d'un mot donné, je m'appuie sur la structure en trie pour rechercher les mots ayant une lettre changée, ajoutée ou supprimée. La structure permet à cette recherche d'être raisonnablement rapide. J'en profite aussi pour ajouter les anagrammes, en utilisant la technique que vous avez déjà exposé plus haut avec une clé consistant à ranger les lettres du mot dans l'ordre.

A la fin de cette étape, on a un graphe qui contient tous les mots et toutes les transitions possibles (le fichier fait 12 Mo et se génère en 90sec)

A la troisième étape, je charge le graphe de la phase 2, et j'utilise l'algorithme A* pour trouver un chemin. La distance de Levenshtein est utilisée comme euristique (avec une exception, la transition d'un mot à une de ses anagrammes compte pour 0), et les calculs de distance sont mis en cache pour éviter de recalculer plusieurs fois la même. IL trouve quand même assez vite quand la solution existe, mais j'ai pu remarquer qu'il mettait quand même 45sec avant de le signaler dans le cas où il n'y en a pas…

Si ça intéresse quelqu'un, je peux mettre le code en téléchargement; j'ai fait ça en java. Pas question que je le colle directement ici par contre, il fait quand même 500+ lignes au total !

Ma plateforme avec 23 jeux de société classiques en 6 langues et 13000 joueurs: http://qcsalon.net/ | Apprenez à faire des sites web accessibles http://www.openweb.eu.org/

+1 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte