Demande propositions améliorations ("bonnes pratiques")

**lautrec1** · 10/11/2014, 16h24

Bonjour,

J'ai un code opérationnel que j'aimerais améliorer avec votre aide. En effet, on m'a déjà dit que je n'avais pas de bonne pratiques de programmation. Je me suis appliqué pour mon projet et certains d'entre vous m'ont déjà aidé d'un point de vue technique (de mémoire je pense S@ear,diogene, medinoc) Mais rien n'est jamais parfait. J'aimerais vos conseils pour qu'ils puissent m'aider à apprendre les "bonnes pratiques" du C.

Voilà le problème que le programme résoud:
En données :

- un fichier contenant une grille de caractères
- un fichier contenant un mot par ligne

Le but du jeu
On peut lire la grille dans les 8 directions (nord,sud,est,ouest,nord-ouest,sud-ouest,nord-est,sud-est).
Un mot se trouve exactement une fois dans la grille.
Lorsqu'un mot est trouvé dans la grille, les caractères qu'il a traversé sont éliminés. Une lettre peut être éliminée plusieurs fois.
Il faut afficher la suite de lettres de la grille qui n'ont pas été éliminés (après avoir traité tous les mots), dans le sens gauche-droite, haut-bas.

Méthode employée

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
Pour chaque caractère C de la grille, 
     pour les 8 directions, 
          enregistrer la sequence de caractères compris entre C et le bord de la grille.
(après cela, il y a donc C*8 chaines de caractères en mémoire, je les appelle des "sous-grilles")
 
Pour chaque mot M à trouver
      pour toutes les sous-grilles
           faire un strncpm(M,sous-grille courant)
           si le test est réussi
               éliminer les lettres présentes dans la sous-grille.
Pour ces C*8 possibilités de lire un mot M cherché

Un exemple :

La grille:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
EELLERIG
TTNBPBSM
ERTEEAEE
GOCERRHH
UEIDLUEC
OAIABMN
RNNLNTAA
ELLIPORT

Les mots à trouver : bar, raie, plie, tanche, merlan, murene, rouget, ablette, sardine, eperlan, girelle, torpille.

Ablette se trouve dans la grille en {(7,7),(6,6),(5,5),(4,4),(3,3),(2,2),(1,1)} --> direction NORD-OUEST donc.
Bar se trouve dans la grille en {(2,6),(3,6),(4,6)} --> direction SUD donc.

Après avoir éliminé toutes les lettres concernées par les mots listés, il reste (de gauche vers droite et de haut vers bas) : "BROCHET".

Voici le code commenté. TOUTE remarque est bienvenue

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
 
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
 
#define MAX_MOT 50
#define DIM_MAX 60
#define MAXGRILLE 1500
 
/*TYPES*/
const short incr1[8]= {-1,0,1, 0,-1,1, 1,-1};
const short incr2[8]= { 0,1,0,-1, 1,1,-1,-1};
enum DIRECTION {NORD=0,EST,SUD,OUEST,NORDEST,SUDEST,SUDOUEST,NORDOUEST};
 
 
typedef int indice_t;
 
typedef struct
{
  char *listeCars;
  enum DIRECTION sens;
  indice_t indice;
 
} SousGrille_t;
 
typedef struct
{
  SousGrille_t *y;
} SousGrilleParCar_t;
 
typedef struct
{
  char *grille;
  SousGrilleParCar_t *x;
  int largeur;
  int hauteur;
} GrilleMotsMeles_t;
 
 
/*PROTOTYPES*/
GrilleMotsMeles_t *initGrilleMotsMeles(FILE *);
char *initCaracteres(FILE *,int *,int *);
SousGrille_t *initElementSousGrille(char *,int,int,int,int);
void resoudreGrille(GrilleMotsMeles_t *,FILE*);
void afficherResultat(GrilleMotsMeles_t *);
void assure(void *, const char *);
 
/*SOLVEUR DE MOTS MELES
 PRE: "tableau.txt" contient la grille de caractères
      "mots.txt" contient un mot par ligne. Ce sont les mots dont les caractères doivent être
		barrés dans la grille
 POST "result.txt" contient la suite de lettre de la grille qui n'ont pas été barrées 
	(sens gauche vers droite, haut vers bas)
*/
int main()
{
GrilleMotsMeles_t *grillemelimelo;
FILE* fGrille;
FILE* fMots;
 
	/*redirection de la sortie standard vers RESULT.TXT*/
	freopen("RESULT.TXT","w",stdout);
 
	/*initialise la grille et les structures sous-jacentes*/
	fGrille=fopen("tableau.txt","r");
	grillemelimelo=initGrilleMotsMeles(fGrille);
 
	/*trouve les mots à chercher dans la grille et barre les lettres une fois trouvées*/
	fMots=fopen("mots.txt","r");
	resoudreGrille(grillemelimelo,fMots);
 
	/*affiche les lettres qui n'ont pas été barrées*/
	afficherResultat(grillemelimelo);
 
	return 1;
}
 
/*initialisation de la structure GrilleMotMeles_t à partir d'un tableau de caractères présent
dans le fichier fichierGrille*/
GrilleMotsMeles_t *initGrilleMotsMeles(FILE *fichierGrille)
{
GrilleMotsMeles_t *p;
SousGrille_t *tmp;
indice_t tailleGrille;
int i,j;
 
	p=(GrilleMotsMeles_t *)malloc(sizeof(GrilleMotsMeles_t));
    assure(p,"initGrilleMotsMeles: erreur malloc");
 
	/*on a besoin d'avoir tous les caractères de la grille de mots mêlés*/
	p->grille=initCaracteres(fichierGrille,&(p->hauteur),(&p->largeur));
 
	tailleGrille=p->hauteur*p->largeur;
 
	p->x=calloc(tailleGrille,sizeof(SousGrilleParCar_t));
    assure(p,"initGrilleMotsMeles: erreur calloc");
 
	/*chargement des données*/
 
	/*pour tous les caractères de la grille...*/
	for(i=0;i<tailleGrille;i++) {
 
		p->x[i].y=calloc(8,sizeof(SousGrille_t));
		assure(p->x[i].y,"initCaracteres:erreur calloc");
 
		/*...pour les 8 directions DIR...*/
		for(j=0;j<8;j++) {
 
			/*...on charge les sous-grilles partant du caractère et allant jusqu'au bord de la grille, 
			dans la direction DIR*/
			tmp=initElementSousGrille(p->grille,i,p->hauteur,p->largeur,j);	  
			memcpy((p->x[i].y)+j,tmp,sizeof(SousGrille_t));
			free(tmp);
		};
	};
 
	return p;
}
 
/*charge la grille de caractères, base de la Grille de Mots Meles*/
char *initCaracteres(FILE *f,int *hauteur,int *largeur)
{
int j,k;
char *p;
char c;
long taille;
 
	p=calloc(MAXGRILLE+1,sizeof(char));
    assure(p,"initCaracteres:erreur calloc");
 
	j=0;
	taille=0;
	*largeur=0;
 
	for (k=0;(c=getc(f))!=EOF; k++)
		if (c!='\n') {
		  j++;
		  taille++;
		  /*on met la lettre en majuscules*/
		  p[k]=toupper(c);
		}
		else {
		  *largeur=j;
		  j=0;
		  k--; /*on ne met pas '\n' dans le tableau*/
		};
 
	*hauteur=taille/(*largeur);
	return p;
}
 
