voila je suis en train de programmer un jeu de Scrabble ( ca existe déjà ! Je sais ! ) et j´ai besoin de vos précieux petits conseils en ce qui concerne l´optimisation. Je vais faire une procédure qui calculera, grace à une liste de mots français, le coup qui rapporte le plus de points. Mais il y a beaucoup de trucs à faire pour ca ! Et je sais pas trop dans quel ordre placer mes critères de test de validité...

• Soit je ballaye tous les coups possibles ( donc des mots qui ne sont pas francais en majorité), je calcule les points, et si c´est suppérieur au MAX que j´avais deja, je teste la validité francaise.

• Soit je construit mes mots théoriquement possibles sur base de la liste des mots francais, puis quand il sort un mot qui existe effectivement, je calcule les points.

D´autre part, pour me ballader dans ma liste de mots, je ne dois pas rester dans le fichier, ce serait trop lent. IL faut que je les copie dans la RAM dans l´initialisation du programme. Mais sous quelle forme ? J´avais pensé rajouter un caractère de fin de mot et placer tous mes mots dans un gigantesque arbre de valeurs booleennes. On aurais une classe qui contiendrait 27 pointeurs bool* a,b,c,d...,z,\end et en progressant ainsi dans l´arbre, des que je tombe sur un false je sais que le mot est faux...
Mais ce genre de truc a deja été fait je suppose et approuvé bien sur. Donc si vous connaissez une méthode simple et efficace ce serait cool !

mais dis ca va ou quoi ?
tu te prend pour qui toi ?

Je m´y connait pas du tout, mais comment tu vas creer ta liste de mot ?
En . txt ?
Si c´est le cas, tu devrais decouper en 26 . txt pour que ca fasse moins lourd a ouvrir peut-etre.

Moi, je ferai :

Je verifie toutes les lettres que j´aie :
Je verifie dans chaque . txt dont j´aie les initiales si je peut faire un mot.
Je regarde celui qui me donne le plus de points.
Je ferme les . txt qui sortent rarement ( x, y, z et je sais pas trop quels autres lettres)

senseizuninja> Tu te prends pour qui ? C´est pas parce que ton QI ne sera jamais assez élevé pour ne serait-ce que entrevoir vaguement ce qu´est un algorithme plus compliqué que mettre d´abord ses chaussettes et ensuites ses chaussure qu´il faut te sentir obligé de tenter de démontrer une pseudo autorité en intimant l´ordre à le_duche de se " casser".

non ca prendra trop de temps, je suis obligé de le mettre dans la RAM
sinon oui un txt est fort pratique car il permet de retoucher à la main

Laisse tomber le_duche, senseizuninja est un débile sorti du forum -15 ans...

Sinon, fais comme tu le sens, mais à ta place voilà ce que je ferais :
-L´ia cherche tous les mots en français qui correspondent à sa pioche
-Elle calcule les points que lui valent chaque mots
-Elle prends le mot qui gagne le plus...

Pour ca va falloir copier tout les mots dans un tableau au lancement du prog et après pour que l´IA s´y retrouve ben, va falloir utiliser les fonctions ANSI ( parfois un peu buggées ( ou plutot qui marchent pas comme tu le pense)...)...

Senseizuninja tu te calme s´il te plait, on est sur un forum " sérieux" ici alros si t´es pas content de ce qu´y s´y dit, retourne voir les autres neu² dans ton genre sur le forum -15 ans!

c est mon ti frere ki a ecrit scuser moi

Pour stocker les mots en mémoire, une map ou une hashmap devrait faire l´affaire.

Laissons aux autres le soin de l´implémentation et contentons nous du prototype.

senseizuninja > Ton ´tit frère c´est un BOULET

Vengeur > Je ne peux pas me contenter de faire ca: imagine que le plus beau coup possible soit simplement de changer le mot " ajoute" en " ajoutez" il n´y a que le z qui sort du chevalet et il n´aurais pas pu le voir avec ta méthode...

