TP 7 : Wordle#

Wordle est un jeu de lettres en ligne gratuit. Ce jeu est une adaptation directe du jeu télévisé américain Lingo (Motus en France) qui propose de faire deviner un mot par plusieurs tentatives, en indiquant pour chacune d’entre-elles la position des lettres bien placées et mal placées. L’objectif est de trouver le mot en un nombre minimum de coups.

Rappels sur les chaînes de caractères#

Une chaîne de caractères est une suite de caractères. En Python, une chaîne de caractères est délimitée par des guillemets simples ou doubles. Les opérations sur les chaînes de caractères ressemblent beaucoup à celles sur les listes :

s = "abc" # exemple de chaîne de caractères
s # affiche la chaîne de caractères

'abc'

len(s) # affiche la longueur de la chaîne de caractères

s[0] # affiche le premier caractère de la chaîne

'a'

for c in s: # parcourt chaque caractère de la chaîne
    print(c) 

for i in range(len(s)): # autre façon de parcourir chaque caractère de la chaîne
    print(s[i])

a
b
c
a
b
c

"bon" + "jour" # concaténation de chaînes de caractères

'bonjour'

Il n’y a pas de append sur les chaînes de caractères, mais on peut utiliser += pour ajouter un caractère à la fin :

s += "def" # ajoute "def" à la fin de la chaîne s
s

'abcdef'

Question

Écrire une fonction appartient(c, s) qui renvoie True si le caractère c appartient à la chaîne de caractères s et False sinon.

Solution

def appartient(c, s):
    for c2 in s:
        if c == c2:
            return True
    return False

appartient("a", "abc") # True
appartient("d", "abc") # False

False

Téléchargement des mots#

La fonction suivante télécharge et renvoie une liste des mots du dictionnaire (sans accent) :

def telecharger_mots():
    import urllib.request
    f = urllib.request.urlopen("https://raw.githubusercontent.com/cpge-itc/bcpst2/main/files/8_wordle/mots.txt")
    return list(map(lambda x: x.decode('utf-8').replace('\n', ''), f.readlines()))

Question

Récupérer la liste des mots dans une variable mots. Combien y a t-il de mots ?

Solution

mots = telecharger_mots()
len(mots)

Question

Dans le jeu de Wordle, les mots doivent être de taille \(5\). Définir une liste mots5 contenant les mots de taille \(5\). Combien y a t-il de mots de taille \(5\) ?

Solution

mots5 = []
for mot in mots:
    if len(mot) == 5:
        mots5.append(mot)
len(mots5)

Simulation#

Dans un premier temps, l’objectif est de deviner un mot que l’ordinateur aura choisi au hasard.

Question

Écrire une fonction mot_aleatoire qui renvoie un mot choisi au hasard dans la liste mots5. On pourra utiliser random.randrange(n) pour générer un entier aléatoire entre \(0\) et \(n-1\).

Solution

import random
def mot_aleatoire(L):
    return L[random.randrange(len(mots5))]

mot_aleatoire(mots5)

'tarte'

Question

Écrire une fonction valide(mot) qui renvoie True si le mot mot est dans la liste mots5. Sinon, elle renvoie False.

Solution

def valide(mot):
    return mot in mots5

print(valide("bonjour"))
print(valide("arbre"))

False
True

Question

Écrire une fonction reponse(mot, proposition) qui renvoie une chaîne de caractères correspondant aux lettres correctes de la proposition par rapport au mot à deviner. On mettra _ si la lettre de proposition n’est pas dans mot et * si elle y est mais mal placée.

Solution

def reponse(mot, proposition):
    s = ""
    for i in range(len(proposition)):
        if proposition[i] == mot[i]:
            s += proposition[i]
        elif proposition[i] in mot:
            s += "*"
        else:
            s += "_"
    return s

reponse("arbre", "heure")

'_*_re'

Pour la question suivante, on utilisera la fonction input qui permet de demander à l’utilisateur de saisir une chaîne de caractères. Par exemple, input("Entrez un mot : ") affiche le message “Entrez un mot : ” et renvoie la chaîne de caractères saisie par l’utilisateur.

Question

Écrire une fonction jeu() qui permet de jouer au jeu de Wordle de la façon suivante :