/*pour un caractère de la grille et une direction donnée, renvoie un pointeur sur une chaine égale
à la sous-grille partant du caractère donné, dans la direction donnée, et se terminant en bord de grille*/
SousGrille_t *initElementSousGrille(char *grille,int i, int h, int l, int numDir)
{
char tmpCar[DIM_MAX];
int k,increment;
SousGrille_t *p;
 
    p=malloc(sizeof(SousGrille_t));
    assure(p,"initElementSousGrille: erreur malloc");
 
	p->indice=i;
    p->sens=numDir;
 
	/*détermination de l'incrément des indices à partir de la direction*/
    increment=incr1[numDir]*l+incr2[numDir];
 
    k=0;
	/* il y a au moins une lettre de la grille à charger*/
	/* on les mémorise, et on charge la suivante, jusqu'à ce que celle-ci dépasse le bord de la grille*/
	/*quand on se déplace vers la gauche de la grille, on n'enregistre pas l'élement pour lequel
	  l'indice%largeur==largeur-1*/
	/*quand on se déplace vers la droite de la grille, on n'enregistre pas l'élement pour lequel
	  l'indice%largeur==0*/
    do{
		tmpCar[k++]=grille[i];
		i+=increment;
		if(incr2[numDir]>0 && i%l==0)
			break;
		else if(incr2[numDir]<0 && i%l==l-1)
			break;
 
    } while (i>=0 && i<l*h);
    tmpCar[k]='\0';
 
    p->listeCars=calloc(k+1,sizeof(char));
    assure(p->listeCars,"initSousGrille:erreur calloc");
 
    strcpy(p->listeCars,tmpCar);
 
	return p;
}
 
/*pour tous les mots M de fichierMots (un mot par ligne), on va trouver la sous-grille 
(couple caractère-directio), pour lequel le début de la sous-grille égale le mot M.*/
void resoudreGrille(GrilleMotsMeles_t *p,FILE* fichierMots)
{
char mot [MAX_MOT];
int i,k,dir,increment,len;
indice_t tailleGrille;
 
	tailleGrille=p->largeur*p->hauteur;
 
	/*tant qu'il y a une ligne contenant un mot*/
	while ((fscanf(fichierMots,"%s\n",mot))!=EOF) {
 
		len=strlen(mot);
 
		/*on met le mot en majuscules*/
		for(i=0;i<len;i++)
			mot[i]=toupper(mot[i]);
 
		/*on va rechercher dans pour tous les les caractères de la grille....*/
		for(i=0;i<tailleGrille;i++)
 
			/*...toutes les directions*/
			for(dir=0;dir<8;dir++) {
 
				/*test d'égalité entre le mot et le début de la listeCars*/
				if (0==strncmp(mot,p->x[i].y[dir].listeCars,len)) {
 
						/*la SousGrille_t [i,dir] égale le mot à trouver*/
						/*on élimine de la grille les lettres du mot trouvé, en les mettant à ' '*/
						increment=incr1[dir]*(p->largeur)+incr2[dir];
						for(k=0;k<len;k++)
							p->grille[i+k*increment]= ' ';
					}
			}			
	}
	return;
}
 
void afficherResultat(GrilleMotsMeles_t *p)
{
char c;
	/*on affiche toutes les lettres de la grilles qui n'ont pas été supprimées (= différentes de ' ')*/
	while((c=*(p->grille++))!='\0')
		if (c!=' ')
			putchar(c);
	return;
}
 
/*affiche un message si pointeur ptr NULL*/
void assure(void *ptr, const char *msg)
{
  if (ptr==NULL)
  {
    fprintf(stdout,"\n");
    fprintf(stdout,msg);
    fprintf(stdout,"\n");
    fflush(stdout);
    exit(EXIT_FAILURE);
  }
}

mots.txt tableau.txt

**diogene** · 11/11/2014, 18h19

1- Quelques critiques sur l'écriture :

- Présentation insuffisamment soignée (indentation, position des } fermantes). La présentation est extrêmement importante pour la lisibilité du code.

- Les identificateurs utilisés ne sont pas toujours signifiant ce qui est très désagréable. Par exemple dans la définition de GrilleMotsMeles_t cet x : SousGrilleParCar_t *xou le y dans SousGrilleParCar_t;

2- Quelques remarques sur le programme :

- y dans SousGrilleParCar_t; est toujours un tableau de 8 SousGrille_t, pourquoi ne pas le déclarer comme tel ?
typedef SousGrille_t SousGrilleParCar_t[8]; .

- Il y a parfois des paramètres mal choisis pour les fonctions :
char *initCaracteres(FILE *,int *,int *);. Il s'agit d'initialiser des données du GrilleMotsMeles_t : largeur, hauteur et contenu de la grille. Il est surprenant que ce GrilleMotsMeles_t (enfin son adresse) ne soit pas en argument de la fonction :void initCaracteres(FILE *f, GrilleMotsMeles_t * p).
(voir les conséquences dans le code plus bas)

SousGrille_t *initElementSousGrille(char *grille,int i, int h, int l, int numDir).
Qui devrait être simplement void initElementSousGrille(GrilleMotsMeles_t * p, int point, int numDir).
(voir les conséquences dans le code plus bas)

3- Ceci fait, on voit que les champs sens et indice de SousGrille_t; ne sont jamais utilisé et peuvent être supprimés. Ils s'en suit que SousGrilleParCar_t peut être défini simplement par typedef char * SousGrilleParCar_t[8]; et les '.listeCars' sont supprimés.

Une dernière remarque :
- il faut toujours tester la bonne ouverture d'un fichier. Tu peux utiliser pour cela ta fonction assure()

