Trichons au jeu des anagrammes vivants

LE voilà: http://vrac.quentinc.net/AnagrammesVivantes.7z Attention, code moche et pas optimisé pour la lecture.

@baptisteguil

Je crois voir que ton problème n'est pas encore résolu?

Comment lances-tu le script?

Comme je suis un peu rouillé en algo, je tenterai sûrement dans les jours qui suivent juste de pondre un code avec vos algos.

Bravos à ceux qui ont fait un code.

Bon, apres verification mon algo est tres semblable aux precedents, mais je vais quand meme le poster, ca en fera un en c++¹

  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

#include <algorithm>
#include <cstdio>
#include <queue>
#include <string>

using namespace std;

const int MAX_MOTS = 500*1000;
const int TAILLE_MAX = 26;
const int INVALIDE = -1;

struct Mot
{
  int id;
  string chaine;
  string normal;
  int pere;
  bool dejaVu;
  Mot(string _chaine = "")
  {
      chaine = _chaine;
      normal = _chaine;
      sort(normal.begin(), normal.end());
      dejaVu = false;
  }
  bool operator < (const Mot& droite) const
  {
      return normal < droite.normal;
  }
};

int nbMots;
char buffer[TAILLE_MAX];
string source, dest, a, b;
Mot dico[MAX_MOTS];
queue<int> file;
int maxi;

int findMot(string normal)
{
  int deb = 0, fin = nbMots, mil;
  while(deb < fin-1)
  {
      mil = (deb+fin)/2;
      if(dico[mil].normal > normal)
          fin = mil;
      else
          deb = mil;
  }
  return dico[deb].normal == normal ? deb : INVALIDE;
}

string insererLettre(string chaine, string lettre, int pos)
{
  chaine.insert(pos, lettre);
  return chaine;
}

void traiter(string chaine, int pere)
{
  int id = findMot(chaine);
  if(id != INVALIDE && !dico[id].dejaVu)
  {
      dico[id].dejaVu = true;
      dico[id].pere = pere;
      file.push(id);
  }
}

void ajouter(string chaine, int pere)
{
  traiter(chaine, pere);
  int curPos = 0;
  for(char iLettre = 'a'; iLettre <= 'z'; ++iLettre)
  {
      while(curPos < (int)chaine.size() && iLettre > chaine[curPos])
          ++curPos;
      traiter(insererLettre(chaine, string(1, iLettre), curPos), pere);
  }
}

int bfs(string source, string dest)
{
  file.push(findMot(source));
  while(file.size())
  {
      Mot& curMot = dico[file.front()];
      file.pop();
      if(curMot.normal == dest)
          return curMot.id;
      string nouveau = curMot.normal;
      ajouter(nouveau, curMot.id);
      nouveau.erase(0,1);
      ajouter(nouveau, curMot.id);
      for(int iLettre = 0; iLettre < (int)curMot.normal.size()-1; ++iLettre)
      {
          nouveau[iLettre] = curMot.normal[iLettre];
          ajouter(nouveau, curMot.id);
      }
  }
  return INVALIDE;
}

void genererDico()
{
  FILE * fDico = fopen ("dico.txt","r");
  while(fscanf(fDico, " %s", buffer) != EOF)
      dico[nbMots++] = Mot(buffer);
  sort(dico, dico + nbMots);
  for(int iMot = 0; iMot < nbMots; ++iMot)
      dico[iMot].id = iMot,
      maxi = max(maxi, (int)dico[iMot].chaine.size());
}

void lireEntree()
{
  printf("Source : ");
  scanf(" %s", buffer);
  source = buffer;
  a = buffer;
  sort(source.begin(), source.end());
  while(findMot(source) == INVALIDE)
  {
      printf("Mot Invalide\nSource : ");
      scanf(" %s", buffer);
      source = buffer;
      a = buffer;
      sort(source.begin(), source.end());
  }
  printf("Destination : ");
  scanf(" %s", buffer);
  dest = buffer;
  b = buffer;
  sort(dest.begin(), dest.end());
  while(findMot(dest) == INVALIDE)
  {
      printf("Mot Invalide\nDestination : ");
      scanf(" %s", buffer);
      dest = buffer;
      b = buffer;
      sort(dest.begin(), dest.end());
  }
}

