Let's Play More Boggle...

Before you begin...

Make a copy of your boggle.c file as boggle2.c by invoking the command

kureyonShin@sf3:~[120]$ cp boggle.c boggle2.c

Part 2 is to be modified using boggle2.c and submitted at the end of the session.

Overview - How are words formed?

In Part 1, you will have noticed that when a valid word is found on the tray as well as in the dictionary, there is no way of showing the user how the letters on the tray are linked together. As such, part 2 of this lab assignment is to improve the output. For example, given the tray below:

   +---+---+---+---+
   | S | Q | E | T |
   +---+---+---+---+
   | N | E | N | I |
   +---+---+---+---+
   | N | O | A | L |
   +---+---+---+---+
   | I | C | L | Y |
   +---+---+---+---+

The word "inconsequential" can be verified by showing a list of adjacent letters linked together. Denote (x,y) as the letter on row x and column y, and let (1,1) represent the top-left corner. The sequence of positions forming the word "inconsequential" is

<4,1> <3,1> <4,2> <3,2> <2,1> <1,1> <2,2> <1,2> <1,3> <2,3> <1,4> <2,4> <3,3> <3,4>

Getting Started

Your first task is to find the sequence of positions of individual letters forming the word and print out according to the above format. In the case whereby there are multiple sequences for a particular word, you need only consider one of them. The list of positions is to be implemented as a linked list with the following node structure.

   typedef struct PosStruct Pos;
   struct PosStruct {
      int x;
      int y;
      Pos *next;
   };

All you need to do now is to modify the WordInTray function (and any other function(s) it invokes) such that if a word is found, the linked list of positions will be returned by the function; otherwise nothing (i.e. NULL) will be returned. As such the function prototype becomes

   Pos *WordInTray(Cell [][], char *);

With the linked list constructed you can proceed to invoke another function DisplayPos that prints out the sequence of positions according to the above print out. The corresponding function prototype is as follows:

   void DisplayPos(Cell [][], Pos *);

The corresponding PlayBoggle function has to be modified accordingly. This portion of the code has been provided for you as shown below. The modifications are in bold.

void PlayBoggle(Cell tray[][SIZE], WordPtr dict)
{   
   char word[101];
   WordPtr wordList = NULL;
   Pos *pos;
      
   /* Initialize the tray with random letters */
   InitTray(tray);
   /* Display the tray with letters */
   PrintTray(tray);
   
   /* Read in a word */
   printf("\nEnter word (any number to quit): ");
   gets(word);
               
   /*
      Check if a word has its first char as a digit.
      If yes, then terminate the loop
   */
   while (!isdigit(word[0]))
   {
      /* Reset the visited flag of all the cells on the tray */
      ResetFlag(tray);
                  
      /* Condition 1: A word should be 3 letters or more */
      if (strlen(word) > 2)
                  
         /* Condition 2: Check if the word is on the tray */
         if ( (pos = WordInTray(tray,word)) != NULL )
                   
           /* Condition 3: Check if the word is in the dictionary */
            if (WordInDict(dict, word))
            
               /* Condition 4: Check if the word has been previously found */
               if (!WordInList(wordList,word))
               {
                  /* Add the valid word into the list of found words */
                  AddWord(&wordList,word);
                  
                  /* Print the list of words already found */
                  printf("\n--- Word(s) Found ---\n");
                  PrintList(wordList);
                  printf("---------------------\n\n");
   
                  /* Display the adjacency of letters */
                  DisplayPos(tray,pos);
                  
                  /* Display the tray with letters again */
                  PrintTray(tray);
               }
             else
                  printf("\"%s\" has already been found\n", word);
            else
               printf("\"%s\" is not found in the dictionary\n", word);
         else   
            printf("\"%s\" is not found on the tray\n", word);
      else
         printf("Word must be at least 3 letters\n");
                  
      /* Read in another word */
      printf("\nEnter another word (any number to quit): ");
      gets(word);
   }
   printf("\nProgram Terminated...\n");   
}

