Winter 2005 UCLA CS 31 Programming Project 6 SPECIFICATION

Winter 2005 UCLA CS 31 (Shinnerl)

Programming Project 6: 2D word-search puzzle generator

DUE: 10pm Fri. 3/4

Will be accepted without penalty until 12:01am Monday 3/7.

Final Specification 4PM Wed. 2/23

1. Overview

Write a menu-driven C++ program which, given a list of words, constructs a 2-dimensional rectangular table of letters, called a puzzle, which contains the given words in various orientations along with other randomly selected letters. Words are allowed to wrap around table boundaries. For example, given the list of words

                     main  cab  back  fit  zap  dinged

one correct solution puzzle is the following.

                                  0 1 2 3 4

                              0   b a c k a
                              1   t a p m w
                              2   d i n g e
                              3   t i f k z

However, many other puzzles are also possible, so there is not a unique answer. Your task is to create a correct puzzle consistent with the details below.

2. Details

When the program is run, it asks the user for the names of three files.
1. word list file--- the name of the plain-text input file with the words to be hidden. [Sample]
2. puzzle file--- the name of the plain-text output file that will contain the puzzle. [Sample]
3. puzzle solution file--- the name of the plain-text output file that will contain the puzzle solution. [Sample]
The formats of these files are prescribed in items (2)--(6) below.
The program keeps track of where it hides the words in the puzzle.
```
PUZZLE SOLUTION:
      Location   Orientation   Word           
      --------   -----------   ----           
      (1, 3)     NE            main           
      (0, 2)     W             cab            
      (0, 0)     E             back           
      (3, 2)     NW            fit            
      (3, 4)     SE            zap            
      (2, 0)     E             dinged         
```
The puzzle solution output file follows the format used in this example, specifying the indices of the first letter of word and the compass direction (East, Northeast, North, Northwest, West, Southwest, South, or Southeast) in which the word is written. Words may appear forwards, backwards, up, down, and diagonally, and words may wrap around the ends of a line, possibly reusing letters (as does the word "dinged" above).
The words in the puzzle-solution output are listed in the same order they appear in the word-list file. A word occurring more than once in the puzzle need only be listed once in the solution; either location may be given in the solution.
Input-File Format. The program reads in the words directly from the user-specified input file. The words in this file are delimited by spaces, tabs, or line breaks only. Characters in the puzzle may be any of the printable nonwhitespace ASCII characters: letters, digits, punctuation and special symbols like @#$%^&*()_-+=.
Puzzle File Format The format follows the example above. Rows and columns are indexed for readability. Consecutive characters in the same row of the puzzle are separated by one space. Consecutive rows of the puzzle appear on consecutive lines of the file.
The program handles the puzzle and word list in a completely case-insensitive way. The data files need not use case consistently. The program output need not preserve the case of the input from the data files.
Given a list of N words, each of the 8 compass directions should be used by words in your puzzle at least int(N/8) - 1 times. The number of words wrapped around puzzle boundaries should not be less than the square root of N, and wrapping should occur in all possible directions when N > 25.
Make the puzzles as small as you can, so that the content ratio, i.e., the number of characters used to form words divided by the number of randomly generated characters is relatively high, e.g., greater than about 2.0. (The example given above has a content ratio of approximately 4.0.) A possible strategy is to try to arrange puzzle words so that most puzzle words overlap with at least one other puzzle word. Although your program is not required to find puzzles containing absolute minimal numbers of characters, approximately 15% of your score will be based on how small you are able to make your puzzles relative to those of other students. Explain in your report how you designed your program to make each puzzle as small as you could.
You may reuse in your solution as much of the code as you wish from the online examples referenced above. State in your report which parts of your code are original and which are reused from those examples.
You may restrict the number of words in the word list to be no more than 64. You may use a statically sized 2-D array for this project, as long as it is large enough to hold a puzzle containing 64 words, each of which might be up to 32 characters long. As always, any fixed size limits should be specified in your program as named constants, so that your code can readily be extended to handle cases not within its current limits.

3. Challenge: Diagonal Wrap-Around

Diagonal wrap-around is probably the trickiest part. Therefore, try to obtain a working prototype that does not handle wrap-around on diagonals before you try to implement wrap-around on diagonals. Diagonal wrap-around will not count for more than 5% of your score.

It is possible, though, to incorporate diagonal traversal into the generic framework of the online traversal example. To determine minimum row and column index values for a given diagonal, it helps visually to consider the pattern of first elements in the diagonals. E.g., in a puzzle with shape...

   x x x x x x x x
   x x x x x x x x
   x x x x x x x x
   x x x x x x x x

... consider the following leading elements for diagonals (oriented as "SE", i.e., going from upper left toward the lower right).

   x x x x x x x x
   x
   x
   x

You get one rule for diagonals with i >= j and another for those with i < j. Diagonals oriented as "NW" are similar.

Similarly, for anti-diagonals (oriented as "NE", going from lower left to upper right), it helps to consider the leading elements, as shown below.

   x
   x
   x
   x x x x x x x x

Diagonals oriented as "SW" are similar.

You may find the following observations useful for implementing wrap-around on diagonal and anti-diagonal directions.

For any two locations (i1, j1) and (i2, j2) on the same diagonal (oriented from NW to SE) of a matrix, j1 - i1 == j2 - i2 .
For any two locations (i1, j1) and (i2, j2) on the same antidiagonal (oriented from SW to NE) of a matrix, j1 + i1 == j2 + i2 .

For a puzzle with nRows rows and nCols columns, these invariants give an indexing of the diagonals from -nRows+1 through nCols-1 and the antidiagonals from 0 through nCols+nRows-2.

Additional hints are posted in the FAQ file.

4. Submission

Submit a file p6.zip which produces two files when decompressed: report.xxx and p6.cpp.

Project 6 Home Page