Après ses remarques le code devient quelque chose comme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
//------------------------------------------------------------------------
#define MAX_MOT 50
#define DIM_MAX 60
#define MAXGRILLE 1500
//------------------------------------------------------------------------
const short incr1[8]= {-1,0,1, 0,-1,1, 1,-1};
const short incr2[8]= { 0,1,0,-1, 1,1,-1,-1};
//------------------------------------------------------------------------
/*TYPES*/
enum DIRECTION {NORD=0,EST,SUD,OUEST,NORDEST,SUDEST,SUDOUEST,NORDOUEST};
typedef int indice_t;
typedef char * SousGrille_t;
typedef SousGrille_t SousGrilleParCar_t[8];
typedef struct
{
  char *grille;
  SousGrilleParCar_t *x;
  int largeur;
  int hauteur;
} GrilleMotsMeles_t;
//------------------------------------------------------------------------
/*PROTOTYPES*/
GrilleMotsMeles_t *initGrilleMotsMeles(FILE *);
void initCaracteres(FILE *f, GrilleMotsMeles_t * p);
void initElementSousGrille(GrilleMotsMeles_t * p, int i, int numDir) ;
void resoudreGrille(GrilleMotsMeles_t *,FILE*);
void afficherResultat(GrilleMotsMeles_t *);
void assure(void *, const char *);
//------------------------------------------------------------------------
/* SOLVEUR DE MOTS MELES
   PRE: "tableau.txt" contient la grille de caractères
        "mots.txt" contient un mot par ligne. Ce sont les mots dont les caractères
        doivent être barrés dans la grille
   POST "result.txt" contient la suite de lettre de la grille qui n'ont pas été barrées
	(sens gauche vers droite, haut vers bas)
*/
//------------------------------------------------------------------------
int main(void)
{
   GrilleMotsMeles_t *grillemelimelo;
   FILE* fGrille;
   FILE* fMots;
 
   // redirection de la sortie standard vers RESULT.TXT
   freopen("RESULT.TXT","w",stdout);
 
   //initialise la grille et les structures sous-jacentes
   fGrille=fopen("tableau.txt","r");
   assure(fGrille,"Erreur d'ouverture du fichier tableau");
   grillemelimelo=initGrilleMotsMeles(fGrille);
 
   // trouve les mots à chercher dans la grille et barre les lettres une fois trouvées
   fMots=fopen("mots.txt","r");
   assure(fMots,"Erreur d'ouverture du fichier mots");
   resoudreGrille(grillemelimelo,fMots);
 
   // affiche les lettres qui n'ont pas été barrées
   afficherResultat(grillemelimelo);
 
   return 1;
}
//------------------------------------------------------------------------
// Initialisation de la structure GrilleMotMeles_t à partir d'un tableau de caractères
// présent dans le fichier fichierGrille
GrilleMotsMeles_t *initGrilleMotsMeles(FILE *fichierGrille)
{
   GrilleMotsMeles_t *p;
   SousGrille_t *tmp;
   indice_t tailleGrille;
   int i,j;
 
   p=(GrilleMotsMeles_t *)malloc(sizeof(GrilleMotsMeles_t));
   assure(p,"initGrilleMotsMeles: erreur malloc");
   initCaracteres(fichierGrille,p);
 
   tailleGrille = p->hauteur*p->largeur;
   p->x = calloc(tailleGrille,sizeof(SousGrilleParCar_t));
   assure(p,"initGrilleMotsMeles: erreur calloc");
   // pour tous les caractères de la grille et toutes les directions
   for(i=0;i<tailleGrille;i++)
      for(j=0;j<8;j++) initElementSousGrille(p,i,j);
   return p;
}
//------------------------------------------------------------------------
// Charge la grille de caractères, base de la Grille de Mots Meles
void initCaracteres(FILE *f, GrilleMotsMeles_t * p)
{
   int j,k;
   char c;
   long taille;
   p->grille=calloc(MAXGRILLE+1,sizeof(char));
   assure(p->grille,"initCaracteres:erreur calloc");
   j=0;
   taille=0;
   p ->largeur=0;
   for (k=0;(c=getc(f))!=EOF; k++)
      if (c!='\n') 
      {
         j++;
         taille++;
         p->grille[k]=toupper(c); // on met la lettre en majuscules
      }
      else 
      {
         p->largeur=j;
         j=0;
         k--; // on ne met pas '\n' dans le tableau
      };
      p->hauteur=taille/p->largeur;
// faire suivre d'une reallocation
}
//------------------------------------------------------------------------
// Pour un caractère en position point de la grille construit la sous-grille
//   dans une direction donnée numDir
void initElementSousGrille(GrilleMotsMeles_t * p, int point, int numDir)
{
   char tmpCar[DIM_MAX];
   int k,increment;
   int i;
   //détermination de l'incrément des indices à partir de la direction
   increment=incr1[numDir]*p->largeur+incr2[numDir];
   // il y a au moins une lettre de la grille à charger*/
   // on les mémorise, et on charge la suivante, jusqu'à ce que celle-ci dépasse
   // le bord de la grille
   // quand on se déplace vers la gauche de la grille, on n'enregistre pas l'élement
   // pour lequel l'indice%largeur==largeur-1
   // quand on se déplace vers la droite de la grille, on n'enregistre pas l'élement
   // pour lequel l'indice%largeur==0
   k=0;
   i=point;
   do
   {
      tmpCar[k++]=p->grille[i];
      i+=increment;
      if(incr2[numDir]>0 && i%p->largeur==0) break;
      else if(incr2[numDir]<0 && i%p->largeur==p->largeur-1) break;
    } while (i>=0 && i<p->largeur*p->hauteur);
    tmpCar[k]='\0';
    p->x[point][numDir] = calloc(k+1,sizeof(char));
    assure(p->x[point][numDir],"initSousGrille:erreur calloc");
    strcpy(p->x[point][numDir],tmpCar);
}
//------------------------------------------------------------------------
// Pour tous les mots M de fichierMots (un mot par ligne), on va trouver la
// sous-grille pour lequel le début de la sous-grille égale le mot M.
void resoudreGrille(GrilleMotsMeles_t *p,FILE* fichierMots)
{
   char mot [MAX_MOT];
   int i,k,dir,increment,len;
   indice_t tailleGrille = p->largeur*p->hauteur;
   // tant qu'il y a une ligne contenant un mot
   while ((fscanf(fichierMots,"%s\n",mot))!=EOF)
   {
      len=strlen(mot);
      for(i=0;i<len;i++) mot[i]=toupper(mot[i]);  // on met le mot en majuscules
      // on va rechercher dans pour tous les caractères de la grille....
      for(i=0;i<tailleGrille;i++)
         for(dir=0;dir<8;dir++)  //dans toutes les directions
            if (0==strncmp(mot,p->x[i][dir]/*.listeCars*/,len))
            {
               // la SousGrille_t [i,dir] égale le mot à trouver
               // on élimine de la grille les lettres du mot trouvé, en les mettant à ' '
               increment=incr1[dir]*(p->largeur)+incr2[dir];
               for(k=0;k<len;k++) p->grille[i+k*increment]= ' ';
            }
   }
   return;
}
//------------------------------------------------------------------------
// on affiche toutes les lettres de la grilles qui n'ont pas été supprimées
// (= différentes de ' ')
void afficherResultat(GrilleMotsMeles_t *p)
{
   char c;
   while((c=*(p->grille++))!='\0')
      if (c!=' ') putchar(c);
   return;
}
//------------------------------------------------------------------------
//affiche un message si pointeur ptr NULL
void assure(void *ptr, const char *msg)
{
  if (ptr==NULL)
  {
    fprintf(stdout,"\n");
    fprintf(stdout,msg);
    fprintf(stdout,"\n");
    fflush(stdout);
    exit(EXIT_FAILURE);
  }
}
//------------------------------------------------------------------------

3- Je ferai pour le principe quelques critiques sur l'efficacité de l'implémentation de l'algorithme utilisé (bien que cela joue peu si la grille et le nombre de mots sont assez petits comme dans ton exemple).

Pour chaque point de la grille tu construit et tu stockes les 8 chaines possibles qu'il est possible de construire en débutant par ce caractère. Puis, pour chaque mot à chercher dans la grille, tu regardes ensuite dans toutes les chaines possibles si le mot peut en être extrait et si oui tu effaces de la grille les caractères correspondant. (Ce qui fait 600*8*95 =456000 comparaisons de chaines à faire dans l'exemple).

Or il y a beaucoup de ces comparaisons qui sont facilement rejetables immédiatement : si le mot à chercher commence par la lettre 'A', tous les points de la grille contenant une autre lettre peuvent être tout simplement ignorés. Seules les 8 chaines associées aux points de la grille contenant un 'A' ont besoin d'être comparées.
Mais tu effaces au fur et à mesure ta grille de départ ce qui rend cela impossible. Il suffit pourtant de marquer qu'une lettre est à ignorer sans pour autant l'effacer effectivement.
Le code est à modifier très légèrement. Par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
typedef struct
{
  char *grille;
  char *ignore;    //<------
  SousGrilleParCar_t *x;
  int largeur;
  int hauteur;
} GrilleMotsMeles_t;

avec à ajouter dans initCaracteres()

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
   p->ignore = calloc(MAXGRILLE+1,sizeof(char));      //<------
   assure(p->ignore,"initCaracteres:erreur calloc");  //<------

dans resoudreGrille()

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
   // on va rechercher dans pour tous les caractères de la grille....
   for(i=0;i<tailleGrille;i++)
      if(mot[0] == p->grille[i])                                //<------
        for(dir=0;dir<8;dir++)  //dans toutes les directions
           if (0==strncmp(mot,p->x[i][dir]/*.listeCars*/,len))
           {
              // la SousGrille_t [i,dir] égale le mot à trouver
              // on marque les lettres du mot trouvé
              increment=incr1[dir]*(p->largeur)+incr2[dir];
              for(k=0;k<len;k++) p->ignore[i+k*increment]= 1;   //<-----
            }

