Word Search -- Recursively

This is a discussion on Word Search -- Recursively within the C Programming forums, part of the General Programming Boards category; Ahhh! It is the return of the Word Search!!! However, any ideas on how to do it recursively? for instance: ...

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    13

    Word Search -- Recursively

    Ahhh! It is the return of the Word Search!!! However, any ideas on how to do it recursively?

    for instance:

    n t o f u g i r l
    h n d d c s e r c
    e e b d u c s f e
    l f e w e t s e e
    p e s e w s e e e
    e w w s b o o p f
    f s j i w y b s e

    Words to find:
    tofugirl
    help

    Answers:
    tofugirl is located at column 2, row 1 - direction is right
    help is located at column 1, row 1 - direction is down

    Sorry for the alignment of the puzzle. I just made it up -- supposedly a 9 x 9 matrix.

    I made it up as a 12 x 12 matrix to account for the null, and to take out the 0 rows & 0 columns (this doesn't happen in real life).

    Account that words show up across (left to right or right to left), and down (left to right or right to left). no diagonals! (thank goodness!)

    I have something using strstr and using as it != NULL as a base case... but I cannot figure out how to get rid of the traditional
    for ( i = 0; i < rows; i++)
    for(j = 0; j < columns; j++)
    ........ etc........

    and make it recursive!

    Any ideas??? Any code snippet would be much appreciated...

    I have an idea there needs to be 4 functions to check for words - Across, Down, Backwards Across, and Backwards Down.

    Any input?

  2. #2
    Registered User
    Join Date
    Nov 2005
    Posts
    31
    wouldn't it be 16 functions, or 16 checks?

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    One function, four checks. I'm not sure how you're getting sixteen.
    Code:
    for each element in the array, with optional pruning for current XY
    coordinates to EOL subtraction for length of the word to find
        if this letter is the first letter in the word
            function( x, y, north )
            function( x, y, east )
            function( x, y, south )
            function( x, y, west )
    Optionally you can add a few more parameters, such as what word you're looking for, and what letter you're on, etc etc. You don't ever need to check more than the direction you're heading, once you've started on a word, because you don't have words that zig-zag all over, so just keep heading in the same direction until you run out of word, have a full word found, or run out of maze...er...word-search.


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

  4. #4
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,066
    I think he's also assuming the diagonals. Which would be 8, though.

    Maybe he was thinking backwards would be another 8.
    Sent from my iPadŽ

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by tofugirl
    Account that words show up across (left to right or right to left), and down (left to right or right to left). no diagonals! (thank goodness!)


    Also, no, there still wouldn't be sixteen. At the most you're ever going to have is 8. Look at your numberpad. The letter you're searching from as a starting point is the 5. That leaves only ever 8 directions to search. Not sixteen.

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

  6. #6
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,066
    Well, I know there wouldn't be 16. ...but good catch on the "no diagonals" quote. You got me there.
    Sent from my iPadŽ

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by SlyMaelstrom
    Well, I know there wouldn't be 16.
    Don't feel bad. I myself often catch myself trying to unravel the thought process of posters. "How in the hell did they come up with that?" More often than not, it just leads to a head-ache, so I try to catch myself in time...


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

  8. #8
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,066
    I'm not gonna get into this arguement of what I meant.

    I'll let you have it since you, after all, are more experienced here.
    Sent from my iPadŽ

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I took it to mean: "I, of the dancing milk clan, know there aren't 16, but I think sloopy was thinking ..." *shrugs*

    No worries. Oh, and to pull this back on track:

    You could make your recursive function return 1 + the other recursive calls, and 0 on failure. If the total returned equals the length of the word you're looking for, you've got a match.
    Code:
    if( length_of_word_to_find == myfun( ... , heading ) )
    {
        printf("Word %s found at %dX,%dY, heading %s!",
            word, x, y, wordofheading( heading ) );
    }
    Or something akin to that.


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

  10. #10
    Registered User
    Join Date
    Nov 2005
    Posts
    13

    Arrow

    No worries. Oh, and to pull this back on track:

    You could make your recursive function return 1 + the other recursive calls, and 0 on failure. If the total returned equals the length of the word you're looking for, you've got a match.
    Code:
    Code:
    if( length_of_word_to_find == myfun( ... , heading ) )
    {
        printf("Word %s found at %dX,%dY, heading %s!",
            word, x, y, wordofheading( heading ) );
    }Or something akin to that.
    Thanks Quzah. I'll try your suggestion. Would this be used as as a base case in the recursive function? Hopefully I won't produce some infinite recursion......

    Any other ideas also appreciated!
    Last edited by tofugirl; 11-20-2005 at 05:49 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Firefox and Google Search
    By DeepFyre in forum Tech Board
    Replies: 0
    Last Post: 01-16-2005, 09:28 AM
  2. finding strings in strings
    By watshamacalit in forum C Programming
    Replies: 14
    Last Post: 01-11-2003, 12:08 AM
  3. Using 'if' with char arrays or string objects
    By c++_n00b in forum C++ Programming
    Replies: 36
    Last Post: 06-06-2002, 09:04 PM
  4. open file, search of word, replace word with another
    By Unregistered in forum C++ Programming
    Replies: 0
    Last Post: 06-05-2002, 01:16 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21