J'ai créé un code dans lequel on effectue un tirage entre 2 et 15 lettres puis il affiche tous les mots valables à partir d'une liste de 400.000 mots. Si le tirage fait N lettres (incluant d'éventuels jokers), il affichera des mots de N lettres J'ai trouvé une astuce pour que le réponse soit instantanée. Reste le problème des jokers pouvant remplacer n'importe quelle lettre de l'alphabet. Avec un joker ça va. Avec deux jokers c'est plus long. Je fais la comparaison avec des sites web donnant une réponse quasi instantanée.
Tout ce que j'ai trouvé concernant les 2 jokers est d'essayer chaque combinaison possible en évitant les mêmes paires et ensuite de vérifier comme d'habitude les mots de N lettres de la liste. Par exemple (a,b) est identique à (b,a). Toutefois pour certaines longueurs de mots c'est un peu long, dans les 20 secondes.
Sans me donner le code, je voudrais savoir s'il est possible d'optimiser cela. Pas trop compliqué svp, je n'ai lu que la première partie du cours (et je vais commencer l'autre sur zestedesavoir).
Pour résoudre des problèmes, il faut un minimum de connaissances en algorithmique. Son apprentissage va de paire avec l'apprentissage d'un premier langage.
Pour le premier problème que tu as réussi à résoudre, la solution souvent utilisée IRL est de simplement de prendre les lettres triées, de les ordonner et d'accéder à une structure de donnée qui associe à cette empreinte une liste de mots correspondant. Avec cette méthode, utiliser un joker revient à insérer dans la liste des lettres toutes les lettres de l'alphabet une à une et faire une recherche (tu en feras donc 26), Pour deux jokers il te faudra construire tous les mots de 2 lettres sans doublons et effectuer les 351 recherches. Bien implémenté (avec des algos efficients) cela ne devrait pas prendre énormément de temps. Ce n'est pas forcément un problème de connaissances sur le langage qui te permettra d'optimiser, mais certainement plus une connaissance sur les structures de données et ce qu'on peut faire avec.
Une autre méthode recquiert un peu plus de connaissances en algo (les arbres). Mais cela ne t'est pas accessible si tu en es à la première partie du cours.
Cela n'est pas forcément compliqué, mais il est clair que cela peut être complexe.
Bon, on revient pas sur les aspects algorithmiques dont parlent @White_Crow mais il faut aussi avoir des structures de données adaptées.
Et aussi, "*" a généralement une "acceptation" d'une séquence de "lettres" arbitraires, c'est plutôt le wildcard "?" qui est utilisé pour un caractère unique.
Mais les frameworks que vraisemblablement vous utiliserez ont de bonnes chances d'utiliser des expressions régulières plutôt que la syntaxe à base de wildchard des années disco.
Je recherche un CDI/CDD/mission freelance comme Architecte Logiciel/ Expert Technique sur technologies Microsoft.
C'est rapide, cependant en effet quand il y a les jokers, ça ralentit les tests. Je remplaçais chaque joker par chacune des lettres, ce qui me faisait 26 tests pour un joker, et 26²2 tests pour 2 jokers.
J'essayais d'optimiser au maximum le temps d'un seul test, ce qui rendait le temps tout à fait acceptable, mais je n'ai pas trouvé d'optimisation pour les jokers.
Je donne suite à ma suggestion. C'est mon preemier programme en Ruby, soyez indulgents. - # Probabilités relatives. prob = [40, 40, 20] puts(prob.to_s()) # Valeurs associées à chaque intervalle. vals = [[0, 9], [19, 36], [53, 113]] # Seules les valeurs dans les intervalles seront choisies. # Probabilités cumulatives pour l'algorithme. for i in 1...prob.length() prob[i] = prob[i-1] + prob[i] end puts(prob.to_s());puts("") r = rand(prob[-1]) puts(r) # Trouver le bon intervalle. for i in 0...prob.length() if r < prob[i] p = i break end end puts(p) # Valeur aléatoire correspondante. n = rand(vals[p][1] - vals[p][0] + 1) + vals[p][0] puts(n) - [40, 40, 20] [40, 80, 100]
52 1 28
Le Tout est souvent plus grand que la somme de ses parties.
En fait pour calculer le nombre de possibilités avec 2 jokers : n*(n-1)/2 = 325 pour avoir des paires uniques. 26*26 est une mauvaise idée car non seulement elle renvoie des mots en double mais 676 fois ralentit beaucoup trop.
Voici comment j'ai transcrit ce problème :
J'enlève les jokers de la chaîne, je concatène, je compare 325 fois.
pour i = 0 to N
pour j = i to N
comparons avec l'algorithme optimisé
Je suis au max là mais content d'avoir trouvé le truc pour une comparaison hyper rapide.
D'abord, je m'excuse pour le message bizarre. J'ai fait un copier-coller du mauvais tampon (ma synthèse vocale me joue des tours) Finalement, je ne comprend pas si tu veux calculer des possibilités ou chercher dans ton dictionnaire. Je connaissait une méthode très efficace pour chercher une chaîne dans un texte formé de lignes. J'avais oublié le nom mais je viens de le retrouver. Il s'agit de l'algorithme de Boyer-Moore. Je ne sais pas si c'est que tu veux faire. À tout hasard, je te donne le lien: https://fr.wikipedia.org/wiki/Algorithme_de_Boyer-Moore Je pense que ça se modifierait facilement pour tenir compte des jockers/wildcards.
Le Tout est souvent plus grand que la somme de ses parties.
PierrotLeFou: optimiser la recherche dans le dico quand 2 jokers sont présents.
Par exemple : je tire 5 lettres et 2 jokers. Tout ce que j'ai trouvé c'est de remplacer simultanément les 2 jokers par un couple de lettres et de tester. le couple de lettre comme AA AB ... AZ puis BB BC ... ZZ. On a 325 possibilités.
Quand je compare certains sites web spécialisés dans les anagrammes, même avec 2 jokers, on attend que 1 à 2 secondes seulement.
C'est principalement parce que ces sites, tout comme les logiciels spécialisés, utilisent d'autres structures de données plus efficaces. Il n'y a pas de secrets
Et il y a 26*27/2=351 possibilités et non 26*25/2=325 …
Quand tu implémentes ton dico comme un arbre de recherche , comme par exemple un trie comme suggéré par @firtman ou plus efficacement comme un dawg (directed acyclic word graph), tu peux élaguer pas mal de recherches dès le départ. Tu ne chercheras pas s'il existe des mots commençant par QR par exemple … Par construction tu ne formeras que des mots existant sans tester des tirages qui ne forment pas de mots.
Mais avant d'en arriver à ce stade il va falloir étoffer tes connaissances en algo.
Surtout si ton but ultime est de construire un solveur de scrabble …
Ou bien c'est moi qui ne comprend rien, ou bien, c'est toi ... Si tu choisis 15 lettres différentes au hasard, tu examines les 15! possibilités? Ça en ferait beaucoup(1307674368000 ...). Si tu prends les lettres dans l'ordre donné au départ, tu compares la chaîne avec chaque mot du dictionnaire. Et que fait-on des jockers? Si je suppose utiliser l'algorithme de Boyer-Moore, je commence par enlever les jockers de la fin. Supposons qu'il y a 2 jockers à la fin. Je considère les N-2 premiers caractères de la chaîne. Et je construit les deux tableaux décrits en excluant ces caractères. Je ne m'occupepas des jockers restants dans la chaîne. Si mes jockers sont représentés par des '*', sachant la longueur de la chaîne, je peux les remplacer par des 0. Ce sera légèrement plus rapide à tester. Et je ne vais pas plus loin que les L-2 premiers caractères de chaque ligne (les mots du dictionnaire). Contrairement à ce qui est dit dans Wikipedia, je place 0 dans le premier tableau à la position de la dernière lettre de la chaîne. C'est à dire, si la chaîne est "wikipedia", je met 0 dans tableau['a'] Avant d'avancer, je teste si l'incrément au niveau du dernier caractère est 0. Si c'est plus grand, j'essaie d'avancer, sinon je fais les comparaisons en reculant. Si un caractère de la chaîne est 0, c'est un jocker, et je suppose l'égalité.
Le Tout est souvent plus grand que la somme de ses parties.
Un schéma de solution sympa est le suivant : il faut trouver une fonction P qui est invariable par anagramme (donc si w et w' sont des anagrammes, alors P(w) = P(w')) et qui se calcule rapidement. On peut alors créer une table de hachage à partir de notre dictionnaire en stockant un mot w à la case P(w). Étant donné une liste de lettres L contenant potentiellement des jokers, on peut alors facilement trouver les mots correspondants.
n = nombre de joker dans L
L' = L sans les joker
Pour chaque combinaison avec répétition C de n lettres (on remplace les n jokers)
Regarder les mots à la case correspondant à P(L' + C).
Fin Pour
On a un temps de précalcul de la table de hachage, et sinon le reste va assez vite, le calcul des combinaisons de n lettres est très rapide si tu veux te limiter à 2 jokers maximum. Reste à trouver des fonctions P qui font le travail. Une fonction simple est celle qui associe à un mot le nombre d'occurrences de chaque lettre. Une que j'aime bien consiste à associer à chaque lettre un nombre premier et à associer à w le produit des nombres premiers associés à ses lettres. L'unicité de la décomposition en nombre premier assure que la fonction P ainsi obtenue respecte le critère que l'on veut.
Ce schéma de solution peut également s'implémenter en se modifiant un peu pour utiliser une structure de trie modifiée (avec l'exemple que je donne, on ne peut même plus vraiment parler de trie). Par exemple, on peut stocker chaque mot du dictionnaire au nœud de ses lettres triées par ordre alphabétique. Ainsi, toutes les anagrammes seront stockées au même nœud.
Par exemple, avec le groupe de mots {ETE, TEE, ET, TE, TOI}, on se retrouve avec cet arbre (entre crochets, on a les mots qu'on peut trouver à chaque nœud).
-- E []
-- E []
-- T [ETE, TEE]
-- T [ET, TE]
-- I []
-- O []
-- T [TOI]
Avec la liste L de lettre et de jokers et T l'arbre dans lequel on a stocké le dictionnaire, on peut alors faire ceci.
n = nombre de joker dans L
L' = L sans les joker, triée
Fonction TrouverMots(arbre, lettres, m)
Si lettres est vide et m = 0
/* On a utilisé toutes les lettres, on
affiche les mots présents à ce noeud. */
Afficher arbre.mots
Sinon Si m = 0
/* On va au noeud correspondant à la lettre suivante. */
a = lettres[0]
suite_lettres = queue(lettres)
TrouverMots(arbre[a], suite_lettres, m)
Sinon si lettres est vide
/* Il ne reste que des jokers */
Pour chaque lettre a de l'alphabet
TrouverMots(arbre[a], lettres, m - 1)
Fin Pour
Sinon
/* Il reste les deux. */
Pour chaque lettre a de l'alphabet
Si lettres[0] = a
TrouverMots(arbre[a], queue(lettres), m)
Sinon
TrouverMots(arbre[a], lettres, m - 1)
Fin Si
Fin Pour
Fin Si
Fin Fonction
TrouverMots(T, L', n)
J'ai laissé quelques détails sous le tapis (notamment, je confonds les mots et les listes de lettres et je ne m'occupe pas des cas où il n'y a pas de nœud avec la lettre voulue dans l'arbre) et il y a des améliorations possibles, mais c'est l'idée globale.
Il semble que ce soit moi qui n'ai rien compris ... Si le problème est vraiment un scrabble où on tire des lettres et des jokers et si on veut afficher les mots qu'on peut faire avec ces jetons, j'ai trouvé un algo de complexité en O(n) où n est la longueur de la chaîne. En fait c'est proportionnel au nombre de jetons différents. Je le rappelle pour les non habitués, je ne peux pas colorer mon code avec ma synthèse vocale: - #include <iostream> #include <array> #include <string> int main(void) { std::array<int, 256> index; std::array<int, 16> cbox; // Boîte pour la chaîne. std::array<int, 16> wbox; // Boîte pour les mots. std::string chain; // Chaîne. std::string word; // Les mots. // Saisie de la chaîne ... std::cout << "chaine >"; std::cin >> chain; // Lors de l'initialisation. for(int i=0; i < 256; i++) { index[i] = 0; } for(int i=0; i < 16; i++) { cbox[i] = 0; } int next = 0; for(int i=0; i < chain.length(); i++) { if(chain[i] == '*') cbox[0]++; else { if(index[chain[i]] == 0) { next++; // Prochin indice disponible. index[chain[i]] = next; cbox[next]=0; // Initialise la boîte pour cet indice. } cbox[index[chain[i]]]++; // Il y a déjà un indice pour cette lettre. } } next++; std::cout << "next=" << next << std::endl; for(int i=0; i<next; i++) std::cout << " " << cbox[i]; std::cout << std::endl; //... std::cout << "mot >"; std::cin >> word; // Pour chaque mot du dictionnaire. for(int i=0; i < next; i++) { wbox[i] = 0; } for(int i=0; i < word.length(); i++) { wbox[index[word[i]]]++; } for(int i=0; i<next; i++) std::cout << " " << wbox[i]; std::cout << std::endl; // Les lettres correspondantes à celles de la chaîne se retrouvent dans les positions appropriées. // Les autres lettres se retrouvent dans la position des jokers. bool ok=true; // Il se peut que le test ne soit pas correct. int miss = cbox[0]; for(int i=1; i < next; i++) { // Pas la façon la plus optimale, ne coùte pas cher si le nombre de jokers est faible. while(miss && wbox[i] > cbox[i]) { cbox[i]++; miss--; } if(wbox[i] > cbox[i]) { ok=false; break; } // Pas assez de lettres dans le mot. } if(miss < wbox[0]) ok=false; if(ok) { std::cout << word << std::endl; } return 0; }
Le Tout est souvent plus grand que la somme de ses parties.
@MarieMignone a écrit: > J'ai créé un code dans lequel on effectue un tirage entre 2 et 15 lettres puis il affiche tous les mots valables à partir d'une liste de 400.000 mots. Donc on compare bien la chaîne choisie à chaque mot du dictionnaire. On ne sait pas si c'est proportionel aux fréquences du Scrabble, ou avec probabilité égale pour chaque lettre. Ni si une lettre peut apparaitre plus d'une fois. Voici les fréquences du Scrabble: aaaaaaaaabbccdddeeeeeeeeeeeeeeeffgghhiiiiiiiijklllllmmmnnnnnnooooooppqrrrrrrssssssttttttuuuuuuvvwxyz** > Si le tirage fait N lettres (incluant d'éventuels jokers), il affichera des mots de N lettres. Est-ce une contrainte imposée ou une mauvaise déduction? J'ai refait mon algo en Python (parce que c'était plus facile ...) Pour un langage interprété comme Python, les performances ne sont pas si mauvaises. Avec un dictionnaire d'environ 325 000 mots, j'ai des temps de l'ordre de 700 ms à 1 s. J'aurais pu améliorer mon algo sur certains points. Par exemple, ne considérer que les mots ayant une longueur inférieure ou égale à celle de la chaîne.
Le Tout est souvent plus grand que la somme de ses parties.
J'ai refait le code en corrigeant une erreur. Dans la boucle while(wbox[i] > cbox[i]) il fallait diminuer wbox[i] et non augmenter cbox[i] qui ne doit pas être touché. Vu que je n'ai qu'un nombre aléatoire à trouver (la longueur de la chaîne), j'ai utilisé srand() et rand(). Dépendamment de la longueur de la chaîne et de sa composition, avec l'option -O3, j'obtiens des temps de 30 ms à 100 ms. - #define NAME "dico.t" #define MAXB 15 #include <iostream> #include <fstream> #include <cstdlib> #include <algorithm> #include <array> #include <random> #include <chrono> #include <string> // ... constexpr int MIN = 2; constexpr int MAX = MAXB; // ... int main(void) { // ... std::chrono::high_resolution_clock::time_point t0 = std::chrono::high_resolution_clock::now(); unsigned seed = std::chrono::system_clock::now().time_since_epoch().count(); std::string scrabble = { "aaaaaaaaabbccdddeeeeeeeeeeeeeeeffgghhiiiiiiiijklllllmmmnnnnnnooooooppqrrrrrrssssssttttttuuuuuuvvwxyz**" }; std::shuffle(scrabble.begin(), scrabble.end(), std::default_random_engine(seed)); srand(time(nullptr)); int limit = rand() % (MAX-MIN+1) + MIN; std::string chain; // Chaîne. for(int i=0; i < limit; i++) { chain.push_back(scrabble[i]); } // ... std::cout << "chaine[" << limit << "]=" << chain << std::endl; std::array<int, 256> index { 0 }; std::array<int, MAXB+1> cbox { 0 }; // Boîte pour la chaîne. int next = 0; for(int i=0; i < chain.length(); i++) { if(chain[i] == '*') cbox[0]++; else { if(index[chain[i]] == 0) { next++; // Prochin indice disponible. index[chain[i]] = next; cbox[next]=0; // Initialise la boîte pour cet indice. } cbox[index[chain[i]]]++; // Il y a déjà un indice pour cette lettre. } } next++; // ... std::string name = { NAME }; std::ifstream file(name); if(!file) { std::cerr << "Impossible d'ouvrir le fichier " << name << std::endl; exit(1); } std::string word; // Les mots. int count = 0; while(getline(file, word)) { if(chain.length() < word.length()) continue; std::array<int, MAXB+1> wbox; // Boîte pour les mots. for(int i=0; i < next; i++) { wbox[i] = 0; } for(int i=0; i < word.length(); i++) { wbox[index[word[i]]]++; } bool ok=true; int joker = cbox[0]; for(int i=1; i < next; i++) { while(joker && wbox[i] > cbox[i]) { wbox[i]--; joker--; } if(wbox[i] > cbox[i]) { ok=false; break; } // Pas assez de lettres dans le mot. } if(joker < wbox[0]) ok=false; if(ok) { count++; std::cout << word << std::endl; } } std::cout << count << " mots" << std::endl; std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now(); unsigned int time = std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count(); std::cout << (double)(time/10)/100 << " milisecondes" << std::endl; return 0; }
Le Tout est souvent plus grand que la somme de ses parties.
Optimiser recherche de mots avec 2 jokers
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.