Enfin à modifier l'affichage :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
void afficherResultat(GrilleMotsMeles_t *p)
{
   int i;
   int taille = p->largeur*p->hauteur;
   for(i=0; i<taille;i++)
     if(! p->ignore[i]) putchar(p->grille[i]);
}

**Sve@r** · 11/11/2014, 18h29

Bonjour

C'est un jeu connu qui se trouve dans beaucoup de magazines. Mais as-tu pensé à vérifier l'unicité de chaque mot ? Par exemple le mot "bar" pourrait se trouver accidentellement plusieurs fois dans la grille (3 lettres c'est pas énorme)...

Sinon par rapport à ton algo, ce n'est pas la peine de stocker les 8 séquences. Te suffit de prendre un mot à trouver (on va par exemple choisir "tanche"), repérer toutes les premières lettres de ce mot dans la grille (donc tous les "t") et à partir de chaque "t", chercher dans les 8 directions (c'est d'ailleurs comme ça que je faisais quand je jouais à ce jeu). En ne prenant que sur la première lettre ça te fait économiser beaucoup de recherches inutiles.

Et question bonnes pratiques bon déjà j'aime bien car tu nommes tes types "xxx_t" (t'es le premier que je vois faire ça). Toutefois moi aussi je faisais ça avant. Mais la première fois que je suis venu sur ce forum et que j'ai montré un de mes codes, je me suis fait jeter par un pro de l'époque "Emmanuel Delahaye" qui m'a dit que les suffixes "_t" étaient réservés aux programmeurs de la librairie C et que les utilisateurs devaient, eux, utiliser un préfixe "t_". Et ça m'a marqué (dommage, Emmanuel a décroché le C depuis quelques années).
D'autres petites remarques anodines comme par exemple le fait que les mots en majuscules (DIRECTION) sont réservés aux macros, que tu pourrais aligner les variables sur la même tabulation que les instructions, et que les globales sont dans 99% des cas toujours une mauvaise idée.
Certains développeurs aiment bien aussi préfixer leurs pointeurs par autant de "p" qu'il y a d'étoile => char *pMot; char **ppTab mais comme ce n'est pas mon cas je t'indique juste cette possibilité sans insister.
Ah oui, aussi, perso je n'initialise que ce qui est absolument nécessaire donc je ne fais jamais de calloc car je maîtrise toujours mes variables. C'est plus difficile mais paradoxalement je suis ainsi certain de ne pas en oublier (celui qui fait un calloc peut en effet faire trop confiance et oublier malencontreusement le pointeur auquel il ne pense pas alors que celui qui se force à tout contrôler garde alors certains réflexes). Mais bon, il y a autant de "bonnes" façons de programmer qu'il y a de "bons" intervenants sur ce forum...

**lautrec1** · 12/11/2014, 14h05

@diogene : merci pour cette idée, ça m'a inspiré un flag et deux breaks dans la boucle de recherche

