Prog 3: BestBoggle

CS 141, Fall 2012, Prof. Reed

Due 10/19 before class at 12:00 noon

Description

Write a program in C / C++ to create a 4x4 Boggle board.  Running your program will look something like the made-up output shown below: 

Author: Dale Reed Program 3: Best Boggle TA: Felix Baumgartner, Wed 7am Oct 9, 2012

O A A N E T R I I H K R I F L V   3 letter words: 29 (29 points)  4 letter words: 15 (30 points)  5 letter words:  5 (20 points)  6 letter words:  1 (7 points)  Score: 86    Words stored in results.txt

Your program should continue to run, printing out only the boards and scores for any board found that is better than what is found so far.The results.txt file should contain all the words from the best board found so far.

You need to know the following concepts in order to write this program:

Reading words from a dictionary file into an array; Writing from an array of words into a file; Manipulating C-style strings (arrays of char); functions.

Notes:

• 1. Note that there is no user input, only output.  Scoring is based on word length and not just one point per letter as follows: 

1. Use the dictionary file included as an attachment at the bottom of this page.  It has 263,533 words in it.

2. You must write this program using only the concepts we have covered so far in this class (functions, arrays and pointers, C-style strings which are arrays of char, but no structs or recursion.)  We will let your program run for at least 30 seconds, on the Mac computers in the CS lab.  Words must be at least 3 letters in length to count for points.

   1. For the execution points, the last 10 points of credit will be given to students whose best board score is above some threshold.  In addition there will be 10 points of extra credit for the student whose program finds the highest scoring board first, posting it as a confidential message to the professor on Piazza.

   2. I suggest you write the program one stage at a time as follows:

   3. Declare an array to represent the board.  Fill it with random characters.  Then display the board.

   4. Read in the dictionary file into an array of the appropriate size.  Note that you do not need to keep words of length <3 or words of length >16.  Ensure everything is in lower case as you read it in.  See this program for an example of reading words from a file into an array.  Similarly see this program that reads words from a file into a really large array.  If it doesn't work, you will need to dynamically allocate memory instead, as illustrated in this program.

   5. Count the alphabetical character frequency counts of the words in the dictionary.  Change your code that generates a board and have it generate characters using the same frequency counts.

   6. Now choose an approach, which will likely be one of the following:

      1. Starting with the characters on the board, generate strings of adjacent letters and see if they are valid dictionary words

      2. Alternatively start with the words in the dictionary and see if they can be found on the board

   7. Store the words found as you go into a large array of some kind.  Also accumulate the score as you go and the number of each length word.  If this board gives the best score so far then display the board, number of each word and the score, and also write all the words to the output file (called results.txt), which should overwrite whatever was there previously.  See this program for an example of writing words in an array to an output file.

   8. Turnin your program electronically into Blackboard.  Multiple submissions are accepted, but only the most recent one will be graded.