Boggle!

In this project your goal is to make an unbeatable Boggle player by storing every word in the English language in your fastest Data Structures.

Due: NLT 2359 on Monday, 7 Dec 2020

Background

Before we move on to the actual programming...

Rules

Let's review how to play Boggle.

Boggle consists of 25 dice, each of which have different letters on the six faces (one face of one die has a "Qu").
The dice are rolled, and placed at random in a 5x5 grid, so that they look something like this:

Players then have 1 minute to find as many words in the letters as they can, moving horizontally, vertically, or diagonally one space. For example, the above board has the word "TIN," starting in the upper right, moving to the left one spot, then moving diagonally, down and to the right. Dice may not be reused in a given word. For example, the above does not have the word "TINT," because we may not reuse the "T" in the upper right in a given word. Additionally, proper nouns are not allowed.

Scoring depends upon the number of letters in the word. Words with 3-4 letters get 1 point, words with 5 letters get 2, 6 letters gets 3, 7 letters gets 5, and 8+ letters gets 11.

Boggle Dice

The below table lists all the letters on the sides of the 25 Boggle Dice.

AAAFRSAAEEEEAAFIRSADENNNAEEEEM
AEEGMUAEGMNNAFIRSYBJKQXZCCENST
CEIILTCEILPTCEIPSTDDHNOTDHHLOR
DHLNORDHLNOREIIITTEMOTTTENSSSU
FIPRSYGORRVWIPRRRYNOOTUWOOOTTU

Tasks

Part1 (50 points): Build an Object Oriented Representation of Boggle

To get you started, your solution consists of two primary classes with the following interfaces.

BoggleDie
class BoggleDie{
public:
  BoggleDie(string f); //accepts a 6-character string like "CEILPT" where each character is one face of a die
  void roll(); //randomly selects one face of the die to be 'up'
  char get() const; //returns the face of the die that is 'up'

friend ostream& operator<<(ostream& out, const BoggleDie& d); //sends the 'up' face of a die to the ostream
private:
//that's up to you
};
Boggle
class Boggle{
public:
  Boggle();  //constructs a standard game of Boggle
  Boggle(string);  //constructs a custom game of Boggle; used for testing; accepts a 25-character string of all of the 'up' faces, in order
  void roll();  //rolls all of the dice and randomly places their position

friend ostream& operator<<(ostream& out, const Boggle& bb); //sends a text representation of the boggle to the ostream
private:
//that's up to you
//but it must have 25 BoggleDie (maybe a container of them?)
//to be a true Object Oriented representation of Boggle
};
Outputing your Boggle to the terminal

Overloading operator<< should produce output that looks like one of the following:

Hint: There's one special BoggleDie.

Don't forget there is one BoggleDie that will be constructed with the 6-character string "BJKQXZ", but there is actually a "Qu" on the face of that BoggleDie which should be printed to the terminal.

Part2 (10 points): Admin
Makefile

Write you own Makefile to go with your code. At a minimum, it should work so that typing make in the terminal automatically compiles your project, and typing make run in the terminal automatically runs your program. You may create additional make commands as you deem useful. Take two screenshots demonstrating use of your Makefile, one for compiling and one for running. Name the files compile.png & execute.png.

Note: If you complete Part3 below, then your screenshots should be of compiling and running your final solution.

README

You must write and inclued a README file that provides:

  1. Instructions on compiling.
  2. Usage instructions (aka how to run your program).
  3. A description of what your program does when it is run, and instructions on how to use your program once it is running (if applicable).

Part3 (40 points): Develop a new Object to solve all Boggles

To get you started, this new class must have the following interface.

BoggleSolver
class BoggleSolver{
public:
  BoggleSolver(string); //creates our BoggleSolver using the filename of our dictionary text file
  set<string> solve(Boggle); //finds all valid words in the given Boggle acording to the dictionary with which it was created

private:
//that's up to you
//but there are hints below
};
Example Usage
int main(){
  Boggle boggle;
  BoggleSolver genius("american-english");
  set<string> answers = genius.solve(boggle);
}
int main(){
  Boggle boggle("HTONELQLHDEEAAPEATNYEIVHA");
  BoggleSolver genius("american-english");
  set<string> answers = genius.solve(boggle);
}
Pseudocode

An algorithm for a program to find all the words in a boggle might have the following steps:
Note: Steps 1 and 2 are interchangeable.

  1. Read through a file containing all words in the English language, and load them into a data structure for the dictionary.
  2. Create a Boggle by rolling each of the 25 Boggle Dice and placing them in a random location on the 5x5 grid.
  3. Start at the upper left corner of the grid.
  4. Follow the Boggle rules to assemble every possible combination of letters that might be a word.
  5. For each of these letter combinations, check to see if is in the dictionary.
  6. If it is, load that word into a second data structure which will hold all English words that appear in that round of Boggle.
  7. Shift over one position in the grid, and repeat steps 4-6 above.
  8. When you have completed the steps above using every position in the grid as the starting location, return the list of all words that appear in the Boggle board (no duplicates allowed).

Hint: BoggleSolver's internal workings

Hopefully you've realized that the trick to this problem is how to accomplish steps 4-6 in the pseudocode above. To help you with this, below is a prototype for a private recursive function you might have in the BoggleSolver class to accomplishes these steps. What would our base case be? Since the likelihood of finding a word with a length greater than 10 in Boggle is extremely low, you can use this as one base case. Are there others? We will talk more about this function in class. 

