Thread: 3D wordsearch.

  1. #1
    Registered User
    Join Date
    Apr 2011
    Posts
    13

    3D wordsearch.

    Hi, I am trying to write a code to make run 3D wordseach. Basically what I have to do is, I have to read a file that has a grid of wordsearch in it. For example,

    3 3 3
    abc
    def
    ghi

    jkl
    mno
    pqr

    stu
    vwx
    yza

    something like this. One chunk is one level, horizontal line is row, vertical line is column. Numbers at the top indicate numbers of level, row, column. So 'a' would be in Level 1, Row 1, Column 1. Letter 'o' would be in Level 2, Row 2, Column 3.
    Then I also have to call another file that contains a list of words that I am looking for. For examiple,

    3
    abc
    aei
    cny

    like this. words are connected in a straight line, so it can be across the grid too.
    So far, I can read the file and print the grid and the word list, and the following code will do so.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    
    
    int main(int argc, char *argv[])
    {
        FILE *grid_open;
    
        grid_open = fopen(argv[1], "r");
    
        int  L, R, C, r, c;
        char new_line;
    
        fscanf(grid_open, "%d %d %d", &R, &C, &L);
        printf("# of Rows: %d   # of Columns: %d    # of Levels: %d ", R, C, L);
        printf("\n");
    
        fscanf(grid_open, "%c", &new_line);     //new line goes in here
    
    
        char grid [R][C][L];
        int l;
    
    
        for(l = 1; l <= L; l++)
        {
            for(r = 1; r <= R; r++)
            {
                for(c = 1; c <= C; c++)
                {
                    fscanf(grid_open, "%c", &grid[r][c][l]);
                }
                fscanf(grid_open, "%c", &new_line);
            }
            fscanf(grid_open, "%c", &new_line);
        }
    
        for(l = 1; l <= L; l++)
        {
            for(r = 1; r != R + 1; r++)
            {
                for(c = 1; c <= C; c++)
                {
                    printf("%c", grid[r][c][l]);
                }
                printf("\n");
            }
            printf("\n");
        }
    
        FILE *word_open;
    
        word_open = fopen(argv[2], "r");
    
        int  W, w;
    
    
        fscanf(word_open, "%d", &W);
        printf("Words left:\n");
        printf("\n");
    
        fscanf(word_open, "%c", &new_line);     //new line goes in here
    
    
    
        char word[W][C];
    
        for(w = 0; w != W; w++)
        {
            fscanf(word_open, "%s", &word[w][0]);
            puts(word[w]);
        }
    
       return 0;
    }

    Now I have to find the words in the grid one by one, but I am not sure how I would do that. What I am thinking is, go through the grid one by one, and if I find the first letter from the word, I store that letter into string, then look for another letter, and if I find the second letter from the word, add that letter after the first letter.

    So for example, if I am trying to find the word "abc", I start with 'a' in the grid. Since it is the first letter of the word, I store that into string. Then I check the next character from the grid, which is 'b', and since it's the second letter of the word, I use [strcat] to add 'b' into 'a', so the string now contains "ab". Then finally, do the same with 'c', so the string now contains "abc", which is the word I am looking for.

    The problem is, I do not know how to do that . . .
    Can anyone PLEASE help me with this problem?
    It would be a huge help for me.
    Thank you.
    Last edited by jh294; 04-01-2011 at 02:44 AM. Reason: mistake

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > for(l = 1; l <= L; l++)
    Well the first problem is you're stepping off the ends of your arrays in a big way.
    for ( i = 0 ; i < N ; i++ )
    is how you subscript an array.

    Do you know how to solve the 2D word grid problem?

    For a 2D grid, you pick a start point, there are 8 directions to go in which to make a word.

    Once you understand this, the 3D case is very similar.


    Also, you can't (easily) use strcat to append a single letter to a string.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    For every letter, you can have up to 8 different directions or vectors, that need to be checked to see whether they have a letter you're looking for. (Up 2 o'clock, right, 4 o'clock, down, 8 o'clock, left, and 10 o'clock).

    All the letters on the edge rows and columns need careful handling so they don't run out of bounds of the array.

    Let's say you've found A, and now you're looking for B, and find it on the right vector. Now from the B key, you need to check all it's vectors, and if it fails, (no C), then return to A, AND CONTINUE SEARCHING the rest of the unsearched vectors.

    It's a naturally recursive search, but it can be done non-recursively as well.

    Give that a try.

  4. #4
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    Are the words you're going to be searching for always the same length as the axes? Or can they be shorter? Do you allow diagonals?
    As a rough count I get 52 different vectors if you count both directions as well.

  5. #5
    Registered User
    Join Date
    Apr 2011
    Posts
    13
    Quote Originally Posted by nonoob View Post
    Are the words you're going to be searching for always the same length as the axes? Or can they be shorter? Do you allow diagonals?
    As a rough count I get 52 different vectors if you count both directions as well.
    No, the length of the word can be different. It can even be a sing letter 'a'.
    Yes, I also have to search in diagonals as well..

  6. #6
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    Ok, in that case it stands to reason that the search for the first letter can begin at any edge(outside plane) up to width_of_cube - length_of_search.

    An interesting problem to make it "fast". But leave that until later. First get it working.

    How about: search for first letter using i, j, k nested loops.
    From that coordinate, use all possible permutations of "vector" direction:
    add 0,0,1 repeatedly to match subsequent letters
    add 0,1,0...
    add 1,0,0
    add 0,1,1
    add 1,0,1
    add 1,1,0
    add 1,1,1
    That takes care of positive movement along any axis, 1 at-a-time, 2 at-a-time, and all 3.
    Then do same for 0,0,-1... That is, negative movement in all permutations.
    Then do same for mixed +1 and -1 movement in all permutations.

    This first "algorithm" looks messy but you get the idea.

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Can words curve, or do you need straight lines?

    abc
    daf
    zbt

    From any given point, you have potentially 27 different directions you can move. 26 if it's not the first letter of the word, since you wouldn't want backtracking I assume:

    adv
    rab
    kac

    aardvark


    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    Registered User
    Join Date
    Apr 2011
    Posts
    13
    Quote Originally Posted by quzah View Post
    Can words curve, or do you need straight lines?

    abc
    daf
    zbt

    Quzah.
    No~ it can only be a straight line.
    The starting point and the end point are given too.

  9. #9
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    I correct myself. 26 different directions.
    Starting points and ending points are given? That's an odd criteria but it would make searching super easy. Just determine the direction between the two end coordinates and iterate from one to the other. You will know if i, j, k will need to get 0, +1. or -1 respectively in each step just by subtracting the two end points from each other.

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by nonoob View Post
    I correct myself. 26 different directions.
    Actually I'm one off on my numbers, there are 26 neighboring moves if you allow all directions of movement (you are int the 27th spot), and 25 if you can't move where you just came from.

    Quzah.
    Hope is the first step on the road to disappointment.

  11. #11
    Registered User
    Join Date
    Apr 2011
    Posts
    1

    Angry

    You forgot to copy this paragraph from the assignment handout:

    Students will work together in teams, and students (even on different teams) are encouraged to learn from one another. However, each team is expected to develop its own project, and no teams should share code, or even look at each other’s code. The evaluation process at the end of term will include an automated and sophisticated comparison of your programs, which will identify instances of similarity. Such instances will be examined closely. (Really, we’re pretty good at detecting copying of any kind, and changing variable and function names doesn’t help at all. Please: just don’t do it.) Violations of the above rules will be dealt with in accordance with the University of Toronto Code of Behaviour on Academic Matters. You are, however, welcome to use any code in the textbook, presented in lecture, or posted on the portal.

    Oh, and have you asked your team members?

  12. #12
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    Sounds like a fun project. Even posting a possible algorithm here would be doing too much homework for people. What if the 3-D array is 100x100x100 and the search word is length 10? Can a program be written to be fast? Don't tempt me... I live for optimizing stuff.

  13. #13
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    Quote Originally Posted by pgries View Post
    You forgot to copy this paragraph from the assignment handout: ...

    Oh, and have you asked your team members?
    lol, busted!
    Devoted my life to programming...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 3D starfield
    By VirtualAce in forum Game Programming
    Replies: 6
    Last Post: 06-26-2003, 12:40 PM
  2. 3D SDK for C++ programmers
    By chand in forum Game Programming
    Replies: 2
    Last Post: 05-20-2003, 07:38 AM
  3. 3D Engines
    By Peter_D3T in forum C++ Programming
    Replies: 5
    Last Post: 06-22-2002, 03:59 PM
  4. 3d engines
    By Unregistered in forum Game Programming
    Replies: 7
    Last Post: 12-17-2001, 11:19 AM