ECOO '12 R1 P4 - Boggled

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

In the game of Boggled, players are given a 4 \times 4 array of letters and about 2 minutes to list as many words as they can find in the array of letters. A word only counts if it is 3 or more letters long and you can trace at least one path through the letters to spell the word without using any letters twice.

Boggled

In the example on the left (depicting the offline version of the game), the two styles of arrows trace the words SALT and MACE.

For the purposes of scoring, 3- and 4-letter words are worth 1 point, 5-letter words are worth 2 points, 6-letter words are worth 3 points, 7-letter words are worth 4 points, and anything longer is worth 11 points. Paths can travel in any direction, including diagonally. There is no penalty for listing words that are too short or not present on the board and there is no penalty for listing the same word twice, but none of these are worth any points. (Of course in the real game, words would also have to be found in some standard dictionary, but we're not going to worry about that here.)

The input will contain 5 test cases. The first 4 lines of each test case will be a Boggled board, followed by an integer n on a line by itself, and then a list of n words that represent a single player's turn. Your program must output that player's score along with the number of legal and illegal words in the list. Illegal words are either not found on the board, too short, or repetitions of words higher up in the list. If a word is illegal for more than one reason, it is recorded once in the most important category of illegal words, with too short being most important, followed by repetition, and then not found. The format of the output must be exactly as shown below.

Sample Input

HIWH
PXBY
ASQK
PVES
15
SAX
SAP
WHIP
WHY
PAP
PAX
VASE
VASES
BY
HIP
HIPS
SAVE
SAVES
PAVE
PAVES
LSUN
DAGE
EBUI
WERJ
37
SUN
SUNG
LANGUAGE
SAGE
BAG
SAG
BEE
WED
WEDS
BED
BEDS
BALD
BALDS
BUG
BUGS
LAGS
LAG
SAD
BEAD
BEADS
EAD
EADS
LAD
LADS
GUN
GAS
BAG
BAGS
BAD
BADE
JIG
JIGS
JIGSAW
RIG
RIGS
RUG
RUGS

Sample Output

Your score: 16 (13 good, 1 not found, 1 too short, 0 repeated)
Your score: 36 (34 good, 2 not found, 0 too short, 1 repeated)

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org


Comments

There are no comments at the moment.