- Getting the Skeleton Files
Getting the Skeleton Files
As usual, run
git pull skeleton master to get the skeleton files.
The skeleton includes
Boggle.java, four Boggle board txt files, and two word
dictionary txt files.
Note: This homework is harder than the other makeup homework.
The game of Boggle involves finding valid words on a 4x4 board of letters.
A brief description of the rules: Each player searches for words that can be constructed from the letters of sequentially adjacent cubes, where “adjacent” cubes are those horizontally, vertically, and diagonally neighboring. Words must be at least three letters long, may include singular and plural (or other derived forms) separately, but may not use the same letter cube more than once per word.
In homework, you will implement a generalized Boggle solver with a few modifications:
- You will not have to account for the “qu” tile
- You must support rectangular boards of arbitrary dimensions
The design choice of data structures and algorithms is up to you. However, we will impose a runtime requirements, which are discussed in a following section.
Boggle reads an
M newline separated letter grid from a .txt file.
You should use Princeton Library, In.java,
for reading from files.
A default dictionary of allowed words, the file
words.txt, is provided in the
skeleton. The file path to this dictionary file is stored in the static variable
String dictPath in
Boggle.java. Your program should support other word dictionary
files. This is done by manually changing the value of
This means that you should not hardcode the dictionary path. More concretely, do
solve(int k, String boardFilePath) method in
This method returns the
k longest unique words sorted in descending order of length.
If multiple words have the same length, print them in ascending alphabetical order.
To accomplish this, you will need to create your own efficent Trie data structure.
You can write this new class in a new file, (e.g.
Trie.java), or in
At this point of the semester, you should have an idea of what elegant code should
look like. Use your best stylistic judgements when writing your code.
For Boggle board file
exampleBoard.txt, default dictionary
k = 7:
ness tack bmuh esft
[thumbtacks, thumbtack, setbacks, setback, ascent, humane, smacks]
For Boggle board file
exampleBoard2.txt, dictionary file
k = 20:
baa aba aab baa
Timing and Runtime
You will be graded on runtime. You should be able to handle large dictionaries
and boards efficiently. For a dictionary of fixed size, and a random board, you
should have runtime expected linear in the size of the board - that is, for an
N x M board and getting the top
k words, your runtime should be expected
k). Don’t think too hard about this expected runtime though - the analysis for
this is a little complex and we can certainly bound it tighter. If you have an
efficient solution that behaves and grows linearly with the size of the board,
you should pass the autograder.
For example, on my computer, one solve on testsmallboard (100x100) takes 209ms and one solve on testlargeboard (500x500, 25x larger) takes 4957ms. Linearly extrapolating from the testsmallboard runtime, we would expect a runtime of 209*25=5225, which is close to the observed runtime for testlargeboard.
Some tips: you cannot inspect all possible permutations of words (in other words, you cannot submit a brute force solution). Your solution should utilize pruning - if you cannot continue constructing a word from a certain letter onwards, you should not explore that letter’s neighbor nodes. As a warning: if you have a recursive solution, it is possible that it is slower by a nontrivial constant factor than an equivalent iterative solution.
For Boggle, throw an
IllegalArgumentException (with some informative message
of your choice) if:
- The input board is not rectangular.
- The dictionary file does not exist.
Do not call
You should submit the usual way, by pushing to GitHub and then submitting on Gradescope.
This assignment was created by Alan Yao.