1. Introduction
Voici une façon d'aborder ce problème de manière systématique : si vous avez un algorithme qui joue bien au pendu, vous pouvez considérer que la difficulté de chaque mot est le nombre de mauvaises réponses que votre programme prendrait pour deviner ce mot.
2. Aside sur la stratégie du pendu
Il y a une idée implicite dans d'autres réponses et commentaires, selon laquelle la stratégie optimale pour le résolveur serait de baser ses décisions sur la fréquence des lettres en anglais, ou sur la fréquence des mots dans un corpus. C'est une idée séduisante, mais ce n'est pas tout à fait juste. Le solveur obtient de meilleurs résultats s'il modélise avec précision la distribution des mots choisis par le passeur et un passeur humain peut très bien choisir des mots en fonction de leur rareté ou en évitant les lettres fréquemment utilisées. Par exemple, bien que E est la lettre la plus fréquemment utilisée en anglais, si le passeur choisit toujours parmi les mots JUGFUL , RHYTHM , SYZYGY y ZYTHUM alors un solveur parfait ne commence pas par deviner E !
La meilleure approche pour modéliser le passeur dépend du contexte, mais je pense qu'une sorte d'inférence inductive bayésienne fonctionnerait bien dans un contexte où le résolveur joue de nombreuses parties contre le même passeur, ou contre un groupe de passeurs similaires.
3. Un algorithme de type hangman
Je vais vous présenter un solveur qui est assez bon (mais loin d'être parfait). Il modélise le fixateur comme choisissant des mots uniformément à partir d'un dictionnaire fixe. C'est un algorithme de gourmandise à chaque étape, il devine la lettre qui minimise le nombre d'échecs, c'est-à-dire les mots qui ne contiennent pas la lettre devinée. Par exemple, si aucune supposition n'a été faite jusqu'à présent, et que les mots possibles sont DEED , DEAD y DARE alors :
- si vous devinez
D o E il n'y a pas de ratés ;
- si vous devinez
A il y a un manque ( DEED ) ;
- si vous devinez
R il y a deux manques ( DEED y DEAD ) ;
- si vous devinez une autre lettre, il y a trois ratés.
Donc, soit D o E est une bonne estimation dans cette situation.
(Merci à Colonel Panic dans les commentaires pour m'avoir fait remarquer que les bonnes réponses sont gratuites au pendu - j'avais totalement oublié cela lors de ma première tentative !)
4. Mise en œuvre
Voici une implémentation de cet algorithme en Python :
from collections import defaultdict
from string import ascii_lowercase
def partition(guess, words):
"""Apply the single letter 'guess' to the sequence 'words' and return
a dictionary mapping the pattern of occurrences of 'guess' in a
word to the list of words with that pattern.
>>> words = 'deed even eyes mews peep star'.split()
>>> sorted(list(partition('e', words).items()))
[(0, ['star']), (2, ['mews']), (5, ['even', 'eyes']), (6, ['deed', 'peep'])]
"""
result = defaultdict(list)
for word in words:
key = sum(1 << i for i, letter in enumerate(word) if letter == guess)
result[key].append(word)
return result
def guess_cost(guess, words):
"""Return the cost of a guess, namely the number of words that don't
contain the guess.
>>> words = 'deed even eyes mews peep star'.split()
>>> guess_cost('e', words)
1
>>> guess_cost('s', words)
3
"""
return sum(guess not in word for word in words)
def word_guesses(words, wrong = 0, letters = ''):
"""Given the collection 'words' that match all letters guessed so far,
generate tuples (wrong, nguesses, word, guesses) where
'word' is the word that was guessed;
'guesses' is the sequence of letters guessed;
'wrong' is the number of these guesses that were wrong;
'nguesses' is len(guesses).
>>> words = 'deed even eyes heel mere peep star'.split()
>>> from pprint import pprint
>>> pprint(sorted(word_guesses(words)))
[(0, 1, 'mere', 'e'),
(0, 2, 'deed', 'ed'),
(0, 2, 'even', 'en'),
(1, 1, 'star', 'e'),
(1, 2, 'eyes', 'en'),
(1, 3, 'heel', 'edh'),
(2, 3, 'peep', 'edh')]
"""
if len(words) == 1:
yield wrong, len(letters), words[0], letters
return
best_guess = min((g for g in ascii_lowercase if g not in letters),
key = lambda g:guess_cost(g, words))
best_partition = partition(best_guess, words)
letters += best_guess
for pattern, words in best_partition.items():
for guess in word_guesses(words, wrong + (pattern == 0), letters):
yield guess
5. Exemples de résultats
En utilisant cette stratégie, il est possible d'évaluer la difficulté de deviner chaque mot d'une collection. Je considère ici les mots de six lettres du dictionnaire de mon système :
>>> words = [w.strip() for w in open('/usr/share/dict/words') if w.lower() == w]
>>> six_letter_words = set(w for w in words if len(w) == 6)
>>> len(six_letter_words)
15066
>>> results = sorted(word_guesses(six_letter_words))
Les mots les plus faciles à deviner dans ce dictionnaire (ainsi que la séquence de devinettes nécessaires pour que le solveur les devine) sont les suivants :
>>> from pprint import pprint
>>> pprint(results[:10])
[(0, 1, 'eelery', 'e'),
(0, 2, 'coneen', 'en'),
(0, 2, 'earlet', 'er'),
(0, 2, 'earner', 'er'),
(0, 2, 'edgrew', 'er'),
(0, 2, 'eerily', 'el'),
(0, 2, 'egence', 'eg'),
(0, 2, 'eleven', 'el'),
(0, 2, 'enaena', 'en'),
(0, 2, 'ennead', 'en')]
et les mots les plus durs sont ceux-là :
>>> pprint(results[-10:])
[(12, 16, 'buzzer', 'eraoiutlnsmdbcfg'),
(12, 16, 'cuffer', 'eraoiutlnsmdbpgc'),
(12, 16, 'jugger', 'eraoiutlnsmdbpgh'),
(12, 16, 'pugger', 'eraoiutlnsmdbpcf'),
(12, 16, 'suddle', 'eaioulbrdcfghmnp'),
(12, 16, 'yucker', 'eraoiutlnsmdbpgc'),
(12, 16, 'zipper', 'eraoinltsdgcbpjk'),
(12, 17, 'tuzzle', 'eaioulbrdcgszmnpt'),
(13, 16, 'wuzzer', 'eraoiutlnsmdbpgc'),
(13, 17, 'wuzzle', 'eaioulbrdcgszmnpt')]
La raison pour laquelle elles sont difficiles est qu'après avoir deviné -UZZLE vous avez encore sept possibilités :
>>> ' '.join(sorted(w for w in six_letter_words if w.endswith('uzzle')))
'buzzle guzzle muzzle nuzzle puzzle tuzzle wuzzle'
6. Choix de la liste de mots
Bien entendu, lorsque vous préparez des listes de mots pour vos enfants, vous ne commencez pas par le dictionnaire système de votre ordinateur, mais par une liste de mots que vous pensez qu'ils sont susceptibles de connaître. Par exemple, vous pouvez consulter Listes des mots les plus fréquemment utilisés par Wiktionary dans divers corpus anglais.
Par exemple, parmi les 1 700 mots de six lettres de la collection Les 10 000 mots les plus courants du Projet Gutenberg en 2006 les dix plus difficiles sont ceux-là :
[(6, 10, 'losing', 'eaoignvwch'),
(6, 10, 'monkey', 'erdstaoync'),
(6, 10, 'pulled', 'erdaioupfh'),
(6, 10, 'slaves', 'erdsacthkl'),
(6, 10, 'supper', 'eriaoubsfm'),
(6, 11, 'hunter', 'eriaoubshng'),
(6, 11, 'nought', 'eaoiustghbf'),
(6, 11, 'wounds', 'eaoiusdnhpr'),
(6, 11, 'wright', 'eaoithglrbf'),
(7, 10, 'soames', 'erdsacthkl')]
(Soames Forsyte est un personnage de l'histoire de l'Europe. La Saga des Forsytes par John Galsworthy ; la liste de mots a été convertie en minuscules, il ne m'a donc pas été possible de supprimer rapidement les noms propres).
