Assignment 1

Goal

The goals of this assignment are:

• Set up your C++ programming environment, with UnitTest++ and make
• Practice with the standard C++ libraries, especially vector, iterator, iostream and algorithm.
• Do some basic algorithm design and analysis in the context of a computationally expensive problem.

There are two parts to this assignment:

• Write and test a program to solve Boggle™ problems
• Analyze the complexity of your algorithm and compare against empirical results.

Boggle™ Problems

A Boggle™ grid is just a square grid of letters. Real games use a 4 x 4 or 5 x 5 grid, but 2 x 2 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, and must be 3 letters or longer. Because diagonals are allowed, quite a few words can be formed, even in a 3 x 3 grid. Here's an example of a grid, and all the words it contains from the list crosswd.txt:

mmg
eus
kde

If interested, the complete rules are here. There's a page that generates 4 x 4 Boggle™ grids if you want to try your hand at them.

Tasks

Don't jump ahead. Be sure you have working tested approved code for one task before submitting the code for the next subtask.

PA1 Task 0: set up your C++ environment

Before you start, you need to set up your C++ programming environment.

After the above have been installed, test your setup with these instructions.

There's nothing to submit. If you run into trouble, post to the newsgroup.

PA1 Task 1: load word list

Your first subtask is to read in a list of all legal words from a plain text file. The file we'll use is crosswd.txt from the Moby Project.

Note: use lowercase for all words and puzzle grids.

Define a class Boggle with the following constructor and member function:

• Boggle::Boggle( std::string fileName ) -- given a file name, construct a Boggle solver with the words contained in the file specified
• std::size_t Boggle::size() const -- return the numbers of words in the internal word list

If you don't know what any of the C++ items above are, search for them at the CPlusPlus site, check the textbook, and check whatever C++ references you have. If that fails, post to the newsgroup.

The internal word list should be a C++ vector of C++ strings, not a C array of C strings. The vector can be loaded with just a few lines, using C++ library functions for copying a range (even from a file!) into a container. See the standard library notes on containers, algorithms and iterators, particularly istream_iterators.

Test your code using a UnitTest++ test file, with at least the following tests in it:

// global to avoid reloading on every test
static Boggle boggle("crosswd.txt");

TEST(boggleSize)
{
  CHECK_EQUAL( 113809, boggle.size() );
}

Don't forget to put the crosswd.txt in your code directory for this project.

See the general homework instructions for additional requirements on files

Submit to Code Critic: your complete header and implementation code for the Boggle class. Be sure to include comments to mark the header code versus the implementation code. Don't send the test code unless you have a particular reason to want it critiqued.

PA1 Task 2: test for word in grid

Your second subtask is to define a function that returns true if a word is in a grid.

Although conceptually a grid is a N x N square of letters, for testing purposes, it's simplest to just use a string that has the rows concatenated together. E.g., a 2 x 2 grid with "pe" in the first row and "sa" in the second would be "pesa". The 3 x 3 grid example above would be "mmgeuskde".

Add the following public member function to your Boggle class:

• bool Boggle::contains( std::string grid, std::string word ) const -- given a grid and a word, return true if the word appears at least once in the grid

Add at least the following tests to your test code file:

TEST(contains)
{
  CHECK( boggle.contains( "pesa", "ape" ) );
  CHECK( boggle.contains( "mmgeuskde", "gummed") );
  CHECK( !boggle.contains( "pesa", "pep" ) );
  CHECK( !boggle.contains( "mmgeuskde", "musk") );
}

Submit to Code Critic: whatever header or implementation code you added or changed. Don't send the entire files or the test code. Be sure to mark the header code versus the implementation code.

PA1 Task 3: solve grid

Define a function that finds all the words in a grid.

Add the following public member function to your Boggle class:

• void Boggle::solve( std::string grid, std::vector<std::string> & results ) const -- given a grid and a reference to a vector of strings, store in the vector every word from the internal word list that appears in the grid

Add at least the following tests to your test code:

