Connection Status:
Competition Arena > BoggleScore

BoggleScore

SRM 349 · 2007-05-15 · by erinn

SRM 349 · 2007-05-15 · by erinn · Dynamic Programming, Math, Search
Class Name: BoggleScore
Return Type: long
Method Name: bestScore
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

In the word game Boggle, a player is presented with a 4x4 grid of letters and has the task of finding words hidden among the letters. A word may start at any location, and each succeeding letter of the word must be adjacent to the preceding letter horizontally, vertically, or diagonally.

In our version of the game, a player is restricted to finding words from a given list of acceptable words. The same letter may be used multiple times in the spelling of a word, and it is permitted to spell words that are part of longer words. For instance, in the following example, one could form the word SANDS, even though there is only a single S:

XXXX
XSAX
XDNX
XXXX

Notice that the above configuration would also yield other words, like SAND, AND, and SAD.

If a word can be formed in more than one way, it may be counted more than once; for instance, the word EYE may be counted multiple times here since it can be found in different directions (see examples):

XEYE
XXXX
XXXX
XXXX

Here, the word EYE could still be formed, but only once, since we are allowed to reuse letters:

XXEY
XXXX
XXXX
XXXX

Here, the word TREE may be formed two different ways (down-right-up or down-diagonal-down):

TEXX
REXX
XXXX
XXXX

The score for each word is the square of its length. Thus, three letter words are worth 9 points, four letter words are 16 points, etc.

You are given a String[] grid with exactly four elements, with each element containing 4 letters, describing the grid of letters you are to search. You are also given a String[] words, each element of which represents an acceptable word.

You are to return a long indicating the maximum score you can achieve after finding all possible paths to spell out acceptable words, summing together the scores from each individual word. Since the maximum score could potentially be quite large, return the result MOD 1E13 (10000000000000).

Constraints

  • grid will contain exactly four elements.
  • Each element of grid will contain exactly four characters.
  • Each character of each element of grid will be an uppercase ('A'-'Z') letter.
  • words will contain between 1 and 50 elements, inclusive.
  • Each element of words will contain between 1 and 50 characters, inclusive.
  • Each character of each element of words will be an uppercase ('A'-'Z') letter.
  • No two elements of words will be the same.
Examples
0)
{"XXEY",
 "XXXX",
 "XXXX",
 "XXXX"}
{"EYE"}
Returns: 9

From the problem statement. There's exactly one way to spell EYE, and it's worth 9 points.

1)
{"XEYE",
 "XXXX",
 "XXXX",
 "XXXX"}
{"EYE"}
Returns: 36

Also from the problem statement. Here, there are four ways to spell EYE. If we number the positions in the grid from 0-15 (top to bottom, left to right), then we can spell EYE by going: 123, 121, 321, 323.

2)
{"TEXX",
 "REXX",
 "XXXX",
 "XXXX"}
{"TREE"}
Returns: 32

Again, from the problem statement. There are two ways to spell TREE, a word worth 16 points.

3)
{"XXXX",
 "XSAX",
 "XDNX",
 "XXXX"}
{"SANDS", "SAND", "SAD", "AND"}
Returns: 59

Each word occurs once, so 25 + 16 + 9 + 9 = 59.

4)
{"XXXX",
 "XXXX",
 "XXXX",
 "XXXX"}
{"X", "XX","XXX","XXXX","XXXXX","XXXXXX","XXXXXXX","XXXXXXXX",
"XXXXXXXXX","XXXXXXXXXX","XXXXXXXXXXX","XXXXXXXXXXXX",
"XXXXXXXXXXXXX","XXXXXXXXXXXXXX","XXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"}
Returns: 9734704571760
8)
{"TREX",
 "XXXX",
 "XXXX",
 "XXXX"}
{"TREE"}
Returns: 0

With only a single E on the board, we can't make the word TREE.

Submissions are judged against all 81 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BoggleScore with a public method long long bestScore(vector<string> grid, vector<string> words) · 81 test cases · 2 s / 256 MB per case

Submitting as anonymous