You really really really need to read this if you don't know how the game of Boggle works.
The official game of Boggle uses a board which is a 4-by-4 grid on which you randomly shake and distribute 16 dice. The 6-sided dice have letters rather than dots on the faces, so this creates a 4-by-4 array of letters in which you can find words. The players all start together and write down all of the words they can spell out by tracing paths through neighboring dice faces on the board. (Two dice are neighbors if they are next to each other horizontally, vertically, or diagonally. So there are up to eight neighbors of a die; dice on the edges of the grid have fewer neighbors). A die can only be used once in a word, and a word must be at least 3 letters long. At the end of a three minute session, all players stop recording words. Non-unique words -- that is, words found by more than one player -- are then removed from all players' lists, and the players receive points equal to the number of letters beyond the minimum word length found in their remaining words.
Note: The version of Boggle for this assignment differs from the original in some respects and is explained in the How the Boggle Program Works section. Refer to Boggle for additional Boggle details.
The computer version of the game you are implementing is limited to a human and computer player with the human player always going first. The objective is to enter, one at a time, each word the human player finds on the game board. A valid word must meet the following requirements:
When a valid word is entered by the player, it is highlighted graphically on the display board. The computer player maintains the lexicon and so determines the validity of the words, but we assume it can be trusted to do so fairly.
When the human player decides they are done entering words, clicking the "Computer play!" button initiates the computer's turn. The computer searches through the board looking for all the valid words it can find. The computer typically beats the human player mercilessly, but the player is free to try again by starting a new game.
Note: Non-unique words are not removed from the players' lists (if they were, the human player would never have any words left!). Players' scores are just the number of words in their lists.
The rules of the original Boggle game, the computer version you are implementing, and the differences should be clear at this point. Next, we cover some of the inner workings of the assignment.
You will implement the back-end logic for a graphical version of the popular board game Boggle. Specifically, you will design and implement the data structures and algorithms necessary for a computer player to compete against a human opponent. If you get everything right, the computer player will most certainly "win" every game by a huge margin.
Like past assignments, Boggle affords you the opportunity to implement new data structures, such as k-ary trees, and algorithms for efficient tree-traversal. Again, the freedom is yours when choosing data-structures needed for solving the problems presented.
Since the assignment's focus is on data-structures, the graphical display layer will be provided. The provided code knows how to generate and render a random Boggle board, interact with a human player, and report the game outcome. It will use your code to verify input from the human player, and to obtain the computer player's results.
You must follow these steps to acquire the starter code and prepare for the assignment. Copy the files from /home/linux/ieng6/cs100f/public/handout/PA4_handout.tar (cp /home/linux/ieng6/cs100f/public/handout/PA4_handout.tar . to copy into current directory) and uncompress (tar -xf PA4_handout.tar) in the appropriate location. As a review of linux command line, you can change directories using "cd" and to build the code, you can type "make" in the appropriate directory.
After having followed the instructions acquiring the files, you will see the following files:
| Filename | description |
|---|---|
| README_brd | Describes the brd.txt file and how to create your own board |
| baseboggleplayer.h | The interface for the boggleplayer subclass |
| boggleplayer.h | BogglePlayer class conforming to the BaseBogglePlayer interface. |
| boggleutil.h | Define all your supported class/function here. |
| boggleboard.h/cpp | Provided implementation for Boggle board |
| boggleref | Reference executable file |
| boglex.txt | The lexicon (dictionary) of words |
| bogtest.cpp | Starter test file with basic test cases |
| brd.txt | A sample Boggle game board |
| lex.txt | Lexicon that contains 5,450 words of two or more characters when used with brd.txt |
| main.cpp | Provided implementation file for GUI |
| mainwindow.h/cpp/ui | Provided implementation file for GUI |
In addition to the provided starter files, you will also turn in the following files with your submission. Note: You should not include any other source dependencies for files we handed out to you (other than baseboggleplayer). Your boggleplayer and boggleutil together should be standalone.
| Filename | description |
|---|---|
| boggleplayer.h/boggleplayer.cpp | Your implementation of the baseboggleplayer class (See description below) |
| boggleutil.h/boggleutil.cpp | All supported class/function definitions |
You are given the class BaseBogglePlayer. This class declares several pure virtual member functions to define the interface that all BogglePlayer objects must provide.
These member functions have the following signatures:
Note: You must NOT make any changes to the class BaseBogglePlayer
using std::vector;
using std::set;
using std::string;
class BaseBogglePlayer {
public:
virtual void buildLexicon(const set<string>& word_list) = 0;
virtual void setBoard(unsigned int rows, unsigned int cols, string** diceArray) = 0;
virtual bool getAllValidWords(unsigned int minimum_word_length, set<string>* words) = 0;
virtual bool isInLexicon(const string& word_to_check) = 0;
virtual vector<int> isOnBoard(const string& word_to_check) = 0;
virtual void getCustomBoard(string** &new_board, unsigned int *rows, unsigned int *cols) = 0;
virtual ~BaseBogglePlayer() {}
};
In boggleplayer.h/cpp you will implement the class BogglePlayer.
The class BogglePlayer is a subclass of BaseBogglePlayer
and implements the virtual member functions of BaseBogglePlayer.
In addition, you are free to implement any other functions that you may find useful.
Thus, the use of a virtual base class enables you to define a new class interface, customize it with new member
functions and variables, while sticking to a contract requiring that certain functions be provided with required
signatures. In other words, pure virtual functions are similar to java interfaces.
In addition the BogglePlayer should contain a data member that maintains the Boggle player's lexicon.
buildLexicon: takes as argument a set containing the words specifying the
official lexicon to be used for the game. Each word in the set will be a string consisting of lowercase
letters a-z only. This function must load the words into an efficient data structure (e.g., a multiway trie)
that will be used internally as needed by the BogglePlayer. The multiway trie would be used to maintain the
BogglePlayer's lexicon. For a good-object oriented design this data structure should be implemented in a
different class (possibly in the file boggleutil.h/cpp) and appropriately used by the BogglePlayer class.
setBoard: takes two arguments: the number of rows and columns in the board, and an
array of arrays of strings representing what is shown on the face of dice on a Boggle board. A Boggle board
is a rectangular grid of dice; the height (number of rows) is given by the first argument, the width of this
grid (i.e. number of columns) is given by the second argument. The elements of the vector specify the
contents of the board in row major order. That is, consider the board as a two-dimensional array, with
columns indexed 0 to width, and rows indexed 0 to height. The die at row R and column C has on its face the
string in the position diceArray[R][C]. Each string may be upper or lower case, and may contain one or more
letters. (In official Boggle, these strings would contain one character only, except for the double letter
die face "Qu"; but your BogglePlayer should work correctly for strings of any length as we have modified the
game so that a die can show multi-character strings, e.g. "ion") For purposes of
finding words on the board, they should all be considered lowercase. Therefore, this function should convert
the strings on each die face to lower case. The function will then use the transformed
information to construct a data structure representing the Boggle board in a way that lends itself
well to your search algorithms.
getAllValidWords: takes two arguments: an int specifying a minimum word length, and a
pointer to a set of strings. It returns false if either setBoard() or buildLexicon()
have not yet been called for this BogglePlayer. If they have both been called, it will return true,
after filling the set with all the words that (1) are of at least the given minimum length, (2) are in the
lexicon specified by the most recent call to buildLexicon(), and (3) can be found by following an acyclic
simple path on the board specified by the most recent call to setBoard().
isInLexicon: takes as argument a const string passed by reference, and determines whether
it can be found in the lexicon specified by the most recent call to buildLexicon(). The function returns
true if the word is in the lexicon, and returns false if it is not in the lexicon or if buildLexicon() has
not yet been called.
isOnBoard: takes as argument a string passed by reference. It determines whether the
string can be found by following an acyclic simple path on the board specified by the most recent call to
setBoard(). If it is possible to find the word in the current board, the function returns a vector with
integers specifying the locations of dice that can be used to form the word, in the order that spells the
word. The integers used to specify the locations shall be in row-major-order indices. That is, if a letter
is in row R and column C, the location will be R*Width+C. If it is NOT possible to form the word, or if
setBoard() has not yet been called, the function returns an empty vector.
getCustomBoard: this is a method that will allow you to implement extra functionality, should
you choose to (you may find it very useful for testing). This function will be called by the GUI application
when a choice of "custom", non-randomly selected board layout is requested. This function should populate
the array of arrays referenced by the first argument, and the ints pointed to by the second and third
argument, with a Boggle board specification suitable for passing to setBoard(). Note, the first argument,
which will contain the array of arrays that represents the board, will not be allocated for you; you must
allocate the memory for it yourself.
All supporting classes need to be declared in your boggleutil.h file, and defined in your boggleutil.cpp file.
We provide you with bogest.cpp to perform very basic testing of the code. You will need to perform additional tests to stress the corner cases.
Perform these steps if you want to use the GUI to test your code. This is not necessary if you are simply using the tester file (bogtest.cpp) that we have provided you
Before building your code, you must prep your
environment to use Qt5.5.0.
To do this type the following at the
command prompt on ieng6:
prep cs100f
Note that if you have a OCE account type, you have to enter cs100f at the command prompt before using the prep command.
Warning: These steps edit the Makefile, so if you have made changes to the makefile we have handed out, they will be wiped out.
After you have prepped your environment and created the files boggleplayer.h, boggleplayer.cpp, boggleutil.h, boggleutil.cpp files, run the following commands, which set you up to use the Qt GUI capability.
uic mainwindow.ui -o ui_mainwindow.hpp
qmake -project
QMAKE_CXXFLAGS += -std=c++11
QT += core gui widgets
and also remove the reference to bogtest.cpp from the SOURCES list.
qmake to create a Makefile with appropriate targets.
From this point on, you can just run make to build or re-build the GUI application as an executable
named Handout.
Note however that your BogglePlayer class must have all the required functionality without the GUI code present. Also keep in mind that the GUI application by default only deals with square Boggle boards, and official Boggle dice, while your BogglePlayer needs to be able to handle any dimension board, and any strings on the die faces.
The executable boggleref in your handout uses a basically correct, but not very efficient,
solution to the assignment. You can run the executable by typing ./boggleref . This will only
run on ieng6. Additionally, to make it work, you will need to ssh with X forwarding. Additionally, your local
machine you are SSH'ing from must support X. It is recommended you just use the lab machines to SSH into ieng6
to use boggleref.
In a project of this complexity, it is important that you get an early start and work consistently toward your goal. To be sure that you are making progress, it also helps to divide up the work into manageable pieces, each of which has identifiable milestones. Here is a suggested plan of attack that breaks the problem down into phases:
Keep in mind that in order to implement the getAllValidWords() and isOnBoard() functions, there are two types of search necessary. For the former, you are searching for all words on the board, in the lexicon, and of the minimum length. For the latter, you search for a specific word on the board and stop as soon as you find an occurrence of it. It is possible to implement the former in part by using multiple calls to the latter, though it is not the only, or necessarily the best, approach.
We suggest that you tackle the board representation first, and verify the correctness of isOnBoard() using test cases that you can verify by hand. At this point you'll populate the board with symbols of your own choosing. Once this is done, you can then test isOnBoard(); choose board configuration that you can verify by hand. Next, turn the lights on on buildLexicon() and then test getAllValidWords(). At any time you may add the code needed to interface with the GUI so that you verify the above capabilities using a pleasing visual display. However, you should always retain the ability to work without the display, as it can be convenient when testing for bugs.
You should set milestones for when you'll complete each item, so that you can chart your progress and make adjustments as needed. This assignment will take time and you should not wait until the last days to begin!
You are strongly encouraged to test your data structures BEFORE proceeding to solve the final part of the assignment. Individual test cases should be written to ensure each public class method works as intended. Be especially mindful of edge/corner cases. Students tend to lose the most points in these areas.
If you are working with a partner, one suggestion is one person works on the tests and the other works on implementation.
A strategy for this is to first define the class, stubbing out all the methods. Stubbing the methods means do
not implement them yet. If a method returns void, then create the method with an empty body. If a
method needs to return an int, pointer, or something else, place only the appropriate
return statement in the method body. For example, return -1, return nullptr, or
whatever is appropriate. This allows your code to be compiled.
Having done this, the person working on tests can at least call your methods and compile the tests against them. At this point, all tests should fail since nothing is implemented yet. As you complete various methods in the class, the tester can then test these modules one at at time. As more functionality is introduced, test everything again.
This should also help you understand how each method needs to work.
Do not rely on the GUI application to do your testing. If you do, you will most likely miss many cases and this will negatively affect your grade.
When you have completed the assignment, you must submit it. One thing you must add to identify yourself and who you worked with, you must have a file called student_numbers.txt that contains student numbers one per line with UNIX style endings. Now you will do this in two steps. We have created a turnin prep script that checks to make sure your code builds with our makefiles and passes some sanity checks.
Some points to keep in mind:
Final submission: Dec 3 @ 8:00 PM
Required solution files:boggleplayer.h, boggleplayer.cpp, boggleutil.h, boggleutil.cpp
For the final submission you will need to implement all the functionality explained under the section "What you need to implement" (above)
There are 20 possible points on the assignment.
If your solution files do not compile and link error-free, you will receive 0 points for this assignment.
We will grade your program (on ieng6) using our own Makefile. We have provided you with a separate Makefile for
the checkpoint (Makefile.checkpoint). Makefile applies to the final version of the assignment. Our Makefile will
compile your code using the GNU C++ compiler with the following flags: -std=c++11 -O2 -c and then
linking the separate object files with a test driver.
The test driver expects your BogglePlayer class to satisfy the interface specifications outlined in
this writeup, using the cs100f environment on ieng6. We will test your code for conformance to the
specification given above.
If you develop your code on another machine you are responsible for properly testing on ieng6. Otherwise, you may lose significant credit, possibly all 20 points, depending on the circumstances.
IsInLexicon()isOnBoard()getAllValidWords()getAllValidWords() that meets our speed criterion
You've been provided with a 50,000 word lexicon, and board configuration specified in
brd.txt (the format is explained in README_brd). There are 5,450 words of length two
or more with this lexicon-board pair.
To get the extra credit speed points for getAllValidWords() will be
awarded based on the margin by which your implementation can beat the reference solution (more than twice as
fast = 3 points; only a little faster but not twice as fast = 2 points; about as fast = 1 point; slower than the
reference solution = 0 points).