EECS 311: DATA STRUCTURES |
Home Course Info Links Grades |
Lectures Newsgroup Homework Exams |
The goals of this assignment are:
matrix
built on top of vectorsThere are three parts to this assignment:
Pair-programming is allowed but only if it is true pair programming, i.e., coding done by both partners together, on one computer, switching every 20 minutes or so. The analyses should be done individually.
A Boggle™ grid is just a square grid of letters. Real games use a 5 x 5 grid, but 3 x 3 and up are possible. The goal of the game is to find as many words as possible in the grid. Words must be formed from letters in adjacent positions. Because diagonals are allowed, quite a few words can be formed, even in a 3 x 3 grid. Here's an example, using the words in crosswd.txt:
Grid | Words in grid |
---|---|
mmg eus kde |
des, due, dues, dug, dugs, duke, ems, emu, emus, gude, gudes, gum, gummed, gums, kue kues, mem, mems, mud, muds, mug, mugs, mum, mums, mus, muse, mused, sedum, smug, sue sued, suede, sum, summed, uke, use, used |
If interested, the complete rules are here. There's a page that generates 4x4 Boggle™ grids if you want to try your hand at them.
You can use any algorithm you want to find words, efficient or not, but you have to be able to analyze the time and space requirements of whatever algorithm you choose. Here are two possible simple but dumb algorithms:
Notice that the same word may appear in multiple positions, but duplicates don't count.
Make no assumptions about the size of the dictionary, the size of the grid, or maximum word length, though note that the rules of Boggle™ place a word length limit for a given grid size.
Do as formal an analysis of the upper and lower complexity bounds of your algorithm as you can, in terms of the size of the puzzle, the size of the word list, the number of solutions present, and so on.
To help me compare analyses, use the following variable names:
Use other variable names as needed. Use "big-Oh" notation, as shown in the book. Include in your analysis the key lines of code that dominate the program run-time.
Create a project directory called boggle
. Put your source
code and the Magic Makefile in that directory.
Use crosswd.txt from the Moby Project as your word list.
Define a class Boggle with the following member functions:
Example usage:
Test(mmgeuskde) { Boggle boggle("crosswd.txt"); CHECK_EQUAL( 14, boggle.solve("mmgeuskde"); } Test(random3x3) { Boggle boggle("crosswd.txt"); std::string grid = boggle.randomGrid(3); CHECK_EQUAL( 9, grid.length() ); std::cout << grid << " has " << boogle.solve(grid) << " words" << std::endl; }
Put tests in your code to theake sure your code gets the answers shown in pa1-test1.txt and pa1-test2.txt. Each file contain a grid, as a single word string, followed by all the words in that grid.
To generate random grids of different sizes, make matrices and fill them with characters randomly selected from this string:
aaaaaabbccdddeeeeeeeeeeeffgghhhhhiiiiiijkllllmmnnnnnnoooooooppqrrrrrssssssttttttttuuuvvwwwxyyyz
This string has the same mix of letters as Boggle™ dice and generates grids with many solutions on average. (Boggle™ treats the letter 'Q' specially but we won't worry about that.)
Your program must run standalone, with no user input of any kind. That includes not stopping at the end with a "hit any key to continue" message. If your program can't be run automatically from a script, it will be returned.
Your program should
Then your program should print the results (as described below) for
Results to calculate and print:For each grid, print
input Ksmall Tsmall Khalf Thalf Kfull Tfull
where input is the input grid, as a single word, Ksmall is the number of words found for the small word list, Tsmall the time it to to find those words, and similarly for the half-size and full-size word lists. Print runtime in seconds to three decimal places. Put the results for each grid on a separate line, e.g.,
uaesotwislfntebg 26 .203 53 .438 151 1.843
Do not include the time to read the dictionary file, generate a random board, or print the results in your runtime.
How does your program behavior actually perform with word lists and grids of different sizes? Compare your theoretical predictions to your empirical results. Ideally they should match, but don't claim a match that isn't there. It's better to recognize mismatch than to fudge or misread the data.
You can organize your code into multiple .cpp and .h
files, if that makes sense, but be sure to define
main()
in a file called main.cpp.
Store the grid using the book's matrix
class,
which is
available online.
Use appropriate data structures to store the dictionary
and results.
Use your Makefile to create a Zip file with your source code.
make handin
Create a text document with your algorithmic analysis and comparison to the empirical results.
Email both as attachments to me with the Subject line EECS 311 PA1.
Be sure yourmain.cpp
file has an opening header comment of the following
form:
// EECS311 PA1 solution: Brute-force approach to solving Boggle // Date: September 30, 2009 // Authors: T.H.E.Hacker // // Except for code provided by the instructor or textbook, this code was written // solely by the authors listed above, and not copied from another student // or external source.