Discussion :

[bogoss91]

Salut! Dans le cadre du concours informatique Prologin, je cherche à faire un programme qui trouverai le nombres de mots qu'on lui demande de chercher et qui sont présents dans la grille, chaque mot pouvant être comptabilisé qu'une fois.

J'ai déjà un fait le programme de recherche par la méthode naïve :

On lit la première ligne, puis, pour chaque mot, on teste si on les voit dans la ligne. Si on les voit, on remplace le mot par un caractère qui ne peut pas être présent dans la grille (par exemple 1), pour qu'il ne soit pas compté 2 fois. Puis ont fait pareil avec les lignes suivantes.
Idem pour les colones.

Ensuite j'ai pensé à utiliser une liste chainée, pour pouvoir supprimer les mots qu'on a trouvé de la liste. (J'ai essayé et ça m'a sortit plein d'erreur, mais bon, c'est pas ma question).


Donc je demande, y a-t-il une meilleure méthode de recherche de mots?

[Jedai]

L'idéal serait sûrement d'utiliser un trie (arbre à lettre) contenant les mots du dictionnaires, et de lire horizontalement puis verticalement la grille, en maintenant un ensemble de curseurs dans le trie tant que le mot depuis une case précédente jusqu'à la case présente est présent dans le trie (et donc un préfixe potentiel d'un des mots du dictionnaire).

--
Jedaï

[bogoss91]

J'avoue ne pas avoir bien saisi le concept (et google est pas très explicatif...).

J'ai aussi oublié de préciser que les mots peuvent être à l'endroit ou à l'envers dans la grille.

[Zavonen]

http://en.wikipedia.org/wiki/Trie

Si, Google est assez explicatif, et l'exemple qu'il donne permet de comprendre vite de quoi il s'agit.
Le fait que les mots puissent être à l'endroit ou à l'envers t'obligera simplement à parcourir ta grille une fois dans le bon sens et une fois en sens inverse, sur les lignes et sur les colonnes, 4 parcours donc.
Les difficultés sont:

• La représention d'un 'trie', mais après tout ce sont des arbres comme tous les autres (donc pointeurs ou listes selon le type de langage utilisé).
• Une interface conviviale pour remplir ton arbre (les wxwidgets, disponible avec beaucoup de langages et sur la plupart des plate-formes, proposent des contrôles 'ready-made' à utiliser sur un formulaire).
• Le parcours de la grille, en cas d'échec il faut revenir à la première position suivant la lettre qui à permis de commencer le parcours de l'arbre.

[bogoss91]

Si, Google est assez explicatif, et l'exemple qu'il donne permet de comprendre vite de quoi il s'agit.
Le fait que les mots puissent être à l'endroit ou à l'envers t'obligera simplement à parcourir ta grille une fois dans le bon sens et une fois en sens inverse, sur les lignes et sur les colonnes, 4 parcours donc.
Les difficultés sont:
la représention d'un 'trie', mais après tout ce sont des arbres comme tous les autres (donc pointeurs ou listes selon le type de langage utilisé).
Le parcours de la grille, en cas d'échec il faut revenir à la première position suivant la lettre qui à permis de commencer le parcours de l'arbre.

Merci, je vais lire le lien que tu m'as donné.
Mes recherches n'avaient pas abouti, car j'avais tapé arbre à lettres dans google (je te laisse voir ce que ça donne...).

[Jedai]

Les difficultés sont:

• Une interface conviviale pour remplir ton arbre (les wxwidgets, disponible avec beaucoup de langages et sur la plupart des plate-formes, proposent des contrôles 'ready-made' à utiliser sur un formulaire).
• Le parcours de la grille, en cas d'échec il faut revenir à la première position suivant la lettre qui à permis de commencer le parcours de l'arbre.

Je ne pense pas que le but soit de fournir une jolie interface, en tout cas sûrement pas pour remplir le trie (la grille et la présentation des résultats je ne dis pas), mais que vient faire WxWidget dans une discussion sur un concours d'algorithmique ??
Il dispose déjà d'un dictionnaire (une liste de mot), il lui suffit donc d'une fonction qui le transforme en trie.

Plutôt que de faire un backtracking, je proposais plutôt de maintenir en parallèle une liste de couple (préfixe, curseur dans le trie), évitant ainsi de devoir lire plus de 4 fois une lettre (éventuellement 2 fois si on a fait un trie inversé, mais je suis pratiquement sûr que ça ne vaut pas le coup, sauf si les grilles sont vraiment énormes)

--
Jedaï

[Zavonen]

mais que vient faire WxWidget dans une discussion sur un concours d'algorithmique

C'est un produit 'open source' et je n'ai donc pas d'actions dans la maison. Juste histoire de ne pas réinventer la rue et de se concentrer sur le problème principal.