TEST(pesa)
{
  const char *strs[] = {
    "ape", "apes", "apse", "asp", "pas", "pase", "pea",
    "peas", "pes", "sae", "sap", "sea", "spa", "spae"
    };
  std::vector<std::string> expected(strs, strs + 14);
  std::vector<std::string> results;
  boggle.solve( "pesa", results );

  CHECK_EQUAL( 14, results.size() );
  CHECK( expected == results );
}

TEST(mmgeuskde)
{
  const char *strs[] = {
    "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"
    };
  std::vector<std::string> expected(strs, strs + 37);
  std::vector<std::string> results;
  boggle.solve( "mmgeuskde", results );

  CHECK_EQUAL( 37, results.size() );
  CHECK( expected == results );
}

This code demonstrates two useful features of C++ containers that reduce the number of explicit loops we need to write:

• They can be initialized from another container, including arrays.
• They can be compared using the operator ==.

Unfortunately, we can't write CHECK_EQUAL( expected, actual ), because containers don't implement the output operator <<. CHECK_EQUAL() requires that in order to print test failure messages.

Submit to Code Critic: whatever header or implementation code you added or changed. Don't send the entire files or the test code. Be sure to mark the header code versus the implementation code.

PA1 Task 4: get timings

To get timing data, you need to try your solver on a number of different grids of different sizes. Therefore, you need a function to generate random grids.

Add the following public member function to your Boggle class:

• std::string Boggle::randomGrid( int n ) const -- given a number N, returns the string for a random N x N grid of letters

Generate strings by picking letters randomly from:

aaaaaabbccdddeeeeeeeeeeeffgghhhhhiiiiiijkllllmmnnnnnnoooooooppqrrrrrssssssttttttttuuuvvwwwxyyyz

This string has the same mix of letters as Boggle™ dice, except for the special case of "Qu" in real Boggle™. Using this string generates grids with more solutions than a purely random string.

Add the following to your test code:

TEST(timing)
{
  const int repeat = 3;
  const int maxSize = 5;
  for (int n = 3; n <= maxSize; ++n) {
    for (int i = 0; i < repeat; ++i) {
      std::vector<std::string> results;
      std::string grid = boggle.randomGrid( n );
      std::clock_t start = std::clock();
      boggle.solve( grid, results );
      std::clock_t end = std::clock();

      std::cout << "Grid " << grid << " " << results.size() << " solutions "
        << (end - start) << " ticks" << std::endl;
    }
  }
}

This isn't really a test, since it doesn't assert anything. It just prints the timing results for different grids of different sizes. Increase the limits after you've debugged your code. You should go to at least 5 repeats for sizes up to at least 6 x 6. You may need more to support your algorithm analysis.

Submit to Code Critic: whatever header or implementation code you added or changed to implement the random grids. Don't send the entire files or the test code. Be sure to mark the header code versus the implementation code.

PA1 Task 5: Analyze your algorithm

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:

• N -- the size of the word list
• M -- the size of the grid, e.g., 3 for a 3 x 3 grid
• K -- the number of answers found for a grid
• L -- the average answer length for a grid
• T -- the time to solve a grid

Use other variable names as needed. Use "big-Oh" notation, as shown in the book, to specify which parts grow linearly, quadratically, logarithmically, etc. Identify which parts of the algorithm dominate the run-time and therefore merit improvement.

Discuss how your theoretical predictions do and do not match your empirical results. Don't claim a match that isn't there. It's better to recognize mismatch than to fudge or misread the data.

See these notes for what I'm looking for in this analysis, and these notes on space complexity for that under-discussed topic.

Wrap Up

When all of the above has been completed, and approved as necessary via the Code Critic, check over your code and send it in.

Make sure your program runs standalone, with no user input of any kind. That includes not stopping at the end with a "hit any key to continue" message. If I can't run your program automatically from a script, it will be returned.

Be sure your test code file has an opening header comment that identifies the authorship of the code, as follows:

// 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.

Run make handin to generate a Zip archive of all your source code. By design, the Magic Makefile does not include the word list file. Do not include the word list file.

Email your analysis document and the Zip archive produced by the Magic Makefile to me. Use the Subject EECS 311 PA 1 Boggle.