Nesca > Je ne sais pas ce qu´est une map ou une hashmap...

sensei C´est une question interessante donc t´es prié de pas insulter la personne qui la pose.

Ma solution :
-je fais une liste de tous les mots

-Je classe mes lettres pas nombre de points décroissants ( du plus au moins)

-je fais un tri, façon passoire :
je prend ma premiere lettre et je garde uniquement les mots qui on cette lettre ( pas forcement en initiale), puis la deuxieme etc etc...

-A la fin il reste:
A)Un mot qui contient toutes les lettres
B)Plusieurs mots qui contiennent toutes les lettres
C)Aucun mot: on revient à l´état précédent de la liste ( ne contentant pas la derniere lettre) si il n´ya rien non plus, on revient encore en arriere jsquu´à avoir un ou plusieurs mots

-Si j´ai plusieurs mots j´étudie les plus avantageux en fonction des doubles et des triples sur la grille et s´il est possible de les placer selon les mots déjà en jeu:
A)Je place le meilleur mot
B)Pas moyen de caser mes supers mots, je reviens à l´etat precedent de la liste

Je pense que la methode est à peu pres valable

mmmh la faudra que j´y réfléchisse pausément...
Pour ce qui est du comptage des points pour chaque possibilité de mot, j´ai déja inclu les " compte double", " compte triple",...

J´ai trouvé cela : http://www.cppfrance.com/code.aspx?id=26754

Il est clair qu´il faut y stocker en RAM : et ne t´en fait pas, il y assez de place en RAM
Le plus simple : le grand tableau... Mais bon...
Si tu as vu mon programme " lettres" sur le forum " programmation", j´avais fait l´optimisation suivante :

( formelle)

liste < mot> L[26][26]

--> une série de 26 * 26 listes chainées :
Imagine un grand tableau 2 dimensions :

26 cases pour classer les mots par rapport a leur 1ere lettre
pour chacune de ces cases, 26 cases pour classer les mots par rapport a leur 2e lettre.

De ce fait, chacune de ces 676 listes regroupe les mots ayant la 1ere et la 2e lettre identique.
Evidemment, la liste qui contient la 1ere lettre W et la 2e K est vide
Mais globalement, ça accélere la recherche...

Ce que j´avais fait dans le programme, c´est regarder les lettres 2 par 2
( pour 8 lettres données, j´observe donc 8*7 paires)
Une optimisation supplémentaire pourrait permettre de ne pas regarder plusieurs fois la meme paire.
Ainsi, parmi les 676 listes, seules quelques dizaines sont explorées : ça réduit déja les recherches.

Rien ne t´empeche ensuite d´ordonner chacune de ces listes....

Sinon, tu peux utiliser des structures toutes faites : map ou set ( qui sont des conteneurs standard du C++)
qui pourraient meme accélérer les recherche en gérant pour les toi les optimisations...

De toute façon, je pense que l´algo le plus rapide, c´est d´abord :
- créer une liste des mots possibles, grace a la méthode ci dessous, ou bien les map...
- pour chaque mot de la liste, calculer les points
- retenir le plus grand nombre de points...

Senseizuninja > Ouais vive l´excuse !

Sinon, avec des vectors ( STL) c´est p-e possible... mais j´y connais rien à la STL...

Zut JYY a completement éclipsé ma methode là ^^

le duche tu te calme avec mon frere

senseizuninja > toi et ton frere. tu n´as rien a faire dans ce topic.

Vengeur41 > le vector ne pourra pas etre optimisé, je pense que les meilleurs conteneurs sont map ou set dans ce cas la.

jvais deja aller jeter un oeuil dans le code source du lien ci dessus, je suis membre de ce site...

ps JYY, je peux te rajouter à mes contacts msn ? c´est pas pour te harceler, mais un ptit conseil de temps en temps c´est plus facile en envoyant la source directement...

ben rajoute moi, je t´ajouterai quand je me connecterai