Week 10, 4/1 & 4/4

Boggle Part 2

Overview

1. Implement and benchmark lexicons: improve SimpleLexicon, write BinarySearchLexicon, and complete the TrieLexicon & CompressedTrieLexicon classes that implement the ILexicon interface. Each lexicon implementation facilitates looking up a word or a possible prefix of a word.

2. Find words on a board: design and code GoodWordOnBoardFinder that implements the IWordOnBoardFinder interface to find a word on a Boggle board. This class will be used for implementing one of the auto-player classes and in determining where a word appears on a board when you or another (human) player plays the game.

3. Implement two AutoPlayers (computer players) that find all words on a BoggleBoard: write LexiconFirstAutoPlayer and BoardFirstAutoPlayer classes that implement the IAutoPlayer interface. Each class facilitates playing a game of Boggle by finding every possible word on a given Boggle board.

4. Empirical Analyses: Add code to BoggleStats, run experiments, and make conclusions about which of several methods is best, and reason in general about the trade-offs in different implementations.

Finding words on the board

	public List<BoardCell> cellsForWord(BoggleBoard board, String word) {
		ArrayList<BoardCell> list = new ArrayList<BoardCell>(); 
		for (int r = 0; r < board.size(); r++) 
			for (int c = 0; c < board.size(); c++) 
				if (findHelper(word, 0, r, c, board,list))  
					return list; 
		list.clear(); 
		return list; 
	} 

	  /**
	    * Returns true if and only if the substring of word starting at
	    * index can be formed starting at (row,col) on the board provided
	    * without using any cells stored in list --- and extending list
	    * to include all cells on which substring is found when true is
	    * returned.
	    * @param word is searched for word (e.g., entered by user)
	    * @param index is where in word substring starts, e.g., all chars
	    * before index have been found and cells are in list
	    * @param row is starting point for search
	    * @param col is starting point for search
	    * @param board is board on which word is searched
	    * @param list is cells on board where word is found
	    * @return true if substring found on board without re-using board-cells
	    */
	  private boolean findHelper(String word, int index, int row, int col, 
	                             BoggleBoard board, List<BoardCell> list) {

		  return false;
	  }

}

1. If there's no substring, e.g., index is past the end of the string, what value should the method return and why? Write the code for this check.

2. If either row or col is outside the board what value should be returned and why? Write the code for this check.

3. The call board.getFace(row,col) returns the string on the corresponding board-cube. Use this call to determine if the first letter of the substring starting at index matches the board cell. Write code.

4. If the boardcell matches the first character, you'll need to check whether the boardcell has been used, i.e., appears in list. Write code using list.contains to check. You'll have to create a BoardCell object from (row,col).

5. How many recursive calls are made to check whether the substring can be formed? What's the value of index for each recursive call, based on the value of index passed in? How is the value of parameter list in the recursive calls different from the value passed into the function making the recursive calls?

6. If the recursive calls all fail the method must return false, but what code will you write to ensure that the value of list is the same as it was when the method was first called.

Creating AutoPlayers

1. A LexiconFirstAutoPlayer finds all the words on a board by simply iterating over every value in a lexicon checking to see if the word is on the board by calling the cellsForWord method discussed above. A ILexicon is Iterable, so you can iterate over words in your lexicon with a for-each loop as in

       public void findAllValidWords(BoggleBoard board, ILexicon lex, int minLength) {  	
           clear();
           for (String word: lex) {
               ...
           }
   

   1. An IWordOnBoardFinder is stored as an instance variable for the LexiconFirstAutoPlayer. How should you call the cellsForWord method to determine whether a particular word is on the BoggleBoard?

   2. If word is on the BoggleBoard, then it should be added to the collection of found words by calling the inherited add(..) method. Where is the add method defined and why?

2. A BoardFirstAutoPlayer finds all the words on a board by exhaustively examining all paths on the board.
   1. There about 12 million distinct paths through a 4x4 Boggle board. How can we significantly restrict the number of paths we examine?

   2. You should write a recursive helper method, find to find all the words starting at a specified [row,column]. The basic idea is to pass to this helper method at least the following:
      • the current row & column.
      • the string built and the cells visited from the search so far

          /**
           * Adds all words that are in our lexicon starting from (row,col) 
           * to our list of found words. You cannot repeat cells in creating a word
           * @param row is starting point for search 
           * @param col is starting point for search
           * @param prefix are characters that we have found up to this point
           * @param visited are BoardCells associated with prefix
           */
          private void find(int row, int col, StringBuilder prefix, List<BoardCell> visited) {
          	
      

      The code you write will be very similar to the code you wrote in findHelper above. How will the code be different? What are the different base cases? Why is the return value different?

   3. The method header above does not include a BoggleBoard or ILexicon. Will this method need access to those data structures? If so, how can find access them without adding more parameters?