Bonjour
C'est un jeu connu qui se trouve dans beaucoup de magazines. Mais as-tu pensé à vérifier l'unicité de chaque mot ? Par exemple le mot "bar" pourrait se trouver accidentellement plusieurs fois dans la grille (3 lettres c'est pas énorme)...

L'unicité de chaque mot est pour moi une hypothèse. Je n'ai jamais vu un magazine proposant des grilles à mots non uniques. Je ne vois d'ailleurs pas comment traiter le cas de non-unicité. Envoyer un message d'erreur ? Barrer les mots multiples ?

Sinon par rapport à ton algo, ce n'est pas la peine de stocker les 8 séquences. Te suffit de prendre un mot à trouver (on va par exemple choisir "tanche"), repérer toutes les premières lettres de ce mot dans la grille (donc tous les "t") et à partir de chaque "t", chercher dans les 8 directions (c'est d'ailleurs comme ça que je faisais quand je jouais à ce jeu). En ne prenant que sur la première lettre ça te fait économiser beaucoup de recherches inutiles.

En effet, pourquoi faire simple quand on peut faire compliqué. Maintenant avec vos conseils, le prg tourne beaucoup plus vite.

les globales sont dans 99% des cas toujours une mauvaise idée.

Comment pouvoir les éviter quand elles sont utilisées par deux fonctions tout en gardant le code maintenable? Dans main() ?

@diogene: Bravo. Tu m'as donné des idées pour accélérer les recherches : un flag et deux breaks pour arrêter de parcourir les SousGrille dès qu'on a trouvé, ça fais encore 50% sur ce qui reste.

Merci beaucoup pour votre aide à tous les deux.

Voilà le résultat de vos suggestions et de l'ajout de breaks dans la boucle de recherche:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
223
224
225
226
227
228
229
230
231
232
233
234
235
236
 
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
 
#define MAX_MOT 50
#define DIM_MAX 60
#define MAXGRILLE 1500
 
/*TYPES*/
const short incr1[8]= {-1,0,1, 0,-1,1, 1,-1};
const short incr2[8]= { 0,1,0,-1, 1,1,-1,-1};
 
typedef int indice_t;
typedef struct
{
  char *grille;
  char *ignore;
  int largeur;
  int hauteur;
} GrilleMotsMeles_t;
 
 
/*PROTOTYPES*/
GrilleMotsMeles_t *initGrilleMotsMeles(FILE *);
void initCaracteres(FILE *,GrilleMotsMeles_t *);
char *initElementSousGrille(GrilleMotsMeles_t *,int,int);
void resoudreGrille(GrilleMotsMeles_t *,FILE*);
void afficherResultat(GrilleMotsMeles_t *);
void assure(void *, const char *);
 
/*SOLVEUR DE MOTS MELES
 PRE: "tableau.txt" contient la grille de caractères
      "mots.txt" contient un mot par ligne. Ce sont les mots dont les caractères doivent être
		barrés dans la grille
 POST "result.txt" contient la suite de lettre de la grille qui n'ont pas été barrées 
	(sens gauche vers droite, haut vers bas)
*/
int main()
{
GrilleMotsMeles_t *grillemelimelo;
FILE* fGrille;
FILE* fMots;
clock_t debut,fin;
	debut=clock();
 
	/*redirection de la sortie standard vers RESULT.TXT*/
	freopen("RESULT.TXT","w",stdout);
 
	/*initialise la grille et les structures sous-jacentes*/
	fGrille=fopen("tableau.txt","r");
	assure(fGrille,"Erreur ouverture fichier tableau.txt");
	grillemelimelo=initGrilleMotsMeles(fGrille);
 
	/*trouve les mots à chercher dans la grille et barre les lettres une fois trouvées*/
	fMots=fopen("mots.txt","r");
	assure(fMots,"Erreur ouverture fichier mots.txt");
	resoudreGrille(grillemelimelo,fMots);
 
	/*affiche les lettres qui n'ont pas été barrées*/
	afficherResultat(grillemelimelo);
 
	fin=clock();
	printf("\nTemps run : %2.30f secondes\n",(double) (fin-debut)/CLOCKS_PER_SEC);		
 
	return 1;
}
 
/*initialisation de la structure GrilleMotMeles_t à partir d'un tableau de caractères présent
dans le fichier fichierGrille*/
GrilleMotsMeles_t *initGrilleMotsMeles(FILE *fichierGrille)
{
GrilleMotsMeles_t *pGrille;
indice_t tailleGrille;
int i,j;
 
	pGrille=malloc(sizeof(GrilleMotsMeles_t));
    assure(pGrille,"initGrilleMotsMeles: erreur malloc");
 
	/*on a besoin d'avoir tous les caractères de la grille de mots mêlés*/
	initCaracteres(fichierGrille,pGrille);
 
	pGrille->ignore=calloc(MAXGRILLE+1,sizeof(char));
    assure(pGrille->ignore,"initCaracteres:erreur calloc");
 
	strcpy(pGrille->ignore,pGrille->grille);	
	return pGrille;
}
 
/*charge la grille de caractères, base de la Grille de Mots Meles*/
 void initCaracteres(FILE *f,GrilleMotsMeles_t *pGrille)
{
int j,k;
char c;
long taille;
 
	pGrille->grille=calloc(MAXGRILLE+1,sizeof(char));
    assure(pGrille->grille,"initCaracteres:erreur calloc");
 
	j=0;
	taille=0;
	pGrille->largeur=0;
 
	for (k=0;(c=getc(f))!=EOF; k++)
		if (c!='\n') {
		  j++;
		  taille++;
		  /*on met la lettre en majuscules*/
		  pGrille->grille[k]=toupper(c);
		}
		else {
		  pGrille->largeur=j;
		  j=0;
		  k--; /*on ne met pas '\n' dans le tableau*/
		};
 
	pGrille->hauteur = taille/pGrille->largeur;
 
	return;
}
 
/*pour un caractère de la grille et une direction donnée, renvoie un pointeur sur une chaine égale
à la sous-grille partant du caractère donné, dans la direction donnée, et se terminant en bord de grille*/
char *initElementSousGrille(GrilleMotsMeles_t *pGrille,int point, int numDir)
{
char tmpCar[DIM_MAX];
int i,k,increment;
char *pReturnValue;
 
	/*détermination de l'incrément des indices à partir de la direction*/
    increment=incr1[numDir]*pGrille->largeur+incr2[numDir];
 
    k=0;
	i=point;
	/* il y a au moins une lettre de la grille à charger*/
	/* on les mémorise, et on charge la suivante, jusqu'à ce que celle-ci dépasse le bord de la grille*/
	/*quand on se déplace vers la gauche de la grille, on n'enregistre pas l'élement pour lequel
	  l'indice%largeur==largeur-1*/
	/*quand on se déplace vers la droite de la grille, on n'enregistre pas l'élement pour lequel
	  l'indice%largeur==0*/
    do{
		tmpCar[k++]=pGrille->grille[i];
		i+=increment;
		if(incr2[numDir]>0 && i%pGrille->largeur==0)
			break;
		else if(incr2[numDir]<0 && i%pGrille->largeur==pGrille->largeur-1)
			break;
 
    } while (i>=0 && i<pGrille->largeur*pGrille->hauteur);
    tmpCar[k]='\0';
 
    pReturnValue=calloc(k+1,sizeof(char));
    assure(pReturnValue,"initSousGrille:erreur calloc");
 
    strcpy(pReturnValue,tmpCar);
 
	return;
}
 
/*pour tous les mots M de fichierMots (un mot par ligne), on va trouver la sous-grille 
(couple caractère-direction), pour lequel le début de la sous-grille égale le mot M.*/
void resoudreGrille(GrilleMotsMeles_t *pGrille,FILE* fichierMots)
{
char mot [MAX_MOT];
char *pTmp;
int i,k,dir,increment,len;
indice_t tailleGrille;
int motTrouve;
 
	tailleGrille=(pGrille->largeur)*(pGrille->hauteur);
 
	/*tant qu'il y a une ligne contenant un mot*/
	while ((fscanf(fichierMots,"%s\n",mot))!=EOF) {
 
		len=strlen(mot);
 
		/*on met le mot en majuscules*/
		for(i=0;i<len;i++) mot[i]=toupper(mot[i]);
 
		motTrouve=0;
 
		/*on va rechercher dans pour tous les caractères de la grille....*/
		for(i=0;i<tailleGrille;i++) {
 
			/* si le caractères de la grille et la première lettre du mot correspondent*/
			if(mot[0]==pGrille->grille[i])
 
				/*...toutes les directions*/
				for(dir=0;dir<8;dir++){
 
					pTmp=initElementSousGrille(pGrille,i,dir);
 
					/*test d'égalité entre le mot et le début de la listeCars*/
					if (0==strncmp(mot,pTmp,len)) {
 
							/*la SousGrille_t [i,dir] égale le mot à trouver*/
							motTrouve=1;
 
							/*on élimine de la grille les lettres du mot trouvé, en les mettant à ' '*/
							increment=incr1[dir]*(pGrille->largeur)+incr2[dir];
							for(k=0;k<len;k++) pGrille->ignore[i+k*increment]= '\0';
 
							break;
						};
					free(pTmp);
				}
			if (motTrouve) break;
 
		}
	}
	return;
}
 
void afficherResultat(GrilleMotsMeles_t *p)
{
	int i;
	int taille = p->largeur*p->hauteur;
	/*on affiche toutes les lettres de la grilles dont ignore sont encore égales à 0*/
	for(i=0; i<taille;i++)
	 if(p->ignore[i]) putchar(p->grille[i]);
}
 
/*affiche un message si pointeur ptr NULL*/
void assure(void *ptr, const char *msg)
{
  if (ptr==NULL)
  {
    fprintf(stdout,"\n");
    fprintf(stdout,msg);
    fprintf(stdout,"\n");
    fflush(stdout);
    exit(EXIT_FAILURE);
  }
}

Envoyé par Sve@r

C'est un jeu connu qui se trouve dans beaucoup de magazines.

Une fois ce programme fini, je compte m'atteler aux "mots à caser"...puis de façon ultime aux "nombres fléchés", cas particuliers des kakuros, mais là c'est très ambitieux (ça c'est vraiment hard, déjà quand on les fait "à la main"). Il faudrait que je fasse ça en C++

Amicalement.

**Sve@r** · 12/11/2014, 18h02

Envoyé par lautrec1

L'unicité de chaque mot est pour moi une hypothèse. Je n'ai jamais vu un magazine proposant des grilles à mots non uniques. Je ne vois d'ailleurs pas comment traiter le cas de non-unicité. Envoyer un message d'erreur ? Barrer les mots multiples ?

Oui c'est vrai. Je n'avais pas réalisé que tu recopiais en fait une grille réelle, je pensais que t'avais inventé ta propre grille. Bien entendu, à partir d'une grille de magazine tu présupposes évidemment qu'elle est correcte.

Envoyé par lautrec1

Comment pouvoir les éviter quand elles sont utilisées par deux fonctions tout en gardant le code maintenable? Dans main() ?

Exactement. Tu places tes incréments dans le main et tu les passes en paramètres aux fonctions qui en ont besoin. A ce propos, tu as deux tableaux (je présume que l'un gère les "x" et l'autre les "y") ben ça c'est pas super tiptop. Le C possède un outil dédié à associer des éléments disparates: la structure. Et tu as montré que tu savais la manipuler...

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct {
    short x;
    short y;
} t_dep;
t_dep tabDep[]={
    {-1, 0},
    {0, 1},
    {1, 0},
    {0, -1},
    {-1, 1},
    {1, 1},
    {1, -1},
    {-1, -1},
};

Ainsi tu n'as maintenant plus qu'un seul item à passer à tes fonctions et non 2. Ceci dit, à bien réfléchir, as-tu vraiment besoin de mémoriser ces valeurs ??? En faisant varier x de -1 vers +1 puis en faisant varier y de -1 vers +1 tu couvres les 8 directions (un cas particulier quand x et y valent 0 mais c'est que dalle)...

Envoyé par lautrec1

Il faudrait que je fasse ça en C++

Tu devrais t'intéresser à Python...

**lautrec1** · 12/11/2014, 19h09

Envoyé par Sve@r

Ceci dit, à bien réfléchir, as-tu vraiment besoin de mémoriser ces valeurs ??? En faisant varier x de -1 vers +1 puis en faisant varier y de -1 vers +1 tu couvres les 8 directions (un cas particulier quand x et y valent 0 mais c'est que dalle)...

Punaise, je l'avais pas vue celle-là! J'ai corrigé le code en ce sens.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
223
224
225
226
227
228
229
230
231
232
 
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
 
#define MAX_MOT 50
#define DIM_MAX 60
#define MAXGRILLE 1500
 
/*TYPES*/
typedef int indice_t;
typedef struct
{
  char *grille;
  char *ignore;
  int largeur;
  int hauteur;
} GrilleMotsMeles_t;
 
 
/*PROTOTYPES*/
GrilleMotsMeles_t *initGrilleMotsMeles(FILE *);
void initCaracteres(FILE *,GrilleMotsMeles_t *);
char *initElementSousGrille(GrilleMotsMeles_t *,int,int,int);
void resoudreGrille(GrilleMotsMeles_t *,FILE*);
void afficherResultat(GrilleMotsMeles_t *);
void assure(void *, const char *);
 
/*SOLVEUR DE MOTS MELES
 PRE: "tableau.txt" contient la grille de caractères
      "mots.txt" contient un mot par ligne. Ce sont les mots dont les caractères doivent être
		barrés dans la grille
 POST "result.txt" contient la suite de lettre de la grille qui n'ont pas été barrées 
	(sens gauche vers droite, haut vers bas)
*/
int main()
{
GrilleMotsMeles_t *grillemelimelo;
FILE* fGrille;
FILE* fMots;
clock_t debut,fin;
	debut=clock();
 
	/*redirection de la sortie standard vers RESULT.TXT*/
	freopen("RESULT.TXT","w",stdout);
 
	/*initialise la grille et les structures sous-jacentes*/
	fGrille=fopen("tableau.txt","r");
	assure(fGrille,"Erreur ouverture fichier tableau.txt");
	grillemelimelo=initGrilleMotsMeles(fGrille);
 
	/*trouve les mots à chercher dans la grille et barre les lettres une fois trouvées*/
	fMots=fopen("mots.txt","r");
	assure(fMots,"Erreur ouverture fichier mots.txt");
	resoudreGrille(grillemelimelo,fMots);
 
	/*affiche les lettres qui n'ont pas été barrées*/
	afficherResultat(grillemelimelo);
 
	fin=clock();
	printf("\nTemps run : %2.30f secondes\n",(double) (fin-debut)/CLOCKS_PER_SEC);		
 
	return 1;
}
 
/*initialisation de la structure GrilleMotMeles_t à partir d'un tableau de caractères présent
dans le fichier fichierGrille*/
GrilleMotsMeles_t *initGrilleMotsMeles(FILE *fichierGrille)
{
GrilleMotsMeles_t *pGrille;
indice_t tailleGrille;
int i,j;
 
	pGrille=malloc(sizeof(GrilleMotsMeles_t));
    assure(pGrille,"initGrilleMotsMeles: erreur malloc");
 
	/*on a besoin d'avoir tous les caractères de la grille de mots mêlés*/
	initCaracteres(fichierGrille,pGrille);
 
	pGrille->ignore=calloc(MAXGRILLE+1,sizeof(char));
    assure(pGrille->ignore,"initCaracteres:erreur calloc");
 
	strcpy(pGrille->ignore,pGrille->grille);	
	return pGrille;
}
 
/*charge la grille de caractères, base de la Grille de Mots Meles*/
 void initCaracteres(FILE *f,GrilleMotsMeles_t *pGrille)
{
int j,k;
char c;
long taille;
 
	pGrille->grille=calloc(MAXGRILLE+1,sizeof(char));
    assure(pGrille->grille,"initCaracteres:erreur calloc");
 
	j=0;
	taille=0;
	pGrille->largeur=0;
 
	for (k=0;(c=getc(f))!=EOF; k++)
		if (c!='\n') {
		  j++;
		  taille++;
		  /*on met la lettre en majuscules*/
		  pGrille->grille[k]=toupper(c);
		}
		else {
		  pGrille->largeur=j;
		  j=0;
		  k--; /*on ne met pas '\n' dans le tableau*/
		};
 
	pGrille->hauteur = taille/pGrille->largeur;
 
	return;
}
 
/*pour un caractère de la grille et une direction donnée, renvoie un pointeur sur une chaine égale
à la sous-grille partant du caractère donné, dans la direction donnée, et se terminant en bord de grille*/
char *initElementSousGrille(GrilleMotsMeles_t *pGrille,int point, int incrY,int incrX)
{
char tmpCar[DIM_MAX];
int i,k,increment;
char *pReturnValue;
 
	/*détermination de l'incrément des indices à partir de la direction*/
    increment=incrY*(pGrille->largeur)+incrX;
 
    k=0;
	i=point;
	/* il y a au moins une lettre de la grille à charger*/
	/* on les mémorise, et on charge la suivante, jusqu'à ce que celle-ci dépasse le bord de la grille*/
	/*quand on se déplace vers la gauche de la grille, on n'enregistre pas l'élement pour lequel
	  l'indice%largeur==largeur-1*/
	/*quand on se déplace vers la droite de la grille, on n'enregistre pas l'élement pour lequel
	  l'indice%largeur==0*/
    do{
		tmpCar[k++]=pGrille->grille[i];
		i+=increment;
		if(incrX>0 && i%pGrille->largeur==0)
			break;
		else if(incrX<0 && i%pGrille->largeur==pGrille->largeur-1)
			break;
 
    } while (i>=0 && i<pGrille->largeur*pGrille->hauteur);
    tmpCar[k]='\0';
 
    pReturnValue=calloc(k+1,sizeof(char));
    assure(pReturnValue,"initSousGrille:erreur calloc");
 
    strcpy(pReturnValue,tmpCar);
 
	return;
}
 
/*pour tous les mots M de fichierMots (un mot par ligne), on va trouver la sous-grille 
(couple caractère-direction), pour lequel le début de la sous-grille égale le mot M.*/
void resoudreGrille(GrilleMotsMeles_t *pGrille,FILE* fichierMots)
{
char mot [MAX_MOT];
char *pTmp;
int i,k,m,n,increment,len;
indice_t tailleGrille;
int motTrouve;
 
	tailleGrille=(pGrille->largeur)*(pGrille->hauteur);
 
	/*tant qu'il y a une ligne contenant un mot*/
	while ((fscanf(fichierMots,"%s\n",mot))!=EOF) {
 
		len=strlen(mot);
 
		/*on met le mot en majuscules*/
		for(i=0;i<len;i++) mot[i]=toupper(mot[i]);
 
		motTrouve=0;
 
		/*on va rechercher dans pour tous les caractères de la grille....*/
		for(i=0;i<tailleGrille;i++) {
 
			/* si le caractères de la grille et la première lettre du mot correspondent*/
			if(mot[0]==pGrille->grille[i])
 
				/*...toutes les directions*/
				for(m=-1;m<=1;m++)
					for(n=-1;n<=1;n++)
						if(m || n) {
							pTmp=initElementSousGrille(pGrille,i,m,n);
 
							/*test d'égalité entre le mot et le début de la listeCars*/
							if (0==strncmp(mot,pTmp,len)) {
 
									/*la SousGrille_t [i,dir] égale le mot à trouver*/
									motTrouve=1;
									increment=m*(pGrille->largeur)+n;
 
									/*on élimine de la grille les lettres du mot trouvé, en les mettant à ' '*/
									for(k=0;k<len;k++) pGrille->ignore[i+k*increment]= '\0';
								};
							free(pTmp);
							if (motTrouve) break;
						}
			if (motTrouve) break;
		}
	}
	return;
}
 
void afficherResultat(GrilleMotsMeles_t *p)
{
	int i;
	int taille = p->largeur*p->hauteur;
	/*on affiche toutes les lettres de la grilles dont ignore sont encore égales à 0*/
	for(i=0; i<taille;i++)
	 if(p->ignore[i]) putchar(p->grille[i]);
}
 
/*affiche un message si pointeur ptr NULL*/
void assure(void *ptr, const char *msg)
{
  if (ptr==NULL)
  {
    fprintf(stdout,"\n");
    fprintf(stdout,msg);
    fprintf(stdout,"\n");
    fflush(stdout);
    exit(EXIT_FAILURE);
  }
}

Mais je ne modifierais pas ce que j'ai mis dans la section "télécharger", car 1) la fonction de recherche est un vrai foutoir maintenant, 2)autant montrer comment définir-déclarer des tab const globaux. (Autant te dire que dans la rubrique télécharger, j'ai mis en première intention un code vraiment honteux je dois dire : 500 lignes serrées non commentées,avec des sections particulièrement horribles).

Tu devrais t'intéresser à Python...

Yeeeah.... c'est parti mon kiki!

**ternel** · 13/11/2014, 11h40

J'ai un peu retravaillé ton code, en gardant l'esprit de ce que tu fais.
Je te laisse libre d'adopter ce qui te plait

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
 
#define MAX_MOT 50
#define DIM_MAX 60
#define MAXGRILLE (DIM_MAX*DIM_MAX)
 
#define IGNORED_CHAR '\0'
 
/* COORDINATE */
 
typedef enum {
	d_ul, d_u, d_ur,
	d_l,       d_r,
	d_dl, d_d, d_dr,
	d_END, d_FIRST = d_ul//to write: for (d = d_FIRST; d < d_END; ++d)
} direction;
 
char dx(direction d) {
	switch(d) {
		case d_ul: case d_l: case d_dl: return -1;
		case d_ur: case d_r: case d_dr: return 1;
		default: return 0;
	}
}
 
char dy(direction d) {
	switch(d) {
		case d_ul: case d_u: case d_ur: return -1;
		case d_dl: case d_d: case d_dr: return 1;
		default: return 0;
	}
}
 
 
/* GRILLE */
typedef unsigned int coordinate_t;
 
typedef struct {
	char *grille;
	char *ignore;
	coordinate_t largeur;
	coordinate_t hauteur;
} GrilleMotsMeles_t;
 
/* retourne la valeur du point (x,y) dans la grille */
char grilleAt(GrilleMotsMeles_t* grille, coordinate_t x, coordinate_t y);
/* retourne la valeur du point (x,y) dans la grille, sans controle de validité */
char unchekedGrilleAt(GrilleMotsMeles_t* grille, coordinate_t x, coordinate_t y);
 
/* retourne la valeur du point (x,y) dans la grille, si pas déjà barré, '\0' sinon */
char ignoredAt(GrilleMotsMeles_t* grille, coordinate_t x, coordinate_t y);
/* marque comme déjà utilisé le point (x,y) dans la grille */
void ignoreAt(GrilleMotsMeles_t* grille, coordinate_t x, coordinate_t y);
 
/* retourne la longueur maximale dans la grille d'un mot partant de (x,y) dans la direction d */
unsigned int lengthToward(GrilleMotsMeles_t *grille, coordinate_t x, coordinate_t y, direction d);
 
/* renvoie la suite de caractères de la grille partant du point (x,y) dans la direction d */
char* gridToward(GrilleMotsMeles_t *grille, coordinate_t x, coordinate_t y, direction d);
 
 
/*PROTOTYPES*/
/* affiche le message et quitte le programme sur une erreur si le pointeur p est vide */
void assure(void *p, const char *message);
 
/* construit une grille d'après un fichier. Elle n'est pas allouée, car GrilleMotsMeles_t est une petite structure, copiable */
GrilleMotsMeles_t createGrilleMotsMeles(FILE *);
/* libère les ressources internes d'une grille, mais de la désalloue pas */
void clearGrilleMotsMeles(GrilleMotsMeles_t* grille);
 
/* cherche les mots d'un fichier dans la grille */
void resoudreGrille(GrilleMotsMeles_t *, FILE*);
 
/* affiche les lettres non utilisées, dans l'ordre de la grille */
void afficherResultat(GrilleMotsMeles_t *);
 
 
/*SOLVEUR DE MOTS MELES
 PRE: "tableau.txt" contient la grille de caractères
      "mots.txt" contient un mot par ligne. Ce sont les mots dont les caractères doivent être
		barrés dans la grille
 POST "result.txt" contient la suite de lettre de la grille qui n'ont pas été barrées
	(sens gauche vers droite, haut vers bas)
*/
int main() {
	GrilleMotsMeles_t grillemelimelo;
	FILE* fGrille;
	FILE* fMots;
	clock_t debut,fin;
 
	debut=clock();
 
	/*redirection de la sortie standard vers RESULT.TXT*/
	freopen("RESULT.TXT","w",stdout);
 
	/*initialise la grille et les structures sous-jacentes*/
	fGrille=fopen("tableau.txt","r");
	assure(fGrille,"Erreur ouverture fichier tableau.txt");
	grillemelimelo=createGrilleMotsMeles(fGrille);
 
	/*trouve les mots à chercher dans la grille et barre les lettres une fois trouvées*/
	fMots=fopen("mots.txt","r");
	assure(fMots,"Erreur ouverture fichier mots.txt");
	resoudreGrille(&grillemelimelo,fMots);
 
	/*affiche les lettres qui n'ont pas été barrées*/
	afficherResultat(&grillemelimelo);
 
	clearGrilleMotsMeles(&grillemelimelo);
 
	fin=clock();
	printf("\nTemps run : %2.30f secondes\n",(double) (fin-debut)/CLOCKS_PER_SEC);
 
	return 1;
}
 
/* FONCTIONS = */
 
/*affiche un message et quitte le programme sur une erreur si p est NULL*/
void assure(void *ptr, const char *msg) {
	if (ptr==NULL) {
		fprintf(stderr, "\n%s\n", msg);
		fflush(stderr);
		exit(EXIT_FAILURE);
	}
}
 
 
 
/* auxiliaires pour les fonctions principales */
void markAsUsed(GrilleMotsMeles_t* grille, coordinate_t x, coordinate_t y, direction d, unsigned int count);
int searchWord(GrilleMotsMeles_t *grille, const char* word);
 
 
void clearGrilleMotsMeles(GrilleMotsMeles_t* grille) {
	free(grille->grille);
	grille->grille=NULL;
 
	free(grille->ignore);
	grille->ignore=NULL;
}
 
/*créée une structure GrilleMotMeles_t à partir du fichier fichierGrille*/
GrilleMotsMeles_t createGrilleMotsMeles(FILE *fichierGrille) {
	GrilleMotsMeles_t grille = {
		calloc(MAXGRILLE+1,sizeof(char)),
		NULL,
		0,
		0
	};
 
	/*on a besoin d'avoir tous les caractères de la grille de mots mêlés*/
	char c;
	char *target = grille.grille;
 
	assure(grille.grille,"createGrilleMotsMeles:erreur calloc");
 
	while ( (c = getc(fichierGrille))!=EOF ) {
		if (isalpha(c)) {
			*(target++) = toupper(c);
		} else if (c=='\n') {
			if(grille.largeur == 0) {
				grille.largeur = grille.grille - target;
			}
			++grille.hauteur;
		}
	}
 
	grille.ignore=calloc(MAXGRILLE+1,sizeof(char));
    assure(grille->ignore,"createGrilleMotsMeles:erreur calloc");
 
	strcpy(grille->ignore, grille->grille);
	return grille;
}
 
 
 
/*pour tous les mots M de fichierMots (un mot par ligne), on va trouver la sous-grille
(couple caractère-direction), pour lequel le début de la sous-grille égale le mot M.*/
void resoudreGrille(GrilleMotsMeles_t *pGrille,FILE* fichierMots) {
	char mot [MAX_MOT];
 
	/*tant qu'il y a une ligne contenant un mot*/
	while ((fscanf(fichierMots,"%s\n",mot))!=EOF) {
		int len=strlen(mot);
		int i;
 
		/*on met le mot en majuscules*/
		for(i=0;i<len;i++) mot[i]=toupper(mot[i]);
 
		/*on va rechercher dans pour tous les caractères de la grille....*/
		searchWord(grille, mot);
	}
}
 
 
void afficherResultat(GrilleMotsMeles_t *g) {
	int i;
	const int taille = g->largeur*g->hauteur;
	/*on affiche toutes les lettres de la grilles dont ignore sont encore égales à 0*/
	for(i=0; i<taille;i++)
		if(g->ignore[i]!=IGNORED_CHAR) putchar(g->grille[i]);
}
 
void markAsUsed(GrilleMotsMeles_t* grille, coordinate_t x, coordinate_t y, direction d, unsigned int count) {
	const unsigned int length = lengthToward(grille, x, y, d);
	const int bound = min(length, count);
	for (i = 0; i < bound; ++i) {
		ignoreAt(grille, x+i*dx(d), y+i*dx(d));
	}
	return data;
}
 
int searchWord(GrilleMotsMeles_t *grille, const char* word) {
	if (word==NULL) return 0;
 
	int len=strlen(word);
	/*on va rechercher dans pour tous les caractères de la grille....*/
	int x, y;
	direction d;
 
	for(x=0; x<grille->largeur; ++x) {
		for(y=0; y<grille->hauteur; ++y) {
			if (word[0] != grilleAt(grille, x, y)) continue;
 
			for (d = d_FIRST; d < d_END; ++d) {
				char *sub = gridToward(grille, x, y, d);
				if (sub!=NULL) {
					if (strncmp(word,pTmp,len) == 0) {
						markAsUsed(grille, x, y, len);
						free(sub);
						return 1;
					};
					free(sub);
				}
			}
		}
	}
	return 0;
}
 
/* GRILLE = */
 
/* retourne l'index dans la grille du point (x,y) */
unsigned int gridIndexOf(GrilleMotsMeles_t* grille, coordinate_t x, coordinate_t y) {
	return x+y*grille->largeur;
}
 
char ignoredAt(GrilleMotsMeles_t* grille, coordinate_t x, coordinate_t y) {
	return grille->ignore[ gridIndexOf(grille, x, y) ];
}
void ignoreAt(GrilleMotsMeles_t* grille, coordinate_t x, coordinate_t y) {
	grille->ignore[ gridIndexOf(grille, x, y) ] = IGNORED_CHAR;
}
 
char grilleAt(GrilleMotsMeles_t* grille, coordinate_t x, coordinate_t y) {
	if (grille->grille == NULL || x >= grille->largeur || y >= grille->hauteur) return '\0';
	return uncheckedGrilleAt(grille, x, y);
}
 
char uncheckedGrilleAt(GrilleMotsMeles_t* grille, coordinate_t x, coordinate_t y) {
	return grille->grille[ gridIndexOf(grille, x, y) ];
}
 
/* return the length of the subarray from (x,y) to the border of the grid. 0 means already out of the grid */
unsigned int lengthToward(GrilleMotsMeles_t *grille, coordinate_t x, coordinate_t y, direction d) {
	if (grille==NULL || x>=grille->largeur || y >= grille->hauteur) return 0;
	switch(d) {
		case d_u:	return grille->hauteur - y;
		case d_d:	return 1 + y;
		case d_l:	return 1 + x;
		case d_r:	return grille->largeur - x;
		case d_ul:	return min(grille->hauteur - y, 1 + x);
		case d_ur:	return min(grille->hauteur - y, grille->largeur - x);
		case d_dl:	return min(1 + y, 1 + x);
		case d_dr:	return min(1 + y, grille->largeur - x);
		default: return 0;
	}
}
 
 
/*pour un caractère de la grille et une direction donnée, renvoie un tableau de chars correspondant
à la sous-grille partant du caractère donné, dans la direction donnée, et se terminant en bord de grille.
not NULL terminated.
*/
 
char* gridToward(GrilleMotsMeles_t *grille, coordinate_t x, coordinate_t y, direction d) {
	const unsigned int length = lengthToward(grille, x, y, d);
	char* data = NULL;
	if (length>0) {
		int i;
		data = calloc(length, sizeof(char));
		assure(pReturnValue,"gridToward:erreur calloc");
		for (i = 0; i < length; ++i) {
			data[i] = uncheckedGrilleAt(grille, x+i*dx(d), y+i*dx(d));
		}
	}
	return data;
}

Les principaux changements sont:

regroupement des fonctions pour pouvoir découper en fichiers.
déclarer un peu plus tard les fonctions auxiliaires non utilisées par main()
remplacement des "incr" par une énumération est deux fonctions utilitaires
ajout d'une fonction intermédiaire "searchWord(...)" pour alléger résoudre()
ajout de fonctions utilitaires autour de la grille, pour avoir un type de plus haut niveau (pense à fopen, fclose, fread... pour File), l'utilisateur ne veut pas s’embêter avec l'indexation des cases.
amélioration de commentaires, pour donner des informations précises sur le résultat d'une fonction, plutôt que les détails internes.

**lautrec1** · 15/11/2014, 19h12

Envoyé par leternel

J'ai un peu retravaillé ton code, en gardant l'esprit de ce que tu fais.
Je te laisse libre d'adopter ce qui te plait

Merci beaucoup

Ca a dû te prendre bien du temps.... Face à ce résultat, je me sens tout petit d'un coup

Je comprends qu'il faut faire des fonctions les plus petites possibles, mais du coup je ne comprend plus (en lisant en vitesse c'est vrai), le système des "incréments".

A la base, il y avait une possibilité que j'en fasse un article sur base de mon premier programme, mais quand je vois le programme pro qui devrait finalement y être décrit, je serais bien à mal de décrire toute la démarche.

Je vais mieux m'appliquer sur une version objet (j'ai commencé TIC++ 2 de Eckel) pour résoudre les "mots casés". A dans quelques semaines dans le forum "algo"... Ca promet d'être un code encore bien foireux !

PS: un pTmp à la place de sub à la ligne 233

**ternel** · 18/11/2014, 17h18

Ta liste des incréments donnait des vecteurs unitaires dans les différentes directions.
ton ancien incr1[4], incr2[4] devient dx(d_l), dy(d_l).

C'est la même chose, sauf que j'ai ajouté un peu de protection, et surtout supprimé une variable globale.
Le fait de travailler en objet va probablement te permettre de créer un "itérateur de grille", qui pourra se déplacer le long d'une direction, mais le reste du code sera sensiblement équivalent.

**lautrec1** · 18/11/2014, 20h56

Ton travail me servira de référence.

Envoyé par leternel

Le fait de travailler en objet va probablement te permettre de créer un "itérateur de grille", qui pourra se déplacer le long d'une direction, mais le reste du code sera sensiblement équivalent.

Parce que je ne trouve pas d'autre challenge pour appliquer des connaissances fraîchement acquises, le prochain projet en objet est les "mots à caser". On a une grille vide avec quelques cases noires et une liste de mots; il faut caser tous les mots dans la grille.
Ce sera très différent : que deux sens à parcourir: SUD et EST.

**ternel** · 24/11/2014, 10h24

Bonne continuation, donc!

Et rappelle-toi Boileau:

Envoyé par Boileau

Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire viennent facilement.

Si tu n'arrives pas à écrire un code, c'est que tu n'as pas encore assez réfléchi.

J'ajoute quand même que savoir ce qui existe (par exemple dans la STL) permet de réfléchir plus vite.

Demande propositions améliorations ("bonnes pratiques")

C

Discussions similaires

Partager

Partager