Choisir le mot à chercher, au hasard dans la liste mots5.
Tant que l’utilisateur n’a pas trouvé le mot à chercher, demander à l’utilisateur de proposer un mot et afficher la réponse (avec print). Le mot proposé par l’utilisateur doit être valide (dans mots5).

Solution

def jeu():
    mot = mot_aleatoire(mots5)
    proposition = ""
    while proposition != mot:
        proposition = input("Proposition : ")
        if valide(proposition):
            print(proposition, "\n", reponse(mot, proposition))
        else:
            print("Mot invalide. Recommencez.")
    print("Bravo !")

jeu()

Résolution par l’ordinateur#

Nous souhaitons maintenant choisir un mot secret que l’ordinateur devra trouver.

Question

Écrire une fonction possibles(L, proposition, rep) qui conserve uniquement les mots m de la liste L qui donnent la même réponse que proposition si on les compare à rep, c’est-à-dire tels que reponse(m, proposition) == rep.

Solution

def possibles(L, proposition, rep):
    res = []
    for mot in L:
        if reponse(mot, proposition) == rep:
            res.append(mot)
    return res

print(possibles(mots5, "heure", "_*_re"))

['acere', 'adore', 'adore', 'aigre', 'amere', 'ancre', 'arbre', 'astre', 'avare', 'avere', 'barre', 'biere', 'boire', 'cadre', 'carre', 'clore', 'elire', 'encre', 'entre', 'entre', 'fibre', 'fiere', 'flore', 'foire', 'frere', 'frire', 'givre', 'libre', 'litre', 'livre', 'livre', 'loire', 'madre', 'maire', 'marre', 'mitre', 'moore', 'noire', 'notre', 'notre', 'offre', 'ombre', 'opere', 'opere', 'ordre', 'paire', 'patre', 'pitre', 'poire', 'sabre', 'sacre', 'score', 'sobre', 'spore', 'taire', 'tiare', 'tigre', 'tigre', 'titre', 'vitre', 'vivre', 'voire', 'votre', 'votre']

Question

Écrire une fonction resolution() qui permet à l’ordinateur de résoudre le jeu de Wordle. Pour cela :

On stocke dans une liste L les mots encore possibles étant données les réponses précédentes.
L’ordinateur choisit une proposition au hasard dans L et l’utilisateur donne la réponse (avec input()).
On met à jour L en conservant uniquement les mots qui donnent la même réponse que le mot choisi.

On renverra le nombre de coups nécessaires pour trouver le mot.
Pour tester, on pourra utiliser https://wordle.louan.me.

Solution

def resolution():
    L = mots5
    n = 0
    while len(L) > 1:
        n += 1
        proposition = random.choice(L)
        rep = input("Réponse pour " + proposition + " : ")
        L = possibles(L, proposition, rep)
    print("Le mot est", L[0])
    return n

Question

Plutôt que de donner la réponse à la main, on peut faire jouer l’ordinateur contre lui-même. Écrire une fonction resolution2(mot) en utilisant reponse(mot, proposition) à chaque proposition de l’ordinateur (au lieu de input).

Solution

def resolution2(mot):
    L = mots5
    n = 0
    while len(L) > 1:
        n += 1
        proposition = random.choice(L)
        rep = reponse(mot, proposition)
        L = possibles(L, proposition, rep)
    # print("Le mot est", L[0])
    return n

Question

Écrire une fonction nombre_coups(n) qui appelle resolution2 \(n\) fois (sur des mots choisis aléatoirement) et renvoie le nombre moyen de coups nécessaires pour trouver le mot.

Solution

def nombre_coups(n):
    coups = 0
    for _ in range(n):
        mot = mot_aleatoire(mots5)
        coups += resolution2(mot)
    return coups / n

nombre_coups(1000)

Amélioration avec une heuristique#

Dans la suite, on essaie d’améliorer resolution2 (pour trouver la solution en moins d’essais) en choisissant une proposition autrement qu’au hasard.
Pour cela, nous allons utiliser une heuristique (c’est-à-dire une méthode qui n’est pas toujours optimale mais qui donne de bons résultats en pratique) qui consiste à choisir la proposition dont les lettres sont les plus fréquentes parmi les possibilités restantes.

Question

