Prog 4: Vexed

10/16 Added the error message shown in blue: Invalid move direction.  Please retry.

10/25 You may use a 1d or 2d array to store your boards.  The sample code I have provided assumes use of a 1d array, but you can change that part of it to use a 2d array without penalty.

10/30 Vector based approach (rather than recursion) to blanking out adjacent matching pieces, shown in purple.

Write an ASCII text version of the classic Palm game called Vexed.  There are ad-supported online versions (shown below), as well as Android and iOS versions, though they may be dated and buggy.

In our solution commands will be entered from the Terminal and not done graphically.  This should look like the following, and is explained more fully below:

Welcome to Vexed!   The objective is to place identical pieces next to each other, so that they vanish,    clearing the board completely within the indicated number of moves. On each move       enter the row, column, and direction (L or R) to move, in either upper or lower        case. You may also enter 'x' to exit the program, or 'r' to reset the current level.        Board 0 par 4       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . . @ &     . . . | C   D | . . . . .     . . . | D   E | . . .         . . . | E   F | . . . &     @ . . . | F   G | . . . . & @ . . . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9   1. Your move: c4r      Board 0 par 4       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . . @   &   . . . | C   D | . . . . .     . . . | D   E | . . .         . . . | E   F | . . . &     @ . . . | F   G | . . . . & @ . . . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 0 par 4       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . . @       . . . | C   D | . . . . . &   . . . | D   E | . . .         . . . | E   F | . . . &     @ . . . | F   G | . . . . & @ . . . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 0 par 4       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . . @       . . . | C   D | . . . . .     . . . | D   E | . . .     &   . . . | E   F | . . . &     @ . . . | F   G | . . . . & @ . . . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 0 par 4       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . . @       . . . | C   D | . . . . .     . . . | D   E | . . .         . . . | E   F | . . . &   & @ . . . | F   G | . . . . & @ . . . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9   2. Your move: c3r      Board 0 par 4       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .   @     . . . | C   D | . . . . .     . . . | D   E | . . .         . . . | E   F | . . . &   & @ . . . | F   G | . . . . & @ . . . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9   3. Your move: c4r      Board 0 par 4       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .     @   . . . | C   D | . . . . .     . . . | D   E | . . .         . . . | E   F | . . . &   & @ . . . | F   G | . . . . & @ . . . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 0 par 4       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .         . . . | C   D | . . . . . @   . . . | D   E | . . .         . . . | E   F | . . . &   & @ . . . | F   G | . . . . & @ . . . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 0 par 4       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .         . . . | C   D | . . . . .     . . . | D   E | . . .     @   . . . | E   F | . . . &   & @ . . . | F   G | . . . . & @ . . . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9   4. Your move: f5l      Board 0 par 4       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .         . . . | C   D | . . . . .     . . . | D   E | . . .     @   . . . | E   F | . . . & &   @ . . . | F   G | . . . . & @ . . . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 0 par 4       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .         . . . | C   D | . . . . .     . . . | D   E | . . .         . . . | E   F | . . . & & @ @ . . . | F   G | . . . . & @ . . . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 0 par 4       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .         . . . | C   D | . . . . .     . . . | D   E | . . .         . . . | E   F | . . .     @ @ . . . | F   G | . . . .   @ . . . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 0 par 4       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .         . . . | C   D | . . . . .     . . . | D   E | . . .         . . . | E   F | . . .         . . . | F   G | . . . .     . . . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9    Congratulations!  On to the next level. Score: 4      Board 1 par 3       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .     &     . . | C   D | . . .     @     . . | D   E | . . .   & +     . . | E   F | . . .   @ %     . . | F   G | . . . @ % +   + . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9   1. Your move: d5l      Board 1 par 3       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .     &     . . | C   D | . . .   @       . . | D   E | . . .   & +     . . | E   F | . . .   @ %     . . | F   G | . . . @ % +   + . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 1 par 3       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .           . . | C   D | . . .   @ &     . . | D   E | . . .   & +     . . | E   F | . . .   @ %     . . | F   G | . . . @ % +   + . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9   2. Your move: d4l      Board 1 par 3       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .           . . | C   D | . . . @   &     . . | D   E | . . .   & +     . . | E   F | . . .   @ %     . . | F   G | . . . @ % +   + . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 1 par 3       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .           . . | C   D | . . .     &     . . | D   E | . . . @ & +     . . | E   F | . . .   @ %     . . | F   G | . . . @ % +   + . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 1 par 3       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .           . . | C   D | . . .     &     . . | D   E | . . .   & +     . . | E   F | . . . @ @ %     . . | F   G | . . . @ % +   + . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 1 par 3       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .           . . | C   D | . . .     &     . . | D   E | . . .   & +     . . | E   F | . . .     %     . . | F   G | . . .   % +   + . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 1 par 3       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .           . . | C   D | . . .     &     . . | D   E | . . .     +     . . | E   F | . . .   & %     . . | F   G | . . .   % +   + . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9   3. Your move: e5r      Board 1 par 3       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .           . . | C   D | . . .     &     . . | D   E | . . .       +   . . | E   F | . . .   & %     . . | F   G | . . .   % +   + . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 1 par 3       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .           . . | C   D | . . .     &     . . | D   E | . . .           . . | E   F | . . .   & % +   . . | F   G | . . .   % +   + . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 1 par 3       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .           . . | C   D | . . .     &     . . | D   E | . . .           . . | E   F | . . .   & %     . . | F   G | . . .   % + + + . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 1 par 3       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .           . . | C   D | . . .           . . | D   E | . . .     &     . . | E   F | . . .   & %     . . | F   G | . . .   % + + + . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 1 par 3       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .           . . | C   D | . . .           . . | D   E | . . .     &     . . | E   F | . . .   & %     . . | F   G | . . .   %       . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 1 par 3       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .           . . | C   D | . . .           . . | D   E | . . .     &     . . | E   F | . . .   &       . . | F   G | . . .   % %     . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 1 par 3       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .           . . | C   D | . . .           . . | D   E | . . .           . . | E   F | . . .   & &     . . | F   G | . . .   % %     . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 1 par 3       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .           . . | C   D | . . .           . . | D   E | . . .           . . | E   F | . . .           . . | F   G | . . .   % %     . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9        Board 1 par 3       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . .           . . | C   D | . . .           . . | D   E | . . .           . . | E   F | . . .           . . | F   G | . . .           . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9    Congratulations!  On to the next level. Score: 7      Board 2 par 14       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . .     . . . . | B   C | . . .         . . . | C   D | . . ^   = #   ^ . . | D   E | . . #   . .   = . . | E   F | . . . #     = . . . | F   G | . . . .     . . . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9   1. Your move: 

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

