Créer un jeu du mot mêlé

Salut à tous et bonne année ! :)

J'ai vu ce matin un énoncé pour un concours nommé prolo*** qui consistait à créer un algo mots mêlés.
J'ai trouvé cela pas mal et, étant donné que je débute en C, je me suis dit que j'allais tenter l'exo.

Le principe est simple on écrit:

Citation:

---

-Sur la première ligne, trois entiers : N, M, P, séparés par un espace.
-Sur les P lignes suivantes, la liste des mots à chercher dans la grille. Chaque mot contiendra entre 1 et 500 lettres majuscules.
-Sur les N lignes suivantes, la grille. Chacune des lignes de la grille est une chaîne de M lettres majuscules.

---

Citation:

---

ex: (cette fonction renvoie 3 pour la liste de mots RAT,MANGER,BAZAR,CODER)
BAZARD
ARTRG
ZAMAN
ATYNQ
REDOC

---

Je me demande comment faire cela car, à ce qu'il parrait je suis capable de le faire avec ce que j'ai appris depuis le début de l'année. Cependant, je ne vois absolument pas comment, par exemple pouvoir reconnaitre un mot écrit en colone ou un mot écrit à l'envers...

Citation:

---

Envoyé par Glopsos

Je me demande comment faire cela car, à ce qu'il parrait je suis capable de le faire avec ce que j'ai appris depuis le début de l'année. Cependant, je ne vois absolument pas comment, par exemple pouvoir reconnaitre un mot écrit en colone ou un mot écrit à l'envers...

---

Problème d'algorithme. Rien à voir avec le langage C.

Il suffit d'organiser les données dans un tableau à 2 dimensions, puis pour chaque mot, chercher un pattern caractères par caractères.

• ligne W-E
• ligne E-W
• colonne N-S
• colonne S-N
• diagonale NW-SE
• diagonale NE-SW

(rappel : W=Ouest, E=Est, etc.)

Ca fait beaucoup de boucles, mais ce n'est pas très compliqué... En gros, dès qu'il y a une différence, on arrête la recherche en cours.

Citation:

---

Envoyé par Emmanuel Delahaye

Problème d'algorithme. Rien à voir avec le langage C.

Il suffit d'organiser les données dans un tableau à 2 dimensions, puis pour chaque mot, chercher un pattern caractères par caractères.

• ligne W-E
• ligne E-W
• colonne N-S
• colonne S-N
• diagonale NW-SE
• diagonale NE-SW

(rappel : W=Ouest, E=Est, etc.)

Ca fait beaucoup de boucles, mais ce n'est pas très compliqué... En gros, dès qu'il y a une différence, on arrête la recherche en cours.

---

C'est clairement pas vraiment dutout ce qui se fait de plus efficace hein... Je te conseille de regarder du coté des algorithme pour détecter une sous chaine de caractère, puis de les appliquer dans tous les sens possibles.

Citation:

---

Envoyé par alex_pi

C'est clairement pas vraiment dutout ce qui se fait de plus efficace hein... Je te conseille de regarder du coté des algorithme pour détecter une sous chaine de caractère, puis de les appliquer dans tous les sens possibles.

---

Vu qu'il s'agit de détecter un ensemble de mot, tu peux également regarder du côté des trie ("arbres à lettres"), pour ne faire qu'une boucle par "ligne" au lieu de P boucles.

NB : Il y a déjà un sujet sur cet exercice sur ce forum, une petite recherche t'en dirait plus.
--
Jedaï

Citation:

---

Envoyé par Jedai

NB : Il y a déjà un sujet sur cet exercice sur ce forum, une petite recherche t'en dirait plus.
--
Jedaï

---

Hmm... ma recherche n'a pas été fructueuse...

Citation:

---

Il suffit d'organiser les données dans un tableau à 2 dimensions

---

C'est à dire explicitement? (c'est peut être explicite et j'en suis confus, mais je suis débutant et je n'ai pas compris :) )

Code:

---

1 2	diagonale NW-SE diagonale NE-SW

---

Je vais déjà essayer de faire les colones et EW...:P

Citation:

---

Vu qu'il s'agit de détecter un ensemble de mot, tu peux également regarder du côté des trie ("arbres à lettres"), pour ne faire qu'une boucle par "ligne"

---

Ca fonctionne aussi pour les colones?

Merci pour toutes ces réponses, je vais commencer l'algo :)

Citation:

---

Envoyé par alex_pi

C'est clairement pas vraiment dutout ce qui se fait de plus efficace hein... Je te conseille de regarder du coté des algorithme pour détecter une sous chaine de caractère, puis de les appliquer dans tous les sens possibles.

---

C'est sûr, mais il faut bien démarrer par quelque chose de compréhensible par un débutant.

Citation:

---

Il suffit d'organiser les données dans un tableau à 2 dimensions

---

J'aurais besoin d'en savoir plus afin d'essayer de commencer l'exercice... :)

L'idéal serait d'utiliser un tri arbre à lettre et de lire horizontalement puis verticalement le tableau. Cependant, j'ai besoin de tutos et/ou de votre aide.
Google ne m'a pas becoup aidé pour le moment...

Citation:

---

Envoyé par Emmanuel Delahaye

C'est sûr, mais il faut bien démarrer par quelque chose de compréhensible par un débutant.

---

Dans ce cas, il ne faut peut être pas s'attaquer à prologin...

Aha en cherchant depuis qques temps comment faire un programme pour monter un site de générateur de mots mêlés je suis tombé sur ce thread.
Je peux te donner le code que j'ai utilisé si tu vx, n'hésite pas à m'enovyer un message :)

Bonjour,

J'aurais tendance à faire un tableau A à 2 dimensions des caractères augmenté d'une colonne et d'une ligne dans lesquels je mets un caractère séparateur (un espace par exemple) puis suivre le processus suivant :

1. Compléter la liste des mots à chercher de X, Y, D (un tableau B de structures serait mieux). (X, Y) désigne la case où débute le mot trouvé et D donne le sens de lecture. (X,Y) initialisés à (-1,-1) pour indiquer "non trouvé".
2. Pour chaque direction et sens (donc 8)
3. Créer une grande chaine de caractères de la taille du tableau par concaténation à partir de A (les séparateurs inclus évitent de trouver de faux mots, par exemple à cheval sur la fin d'une ligne et le début de la suivante)
4. Pour chaque mot i à rechercher (B[i].X < 0)
5. Chercher dans la chaîne
6. Si trouvé, recalculer sa position (B[i].X, B[i].Y) d'origine (facile en H et V, un peu plus difficile en diagonal). Noter également de sens de lecture B[i].D.
7. That's all folks !

Salutations