C++ Sample Project - Need help with algorithm

Question

I had one of my friends send me this programming assignment so I could brush up on some of my C++ skills. Below is the program description and my proposed algorithm. Could someone please provide some feedback/alternative solutions:

Problem:

This program creates word search puzzles - Words are printed at random locations in a rectangular grid. Words may be horizontal or vertical and may be forward (left-to-right or top-to-bottom) or reversed (right-to-left or bottom-to-top). Unused grid squares are filled with random letters. The program should take a set of word lists as input and produce two files as output. The first lists, for each puzzle, the list of words in the puzzle, followed by the puzzle itself. The second should show where in each puzzle the words are located, without the random filler letters

Our input file contains the following: A number n > 0 (representing the # of words in the puzzle) followed by that many words. For example:

3
FRODO
GIMLI
ARAGORN

N will not be larger than 10

We need to create the puzzle using a multidimensional array of size 12 x 12

Requirements:
1. Two output files - One containing the puzzle words and he puzzles, one with only the solutions and no filler characters
2.There needs to be as many horizontal words as there are vertical words
3. A 1/3 of the words needs to be reversed
4. There needs to be at least two intersections in the puzzle

---

Proposed Algorithm:
1. Create two multidimensional arrays - one for the puzzle and one for the solutions
2. Create a one-dimensional array that contains the various letters of the alphabet
3. Fill the puzzles array with random letters of the alphabet (using a pseudo-random # generator and the array from step # 2)
4. Begin reading the input file
5. Read in n
6. While counter is less than n, read in words, also have a counter for vertical words and horizontal words
7. For each word, find the length of the string
8. Find a random array location to insert the word.
9. If random location index + string length <= 12 or if random location index - string length is >= 0 (to ensure that the word will fit forward or reverse) insert the word
10. Also insert the word into the solutions array
12. Reuse arrays to insert all the words in the input file (in a similar manner)

I am still unsure as to how I can ensure that at least two intersections exist.

I am also concerned that my proposed algorithm is unnecessarily convoluted.

Your feedback is greatly appreciated!

---

OK, Here's as far as I got into the coding process, before I decided to go back and revisit the algorithm:

#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <ctime>
using namespace std;

//Error Codes
const int INPUT_FAIL = 1;
const int PUZZLES_OUTPUT_FAIL = 2;
const int SOLUTIONS_OUTPUT_FAIL = 3;

//Function Declarations/Prototypes
void OpenFiles(ifstream& input, ofstream& puzzles, ofstream& solutions);
//PRE:  The filestream objects exist and their address locations are passed in
//POST: The filestreams are opened. If they cannot be opened, an error message is printed to screen
//      and the program is terminated.

void FillArray(char puzzle[][12], char alphabet[]);
//PRE:  The address of the array is passed in
//POST: The array is filled with a random set of 

void CreatePuzzle(char puzzle[][12], ifstream& input, ofstream& puzzles, ofstream& solutions);
//PRE:  The address of the puzzle array,the address of the ifstream object and the addresses of the
//      ofstream objects are passed in.
//POST: The data in the input file is read and the words are input into the puzzle AND the puzzle
//      and solutions are printed to file.

void PrintPuzzle(char puzzle[][12], ofstream& output);
//PRE:  The address of the puzzle array and the ofstream object is passed in
//POST: The puzzle is output to the file

int main()
{
    //Seed the pseudo random generator
    srand(time(NULL));



    //Declare the filestream objects
    ifstream input;
    ofstream puzzles, solutions;

    //Declare the 2D array
    char puzzle[12][12];
    char solution[12][12];

    //Declare an alphabet array
    char alphabet[27] = {"ABCDEFGHIJKLMNOPQRSTUVWXYZ"};
    /*char alphabet[27] = {'A','B','C','D','E','F','G','H','I','J','K','L',
    'M','N','O','P','Q','R','S','T','U','V','W',
    'X','Y','Z'};*/

    //Attempt to open files
    OpenFiles(input, puzzles, solutions);

    //Fill puzzle array with random letters of the alphabet
    FillArray(puzzle, alphabet);

    //Print puzzle
    PrintPuzzle(puzzle, puzzles);

    //Read in data to create puzzle
    input >> numwords;

    return 0;
}



//Function definitions
void OpenFiles(ifstream& input, ofstream& puzzles, ofstream& solutions)
{

    //Attempt to open files
    input.open("input.txt");
    puzzles.open("puzzles2.txt");
    solutions.open("solutions2.txt");

    //Ensure they opened correctly
    if (input.fail())
    {
        cout << "Input file failed to open!" << endl;
        exit(INPUT_FAIL);
    }

    if (puzzles.fail())
    {
        cout << "Output file - puzzles.txt failed to open!" << endl;
        exit(PUZZLES_OUTPUT_FAIL);
    }

    if (solutions.fail())
    {
        cout << "Output file - solutions.txt failed to open" << endl;
        exit(SOLUTIONS_OUTPUT_FAIL);
    }

}


void FillArray(char puzzle[][12], char alphabet[])
{
    int tmp;
    for(int i = 0; i < 12; i++)
    {
        for(int j = 0; j < 12; j++)
        {
            tmp = rand()%26;
            puzzle[i][j] = alphabet[tmp];
        }
    }
}


void PrintPuzzle(char puzzle[][12], ofstream& output)
{
    for(int i = 0; i < 12; i++)
    {
        for(int j = 0; j < 12; j++)
        {
            output <<   puzzle[i][j] << " ";
        }
        output << endl;
    }
}



void CreatePuzzle(char puzzle[][12], ifstream& input, ofstream& puzzles, ofstream& solutions)
{
    string pword; //#the puzzle word being read
    int numwords; //# of words in a given puzzle
    char tmparray[13];
    int wordlength = 0;
    int startloc;

    //Read the number of words to be used in the puzzle
    input >> numwords;

    int vwords = numwords/2; //#of vertical words
    int rwords = numwords/3; //# of reversed words
    int hwords = (numwords - (numwords/2)); //# of horizontal words

    for(int i = 0; i < numwords; i++)
    {
        //Read the word into our tmparray
        input >> pword;
        tmparray[] = pword;
        wordlength = pword.length();

        //Find a random array location to begin inserting the words
        startloc = rand()%12;
    int tmpcount = 0; //a temporary counter to ensure that 
        for(tmpcount; tmpcount <= 1; tmpcount ++)startloc + wordlength < 12)
        {
            for(int j = 0; j <= wordlength; j++)
            {
                puzzle[startloc][startloc]

Answer 1

Try it on paper first
Then make it work (in code)
Then make it fast /efficent / elegant

edit - Sorry I wasn't being sarcastic, this was before the OP posted code, and it wasn't clear they had attempted the problem.

Answer 2

A few thoughts/suggestions:

1. I think you could do this with one single 2D array instead of two. It seems simpler in my mind, though of course you may find I'm wrong when you sit down to actually implement this.
2. At step 9, instead of finding a spot where the word could fit either forward or reversed, first decide which way it's going to go in (perhaps using a random number generator). Then pick a spot and check the first condition, and just insert the word, either forwards or backwards. Remember this is a 2D array though, so you'll need to look at both the x and y coordinates of the point you chose. You'll also have to look at the words you've already placed in the grid, to make sure you don't overwrite something that's already there.
3. For finding intersections, think about how you would do it by hand (like Martin said). You've already placed a few words in the grid and now you want to add a new one. Suppose there aren't many intersections yet so you'd like to have the current word intersect one of the ones already in teh grid, if possible. How do you know if an intersection is possible, and how do you know where to place the word so that it creates an intersection?

Answer 3

My first thoughts are:

1. Place the words first and then randomly fill the gaps. I think it will be much easier for you to visualise it that way and also be easier to check if the word placement is done correctly.
2. After placing the first word I would save the word into an array. After checking if the second word is small enough to fit the puzzle I would have the program find the common letters of word 1 and 2. If they have a common letter, place the second word so the two words intersect(of course you must first check if the way you try to place word 2 is legal aka if it fits the puzzle the way you are trying to place it). Word 3 is the same way except look for possible intersections between words 1 and 2.If there is no possible intersection try the next word. If you can't have 2 or more intersections after placing all words, empty the array and replace the first word in a different random position. After having placed words in such a way that at least two intersections exist, you can continue and place the rest of the words.

Answer 4

My first suggestion would be don't bother pre-filling the array with anything - just stick th words in, and fill in the gaps randomly once you're finished.