Analyse de données/jeu Python

[kizakoo]

Bonjour, je travaille sur un exercice d'analyses de donnée:
l'ordi choisit au hasard un mot parmi ~50000 mots de même longueur (un mot par ligne dans un fichier texte) et je dois coder un joueur qui devine ce mot.
Je dois maximiser le score du joueur dans 100 tours où à chaque tour il obtient un score : le score est calculé par une fonction qui prend deux mots et retourne un score suivant la compatibilité des deux mots (nb de voyelles, nb de consonnes, ordre des lettres ...)

J'ai deux question :

1-quelle est la meilleure "heuristique" pour maximiser le score du joueur dans 80 trs ?
2- comment optimiser l'algorithme puisque la quantité des données est énorme et avoir le résultat des 80 après une durée de temps raisonnable ?

Merci infiniment de votre aide !
-----

[Paraboloide_Hyperbolique]

Bonjour,

Pour votre seconde question, je suppose que votre liste de mots est triée (sinon faire le tri une fois et générer un fichier des mots triés). Faites alors une petite recherche sur "recherche dans liste triée". Vous verrez que la complexité algorithmique d'une telle recherche est en O(log(n)) (avec n la longueur de la liste).

[kizakoo]

Bonsoir, lorsque vous dîtes que ma liste est triée ... quel est le critère de tri auquel vous pensez (par rapport au score ??) ?
Merci

[invite896757ff]

Pour optimiser le temps d'analyse, il faut trier les mots par ordre alphabétique, découper la liste en 26 listes (en tableaux ce serait sans doute mieux); et faire l'analyse en fonction de la première lettre du mot proposé .
Mais que va-tu donner comme élément(s) pour faire deviner le mot ?
Remplacer une lettre sur deux par un tiret, en changeant pair/impair à chaque tour ?
Autre ?

[A voir en vidéo sur Futura]

[pm42]

je dois coder un joueur qui devine ce mot.

Quelle information reçoit le joueur quand il propose un mot ? Connait il la liste des 50 000 ? Quelle est la longueur d'un mot ?
Les mots en question sont ils aléatoire ou des mots d'un dictionnaire d'une langue bien connue ?
En gros, quelle est la fonction de probabilité de la position d'une lettre e en position p dans un mot ?

Je dois maximiser le score du joueur dans 100 tours où à chaque tour il obtient un score : le score est calculé par une fonction qui prend deux mots et retourne un score suivant la compatibilité des deux mots (nb de voyelles, nb de consonnes, ordre des lettres ...)

Qu'elle est la définition d'un tour ? Combien de tentatives un joueur fait il par tour ?
Quelle est la définition exacte du score ?

1-quelle est la meilleure "heuristique" pour maximiser le score du joueur dans 80 trs ?

Pourquoi est on passé de 100 tours à 80 tours ?
De plus, il est impossible de définir une heuristique sans les réponses aux questions précédentes.

Tu demandes "comment optimiser une fonction inconnue sur un ensemble de données inconnues ?". Réponse : inconnue.

2- comment optimiser l'algorithme puisque la quantité des données est énorme et avoir le résultat des 80 après une durée de temps raisonnable ?

La quantité de données n'est pas du tout énorme. Manipuler un ensemble de 50 000 entrées n'est rien du tout. Simuler 100 tirages se fait en très peu de temps et est parallélisable.
Donc où est le problème ?

[invite896757ff]

Si c'est du français, il faut à priori faire alterner voyelles et consonnes (dans une première approche).
Tenter des: "ch"; des: "th"; des: "gn" et autres singularités.

@ Jack concernant le précédent: "Entre la chaise et le clavier" signifiait au posteur que la demande était mal formulée, ce qui peut être considéré comme "constructif".

[invite7a0a8d2e]

@ Jack concernant le précédent: "Entre la chaise et le clavier" signifiait au posteur que la demande était mal formulée, ce qui peut être considéré comme "constructif".

Et même Incompréhensible.
On ne sait même pas s'il s'agit d'un jeu ou d'une simulation d'un jeu...

Sinon, concernant le tri du fichier des mots, ça vient après, éventuellement, et peut-être même qu'on n'aura pas besoin de s'en préoccuper vu la vitesse d'exécution des machines actuelles (surtout si le fichier est chargé en mémoire).
Si son emploi consomme 2 milliseconde avec tri et 100 millisecondes sans tri, franchement, s'occuper du tri est secondaire.

Moi ce que je suggère, c'est que Kizakoo décrive de manière non ambiguë (avec des mots en français pour le moment) ce que va faire le programme.
C'est la base pour celui qui ne sait pas directement coder : Formuler en langage naturel en essayant de faire en sorte que celui qui lit ce texte n'ai aucun besoin d'information supplémentaire.
Si c'est le cas, le programme est déjà presque terminé...

