Prog 5: AcrossWords

Create the game of AcrossWords, where a 4x4 grid of letters contains four four-letter words that have been scrambled.  You have to unscramble them.  

Note that while you could work with a partner on programs 3 and 4, you must work on this program (5) and the next program (6) on your own.

4/4 Updates below shown in blue, clarifying what the extra credit does and what the 'u' (for unveil) option does. Program output was made consistent, removing the references to a timer, which is not used in this program.  A clarifying statement was made for the step describing reading in input from the dictionaries.

4/11 Clarification of the extra credit shown in green.

4/14 Comment added before steps 3 & 4: Steps 3 & 4 below are intermediate steps in your program development process, to help you get to step 5.

Running Your Program

Running the program looks like the following:

Welcome to AcrossWord puzzle, where you rotate rows or columns        to restore the board back to containing four words. Each move is      a row or column letter followed by the rotation distance 1,2 or 3.    When prompted to provide input you may enter:                    Enter 'r' to reset the board to user-defined values.        Enter 'u' to unveil the underlying words.           Enter 's' to auto solve the board (Extra Credit)            Enter 'x' to exit the program.                            Which dictionary size do you want? (1=small, 2=medium, 3=large): 1 There are 500 4-letter words.        E F G H      -------   A| e u s h   B| t n e w   C| b l i v   D| o k k o 1. Enter the row or column to be rotated, and a number 1..3: d2       E F G H      -------   A| e u s h   B| t n e w   C| b l i v   D| k o o k 2. Enter the row or column to be rotated, and a number 1..3: e2       E F G H      -------   A| b u s h   B| k n e w   C| e l i v   D| t o o k 3. Enter the row or column to be rotated, and a number 1..3: c3       E F G H      -------   A| b u s h   B| k n e w   C| l i v e   D| t o o k Congratulations! You solved it!  End of program.  Exiting...

Running the program a different time, with a larger (medium) dictionary could give you:

Author: Dale Reed           Program: #5, AcrossWords    TA: Claude Shannon, Th 4-5  Mar 30, 2017                 Welcome to AcrossWord puzzle, where you rotate rows or columns        to restore the board back to containing four words. Each move is      a row or column letter followed by the rotation distance 1,2 or 3.    When prompted to provide input you may enter:                    Enter 'r' to reset the board to user-defined values.        Enter 'u' to unveil the underlying words.           Enter 's' to auto solve the board (Extra Credit)            Enter 'x' to exit the program.                            Which dictionary size do you want? (1=small, 2=medium, 3=large): 2 There are 2404 4-letter words.        E F G H      -------   A| d u t l    B| s g e e    C| s i r o    D| o u z y  1. Enter the row or column to be rotated, and a number 1..3: h1       E F G H      -------   A| d u t y    B| s g e l    C| s i r e    D| o u z o  2. Enter the row or column to be rotated, and a number 1..3: u You chose 'u' to unveil.  Here are the underlying words:        E F G H      -------   A| d u t y    B| g e l s    C| i r e s    D| o u z o         E F G H      -------   A| d u t y    B| s g e l    C| s i r e    D| o u z o  2. Enter the row or column to be rotated, and a number 1..3: r You chose 'r' to reset the board.  Enter 16 char values to reset the board: eushtnewblivo    Sorry, needed to provide exactly 16 characters of user input to reset the board.  Please retry. Enter 16 char values to reset the board: eushtnewblivokko       E F G H      -------   A| e u s h    B| t n e w    C| b l i v    D| o k k o  2. Enter the row or column to be rotated, and a number 1..3: x You chose x to Exit...

What to Do

You will write the program in steps.  To get credit you must finish each step before you go on to the next.  The outline of the steps and the number of points are given here, but details for each step then follow below.

