Coding Solution

Scrabble – solution CodinGame en C

Moyenletter countingstring processinglinear searchhash mapMis à jour le
Réponse courte

On compte combien de fois chaque lettre apparaît parmi les 7 tuiles, puis on parcourt le dictionnaire une seule fois : un mot est jouable si, pour chaque lettre, il n'en utilise pas plus d'exemplaires qu'on en possède. On note les mots jouables avec les valeurs des lettres du Scrabble et on garde le meilleur avec une comparaison strictement supérieure, de sorte qu'à égalité c'est le mot apparu en premier dans le dictionnaire qui l'emporte.

L'énoncé

On reçoit un dictionnaire d'au plus 100 000 mots en minuscules (de 30 lettres maximum chacun), suivi des 7 lettres que l'on possède. Parmi les mots du dictionnaire que ces lettres permettent réellement d'écrire, il faut trouver celui qui rapporte le plus de points.

Chaque tuile ne sert qu'une fois, les valeurs des lettres sont celles du Scrabble anglais, et si plusieurs mots atteignent le meilleur score, on affiche celui qui apparaît en premier dans le dictionnaire fourni. Il existe toujours au moins un mot valide.

La démarche, étape par étape

  1. Compter les lettres disponiblesOn transforme les 7 tuiles en un tableau de 26 compteurs. Les doublons comptent : avec « aab », on peut écrire « baa » mais pas « aaa ».
  2. Vérifier chaque mot contre les compteursPour un mot du dictionnaire, on incrémente un nouveau tableau de 26 compteurs lettre par lettre et on s'arrête dès qu'un compteur dépasse ce qu'on possède. Les mots de plus de 7 lettres peuvent être rejetés d'emblée.
  3. Noter en même tempsOn additionne les valeurs des lettres dans la même boucle : 1 pour e a i o n r t l s u, 2 pour d g, 3 pour b c m p, 4 pour f h v w y, 5 pour k, 8 pour j x et 10 pour q z.
  4. Garder le premier meilleur motOn parcourt dans l'ordre du dictionnaire et on remplace le meilleur courant seulement si le nouveau score est strictement supérieur. Cela applique la règle d'égalité automatiquement, sans tri.

Complexité

TempsO(N * k)
MémoireO(N * k)

Chacun des N mots est examiné une fois, lettre par lettre, avec k <= 30, et le rejet anticipé ramène le coût réel à environ 7 étapes par mot. Le stockage du dictionnaire est la seule mémoire notable ; on pourrait aussi traiter les mots au fil de la lecture.

Code de la solution

Scrabble – C

#include <stdio.h>
#include <string.h>

static const int POINTS[26] = {1,3,3,2,1,4,2,4,1,8,5,1,3,1,1,3,10,1,1,1,1,4,4,8,4,10};
static char words[100000][32];

int main(void) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%31s", words[i]);
    char letters[16];
    scanf("%15s", letters);

    int available[26] = {0};
    for (int i = 0; letters[i]; i++)
        available[letters[i] - 'a']++;

    int best = -1, bestScore = -1;
    for (int i = 0; i < n; i++) {
        int used[26] = {0}, score = 0, ok = 1;
        for (int j = 0; words[i][j] && ok; j++) {
            int c = words[i][j] - 'a';
            if (++used[c] > available[c]) ok = 0;
            score += POINTS[c];
        }
        /* strict '>' keeps the first word of the dictionary on a tie */
        if (ok && score > bestScore) {
            bestScore = score;
            best = i;
        }
    }
    printf("%s\n", words[best]);
    return 0;
}

Erreurs fréquentes

Pour aller plus loin

Comme le chevalet n'a que 7 tuiles, seule la taille du dictionnaire peut ralentir la solution, et le filtre sur la longueur est l'optimisation la moins chère : tout mot de plus de 7 lettres est rejeté avant même de regarder une lettre. Une autre représentation élégante est le multi-ensemble vu comme un vecteur à 26 composantes : le mot est jouable quand son vecteur est inférieur ou égal composante par composante à celui du chevalet, ce qu'exprime en une ligne la soustraction de Counter en Python (not Counter(word) - Counter(rack)). Si l'on devait traiter de nombreux chevalets contre le même dictionnaire, on précalculerait le vecteur d'effectifs de chaque mot une fois pour toutes, et l'astuce classique des vrais jeux de lettres consiste à indexer les mots par leurs lettres triées (clé d'anagramme) pour traiter toutes les permutations ensemble.

Questions fréquentes

Peut-on utiliser deux fois la même tuile dans Scrabble sur CodinGame ?

Non. Chaque tuile sert au plus une fois, donc un mot avec deux « e » exige deux tuiles « e ». C'est pourquoi on compare des effectifs de lettres et non une simple présence.

Que faut-il afficher si deux mots ont le même score ?

Celui qui apparaît en premier dans le dictionnaire donné en entrée. Parcourir dans l'ordre et ne remplacer le meilleur que sur un score strictement supérieur fait exactement cela.

Faut-il gérer les jokers ou les bonus du plateau ?

Non. Il n'y a ni plateau ni joker : le score est simplement la somme des valeurs des lettres du mot.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome