P R E L I M I N A R Y   S P E C I F I C A T I O N

                                               Due 2:00 am, Friday, 06 May 2016

CPSC 223b  Homework #7  If At First You Don't Succeed, ... (It Boggles my Mind)

REMINDER:  Do not under any circumstances copy another student's code or give
a copy of your code to another student.  After discussing the assignment with
another student, you may not take any written or electronic record away.
Moreover, you must engage in a full hour of mind-numbing activity before you
work on it again.  Such discussions must be noted in your log file.

(40) Write a program

      Boggle [-c] [-t] nRows nCols board

that can be used to list every word in the standard input that is a "Boggle
word" for the NROWS x NCOLS array BOARD.

The standard input contains one word per line, each containing only alphabetic
characters.  These words serve as the "Boggle dictionary".

The characters in the array are stored in the command-line argument BOARD by
rows.  For example,

      % Boggle 3 4 ABCDEFGHIJKL

specifies the board

      A B C D
      E F G H
      I J K L

since NROWS = 3 and NCOLS = 4.

A word is a Boggle word if its letters can be spelled out by starting at one
square on the board and passing through a sequence of squares that is connected
horizontally, vertically, or diagonally.  That is, you cannot skip intervening
squares or remain on the same square to get the next letter.  For example, the
board

      E P I
      P R O
      U S T

contains the words PEPPER, SUPERIOR, and REPERTOIRE among others, but not
PEEPER or PROUST.  When comparing letters, case is ignored and a _ on the board
matches any letter (a la the blank tile in Scrabble).  For example, the board

      E P I
      _ R O
      U S T

also contains the words PEEPER and PROUST, but not JOUST.

The Boggle words found are printed out in alphabetical order, in lower case,
along with the number of times that they appear, using the format "%s: %d\n".
For example, for the EPIPROUST board and the list of words above:

      pepper: 4
      repertoire: 2
      superior: 1
      
And for the EPI_ROUST board,

      peeper: 11
      pepper: 12
      proust: 4
      repertoire: 16
      superior: 4

With the -c flag all non-Boggle words in the dictionary are printed using the
format "%s\n".

Note:  The real Boggle also requires that letters/wildcards on the board cannot
be used more than once to form a word.  This behavior is invoked by the -t
flag.

Use the submit command to turn in the source files for Boggle, a Makefile, and
your log file (see Homework #1).

YOU MUST SUBMIT YOUR FILES (INCLUDING THE LOG FILE) AT THE END OF ANY SESSION
WHERE YOU SPEND AT LEAST ONE-HALF HOUR WRITING OR DEBUGGING CODE, AND AT LEAST
ONCE EVERY HOUR DURING LONGER SESSIONS.  (All submissions are retained.)

Notes
~~~~~
1. Boggle should detect invalid command-line arguments (e.g., nonpositive
   numbers of rows or columns or a mismatch between the size of board and the
   size of the array), printing a one-line error message to stderr and exiting.
   However, you may use atoi() to extract a number from an argument without
   checking that the argument contains only digits or that the number fits into
   an int.

2. Your implementation of Boggle should use tries to represent the dictionary.
   However, you need not create a Trie ADT.  Hint:  You can also store in the
   trie a count of the number of ways to form a Boggle word.

3. To make Boggle slightly more robust (and able to use dictionaries such as
   /c/cs223/Doc/words that contain ', -, &, etc.), lines in the standard input
   that contain nonalphabetic characters are ignored and do not provoke error
   messages.

4. To conserve space, Boggle should

   * Store in the trie only those pointers that are non-NULL (worth at most
     5 points).  While binary search of the letters corresponding to non-NULL
     pointers would be more efficient, you may use linear search instead.

   * Free all storage before exiting (worth 0 points itself but assumed when
     testing the previous property).

5. The cubes in the 4x4 Boggle game contain the following combinations of
   letters (each group of 6 represents the 6 faces of one cube):

     LRYTTE   ANAEEG   AFPKFS   YLDEVR   EGHWNE   OATTOW   HCPOAS   NMIQHU
     VTHRWE   IDSYTT   XLDERI   ZNRNHL   SEOTIS   MTOICU   ENSIEU   OBBAOJ

   There is also a 5x5 version.

                                                                CS-223-04/20/16