1998 ACM South Central USA Collegiate Programming Contest
Rice University

Scrabble

Solution      Judge's input     Judge's output      Clarifications   Comments

Scenario

The board game Scrabble (copyright Hasbro, Inc.) requires players to draw seven letter tiles from a pool, and form words on a game board, arranged horizontally or vertically, with their letters and the letters already played; just what constitutes a ``word'' is often subject to dispute, so it's handy to have a dictionary nearby when you play.  Scoring is based on the point values of the letters used to form the words, with the letters associated with point values as follows:

A-1 B-3 C-3 D-2  E-1 F-4 G-2 H-4 I-1 J-8 K-5 L-1 M-3
N-1 O-1 P-3 Q-10 R-1 S-1 T-1 U-1 V-4 W-4 X-8 Y-4 Z-10

Scoring is also affected by the positions on the board where the letters are played.  Some positions have the feature that they double or triple the score of the letter played there.  This bonus goes only to the first player to play a tile on that position, and not to another player who later uses that letter in a word.  The score for a word is obtained by summing the letter scores (including any doubling and tripling of letter values).  For example, the word ``MOUSE'', which would normally score 7 points, would score 10 if played so that the ``M'' falls on one of the double letter positions.  There are also positions that double or triple the score of the entire word.  These bonuses can accumulate; thus, if our word ``MOUSE'' managed to land with the ``M'' on a double letter position, and the ``E'' on a double word position, then the resulting score for the word is 20.  We will denote these kinds of positions as follows:
 


The map below illustrates the scrabble board in terms of these symbols; note the symmetries.

5--2---5---2--5
-4---3---3---4-
--4---2-2---4--
2--4---2---4--2
----4-----4----
-3---3---3---3-
--2---2-2---2--
5--2---4---2--5
--2---2-2---2--
-3---3---3---3-
----4-----4----
2--4---2---4--2
--4---2-2---4--
-4---3---3---4-
5--2---5---2--5

Finally, there is a 50 point bonus if all seven letters get played in a single turn.

The game begins with one player placing a word of up to seven letters on the board so that one letter covers that '4' (double word score) marker in the center of the board.

Now, it's your move.

Input

You will receive, in the file ``scrabble.inp'', a series of Scrabble puzzles, and in the file ``words'' a list of legal words.  Each puzzle poses the problem of playing second, after your opponent has made the first move of the game; thus, there is just one word you will have to intersect with when you choose your word.  Your opponent's first word is also in the list of legal words.  In our nonstandard version of the game, we require that the word you play must use one of the letters of of your opponent's word to form your own.  The objective in a puzzle is to find a word that uses some of your letters and one of the letters already played to form the highest scoring word, including bonuses for double-letter, triple-letter, double-word and triple-word positions, and the 50 point bonus for using all seven letters.

Each puzzle is represented on one line of the input file. A puzzle consists of the following information:
 

You may assume that the first word is played horizontally, and thus that your word will be played vertically.  The symmetry of the board actually makes it irrelevant whether the word was played horizontally or vertically.

In the file ``words'', the list of words that can be used in the game, each word is on a line by itself, at the beginning of the line, with no trailing spaces.  The words in the file are contain only uppercase letters, with no digits, punctuation, or lowercase letters.  You may assume that there are no more than 25000 words in the list, and that no word is more than eight letters long.

Output

You will print, to the file ``scrabble.out'', one line for each puzzle.  In that line you will show your word, in a field 8 characters wide, left-justified, padded by spaces on the right as necessary; a digit in a 2 character field, right-justified, that shows which letter of the original word you used, a digit in a 2 character field, right-justified, that shows which letter of your word is part of your opponent's word, and finally a number in a 4 character field, right justified.  that is your score for your word.

Sample Input

RDAWEER1ABDOMEN
OADPZBI5OPIATE
RTWXAIB3SMELL
AEFGOOS1BILLION
CYOKDAR7DOLTISH
CYOKDAR1DOLTISH
 

Sample Output

The line of digits is intended to guide you in proper output alignment, and is not part of the output that your solution should produce.

1234567890123456
WANDER   7 3  20
ZAP      4 2  27
AXIS     1 4  27
FALSE    3 3  18
DOCKYARD 1 1 100
DOCKYARD 1 8 122



 

Solution

#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>
#include <stdlib.h>
#include <strings.h>

unsigned const letterScore[] = {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};

enum { PLAIN='1', DBL_LETR='2', TRI_LETR='3', DBL_WORD='4', TRI_WORD='5' };