Classes and Objects in C++.  More specifically you need to know how to create a class that contains private data members, get() and set() member functions, a default constructor, and a fully qualified constructor (with all the initialization values).  You need to know how to declare an instance of a class, and how to create utility functions (e.g. displayBoard() for this program).

Notes:

SourceForge has a historic Palm Vexed site, along with source code. (Warning: write your own, don't use any of theirs. Moss is very picky about things like this...)  The bottom of this page has links to some starting code (vexed.cpp) as well as the data file boards.txt.

I suggest you write your program using the following steps.  

• 1. (0 points) You must use the provided sample allBoards class.  Start by verifying that reading from a file is working, and that you can display any Board.  You are given the allBoards class which reads from a file, but you must write the Board class yourself.  The Board class should have:

     1. Private data members for an integer board number (the level), an array of 8 x 10 integers for the board, and an integer par value.  ("Par" is a term from golf that represents the expected number of moves it should take to solve a level.)

     2. A default constructor.  This should set everything to -1 values;

     3. Fully qualified constructor, catching 1. The board number, 2. An array of 8 * 10 integer board values, and 3. The par value for the board.

     4. A member function called displayBoard() which uses the above values to display the board in the format shown in the examples below.

1. (0 points) Test the above code so far by displaying the first five boards, where you display all the numbers read in.  For instance the first two boards would look like the following:

   1. • 1. Board 0 with par 4 is:

        2. 9 9 9 9 9 9 9 9 9 9

        3. 9 9 9 9 9 9 9 9 9 9

        4. 9 9 9 2 1 0 0 9 9 9

        5. 9 9 9 9 9 0 0 9 9 9

        6. 9 9 9 0 0 0 0 9 9 9

        7. 9 9 9 1 0 0 2 9 9 9

        8. 9 9 9 9 1 2 9 9 9 9

        9. 9 9 9 9 9 9 9 9 9 9

        10. Board 1 with par 3 is:

        11. 9 9 9 9 9 9 9 9 9 9

        12. 9 9 9 9 9 9 9 9 9 9

        13. 9 9 9 0 0 1 0 0 9 9

        14. 9 9 9 0 0 2 0 0 9 9

        15. 9 9 9 0 1 3 0 0 9 9

        16. 9 9 9 0 2 4 0 0 9 9

        17. 9 9 9 2 4 3 0 3 9 9

        18. 9 9 9 9 9 9 9 9 9 9

• 1. and this might be called within main as:

     1.    AllBoards allTheBoards;     // Reads in and stores all the boards from a data file     int currentBoardIndex = 0;  // Starting board index     Board theBoard;          for( currentBoardIndex=0; currentBoardIndex<5; currentBoardIndex++) {         theBoard = allTheBoards.getBoard( currentBoardIndex);         theBoard.displayBoard();     } 

  2. (0 points) Next update your Board class displayBoard() member function so that it displays a border around the board, and looks like this:

• • 1. Board 0 with par 4 is:

    2. -----------------------

    3. | 9 9 9 9 9 9 9 9 9 9 |

    4. | 9 9 9 9 9 9 9 9 9 9 |

    5. | 9 9 9 2 1 0 0 9 9 9 |

    6. | 9 9 9 9 9 0 0 9 9 9 |

    7. | 9 9 9 0 0 0 0 9 9 9 |

    8. | 9 9 9 1 0 0 2 9 9 9 |

    9. | 9 9 9 9 1 2 9 9 9 9 |

    10. | 9 9 9 9 9 9 9 9 9 9 |

    11. -----------------------

• 3. (0 points) Now again update the board class to display the board as character values rather than numbers.  You should translate them as follows:

• 1. Now also add the reference letters and numbers to the board, so it looks like the following:

     1. 1.  Board 0 with par 4 is:      0 1 2 3 4 5 6 7 8 9     ----------------------- A | . . . . . . . . . . | A B | . . . . . . . . . . | B C | . . . @ &     . . . | C D | . . . . .     . . . | D E | . . .         . . . | E F | . . . &     @ . . . | F G | . . . . & @ . . . . | G H | . . . . . . . . . . | H   -----------------------     0 1 2 3 4 5 6 7 8 9   

  2. (10 points) Before displaying the board, also display the directions at the beginning of the game and the move prompt.  Running your program at this point should look like the following:

• • • 1. Welcome to Vexed!   The objective is to place identical pieces next to each other, so that they vanish,    clearing the board completely within the indicated number of moves. On each move       enter the row, column, and direction (L or R) to move, in either upper or lower        case. You may also enter 'x' to exit the program, or 'r' to reset the current level.        Board 0 par 4       0 1 2 3 4 5 6 7 8 9       -----------------------   A | . . . . . . . . . . | A   B | . . . . . . . . . . | B   C | . . . @ &     . . . | C   D | . . . . .     . . . | D   E | . . .         . . . | E   F | . . . &     @ . . . | F   G | . . . . & @ . . . . | G   H | . . . . . . . . . . | H     -----------------------       0 1 2 3 4 5 6 7 8 9   1. Your move: 

1. (15 points) Implement making moves.  The prompt should indicate how many moves have been made so far on this level, starting at 1.  Each move consists of three values: row letter, column number, and direction ('L' for left or 'R' for right).  Your program must accept both upper and lower-case input.  

   1. Input of c4r would move the piece at row C, column 4 to the right one position, to c5.  Your program must handle the following special single character inputs:

   2.      - Row letter input of 'x' (or 'X') should exit the program.

   3.      - Row letter input of 'r' (or 'R') should reset this level, restarting the move number to 1.

   4.      - Row letter input of 's' (or 'S') followed by a level number should set the board (and par) to be the ones for that level. 

   5.        Setting the level number is for testing purposes, not normal play, since score at that point will no longer be meaningful.

   6. The following error messages and a prompt to retry the move should be given for:

   7. Attempting to move an invalid character.  Please retry.

   8. Attempting to move into a non-empty space.  Please retry.

   9. Move value is out of bounds.  Please retry.

   10. Invalid move direction.  Please retry.

2.  

3. I suggest the code to prompt for and make a move also be a Board class member function, however it should use a return value or set a reference parameter to keep track of the special cases of user input to exit, reset, or set a new level, returning back to the main part of your program to handle those special cases.  By making it a Board class member function you can directly check the values stored in the board array, to check for the error conditions shown above.

• 1. (20 points) Update the board after a move.  This code should be implemented in one or several Board class member functions.  (At this point your code may have grown enough that you may consider placing your Board function definitions out-of-line (after and outside the class) rather than in-line (inside the class).

     1. Have any piece with spaces under it move downward until it is stopped by a wall '.' or some other piece.  Display the board after each piece moves. You should start checking at the end of the array and work your way back to the beginning of the array.  For each playable piece that has a space under it, move it down as far as possible.

  2. After all pieces have been moved down as far as they can go, for each piece that has moved and come to rest, delete all adjacent pieces (left/right or above/below) that match it, continuing this outwards. You should start checking for matching adjacent pieces from the beginning of the array and work your way towards the end. Display the board after each set of adjacent pieces are erased.

  3. This is possibly the trickiest part of the program.  You could do this using a vector, or using recursion.  These are both explained below.

  4. A.   Using a Vector

• • 1. Create a vector (e.g. pieceVector) that will be used to keep track of a list of pieces.

    2. Go through the board and examine each board position (e.g. call it current).  If that board position has an adjacent neighbor (left, up, right, or down) that is the same type as current, then add current to vector pieceVector. 

    3. Once you are done, go through all the board positions in pieceVector and blank them out.  There may be some redundancy, but it won't hurt the process

                       B.  Using a recursive "marking" algorithm.  

• • • 1. Write a function that for each board piece that is not a wall or a space, checks that piece's left, right, upper, and lower neighbors.  If those neighbors are the same as the original piece, then change the neighbor values to be -1, thus "marking" it as a piece to be cleared, and also recursively from within this function call this same function again, from the perspective of each neighbor.  This should have the effect of marking each adjacent matching board piece to be deleted with the value -1.

      2. Step through the board from the top.  Each board value that is -1 should be set to 0, which is the numerical value used to represent a blank.

      3. (You might also skip step 2 and change matching adjacent pieces directly to 0, but it could be harder to debug if you have problems.)

                       Keep repeating the above two steps (1. Move pieces downward; 2. Delete adjacent matching pieces) while there are changes to the board.

1. (10 points) Check to see if the board has been cleared and this level has been solved. 

   1. If the board has cleared and the number of moves was above par, then give a message:

   2.    Sorry, you took x moves and you must finish within y moves before moving on.

   3. where x is the number of moves taken, and y is the par value for that level.  Then reset that same level. 

   4. If the board has cleared and the number of moves was at or below par, then give the congratulatory message:  

   5.    Congratulations!  On to the next level. 

   6. and update the score by adding the par value for this level, and display it:

   7.    Score: nn

   8. where nn is the current score.  Continue by showing the next level puzzle.

While not required this time around, for programs 5 and 6 we will likely implement a graphical version for program 5, and then for program 6 we will use linked lists to implement infinite undo (and perhaps also mouse-driven input).