cstringcrossword

simple C crossword how to avoid duplicate words


I am new here and also new with coding. How can i find a 'bug' in a simple crossword program, written in C, that could, generate (unwanted) duplicate words?

All tips and suggestions are appreciated

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define ROWS 10
#define COLUMNS 10

char puzzle[ROWS][COLUMNS];

char allWords[20][10] = {
    "GIRL", "BOY", "SHIP", "CAT", "FOG",
    "KITE", "BAG", "STAMP", "ZOOM", "JOY",
    "CAR", "BUS", "VAN", "BOAT", "BIKE",
    "TURBO", "SCHOOL", "COVID", "VIRUS", "STAR"
};

char fourWords[4][10];

char getRandomCharacter()
{
    int r = (rand() % 26) + 65;
    return (char)r;
}   

void getFourRandomWords() // This code can generate duplicate words -- try to fix it
{
    int i;

    for (i = 0; i < 4; i++) {
        strcpy(fourWords[i], allWords[rand() % 20]);
    }
}

void createBlankPuzzle()
{
    int i, j;

    for (i = 0; i < ROWS; i++) {
        for (j = 0; j < COLUMNS; j++) {
            puzzle[i][j] = '*';
        }
    }
}

void displayPuzzel()
{
    int i, j, rowNum = 0;
    char x = 'A';
   
    // First display column names
    printf("  ");
    for (i = 0; i < COLUMNS; i++) {
        printf("%c ", x + i);
    }
    printf("\n");

    for (i = 0; i < ROWS; i++) {
        printf("%d ", rowNum);
        rowNum++;
        for (j = 0; j < COLUMNS; j++) {
            printf("%c ", puzzle[i][j]);
        }
        printf("\n");
    }
}

void putHorizzontalWord(char word[10])
{
    int rRow, rCol, ok, i;

    do {
        rRow = rand() % 10;
        rCol = rand() % 10;

        ok = 1;
        if (rCol + strlen(word) < 10) {
            for (i = 0; i < strlen(word); i++) {
                if (puzzle[rRow][rCol + i] == '*' ||
                    puzzle[rRow][rCol + i] == word[i])
                {
                    puzzle[rRow][rCol + i] = word[i];
                } else {
                    ok = 0;
                }
            }
        } else {
            ok = 0;
        }
    } while (ok == 0);
}

void fillPuzzleWithWords()
{
    int i, orientation;
    getFourRandomWords();

    for (i = 0;i < 4;i++) {
        orientation = 0; //rand() % 3; // To generate a random number from 0, 1, & 2
        if (orientation == 0) {
            putHorizzontalWord(fourWords[i]);
        } else
        if(orientation == 1)
        {
            // put word vertical
        } else {
            // put word diagonal
        }
    }
} 

int main(void)
{
    srand(time(NULL));

    createBlankPuzzle();
    fillPuzzleWithWords();
    displayPuzzel();

    getchar();
    return 0;
}

I executed the code about 10 times and it did reproduced the same word three times. The thing is that I do not understand how the word are picked/chosen from that list hence I do not know how to interact with these lines.


Solution

  • In order to produce distinct words, you can simply iterate over the words selected so far to check if the newly drawn word is different from all the previous ones:

    void getFourRandomWords(void) {
        // draw 4 words from the list, no duplicates
        int i, j;
        for (i = 0; i < 4;) {
            const char *w = allWords[rand() % 20];
            for (j = 0; j < i; j++) {
                if (strcmp(fourWords[i], w) == 0)
                    break;
            }
            if (j == i) {
                // add the word if it compared different from all previous ones
                strcpy(fourWords[i], w);
                i++;
            }
        }
    }
    

    The above naive method may be very inefficient if choosing n from n, as a matter of fact it is not even guaranteed to finish.

    Here is a different approach to cap the number of iterations:

    void getFourRandomWords(void) {
        int draws[4];
        // draw 4 words from the list, no duplicates
        for (int i = 0; i < 4; i++) {
            int n = rand() % (20 - i);
            int j;
            for (j = 4 - i; j < 4 && n >= draws[j]; j++) {
                draws[j - 1] = draws[j];
                n++;
            }
            draws[j - 1] = n;
            strcpy(fourWords[i], allWords[n]);
        }
    }
    

    Here is yet another approach with a single loop and linear time and space complexity:

    void getFourRandomWords(void) {
        // list of possible word numbers
        int draws[20] = {  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
                          10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };
        // draw 4 words from the list, no duplicates
        for (int i = 0; i < 4; i++) {
            // draw a number from i to 19
            int n = i + rand() % (20 - i);
            // select the word from the list
            strcpy(fourWords[i], allWords[draws[n]]);
            // swap the word number and the i-th slot
            // this way the selected number is removed from the list
            draws[n] = draws[i];
        }
    }