Word Board with Undo/Redo

Introduction

In word board games like Scrabble or Words with Friends, players place letters on a grid to form words. After the first word is placed on the board, subsequent words must intersect one or more existing words. In the game, letters from a player are connected to letters already on the board to form words. Many descriptions of the game are available online, including a reasonably thorough discussion on Wikipedia.

For this problem, you will develop a program for recording and displaying player moves involving the addition of a word to the board, where a new word will intersect with an existing word.

For example, consider the following grid:

        P R O G R A M 
  M E M O R Y
      N E T W O R K 
  S Y S T E M                   E
        S T R I N G     A N T I Q U E
                O       L       U
              C O L L E G E     A
    T P       A D       E       T S
    H H       L L       B       I C
    E Y       C E       R       O H I O
    O S       U         A       N E
  G R I N N E L L                 M
    Y C       U                   E
      S       S

This grid contains numerous words arranged horizontally or vertically, and each word is connected to one or more other words at various letters. When inserting a word, it is not required that every letter of the new word must form a word with every adjacent letter. For example, the words PROGRAM, MEMORY, NETWORK, SYSTEM, and STRING at the top left are positioned along the vertical word POETS. Reading down in the next column from POETS, one gets the sequence RRTET; this is not a word, but that is irrelevant to the rules for this problem.

Within this context, a first word may be placed anywhere on the grid. Thereafter adding a new word requires that the word connect with at least one existing letter already on the grid. If the new word would extend over several existing letters, then the corresponding letters must match. For example, in the illustration, the word RARE could be added vertically using the R in PROGRAM and the R in NETWORK. However, the word RAKE could not be added in this position. The first R would fit with the R of PROGRAM, but the K in RAKE does not match the grid element already on the grid (the R in NETWORK).

Details

This problem asks you to support five operations for a simple game of scrabble.

Menu options:
   i:  initialize the board
   a:  add a new word to the board
   u:  undo the previous word addition(s)
   r:  redo the previous undo operation
   q: quit

Operation notes

• Option i: initialize the board, so that all squares are blank. As part of this operation, all record of any past moves is erased.
• Option a: The user is asked for a string, a starting square (row and column numbers), and an orientation (horizontal or vertical).
  • If this is the first string on the board, the program checks that the string fits on the board from the designated starting point.
    • If so, the string is placed on the board, and the move is remembered.
    • If not, the add command is ignored, and the board remains blank.
  • If this is not the first string on the board, the program checks that the string fits on the board and overlaps with one or more existing words and does not conflict with any other existing words.
    • If so, the string is placed on the board, and the move is remembered.
    • If not, this add command is canceled, and the previous history of commands remains the same.
• Option u: The board is updated to remove the word most recently added, if any. If the option is chosen several times, multiple words from the most recent add commands are removed.
• Option r: The previous undo operation, if any, is canceled, so the word removed by "undo" is added again. That is, the redo command cancels exactly one undo operation. Multiple redo commands cancel the corresponding undo operations. If an add command has inserted a word onto the board after the most recent undo command, then the redo command is ignored.
• Option q: all processing is completed, and the game is over.

After each operation (except quit), the program should print the current layout of the board.

Programming notes

Implementing an undo operation requires keeping track of the past letters placed on the board and where they were placed. Implementing several undo operations means that each add operation must be recorded, with access to the most recent add first. This last in-first out represents the standard method of storage for a stack. In this case, an item on the stack will be the letters actually placed on the board (likely ignoring letters already there), the starting location, and the word orientation (e.g., horizontal or vertical).

An undo operation requires popping the top element the stack and removing the relevant characters from the board. However, the undone action should not forgotten, as this information could be needed for a redo operation. Further undo actions would also need to be stored for a potential redo. In every case, it is always the most recent undone action we would want to redo, which suggests we should store these undone actions in their own redo stack.

Thus, a redo action would pop an element from the redo stack, replay the action, and push it onto the undo stack (as with a normal play). Further redo actions would repeat this process.

In this way, a user could conceivably navigate pushing the same items back and forth between the undo and redo stacks in a manner functionally equivalent to navigating forward and backward through a linear history of the board states.

However, an add after undo or redo operations must reset the forward history of the board. Put another way, an add after an undo or redo should empty the redo stack, while undo operations could still go further backward

Your program must use a self-contained list-based stack library package, such as developed in the lab on stacks. You should include a Makefile for building all elements of your program (which will require at least two .c files and one .h file).

Grading

In addition to the general grading guidelines for evaluation, the assignment is worth 25 points.

• [1 point] Initialization clears board and undo history
• [1 point] Program prints board after each operation (except quit)
• [7 points] Added words obey constraints
• [2 point] Words are added to blank board if they fit
• [3 points] Words are added to board if fitting and overlapping
• [2 points] Words are rejected if not fitting or not overlapping
• [6 points] Undo operation implemented with a stack
• [2 points] Undo correctly removes a play from the board
• [2 points] Repeated undo operations remove previous plays
• [4 points] Program library and compilation managed separately
• [2 points] Stack library separated from main program
• [2 points] Makefile compiles and links separately
• [6 points] Tests demonstrate correctness
• [2 points] Test plan enumerates the range of problem circumstances
• [2 points] Test cases include specific inputs and expected outcome(s)
• [1 point] Transcripts demonstrate functionality with test runs
• [1 point] Statement argues why the program is correct
• Comments on Program Format, Comments, Readability, etc.
  (Points not given, but points can be deducted.)

Extra credit

• [10 points] Redo operation implemented with a stack
• [2 points] Undone actions are rendered redoable
• [2 points] Redo correctly replays the appropriate action
• [2 points] Repeated redo operations replay appropriate action
• [2 points] Redone actions are rendered undoable
• [1 point] Redo has no effect when redo history is empty
• [1 point] Word add resets redo history

Note: All extra credit attempts submitted must be fully tested. Failure to test them will yield no extra credit and reduce credit for testing.