set<string> findWords(string soFar, int row, int col, const vector<vector<char>>& letters, vector<vector<bool>>& used);

Note: You may want/need to make your BoggleSolver a friend of your Boggle class.

Hint: Dictionary Data Structure

However, you may not have realized that another important part to getting your solution to run efficiently (quickly) is highly dependent on your choice of data structure for your dictionary. First, you're going to have to build the dictionary, which is going to take time. A poorly chosen/designed data structure would take a lot of time to accomplish this. Second, you're also going to be accessing it often to determine if your string is in the dictionary, so again, a poor choice will cause your program to run extremely slow. You're welcome to use any STL container you choose, or develop your own data structure specifically for this purpose. More on our dictionary below.
I wonder if there exists a data structure that would support our dictionary AND the internal workings of the BoggleSolver?

The Dictionary

We'll use this file as our official dictionary of valid words: american-english
There are 64,117 words in this text file that use the standard 26 letters of the english alphabet (no accented letters). The list is almost, but not entirely, in alphabetical order.

Below is sample code for reading a file as input. You will need to include the fstream library.

int main(){
  ifstream infile;
  infile.open("inputFile.txt");

  string str;
  while(!infile.eof()){ //continues to the end of the file
    infile >> str;  //just use it like you would cin
    //do something with your string...
  }
}
Comparing Efficiency

As we work on finding an efficient solution, we want to measure the speed of our program for comparison against other implementations. Below is an example. You'll need to include the ctime library.

int main(){
  auto time = clock();
  Boggle boggle;
  BoggleSolver genius("american-english");
  set<string> answers = genius.solve(boggle);
  time = clock() - time;
  cout << "Elapsed Time: " << (long double)time/CLOCKS_PER_SEC << " seconds " << endl;
}
Outputing Results

What's the point of solving the Boggle if you don't output the answers and the score that your BoggleSolver achieved? So, in addition to the Elapsed Time above, your program should output results that look like the following (assuming that you implemented the advanced version of operator<<):

Here's a sample main that would produce the above at runtime:

#include "BoggleDie.h"
#include "Boggle.h"
#include "BoggleSolver.h"

#include <vector>
#include <iostream>
#include <ctime>
using namespace std;

int main(){
  srand (time(NULL));

  clock_t time = clock();
  Boggle boggle("AAIAEENABENNETNTLTHLYWPTU");  //specific boggle for testing
  BoggleSolver genius("american-english");
  set<string> answers = genius.solve(boggle);
  time = clock() - time;

  cout << boggle << endl;

  unsigned int score = 0;
  cout << "Found the following " << answers.size() << " words:" << endl;
  unsigned int count = 0;
  for (string s : answers){
    unsigned int wordLen = s.length();
    if(wordLen >= 8) score += 11;
    else if (wordLen == 7) score += 5;
    else if (wordLen == 6) score += 3;
    else if (wordLen == 5) score += 2;
    else if (wordLen >= 3) score += 1;
    else ;
    cout << s << " ";
    if (++count % 10 == 0) cout << endl;
  }
  cout << endl;
  cout << "Elapsed Time: " << (long double)time/CLOCKS_PER_SEC << " seconds" << endl;
  cout << "Score: " << score << endl;

  return 0;
}

Hint Again: There's one special BoggleDie.

Don't forget there is one BoggleDie that will be constructed with the 6-character string "BJKQXZ", but there is actually a "Qu" on the face of that BoggleDie, so you'll have to make sure that the "u" is included in the strings you're building.

Text Graphics

C++ StringBox Symbol C++ StringBox Symbol
"\u256d"╭ "\u252c"┬
"\u2500"─ "\u251c"├
"\u256e"╮ "\u253c"┼
"\u2502"│ "\u2524"┤
"\u2570"╰ "\u2534"┴
"\u256f"╯

For more box drawing options see: https://www.fileformat.info/info/unicode/block/box_drawing/list.htm

Grading

Standard deductions will apply as they always have. You will be evaluated on the accuracy/performance of your solution, and up to 10% of your grade is dependent on compliance with the course coding standards.

Your code must compile. You will receive a zero if it does not.

Partial credit for incomplete parts will be applied under the following guidelines:

Extra Credit!

operator<< (+2 points)

Implement the advanced output version of operator<<

Custom Data Structure (+10 points)

Implement your own custom data structure to improve the performance of your BoggleSolver. You must demonstrate a working solution to the instructor before attempting this Extra Credit. This will require research on your own, and you must discuss your chosen data structure with your instructor before attempting it. Be sure to document all resources used. You must implement the data structure yourself, you cannot simply use one that someone else has already developed.

It's a Game! (up to +10 points)

Take the creative license and turn your program into an interactive game. Points will be awarded based on creativity, difficulty, and positive experiences when playing your game.

Submission

Submit all .cpp and .h files containing the source code for your solution, your Makefile, your README, and the screen captures showing your code compiling and running (compile.png & execute.png) via the the submisison website: submit.cs.usna.edu.

In a terminal window from your project03 folder, use the following command to submit your solution: 

~/bin/submit -c=SI221 -p=Project03 *.cpp *.h README* Makefile compile.png execute.png

Do not submit any .o or executable files!

Paper Submission

Complete and submit a signed copy of this cover sheet / survey after submitting your project electronically. You may bring it to the Final Exam period. If you are not complete with your solution by the Final Exam, then turn it in to my office the by the end of the next work day after submitting your solution.