[kizakoo]

Merci à tous de vos réponses, je vais essayer d'être plus précis cette fois-ci :

Appelons Philippe la personne qui choisit le mot et Jack la personne qui doit deviner ce mot. Philippe et Jack ont tous les deux accès au fichier de 50 000 mots où chaque mot est de longueur 10 (10 lettres). Lorsque Jack propose un mot "guess" Philippe lui donne le score qu'il a eu : score(guess, choisi).

Les mots sont classés par ordre alphabétique, voici un échantillon de la liste (un mot par ligne) :

faceharden
facemaking
facesaving
faceteness

2- Le score est calculé de la manière suivante, une lettre à la même position dans les deux mots donne 2 points, une lettre dans les deux mots à des positions différentes donne 1 point. Par exemple:
score("ebz", "bze") == 3
score("ebc", "ebh") == 4

3- Une partie du jeu (1 game) est une boucle définie comme suit:

for i in [5, 10, 15]:
   jack = Jack(list_words)                                                     #On initialise jack et on lui donne la liste des mots
   play(jack, games=1, rounds=i))                                        #Ici je joue une seule partie (1 game) de i tours

4- La fonction simulator.play() :

def play(self, jack, rounds):
        my_score = 0
        word_chosen = random.choice(self.words)
        jack.new_game()                                                         #ici je ne fais rien pour l'instant (le code de jack.new_game est vide
        for i in range(rounds):
            guess = jack.guess()
            if guess not in self.words:
                return 0
            s = score(word, guess)
            bob.get_score(s)
            my_score += s
        return my_score

Le but est de maximiser le score de Jack dans 10 games.
@BraiMan la solution te semble évidente ? Merci de m'éclairer

[kizakoo]

Ce qui me semble le plus bloquant et ce qui fait ralentir le programme le plus c'est la fonction score :

def score(mot1, mot2):
    ans = 0
    ht = Counter(mot1)
    for c in word2:
        if ht[c]:
            ht[c] -= 1
            ans += 1
    for c1, c2 in zip(mot1, mot2):
        ans += c1 == c2
    return ans

J'ai essayé ce qui suit et le programme ne s'arrête pas ... la complexité explose :

for ChosenWord in list_word :
list(map(lambda x: score(x,'ChosenWord'), myWordList))

list_word contient 50 000 mots. Faut-il que je parallélise l'accès à la fonction score() ??

[kizakoo]

myWordList est list_word ... coquille

[invite896757ff]

Le score est calculé de la manière suivante, une lettre à la même position dans les deux mots donne 2 points, une lettre dans les deux mots à des positions différentes donne 1 point

C'est un "Mastermind" avec des lettres. Cherche sur Google: "résolution Mastermind", ça devrait t'aider.

[invite896757ff]

C'est un "Mastermind" avec des lettres. Cherche sur Google: "résolution Mastermind", ça devrait t'aider.

Ce lien dépiaute pas mal le problème: http://www.normalesup.org/~vernade/td6.pdf

[invite7a0a8d2e]

Ce qui me semble le plus bloquant et ce qui fait ralentir le programme le plus c'est la fonction score :
J'ai essayé ce qui suit et le programme ne s'arrête pas ... la complexité explose :

Je ne sais pas d'où sort word2
Peut-être qu'il s'agit de mot2

[kizakoo]

ouiiii.. une coquille

[pm42]

Ce qui me semble le plus bloquant et ce qui fait ralentir le programme le plus c'est la fonction score :

On peut probablement l'écrire plus rapide mais je ne suis pas sur que cela change grand chose parce que :

for ChosenWord in list_word :
list(map(lambda x: score(x,'ChosenWord'), myWordList))

C'est quoi myWorldList ? Parce que là effectivement, tu as une boucle dans une boucle donc tu as une complexité qui peut exploser.

Et quel est la logique de ton algorithme ? Tu ceux maximiser le score mais une bonne solution est sans doute d'essayer de trouver le bon mot le plus rapidement possible.
Après tout, le score maximal est atteint si on trouve la solution au 1er coup puis qu'on répète à chaque fois.

Mais je ne vois pas pourquoi tu calculerais un score sur les 50 000 mots.

[MissJenny]

C'est un "Mastermind" avec des lettres.

pas tout à fait. Dans le jeu MasterMind si je me souviens bien on dit au joueur le nombre de lettres (des couleurs en fait) bien placées et le nombre de lettres mal placées, alors qu'ici on a juste un score global, donc une information beaucoup plus pauvre.

[umfred]

retire aussi les guillemets autour de ChosenWord dans l'appel à score, le mot n'est pas 'ChosenWord' mais est dans la variable ChosenWord.