Sample Output

kureyonShin@sf3:~[123]$ a.out
+---+---+---+---+
| S | Q | E | T |
+---+---+---+---+
| N | E | N | I |
+---+---+---+---+
| N | O | A | L |
+---+---+---+---+
| I | C | L | Y |
+---+---+---+---+

Enter word (any number to quit): inconsequential

--- Word(s) Found ---
1	inconsequential
---------------------

<4,1> <3,1> <4,2> <3,2> <2,1> <1,1> <2,2> <1,2> <1,3> <2,3> <1,4> <2,4> <3,3> <3,4> 

+---+---+---+---+
| S | Q | E | T |
+---+---+---+---+
| N | E | N | I |
+---+---+---+---+
| N | O | A | L |
+---+---+---+---+
| I | C | L | Y |
+---+---+---+---+

Enter another word (any number to quit): local

--- Word(s) Found ---
1	inconsequential
2	local
---------------------

<4,3> <3,2> <4,2> <3,3> <3,4>

+---+---+---+---+
| S | Q | E | T |
+---+---+---+---+
| N | E | N | I |
+---+---+---+---+
| N | O | A | L |
+---+---+---+---+
| I | C | L | Y |
+---+---+---+---+

Enter another word (any number to quit): 123

Program Terminated...
kureyonShin@sf3:~[124]$

That's not all...

If you have completed the first task, the next task will be to additionally show the adjacency of letters graphically. For example, given the word "inconsequential", we want to display the following.

   +---------------+
   | S   Q - E   T |
   | | \ |   | / | |
   | N   E   N   I |
   |   \       /   |
   | N   O   A - L |
   | | \ |         |
   | I   C   L   Y |
   +---------------+

As for the word "local", the sequence of adjacent letters is the following in which the X denotes that the path of the sequence crosses.

   +---------------+
   | S   Q   E   T |
   |               |
   | N   E   N   I |
   |               |
   | N   O   A - L |
   |     | X       |
   | I   C   L   Y |
   +---------------+

Given the list of positions in the first task, you are required to generate the output that uses the five characters from the set {|,-,\,/,X}. You need to modify the implementation of the DisplayPos function while keeping the function header untouched.

Hint: You might want to first declare a 2D character array that represents the output and fill it up nicely before dumping the entire array onto the screen.

Sample Output

kureyonShin@sf3:~[133]$ a.out
+---+---+---+---+
| S | Q | E | T |
+---+---+---+---+
| N | E | N | I |
+---+---+---+---+
| N | O | A | L |
+---+---+---+---+
| I | C | L | Y |
+---+---+---+---+

Enter word (any number to quit): inconsequential

--- Word(s) Found ---
1	inconsequential
---------------------

<4,1> <3,1> <4,2> <3,2> <2,1> <1,1> <2,2> <1,2> <1,3> <2,3> <1,4> <2,4> <3,3> <3,4> 

+---------------+
| S   Q - E   T |
| | \ |   | / | |
| N   E   N   I |
|   \       /   |
| N   O   A - L |
| | \ |         |
| I   C   L   Y |
+---------------+

+---+---+---+---+
| S | Q | E | T |
+---+---+---+---+
| N | E | N | I |
+---+---+---+---+
| N | O | A | L |
+---+---+---+---+
| I | C | L | Y |
+---+---+---+---+

Enter another word (any number to quit): local

--- Word(s) Found ---
1	inconsequential
2	local
---------------------

<4,3> <3,2> <4,2> <3,3> <3,4>

+---------------+
| S   Q   E   T |
|               |
| N   E   N   I |
|               |
| N   O   A - L |
|     | X       |
| I   C   L   Y |
+---------------+

+---+---+---+---+
| S | Q | E | T |
+---+---+---+---+
| N | E | N | I |
+---+---+---+---+
| N | O | A | L |
+---+---+---+---+
| I | C | L | Y |
+---+---+---+---+

Enter another word (any number to quit): 123

Program Terminated...
kureyonShin@sf3:~[134]$