Please read the remarks about programming problems for this course.

Task

A word search puzzle consists of words hidden in a rectangular block of random characters. You will complete a C++ program to produce such a puzzle.

Organization

The word search program you are to complete consists of six C++ files, found here:

• wspuzzle.cpp. This file contains the main function and a function that reads the list of words from a text file and inserts them into a C++ std::vector. The code in this file loads the words, builds the key and puzzle, and prints the key and puzzle. You should not modify this file.

• lettermatrix.h. This header file contains the declaration of a new type name, LetterMatrix, which represents a two-dimensional vector of characters. A word search puzzle and its key will be a LetterMatrix. Additionally, this file provides the declaration of several overloaded operators that work with LetterMatrix objects. This type provided as a convenience to simplify the code you need to write. You should not modify this file.

• lettermatrix.cpp. This file defines the functions declared in lettermatrix.h. You should not modify this file.

• wordsearch.h. This header file contains the declarations of the functions to build the key and puzzle and to print them. You should not modify this file.

• wordsearch.cpp. This incomplete file contains the definitions of the functions declared in wordsearch.h. You must provide the code for the make_key and make_puzzle functions. You are encouraged to add helper functions to assist these two functions.

• uniformrandom.h. This header file contains the code for a decent pseudorandom generator. You should not modify this file. Generating a pseudorandom number is easy; the following code demonstrates by printing 100 random integers in the range 20 to 30, inclusive:
  #include <iostream> #include "uniformrandom.h" using namespace std; int main() { auto r = UniformRandomGenerator(20, 30); // r makes random integers for (int i = 0; i < 100; i++) { int x = r(); // Obtain a random integer from r cout << x << endl; // Print the integer } }

  As you can see, you first create a random number generator object, specifying its range of values in the construction. Afterward when you need a pseudorandom number, you simply "call" the object like a function. Every time you "call" the object it will return the next pseudorandom integer in its sequence.

These files constitute a C++ project that will build and run. The make_key and make_puzzle functions are stubs that contain no useful code; you will replace their contents with your code. Complete make_key first; it fills a puzzle with space characters (' ') and then inserts the words. After that, the make_puzzle function is easy—it simply makes a copy of the key and then replaces all the remaining empty spaces with random characters.

You should study all the code provided, especially the code that reads data from a text file and the overloaded operator functions. You may need to write similar code yourself in the future.

Details

The program reads the list of words from a text file named wordlist.txt. The file should contain ten words, each on its own line. No word will contain more than 15 letters.

The program places the words in a 20 x 20 block filled with random letters.

Your code should place the words randomly in different several ways:

• It should determine the position of each word randomly.
• It should randomly decide whether to orient a word horizontally, vertically, or diagonally.
• It should randomly choose whether to order the letters forwards (left-to-right or top-to-bottom) or backwards (right-to-left or bottom-to-top).

You can simplify this process by computing a random row, column starting location for the first letter in the word and then computing a random row change, column change vector (the term vector is used here in the mathematical sense, not the C++ std::vector data structure sense). This vector then can take care of both the orientation and forwards/backwards direction.

Using randomness in this way means you should not determine ahead of time how many words are printed backwards or diagonally, etc. Since the placement is done entirely at random, some puzzles, although rare, may contain no diagonally-placed words, or no backwards words; however, multiple runs of your program over the same list of words must clearly demonstrate that your program satisfies all the requirements listed in this specification.

Another use of randomness is in the selection of letters to fill in around the words to hide; they too should be chosen at random and not predetermined.

Your program should be able to handle correctly words that overlap, such as:

                   R
                 O
	 S T A T I C
     D       C
       E   E
         V
           I
             C
               E

Notice how DEVICE and VECTOR overlap at V, and STATIC and VECTOR overlap at T. Such overlap is not common via purely random placement, so you may need to run your programs multiple times to demonstrate this capability.

The words in the file may may consist of both upper- and lowercase alphabetic letters, but the program capitalizes all the letters in a word before using them in the puzzle.

Output

The program produces the following output, in the following order:

1. the list of words to find
2. the puzzle
3. The answer key

   Here is the output of a sample run.

   COMPUTER ALGORITHM WHILE PROGRAM COMPILER PROCESSOR MEMORY ITERATIVE RECURSIVE CONDITIONAL P M N R B L H R K X R J F T K B P F W C I E X L B U M W E P U V M U Q R N L T B B P M R K L P E C C N T M D O D F Q W G X K T H A F X B O X U T M G H K S E B E C E Z X Y M B R M M G R R L L K M K Y T O R Z Z Q D L E P G H A S R F W R P K E Z D X R T F Y L U V M I G I P E T O W Z O O W E D O B I T J X M N A V J S D W C X U R R Y X T H E L E P H M Z E W B S N A N G R U P C W R R X P L T E V R Y I E Z W L U Y I M P E E R M B E I U A H P X I I M E M O R Y B L L Y T X J R T R T U U E G L D O O E Y I D G C J H G O D J X G C D B U R K J Q P A E Y C P C V G R F Q B X H X E V H U M J G V W E R M R L T Q S R P L X Z L H O L K Y S M D P S Y A E V C O Y B O J M C H K S F E X A S L E Z N E M J O G W F Q N O V U X I L Z D M E V I T A R E T I W R K N H D V X X A I Z G S L S M L A N O I T I D N O C T Z F R P E R C C O O U G M R R E P A S L U M I I T M V H E H E W R R T E I P M E M O R Y L R R I O P C G M E L O S A C S O E V I T A R E T I R L A N O I T I D N O C

   Strategy

   You have only two functions to write, but there is a lot of other code involved that you need to understand. You have one week to complete the assignment, but most students will want to set aside a few hours over several days to complete the assignment. The following represents a reasonable time schedule for this assignment:

   1. Read and re-read this assignment carefully and completely. (1 hour)

   2. Install, if necessary, the C++ IDE or build system of your choice. (1 hour)

   3. Collect all the code into a project within the C++ IDE or build system of your choice. Before you begin to implement the two functions ensure that you can compile and run the code provided. (1–2 hours)

   4. Study the code provided. Be sure you understand the purpose of all the parts. (2 hours)

   5. Think about the problem and devise a solution. (Several hours, possibly spread out over several days)

   6. Implement your solution in C++. (Several hours, possibly spread out over several days as you reacquaint yourself with C++)

   7. Test your solution. (1 hour)

   8. Repeat the previous two steps until you are satisfied that your implementation is correct.

   Submission

   Submit your completed wordsearch.cpp C++ source file to http://eclass.e.southern.edu. Be sure your name appears within a comment as the first line in each source file you submit.

   • Home
   • Labs