int main()
{
  genererDico();
  lireEntree();
  int curMot = bfs(dest, source);
  printf("\n");
  if(curMot != INVALIDE)
  {
      printf("%s\n", a.c_str());
      while(dico[curMot].normal != dest)
      {
          curMot = dico[curMot].pere;
          if(dico[curMot].normal != dest)
              printf(" %s\n", dico[curMot].chaine.c_str());
      }
      printf("%s\n\n", b.c_str());
  }
  else
      printf("Il n'existe pas de chemin entre \"%s\" et \"%s\".\n", a.c_str(), b.c_str());
  return 0;
}

Pour la complexite temps/memoire ca donne :

Si vous voulez que j'explique un peu plus les details de mon algo, je pourrais le faire

Edit: je viens de me rendre compte que j'avais pas parle de mes vraies perfs. Donc pour le moment, en attendant que je puisse bien edit :

• 1m si dans le pire cas, si je dois parcourir tout le graphe,
• 1s pour zeste/mot,

  Source : mot
  Destination : zeste

  mot => sot => set => etes => zeste

• et 25s pour adherence/coquille

  Source : adherence
  Destination : coquille

  adherence => dechainer => chaudiere => doucherai => choquerai => calorique => coquiller => coquille

Hello !

J'ai commencé un truc et je commence à m'attaquer aux parties un peu plus compliqués. Je fais ça en Python car je connais pas grand chose d'autres. J'ai un peu du temps à perdre et ça peut m'apprendre les bases de l'algorithmie.

Bref, pour le moment je bute sur par grand chose je pense. J'ai implémenté la distance de Levenshtein simple. Elle fonctionne (enfin je crois). Par contre, les deux petites lignes nécessaires à l'implémentation de la transposition en plus de la suppression, l'ajout et le remplacement ne veulent pas fonctionner…

Je vous mets le code ici. Le code incriminé est celui en commentaire (ligne 87 à 92). L'erreur est in truc du genre string index out of range. Je comprends bien ce que ça veut dire mais je vois pas trop pourquoi…

Après j'ai bêtement implémenté ça, parce que certain d'entre vous parle de distance Leveinshtein <= 1, tout ça tout ça, mais en fait je ne vois pas l'utilité (oui, c'est le bon moment pour m'interroger, après l'avoir implémenté ^^). Mais pour moi chien et niche sont bien des anagrammes, pourtant leur distance Leveinshtein est de 4… Peut-être que vous parler de distance Damerau-Levenshtein ?

Modification : j'ai trouvé la solution à mon problème, mais je sais toujours pas à quoi elle me sert cette distance, quel soit de Damerau-Levenshtein ou que de Levenshtein…

Exemple : Selon la règle, on peut passer de MIGRAINES à IMAGINER alors que si j'ai bien compris vos postes (ce qui est pas gagner), vous éliminez cette possibilité parce que la distance Damerau-Levenshtein est de 5…

La distance de Levenshtein originale ne tient en effet pas du tout compte des anagrammes; entre chien et niche on a bien 5.

Par contre pour le jeu, il doit y avoir une exception; on doit considérer que la distance entre chien et niche = 0. Si tu ne prends pas en compte cette exception, ton algorithme de recherche de chemin sera nécessairement faussé.

C'est bien de comprendre ce que fait un algorithme, mais c'est encore plus important de savoir en quoi il est utile pour résoudre le problème, quelles sont ses limites et comment le modifier pour qu'il colle exactement aux règles. Au final, on produit une version adapté de l'algorithme de base.

Vivi c'est sûr ! Mais j'ai jamais vraiment fait de programme qui demande un peu à réfléchir. J'ai juste pioché les idées dans le sujet. Mais bon je suis content, j'ai réussi à l'implémenter.

Du coup j'ai voulu partir faire abstraction de cette implémentation en me lançant tête baisser dans une autre direction, et ça marche plutôt pas mal je trouve :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def is_anagram(word1,word2):
    letter_in_word1 = word_to_dict(word1) # la fonction word_to_dict() ne fait que
    letter_in_word2 = word_to_dict(word2) # compter le nombre d’occurrence de chaque lettre

    diff = 0

    for letter in letter_in_word1:
       diff += abs(letter_in_word2[letter]-letter_in_word1[letter])

    return diff <= 1

En relisant le code, je me dis qu'il doit être buggé ou plutôt ne doit pas faire ce qu'on lui demande exactement.