• • 1. (5 points) Create a dynamic array and fill it with four-letter words, handling different size dictionaries. 

    2. (5 points) Create a 4x4 board.  Choose 4 four-letter words 

    3. Steps 3 & 4 below are intermediate steps in your program development process, to help you get to step 5.

    4. (10 points) Prompt for a letter for the row/column to be used, and the distance of the rotation, and make the rotation.  Do this three times.

    5. (10 points) Instead of the user choosing the row/column and number of positions to shift, now have the computer choose them and again make the rotations. Do two row rotations, and then do a single column rotation.

    6. (15 points) Change your program so that it still only does a single column rotation, but your program randomly chooses whether the column rotation is done first, second, or third. Each time you run your program it should give you different rotations.  The two rows selected must be unique.

    7. (5 points) Prompt for the user to enter row/col and distance values for rotations, as they attempt to solve the puzzle. Continue until the user selects 'x' to exit.

    8. (5 points) Rather than have the user enter 'x' to exit, on each turn your program should check to see if all four words on the board are in the dictionary.  Once all four words are found display a congratulatory message and exit.

    9. (10 points) Extra Credit: In response to the menu prompt for 's' to solve the puzzle automatically, for whatever set of letters your program currently has, have it automatically generate all combinations of moves until it finds a solution, printing out the steps from the original board (when you selected 's') to the solution that is found.

Details on What to Do

• 1. Create a dynamic array and fill it with four-letter words.  For different dictionaries this will be different sizes, which is why you have to do it dynamically.  The three dictionaries (smallDictionary.txt,  mediumDictionary.txt,  largeDictionary.txt) can be downloaded at the bottom of this page. Those three file names should be hard-coded into your program.  You may not have three different arrays of set sizes corresponding to these three files, because when testing your program we will likely change the size of the underlying three files, while still maintaining those three file names.

  2. Use the following steps:

     1. Open and read in whichever dictionary file  was selected (e.g. smallDictionary.txt )  and count how many 4-letter words there are (call this numberOfWords), then close the dictionary file.  

     2. Dynamically allocate enough space for the words in the selected dictionary file.  You will need to do this in two steps: 

        1. Dynamically allocate an array of char*, one per word.  (i.e. the array should have numberOfWords char* elements in it.) The dictionary itself should be of type char **, since it is the address of the first char*.  Here is a picture of what this looks like:

• • 1. Now re-read the dictionary, this time storing only the four-letter words in the above-allocated array. To re-read the input file you can either close and reopen the file, or you can rewind the file pointer, such as:  rewind(pInputFile).   Here is a picture of what this step would look like:

• • 1. Print out the number of 4-letter words found.  Running your program at this point should look like the following:

       1. Author: Dale Reed           Program: #5, AcrossWords    TA: Claude Shannon, Th 4-5  Mar 30, 2017                 Welcome to AcrossWord puzzle, where you rotate rows or columns        to restore the board back to containing four words. Each move is      a row or column letter followed by the rotation distance 1,2 or 3.    When prompted to provide input you may enter:                    Enter 'r' to reset the board to user-defined values.        Enter 'u' to unveil the underlying words.           Enter 's' to auto solve the board (Extra Credit)            Enter 'x' to exit the program.                            Which dictionary size do you want? (1=small, 2=medium, 3=large): 1 There are 500 4-letter words. 

1. Now add the code so that any one of the three dictionaries can be used, with your program allocating just the right amount of space for whichever one gets chosen. The other two dictionary names are  mediumDictionary.txt and   largeDictionary.txt  Test to make sure all three work.

   1. Create a 4x4 board.  Choose 4 four-letter words at random from the dictionary and store them on the board, one per row.  Running your program at this point should add the following output to the above step:

      1. 1.     E F G H      -------   A| b u s h    B| k n e w    C| l i v e    D| t o o k  

2. These are the 4 four-letter words that were selected. 

3. Steps 3 & 4 below are intermediate steps in your program development process, to help you get to step 5.

