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 :
- Comment trouver les mots autorisés ?
- 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 :
- Les anagrammes simples
- Les anagrammes du mot avec une lettre en plus
- Les anagrammes du mot avec une lettre en moins
- 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 :
| À 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 !
- 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 boucles
- 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
| 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 :
- 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).
- 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.
(Si on veut le faire en deux programmes ?)
