Frequently Asked Questions

If a valid word can be formed in more than one way, how many times should I return it? Only once. For example, you should return the word EQUATION only once in board-q.txt even though there are two ways to form it.

Do In need to return the words in alphabetical order? No, that is not required.

Which data structure(s) should I use to store the dictionary? It is up to you to decide. A trie is a natural starting point.

My program isn't fast enough to get 100%. What can I do to improve performance? See the Possible Optimizations section below for some ideas. It may be a challenge.

Input, Output, and Testing

The zip file boggle.zip contains some sample dictionaries and boards for testing.

Dictionaries. Below are some dictionaries for testing. Each dictionary consists of a sequence of words containing only the uppercase letters A through Z, separated by whitespace, and in alphabetical order.

file words description
dictionary-nursery.txt 1,647 words that appear in several popular nursery rhymes
dictionary-algs4.txt 6,013 words that appear in Algorithms 4/e
dictionary-common.txt 20,068 a list of common English words
dictionary-shakespeare.txt 23,688   words that appear in the complete works of William Shakespeare  
dictionary-enable2k.txt 173,528 Enhanced North American Benchmark Lexicon
dictionary-twl06.txt 178,691 Tournament Word List
dictionary-yawl.txt 264,061 Yet Another Word List
dictionary-sowpods.txt 267,751 the SOWPODS list of words
  dictionary-zingarelli2005.txt     584,983   Italian Scrabble Dictionary

Boards. We provide a number of boards for testing. The boards named boards-points[xxxx].txt are Boggle board that results in a maximum score of xxxx points using the dictionary dictionary-yawl.txt. The other boards are designed to test various corner cases, including dealing with the two-letter sequence Qu and boards of dimensions other than 4-by-4.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

Possible Optimizations

You will likely need to optimize some aspects of your program to pass all of the performance points (which are, intentionally, more challenging on this assignment). Here are a few ideas: