Scrabble

The aim of this puzzle is to find the best word possible (in a given dictionnary) with a given set of letters. By best, understand the word that earn the most points when playing Scrabble. Once developped a function which determine if it is possible to write a word with a set of letters, and another function which computes the number of points earned by a word, a simple linear search allows to find the result. If not easier, this puzzle is as difficult as the easy puzzles involving string manipulation and linear search.

Difficulty: Medium · Skills: letter counting, scoring, linear search, string matching

What this puzzle tests in a coding interview

Scrabble tests multiset reasoning: can a word be built from seven letters, each usable once? It also checks careful tie-breaking, since the first word in the dictionary wins when two words have the same score.

How to solve it, step by step

  1. Store the letter values in a table indexed by letter.
  2. For each dictionary word, check it can be written by consuming each needed letter from a copy of the available letters.
  3. If a needed letter is missing, reject the word immediately.
  4. For writable words, add up the letter values to get the score.
  5. Keep the first word with the strictly highest score and print it.

Time and memory complexity

With D words of length up to 7 and 7 letters, each check is O(7 x 7), so the total is O(D) time and O(1) extra memory. The dictionary order of the input is kept, so a strict comparison is all the tie rule needs.

Traps to avoid

Tip for a timed test

Counting letters with a 26-slot array per word is less error-prone than searching and blanking characters; compare counts and you are done.

C

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

// Returns 1 if 'word' is writeable with letters contains in 'letters', 0 else
int writeable(char* word, char* letters) {
    char copy[strlen(letters)];
    strcpy(copy, letters);
    
    /* For each letter in word, looks for the letter in copy and replaces it
       by a space. If the letter can't be found, then word is not writeable with
       letters */
    for (int i = 0; word[i] != '\0'; i++) {
        int j = 0;
        while (copy[j] != '\0' && copy[j] != word[i])
            j++;
        if (copy[j] == word[i])
            copy[j] = ' ';
        else
            return 0;
    }
    return 1;
}

// array of 26 integers corresponding to the weight of each letter of the alphabet
int WEIGHTS[] = {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};

// Returns the number of points 'word' earns
int pointCount (char *word, int WEIGHTS[26]) {
    int res = 0;
    for (int i = 0; word[i] != '\0'; i++)
        res += WEIGHTS[word[i]-'a'];
    return res;
}

int main(int argc, char **argv)
{
    // Reading input : the N words of the dictionary, and letters available
    int N;
    scanf("%d\n", &N);
    char dictionary[N][30];
    for (int i = 0; i < N; i++)
        gets(dictionary[i]);
    char letters[8];
    fgets(letters,8,stdin);
    
    // Searches max pointCount amongst writeable words
    int max = 0;
    int count;
    char *res = NULL;
    for (int i = 0; i < N; i++)
        if (writeable(dictionary[i], letters) && (count = pointCount(dictionary[i], WEIGHTS)) > max) {
            max = count;
            res = dictionary[i];
        }

    printf("%s\n", res);
    return EXIT_SUCCESS;
}