Du coup je viens de corriger comme ça : (c'est pas très beau)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def is_anagram(word1,word2):
    letter_in_word1 = word_to_dict(word1)
    letter_in_word2 = word_to_dict(word2)

    diff1 = 0
    for letter in letter_in_word1:
       diff1 += abs(letter_in_word2[letter]-letter_in_word1[letter])

    diff2 = 0
    for letter in letter_in_word2:
       diff2 += abs(letter_in_word1[letter]-letter_in_word2[letter])

    diff = max(diff1,diff2)

    return diff <= 1

Pourquoi ne pas faire:

1
2

def is_anagram(w1,w2):
    return ''.join(sorted(w1)) == ''.join(sorted(w2))

Edit: ok, j'ai mal lu, tu fais plus que simplement vérifier la présence d'un anagrame. N'empêche que c'est moche

Utilisez Counter

1
2
3
4

>>> c = Counter("Edward Gorey".lower())
>>> d = Counter("Ogdred Weary".lower())
>>> c == d
True

@olzd: parce que j'y ai pas pensé / ne connaît pas assez python / suis bête. Merci à toi et fred1599.

QuentinC : je n'ai pas trop le temps de regarder ton code pour l'instant, mais 75s pour générer un trie, ça me paraît absolument énorme. J'ai un programme qui en génère un à partir d'une liste de 315k mots pour trouver par la suite tous les mots d'une grille de ruzzle, et la totalité de l'exécution (construction du trie + backtrack sur une grille d'exemple) prend moins d'une demi-seconde. Tu as probablement un souci de complexité quelque part.

QuentinC : je n'ai pas trop le temps de regarder ton code pour l'instant, mais 75s pour générer un trie, ça me paraît absolument énorme. J'ai un programme qui en génère un à partir d'une liste de 315k mots pour trouver par la suite tous les mots d'une grille de ruzzle, et la totalité de l'exécution (construction du trie + backtrack sur une grille d'exemple) prend moins d'une demi-seconde. Tu as probablement un souci de complexité quelque part.

Je me suis aussi essayé au jeu du ruzzle présenté sur PDP. Oui, en fait je n'ai pas été assez précis dans mon explication: le chargement dans le trie met effectivement moins d'une seconde. Ce qui prend autant de temps, c'est son optimisation/compression en un trie minimal; et en fait, en réfléchissant bien, finalement, ce n'est pas si indispensable que ça, si on fait les deux premières étapes directement à la suite l'une de l'autre. Je voulais faire ça pour finir avec un dictionnaire de 600 Ko plutôt que des dizaines voire centaines de Mo.

Comment passe-t-on de TEST à ZESTE en une seule étape ? Il me semble qu'on remplace T par Z et qu'on ajoute un E. Un anagramme a-t-il le droit de dupliquer ou réunir deux lettres identiques ?

Je pense que c'est une erreur effectivement. La règle stipule que c'est SOIT changer une lettre, SOIT en rajouter une.

Je confirme, il y a une erreur.

La règle exacte est :

Anagramme et (ajout d'une lettre ou suppression d'une lettre ou modification d'une lettre ou rien)

L'anagramme étant défini comme un strict mélange des lettres.

Bonsoir, Exercice intéressant.

Mais si j'ai bien lu les différents algorithmes proposés, tous font un parcours très systématique de l'arbre. On part d'un des mots, on cherche tous ses voisins directs, puis les voisins directs des voisins , jusqu'à arriver à l'autre mot. Du coup pour aller de IRE à HYDROTHERAPIQUE, on galère beaucoup et on parcours à peu près tout le dictionnaire, alors que pour aller de HYDROTHERAPIQUE à IRE, j'imagine que ça doit aller un peu plus vite ?

Ok, la fonction FListeVoisins est incontournable. Mais personne n'a pensé à une fonction FCalculeDistMiniTheorique() ?

Par exemple, entre IRE et HYDROTHERAPIQUE, on sait avant même de commencer qu'il faudra au moins 12 étapes (car 12 lettres à ajouter) ; idem, entre SAVOIR et ZESTE, la distance théorique est de 5 (remplacer les 4 lettre AVOI par ZETE , puis retirer le R , par exemple) Cette fonction sera très utile. Par exemple si on cherche à aller de SAVOIR à ZESTE, on va recenser les voisins de SAVOIR, donc LAVOIR, SAVOIRS, REVOIS, OUVRIS plus tout un tas d'autres mots. Et tout de suite, on voit que REVOIS nous rapproche de ZESTE ( plus que 4 étapes si tout va bien). Alors que OUVRIS ne nous rapproche pas de SAVOIR (on a remplacé A par U ; toujours 5 étapes minimum) Et LAVOIR ou SAVOIRS nous éloignent de ZESTE (6 étapes minimum pour aller de LAVOIR à ZESTE)

On va donc explorer prioritairement la piste SAVOIR-REVOIS-???-ZESTE plutôt que la piste SAVOIR_OUVRIS-???-ZESTE Si la piste SAVOIR-REVOIS-???-ZESTE aboutit effectivement en 5 étapes, parfait, sinon on va explorer une autre piste.

Avec un algorithme un peu pointu, on peut arriver à ces résultats : Pour aller de IRE à HYDROTHERAPIQUE (ou l'inverse), nombre d'appels aux 2 fonctions FListeVoisins() et FCalculeDistMiniTheorique() : 810 Pour aller de ZESTE à SAVOIR, nombre d'appels à ces 2 fonctions : 170.

@Elegance: c'est le boulot d'un algorithme de recherche de chemin comme A* de déterminer successivement les prochaînes étapes qui ont le plus de chances de rapprocher de la solution. ET pour cela on utilise une euristique, autrement dit une fonction qui estime la distance entre deux mots, à priori. La technique de base, c'est qu'à chaque pas on regarde l'issue qui semble être la plus proche du but.

Tout comme pour un espace en 2D on utilise la distance euclydienne (ou éventuellement la distance de Manatann) pour estimer l'espacement entre deux points à priori, sans savoir s'il y a des obstacles sur la route, ici dans le cadre de nos mots, c'est la distance de Levenshtein qu'on utilise.

Ta fonction qui calcule le nombre minimal de modifications est en fait incluse dans le cadre du calcul de la distance de Levenshtein. A mon avis, ce n'est pas vraiment utile d'avoir un truc encore plus générique comme celui que tu proposes, sauf si on était capable de découper l'espace du dictionnaire en zones et de parcourir en rpemier lieu un graphe plus global, à l'image dans un plan 2D de presqu'îles ou bien de pièces et de corridors où il n'y a au plus que 3 ou 4 entrées/sorties générales par zone. Je ne sais pas dans quelle mesures les optimisations qu'on peut faire sur A pour les plans 2D/3D ayant ce genre de terrain marcheraient ici… je ne connais pas suffisament A pour le dire. difficile de voir ce que pourrait être une « zone ». En plus il faut un moyen rapide de les calculer, sinon ça n'a aucun intérêt.

Du coup pour aller de IRE à HYDROTHERAPIQUE, on galère beaucoup et on parcours à peu près tout le dictionnaire, alors que pour aller de HYDROTHERAPIQUE à IRE, j'imagine que ça doit aller un peu plus vite ?

Pas vraiment, en réalité (46 secondes vs 53 chez moi). Ici, ça vient de la structure du graphe qui relie l'ensemble des mots et de la manière dont sont reliés ces deux là.

Dans le fichier dictionnaire d'exemple, la recherche d'un mot relié à rien échoue systématiquement à la 29ème étape (dernier mot trouvé à la 28ème) après le traitement de 299 828 mots. Ce qui signifie tout simplement :

• qu'il y a un groupe de 299 828 mots interconnectés dans l'ensemble des mots existants (92.66% du total),
• que prendre 2 mots dans ce groupe garantit qu'il existe un chemin possible,
• et qu'il sera de longueur 28 au maximum (puisque c'est la profondeur maximale atteinte en parcourant tout le graphe)

Si on cherche une paire de mots très éloignés (comme dans l'exemple ci-dessus), on doit parcourir tout l'arbre (avec ma méthode en tous cas). Donc quel que soit le mot de départ on va mettre à peu près le même temps, sous réserve de choisir une paire de mots dans le graphe principal. La seule différence va venir du mot de début : est-ce qu'il donne beaucoup de possibilités dès les premières itérations ? Si oui, ça ira un peu plus vite, parce qu'on va éliminer plus vite des possibilités.

Dans le fichier dictionnaire d'exemple, la recherche d'un mot relié à rien échoue systématiquement à la 29ème étape (dernier mot trouvé à la 28ème) après le traitement de 299 828 mots. Ce qui signifie tout simplement :

• qu'il y a un groupe de 299 828 mots interconnectés dans l'ensemble des mots existants (92.66% du total),
• que prendre 2 mots dans ce groupe garantit qu'il existe un chemin possible,
• et qu'il sera de longueur 28 au maximum (puisque c'est la profondeur maximale atteinte en parcourant tout le graphe)

Tes observations sur la topologie du graphe sont intéressantes. Instinctivement je ne pensais pas qu'il y avait des « îles » complètement isolées du reste. Le diamètre de 28 est aussi amusant.

Je me demande en quoi ça changerait si on jouait dans une autre langue, par exemple en anglais. J'ai pas de dico anglais pour essayer, zut.

Du coup pour aller de IRE à HYDROTHERAPIQUE, on galère beaucoup et on parcours à peu près tout le dictionnaire, alors que pour aller de HYDROTHERAPIQUE à IRE, j'imagine que ça doit aller un peu plus vite ?

Pas vraiment, en réalité (46 secondes vs 53 chez moi). Ici, ça vient de la structure du graphe qui relie l'ensemble des mots et de la manière dont sont reliés ces deux là.

Mon exemple n'était pas parfait. Imaginons qu'on cherche à aller de IRE à ZYGOMATIQUE. Avec un parcours systématique, en partant de IRE, on va explorer à peu près tout le dictionnaire ( 300 000 sur 350 000 mots) avant de conclure qu'il n'y a pas de solution. Alors que si on inverse la question, en partant de ZYGOMATIQUE, c'est instantané pour conclure qu'il n'y a pas de solution.

L'idée de base de l'algorithme, c'est donc de bâtir 2 demi-arbres (un en partant de chacun des 2 mots donnés) et de voir quand ces 2 demi-arbres se rejoignent. L'autre idée, c'est de ne pas explorer des pistes peu prometteuses. Si on veut relier ZESTE à SAVOIR, ZESTE a de 42 voisins. Par exemple PESTE, PENTE, ZESTES, SEIZE. Mais très facilement, avec une fonction calcule_distance_théorique(), on voit que SEIZE nous rapproche de SAVOIR, alors que PENTE nous en éloigne. On va donc explorer les voisins de SEIZE, putot que les voisins de PESTE ou PENTE. Si on recherche tous les voisins de ces 42 mots, le traitement est 42 fois plus long que rechercher les voisins de SEIZE uniquement.

Pour relier ZESTE à SAVOIR, avec un algorithme 'brutal', on appelle plus de 11000 fois la fonction 'Rechercher tous les voisins d'un mot'. Avec un algorithme optimisé, on appelle cette fonction seulement 8 fois. Le bénéfice est énorme.

Le parcours obtenu peut donner cela :

*Recherche d'un chemin de ZESTE à SAVOIR :

Chemin à priori le plus efficace = ZESTE-?-SAVOIR

Recensement des voisins directs de ZESTE ; Nbre de voisins trouvés = 42

Recensement des voisins directs de SAVOIR ; Nbre de voisins trouvés = 62

ZESTE a 42 voisins, contre 62 pour SAVOIR ; j'explore donc les voisins de ZESTE

Chemin à priori le plus efficace = ZESTE-SEIZE-?-SAVOIR

Recensement des voisins directs de SEIZE ; Nbre de voisins trouvés = 32

SEIZE a 32 voisins, contre 62 pour SAVOIR ; j'explore donc les voisins de SEIZE

Chemin à priori le plus efficace = ZESTE-SEIZE-RISEE-?-SAVOIR

Recensement des voisins directs de RISEE ; Nbre de voisins trouvés = 65

RISEE a 65 voisins, contre 62 pour SAVOIR ; j'explore donc les voisins de SAVOIR

Chemin à priori le plus efficace = ZESTE-SEIZE-RISEE-?-ROSAI-SAVOIR

Recensement des voisins directs de ROSAI ; Nbre de voisins trouvés = 65

RISEE a 65 voisins, contre 65 pour ROSAI ; j'explore donc les voisins de ROSAI

RISEE et ROSAI ont un voisin commun : SEOIR ! Solution trouvée !

ZESTE SEIZE RISEE SEOIR ROSAI SAVOIR *

SpaceFox a évoqué cette idée précédemment, apparemment c'est pas génial.