char const* board[] = {
  "511211151112115",
  "141113111311141",
  "114111212111411",
  "211411121114112",
  "111141111141111",
  "131113111311131",
  "112111212111211",
  "511211141112115",
  "112111212111211",
  "131113111311131",
  "111141111141111",
  "211411121114112",
  "114111212111411",
  "141113111311141",
  "511211151112115",
};

unsigned const SEVENBONUS = 50;

typedef char Word[9];

int alpha_order(void const* a, void const* b)
{
  char aa = *(char*)a;
  char bb = *(char*)b;
  return (aa < bb)? -1 : (aa > bb);
}

int main()
{
  ifstream in("scrabble.inp");

  Word letters;
  unsigned posn;
  Word oppword;
  while (in >> setw(8) >> letters >> posn >> oppword)
    {
      qsort(letters,7,1,alpha_order);

      unsigned maxScore = 0;
      unsigned hpos, vpos;
      Word maxWord;

      ifstream words("words");
      Word trialWord;
      while (words >> trialWord)
        {
          // can the trialWord fit into the puzzle?
          unsigned nMissingLetters = 0;
          char neededLetter;

          {
            Word sortWord;
            strcpy(sortWord, trialWord);
            qsort(sortWord,strlen(sortWord),1,alpha_order);

            char* L = letters;
            for (char* c = sortWord; *c && nMissingLetters < 2; ++c)
              {
                while (*L && *L < *c) ++L;
                // out of letters or found greater or equal letter
                if (*L == *c) // matched one
                  ++L;
                else
                  {
                    ++nMissingLetters;
                    neededLetter = *c;
                  }
              }
          }

          if (nMissingLetters > 1)
            // this word won't work, regardless of opponents word
            continue;

          Word commonLetter; // letters that could be at intersection of the words
          if (nMissingLetters == 1)
            commonLetter[0] = neededLetter, commonLetter[1] = '\0';
          else
            strcpy(commonLetter, trialWord);

          for (char *c = trialWord; *c; ++c)
            {
              unsigned baserow = 7 - (c - trialWord);
              for (char *d = oppword; *d; ++d)
                if (*c == *d && strchr(commonLetter,*c))
                  // Here's a place where words can cross!
                  {
                    unsigned score = 0;
                    unsigned wordMult = 1;
                    unsigned col = (d - oppword) - (posn-1) + 7;

                    for (unsigned i = 0; trialWord[i]; ++i)
                      {
                        unsigned lscore = letterScore[trialWord[i]-'A'];
                        if (baserow + i != 7)
                          switch (board[baserow+i][col])
                            {
                            case DBL_LETR:
                              lscore *= 2; break;
                            case TRI_LETR:
                              lscore *= 3; break;
                            case DBL_WORD:
                              wordMult *= 2; break;
                            case TRI_WORD:
                              wordMult *= 3; break;
                            case PLAIN:
                              break;
                            }
                        score += lscore;
                      }
                    score *= wordMult;
                    if (i == 8)
                      score += SEVENBONUS;
                    if (score >  maxScore)
                      {
                        maxScore = score;
                        strcpy(maxWord, trialWord);
                        hpos = d-oppword+1;
                        vpos = c-trialWord+1;
                      }
                  }
            }
        }
      cout << setiosflags(ios::left) << setw(8) << maxWord
           << resetiosflags(ios::left) << setw(2) << hpos
           << setw(2) << vpos
           << setw(4) << maxScore << "\n";
    }

  return 0;
}

Judge's Input

RDAWEER1ABDOMEN
OADPZBI5OPIATE
RTWXAIB3SMELL
AEFGOOS1BILLION
CYOKDAR7DOLTISH
CYOKDAR1DOLTISH

Judge's Output

WANDER   7 3  20
ZAP      4 2  27
AXIS     1 4  27
FALSE    3 3  18
DOCKYARD 1 1 100
DOCKYARD 1 8 122

Clarifications

No significant clarifications were necessary on this problem.
 

Comments

Hardly anyone tried this problem.  I learned during the contest that the "strchr" function has replaced the "index" function in standard C libraries, with the effect that my initial solution didn't compile.  At the time, we invented our own index function, but in the solution above, I've used strchr, as I should have all along.

The implementation above first considers whether a particular word pulled from the dictionary can be made to work with the letters in hand, rejecting the word if it includes two letters that we don't have.  Then it's basically just an exhaustive search of all the ways the word could intersect the word already played.

The words file we used contained 13714 words.  Printing that word file here would probably not be useful.  Many systems have a file called something like /usr/dict/words; we derived our words file from one of those.