Robert Eisele
Engineer, Systems Architect and DBA

Codingame: Scrabble

Original Problem

The Goal

When playing Scrabble©, each player draws 7 letters and must find a word that scores the most points using these letters.

A player doesn't necessarily have to make a 7-letter word; the word can be shorter. The only constraint is that the word must be made using the 7 letters which the player has drawn.

For example, with the letters etaenhs, some possible words are: ethane, hates, sane, ant. Your objective is to find the word that scores the most points using the available letters (1 to 7 letters).

Rules

In Scrabble©, each letter is weighted with a score depending on how difficult it is to place that letter in a word. You will see below a table showing the points corresponding to each letter:

LettersPoints
e, a, i, o, n, r, t, l, s, u1
d, g2
b, c, m, p3
f, h, v, w, y4
k5
j, x8
q, z10

The word banjo earns you 3 + 1 + 1 + 8 + 1 = 14 points.

A dictionary of authorized words is provided as input for the program. The program must find the word in the dictionary which wins the most points for the seven given letters (a letter can only be used once). If two words win the same number of points, then the word which appears first in the order of the given dictionary should be chosen.

All words will only be composed of alphabetical characters in lower case. There will always be at least one possible word.

Game Input

Input

Line 1: the number N of words in the dictionary

N following lines: the words in the dictionary. One word per line.

Last line: the 7 letters available.

Output
The word that scores the most points using the available letters (1 to 7 letters). The word must belong to the dictionary. Each letter must be used at most once in the solution. There is always a solution.
Constraints
0 < N < 100000
Words in the dictionary have a maximum length of 30 characters.

Solution

The first thing we need to do is creating a hash-map from the given point table:

var Points = {
  e: 1, a: 1, i: 1, o: 1, n: 1, r: 1, t: 1, l: 1, s: 1, u: 1,
  d: 2, g: 2,
  b: 3, c: 3, m: 3, p: 3,
  f: 4, h: 4, v: 4, w: 4, y: 4,
  k: 5,
  j: 8, x: 8,
  q: 10, z: 10
};

Since we need to know the letters first, we must cache the dictionary in an array for the moment, but can skip all words that are longer than 7, since they will be discarded anyway:

var n = +readline();
var dict = [];
for (var i = 0; i < n; i++) {
  var word = readline();
  if (word.length <= 7)
    dict.push(word);
}

We now read in the letters, but directly create a hash-map out of it, which counts the number of letters:

var lettersHash = getHash(readline());

At the end, we simply loop over the created dictionary and calculate the score. We arrange a getScore() function in a moment, which returns -1 if the word is not possible. Since we try to maximize the value, everything is okay with that:

var maxScore = -1;
var maxWord = null;
for (var i = 0; i < dict.length; i++) {
  var score = getScore(dict[i], lettersHash);
  if (maxScore < score) {
    maxScore = score;
    maxWord = dict[i];
  }
}
print(maxWord);

To calculate the hash-map which counts the number of letters, we introduce this little helper function:

function getHash(word) {
  var h = {};
  for (var i = 0; i < word.length; i++) {
    h[word[i]] = (h[word[i]] || 0) + 1;
  }
  return h;
}

All we now need to do is creating a hash of the word itself, loop over the hash and check if the character exists at all in our letter map and if it does, is the number of characters enough? If any of these two cases fails, the word is not correct and we return -1. On the other hand, if everything looks fine, we simply sum the number of letters in the word times the points we get for each letter. All that is needed is then:

function getScore(word, lh) {

  var total = 0;

  var wh = getHash(word);

  for (var w in wh) {
    if (!(w in lh) || lh[w] < wh[w])
      return -1;
    total+= wh[w] * Points[w];
  }
  return total;
}

Go to overview

All images are copyright to Codingame