Écrire une fonction numero_lettre(lettre) qui renvoie le numéro de la lettre dans l’alphabet (de \(0\) à \(25\)). Par exemple, numero_lettre("a") renvoie \(0\) et numero_lettre("z") renvoie \(25\).
On utilisera ord(c) qui renvoie le code ASCII d’une lettre c (par exemple, ord("a") renvoie \(97\)).

Solution

def numero_lettre(c):
    return ord(c) - ord('a')

numero_lettre('e')

Question

Écrire une fonction compter telle que, si L est une liste de mots, compter(L) renvoie une matrice C de taille \(26 \times 5\) telle que C[i][j] est le nombre de mots de L qui contiennent la lettre numéro \(i\) à la position \(j\).
Par exemple, C[1][3] doit être le nombre de mots de L qui ont la lettre numéro 1 (c’est-à-dire \(b\)) en position 3.

Solution

import numpy as np

def compter(L):
    C = np.zeros((26, 5))
    for mot in L:
        for i in range(len(mot)):
            C[numero_lettre(mot[i]), i] += 1
    return C

compter(mots5)

array([[135., 367., 137.,  78.,  36.],
       [120.,  13.,  53.,  25.,   1.],
       [163.,  27.,  85.,  47.,  14.],
       [ 85.,  12.,  35.,  60.,  14.],
       [ 79., 327., 132., 354., 801.],
       [116.,   3.,  18.,  11.,   9.],
       [ 76.,   9.,  69.,  55.,   5.],
       [ 40.,  37.,   6.,  37.,   5.],
       [ 22., 207., 165., 206.,  51.],
       [ 43.,   1.,   6.,   1.,   0.],
       [ 10.,   1.,   2.,   3.,   5.],
       [ 90.,  79., 122., 104.,  52.],
       [114.,  23.,  66.,  59.,   5.],
       [ 51.,  34., 162., 145.,  99.],
       [ 39., 313.,  89.,  85.,  36.],
       [178.,  18.,  42.,  37.,   5.],
       [  9.,   0.,   8.,   0.,   0.],
       [118., 129., 207., 146., 177.],
       [144.,  16.,  87.,  82., 310.],
       [108.,  32., 130., 149., 131.],
       [ 12., 146., 133., 119.,  49.],
       [ 89.,  22.,  51.,  34.,   1.],
       [  1.,   1.,   1.,   1.,   0.],
       [  0.,  10.,  11.,   0.,  22.],
       [  1.,  16.,  23.,   4.,   9.],
       [  2.,   2.,   5.,   3.,   8.]])

Question

Écrire une fonction heuristique(C, mot) qui renvoie la somme de C[c][i] pour chaque lettre c à la position i de mot, où C est la matrice renvoyée par compter.

Solution

def heuristique(C, mot):
    res = 0
    for i in range(5):
        res += C[mot[i]][i]
    return res

Question

Écrire une fonction meilleure_proposition(L) qui renvoie la proposition qui a la plus grande valeur de heuristique(C, mot) pour chaque mot mot de L, où C est la matrice renvoyée par compter(L).

Solution

def meilleure_proposition(L):
    C = compter(L)
    maxi = 0
    for mot in L:
        h = heuristique(C, mot)
        if h > maxi:
            maxi = h
            proposition = mot
    return proposition

Question

Écrire une fonction resolution3(mot) qui utilise meilleure_proposition pour proposer une solution.

Solution

def resolution3(mot):
    L = mots5
    n = 0
    while len(L) > 1:
        n += 1
        proposition = meilleure_proposition(L)
        rep = reponse(mot, proposition)
        L = possibles(L, proposition, rep)
    return n

Question

Écrire une fonction nombre_coups3(n) qui appelle resolution3 \(n\) fois (sur des mots choisis aléatoirement) et renvoie le nombre moyen de coups nécessaires pour trouver le mot. Comparer avec resolution2.

Solution

def nombre_coups(n):
    coups = 0
    for _ in range(n):
        mot = mot_aleatoire(mots5)
        coups += resolution3(mot)
    return coups / n

nombre_coups(100)

Informatique en 2ème année de BCPST

TP 7 : Wordle

Contents

TP 7 : Wordle#

Rappels sur les chaînes de caractères#

Téléchargement des mots#

Simulation#

Résolution par l’ordinateur#

Amélioration avec une heuristique#