• 1. Prompt for a letter for the row/column to be used, and the distance of the rotation, and make the rotation, wrapping around the end of the row/column.  If the user input is A through D then rotate the row to the right the given number of spots.  If the user input is D through G then rotate the column downward the given number of spots. In both cases wrap-around the edge, as if the left-right sides and the top-bottom sides were connected. Repeat this prompting and making the move three times. Running your program at this point should add the following output to the above step:

     1. 1.     E F G H      -------   A| b u s h   B| k n e w   C| l i v e   D| t o o k  1. Enter the row or column to be rotated, and a number 1..3: a1 Rotating row A by 1       E F G H      -------   A| h b u s   B| k n e w   C| l i v e   D| t o o k  2. Enter the row or column to be rotated, and a number 1..3: c2 Rotating row C by 2       E F G H      -------   A| h b u s   B| k n e w   C| v e l i   D| t o o k  3. Enter the row or column to be rotated, and a number 1..3: f1 Rotating row F by 1       E F G H      -------   A| h o u s   B| k b e w   C| v n l i   D| t e o k  End of program.  Exiting...

  2. Instead of the user choosing the row/column and number of positions to shift, now have the computer choose them using the random number generator.  Rotate a random row twice, and then rotate a random column once.  Don't display the board until the rotations have been made.  Running your program at this point will look like the following:

• • • 1. Author: Dale Reed Program: #5, AcrossWords TA: Claude Shannon, Th 4-5 Mar 30, 2017  Welcome to the AcrossWord puzzle, where you play against the clock to make four board rotations to restore the board back to containing four words.  Each rotation can be a row letter, or column letter, followed by the number 1..3 which is how far to rotate.  When prompted to provide input you may enter:      Enter 'r' to reset the board to user-defined values.        Enter 'u' to unveil the underlying words.           Enter 's' to auto solve the board (Extra Credit)            Enter 'x' to exit the program.   There are 500 4-letter words.       E F G H      -------   A| b u s h   B| k n e w   C| l i v e   D| t o o k Rotating row/col D by 2       E F G H      -------   A| b u s h   B| k n e w   C| l i v e   D| o k t o Rotating row/col B by 3       E F G H      -------   A| b u s h   B| n e w k   C| l i v e   D| o k t o Rotating row/col G by 1       E F G H      -------   A| b u t h   B| n e s k   C| l i w e   D| o k v o  End of program.  Exiting...

• 3. At this point it is still fairly easy to solve the puzzle.  All you have to do is to first figure out which column needs to be rotated to give the letters for valid words in each row.  We do this first because we know it was done last when creating the puzzle.  Now change your program so that it still only does a single column rotation, but your program randomly chooses whether it is done first, second, or third.  The two rows selected must be unique.  Still display the rotations, so you can validate that it is working correctly.  Running your program should look something like:

• • • 1. Author: Dale Reed Program: #5, AcrossWords TA: Claude Shannon, Th 4-5 Mar 30, 2017  Welcome to the AcrossWord puzzle, where you play against the clock to make four board rotations to restore the board back to containing four words.  Each rotation can be a row letter, or column letter, followed by the number 1..3 which is how far to rotate.  When prompted to provide input you may enter:      Enter 'r' to reset the board to user-defined values.        Enter 'u' to unveil the underlying words.           Enter 's' to auto solve the board (Extra Credit)            Enter 'x' to exit the program.   There are 500 4-letter words.       E F G H      -------   A| b u s h   B| k n e w   C| l i v e   D| t o o k Rotating row/col B by 2       E F G H      -------   A| b u s h   B| e w k n   C| l i v e   D| t o o k Rotating row/col F by 3       E F G H      -------   A| b w s h   B| e i k n   C| l o v e   D| t u o k Rotating row/col A by 1       E F G H      -------   A| h b w s   B| e i k n   C| l o v e   D| t u o k  End of program.  Exiting...

• 4. and running your program a second time should show different choices made for the rotations. To make sure it is different in this way be sure to seed your random number generator with time(0) rather than just 0. You may need to #include at the top of your program to get this to work.  Just the rotations part of the output might instead be:

• • • 1.     E F G H      -------   A| b u s h   B| k n e w   C| l i v e   D| t o o k Rotating row/col A by 2       E F G H      -------   A| s h b u   B| k n e w   C| l i v e   D| t o o k Rotating row/col C by 2       E F G H      -------   A| s h b u   B| k n e w   C| v e l i   D| t o o k Rotating row/col G by 1       E F G H      -------   A| s h o u   B| k n b w   C| v e e i   D| t o l k  End of program.  Exiting... 

