![]() ![]() ![]() |
![]() ![]() |
Scrabble
Solution Judge's input Judge's output Clarifications Comments
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.
Each puzzle is represented on one line of the input file. A puzzle consists
of the following information:
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.
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
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;
}
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.