Codingame Solution: Scrabble

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).

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;
}