• 5. Once you have verified this is working, remove the display of the original board and the intermediate boards and the rotation selections, displaying only the board with the rotations having been made. This should look something like the following:

• • • 1. Author: Dale Reed Program: #5, AcrossWords TA: Claude Shannon, Th 4-5 Mar 30, 2017  Welcome to the AcrossWord puzzle, where you play against the clock to make four board rotations to restore the board back to containing four words.  Each rotation can be a row letter, or column letter, followed by the number 1..3 which is how far to rotate.  When prompted to provide input you may enter:      Enter 'r' to reset the board to user-defined values.        Enter 'u' to unveil the underlying words.           Enter 's' to auto solve the board (Extra Credit)            Enter 'x' to exit the program.   There are 500 4-letter words.       E F G H      -------   A| h n u s   B| k e e w   C| v o l i   D| t b o k  End of program.  Exiting...

• 6. Next prompt for the user to enter row/col and distance values for rotations, as the user attempts to solve the puzzle.  Make the rotations specified by the user and keep going until the user enters 'x' to exit. Add the move number for each move.

  7. Rather than have the user enter 'x' to exit, on each turn your program should check to see if all four words on the board are in the dictionary.  If they are it should display a congratulatory message and exit.

Notes:

1. You don't need to do any error checking.  You do need to allow the user to provide row/column letters in upper or lower case, with or without spaces between the user inputs.  I suggest you use char input to handle this. 

2. If 'u' to "unveil" is chosen, display the original board but then again display the current scrambled board.  To do this you don't need to solve the puzzle.  Rather you should create a saved version of the original board when the four words are first chosen and placed on the board.  The 'u' option should just display this original saved board.

   1. If 'r' to "reset" is chosen, the user has to supply exactly 16 characters.  If the user input isn't exactly 16 characters you should display an error message and prompt them to retry.  Also when 'r' to "reset" the board is entered, the underlying solution that would otherwise be displayed with 'u' to "unveil" does not change, and would still be whatever had been there prior to 'r' being chosen.

3. If you decide to implement the extra credit ('s' to auto-solve), to get credit your program must display the rotations and resulting boards along the way to the destination, not just the final board.  This sequence of steps and display of resulting boards should start with the board at the point where 's' is chosen. Note that this is not the same as 'u', as explained above, where a backup of the original board is displayed.  To test your auto-solving of the board we will first use the 'r' option to reset the board to some other characters, and then select 's' to solve it, so your program will truly need to try all possible combinations of moves to find some valid solution where all four rows are found in the dictionary.  Note that after the board is reset with 'r', the 'u' option would still show the old original board, but it would not be the solution for the current set of letters and so would not be helpful.

4. The set of letters used to check the extra credit will have been generated the same way as any other board puzzle: four words selected at random, with three rotations, one of them being a column rotation. To implement the extra credit you need to try all possible permutations of the three possible rotations.

Submitting your Program

1. Your program must have the .cpp file extension.  The name of the program you will turn in should be  prog5Words  followed by your netid and the .cpp file extension.  In other words, if your netid is reed then your program would be called:   prog5Wordsreed.cpp      Remember, you may not work with a partner on this or the next program!

2. You must also zip up the file you turn in, which typically is done by right-clicking on it and choosing the "compress" option.  After zipping your program (e.g. prog5Wordsreed.cpp), you will likely end up with a file called something like: 

3.      prog5Wordsreed.zip 

4. Only turn in this single file, turning it in on Blackboard into the assignment Program 5.  Do not turn in any dictionary files. Please do not put it into a folder before zipping it, rather zip the one file by itself.

5. After submitting your program to Blackboard, select it to download it from Blackboard so you can verify that you uploaded the correct file. You will not receive credit for this program if you submit the wrong file!

6. Failing to follow these naming conventions and failure to turn in a zip file will result in a 5 point deduction, even if everything else is perfect in your program.