Tips anyone

Discussion in 'C++' started by pleatofthepants, Feb 29, 2008.

  1. Ok, I have to solve the "Rat Maze" problem"

    I am opening a file called maze.txt which looks similar to this

    20 *this is # of rows
    20 *this is # of columns
    9 *starting row
    9 *starting column
    11111111111111101111
    10101010101010101011
    10000010001000101001
    10111000100010000011
    10111111111111111011
    etc....

    I have to find the path out of the maze using recursion

    This is what I have come up with for the recursion function, ant tips?

    int maze(int data[][])
    {
    data[r][c];

    if( data[r][0] | data[0][c] | data[r][19] | data[19][c] == 0) //
    base case
    {
    cout << "The Rat Is Free!" << endl;
    }
    if( data[r+1][c] == 0 )
    {
    cout << "Move Up" << endl;
    return maze(data[r+1][c]);
    }

    if ( data[r-1][c] == 0 )
    {
    cout << "Move Down" << endl;
    return maze(data[r-1][c]);
    }

    if ( data[r][c+1] == 0 )
    {
    cout << "Move Right" << endl;
    return maze(data[r][c+1]);
    }

    if ( data[r][c-1] == 0 )
    {
    cout << "Move Left" << endl;
    return maze(data[r][c-1]);
    }

    else
    {
    cout << "Rat your are stuck" << endl;
    }
    }
     
    pleatofthepants, Feb 29, 2008
    #1
    1. Advertising

  2. pleatofthepants

    Klarth Guest

    On Feb 29, 2:17 pm, pleatofthepants <> wrote:
    > Ok, I have to solve the "Rat Maze" problem"
    >
    > I am opening a file called maze.txt which looks similar to this
    >
    > 20 *this is # of rows
    > 20 *this is # of columns
    > 9 *starting row
    > 9 *starting column
    > 11111111111111101111
    > 10101010101010101011
    > 10000010001000101001
    > 10111000100010000011
    > 10111111111111111011
    > etc....
    >
    > I have to find the path out of the maze using recursion
    >
    > This is what I have come up with for the recursion function, ant tips?
    >
    > int maze(int data[][])
    > {
    > data[r][c];
    >
    > if( data[r][0] | data[0][c] | data[r][19] | data[19][c] == 0) //
    > base case
    > {
    > cout << "The Rat Is Free!" << endl;
    > }
    > if( data[r+1][c] == 0 )
    > {
    > cout << "Move Up" << endl;
    > return maze(data[r+1][c]);
    > }
    >
    > if ( data[r-1][c] == 0 )
    > {
    > cout << "Move Down" << endl;
    > return maze(data[r-1][c]);
    > }
    >
    > if ( data[r][c+1] == 0 )
    > {
    > cout << "Move Right" << endl;
    > return maze(data[r][c+1]);
    > }
    >
    > if ( data[r][c-1] == 0 )
    > {
    > cout << "Move Left" << endl;
    > return maze(data[r][c-1]);
    > }
    >
    > else
    > {
    > cout << "Rat your are stuck" << endl;
    > }
    >
    > }


    The way it is currently written, it looks like you get some confusing
    output! For example, I can see that it is possible for your program's
    output to be:

    The Rat Is Free!
    Rat your are stuck

    Or even a combination of "The Rat Is Free" and one of the other
    movement messages (and make further unnecessary moves). Also, if your
    rat finds a dead end, how does your algorithm prevent going backwards
    and towards the start? I don't see how you keep track of which
    direction the rat came from, so it looks like your algorithm will
    retry going in the direction that you came from.

    On a large maze, it also looks like there is going to a heck of a lot
    of recursive calls. Perhaps you can move forward using a while loop
    and use recursive call to change or try different directions?
     
    Klarth, Feb 29, 2008
    #2
    1. Advertising

  3. pleatofthepants

    Jim Langston Guest

    pleatofthepants wrote:
    > Ok, I have to solve the "Rat Maze" problem"
    >
    > I am opening a file called maze.txt which looks similar to this
    >
    > 20 *this is # of rows
    > 20 *this is # of columns
    > 9 *starting row
    > 9 *starting column
    > 11111111111111101111
    > 10101010101010101011
    > 10000010001000101001
    > 10111000100010000011
    > 10111111111111111011
    > etc....
    >
    > I have to find the path out of the maze using recursion
    >
    > This is what I have come up with for the recursion function, ant tips?
    >
    > int maze(int data[][])
    > {
    > data[r][c];
    >
    > if( data[r][0] | data[0][c] | data[r][19] | data[19][c] == 0) //
    > base case
    > {
    > cout << "The Rat Is Free!" << endl;
    > }
    > if( data[r+1][c] == 0 )
    > {
    > cout << "Move Up" << endl;
    > return maze(data[r+1][c]);
    > }
    >
    > if ( data[r-1][c] == 0 )
    > {
    > cout << "Move Down" << endl;
    > return maze(data[r-1][c]);
    > }
    >
    > if ( data[r][c+1] == 0 )
    > {
    > cout << "Move Right" << endl;
    > return maze(data[r][c+1]);
    > }
    >
    > if ( data[r][c-1] == 0 )
    > {
    > cout << "Move Left" << endl;
    > return maze(data[r][c-1]);
    > }
    >
    > else
    > {
    > cout << "Rat your are stuck" << endl;
    > }
    > }


    There is an algorithm for pathfinding that would work perfect for this, but
    I'm fairly sure this is homework and the professor wants you to come up with
    your own algorithm.

    Think of it this way though as a general idea.

    Look at your current position and see if it is free.
    If not call this function with one position north.
    If not call this function with one positon south.
    If not call this function with one postion east.
    If not call this function with one positon south.

    That is a very base and doesn't take into account a lot of things which you
    need to code for. The function will need to be called wtih the postion to
    check, and also need to return something indicating what it found there.
    Impassible, opne or free.

    Also, it won't find the most effecient way out, just a way out.

    Another possibiltiy is the right wall way. You follow a right wall (or left)
    until you are out. This works in all mazes such as this unless the walls
    are not continiguous.

    I don't want to give too much because this is info, but the function you
    have shown is not recursive at all. A recursive function calls itself.


    --
    Jim Langston
     
    Jim Langston, Feb 29, 2008
    #3
  4. pleatofthepants

    Triple-DES Guest

    On 29 Feb, 11:19, "Jim Langston" <> wrote:
    > I don't want to give too much because this is info, but the function you
    > have shown is not recursive at all.  A recursive function calls itself.


    His function is recursive, look at the points of exit.

    DP
     
    Triple-DES, Feb 29, 2008
    #4
  5. pleatofthepants

    James Kanze Guest

    On Feb 29, 12:33 pm, Triple-DES <> wrote:
    > On 29 Feb, 11:19, "Jim Langston" <> wrote:


    > > I don't want to give too much because this is info, but the
    > > function you have shown is not recursive at all. A
    > > recursive function calls itself.


    > His function is recursive, look at the points of exit.


    Yes. The problem is that recursion isn't enough; he needs
    backtracking. Basically, at each level of recursion, try up,
    right, down and left until one works. The recursive function
    must return a value to indicate whether it succeeded or not.
    Basically, a loop along the lines of:

    bool
    try( position )
    {
    bool found = false ;
    for ( direction in up, right, down, left and ! found ) {
    if ( open( position + direction ) &&
    ! visited( position + direction ) ) {
    found = try( position + direction ) ;
    }
    }
    return found ;
    }

    (Obviously, this needs a good deal of fleshing out. That for
    isn't going to pass as written, and you also need checks to end
    the recursion, and possibly to avoid wandering off the edges of
    the maze---although that could also be handled in open(). But
    the basic idea is there. And I sort of like the idea of
    declaring direction as an enum, with position a class type which
    defined addition with a direction. But then, I've already got a
    small program which will generate an iterator over an enum, so
    the for loop becomes very simple.)

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Feb 29, 2008
    #5
  6. pleatofthepants

    red floyd Guest

    pleatofthepants wrote:
    > Ok, I have to solve the "Rat Maze" problem"
    >
    > I am opening a file called maze.txt which looks similar to this
    >
    > 20 *this is # of rows
    > 20 *this is # of columns
    > 9 *starting row
    > 9 *starting column
    > 11111111111111101111
    > 10101010101010101011
    > 10000010001000101001
    > 10111000100010000011
    > 10111111111111111011
    > etc....
    >
    > I have to find the path out of the maze using recursion
    >
    > This is what I have come up with for the recursion function, ant tips?
    >
    > int maze(int data[][])

    This line should not compile.
    > {
    > data[r][c];

    this line is bad.

    >
    > if( data[r][0] | data[0][c] | data[r][19] | data[19][c] == 0) //
    > base case
    > {
    > cout << "The Rat Is Free!" << endl;
    > }
    > if( data[r+1][c] == 0 )
    > {
    > cout << "Move Up" << endl;
    > return maze(data[r+1][c]);
    > }
    >
    > if ( data[r-1][c] == 0 )
    > {
    > cout << "Move Down" << endl;
    > return maze(data[r-1][c]);
    > }
    >
    > if ( data[r][c+1] == 0 )
    > {
    > cout << "Move Right" << endl;
    > return maze(data[r][c+1]);
    > }
    >
    > if ( data[r][c-1] == 0 )
    > {
    > cout << "Move Left" << endl;
    > return maze(data[r][c-1]);
    > }
    >
    > else
    > {
    > cout << "Rat your are stuck" << endl;
    > }
    > }
     
    red floyd, Feb 29, 2008
    #6
  7. pleatofthepants

    Jim Langston Guest

    Triple-DES wrote:
    > On 29 Feb, 11:19, "Jim Langston" <> wrote:
    >> I don't want to give too much because this is info, but the function
    >> you have shown is not recursive at all. A recursive function calls
    >> itself.

    >
    > His function is recursive, look at the points of exit.


    yes, you are right. I missed that. It's just not effective.

    --
    Jim Langston
     
    Jim Langston, Mar 1, 2008
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kent P. Iler
    Replies:
    2
    Views:
    533
    Kent P. Iler
    Sep 18, 2003
  2. JDS

    Anyone?? Anyone at all??

    JDS, Sep 26, 2005, in forum: HTML
    Replies:
    2
    Views:
    406
    Montgomery BOO...URNS
    Sep 29, 2005
  3. Steve Williams

    Anyone? Anyone?

    Steve Williams, Sep 16, 2003, in forum: Python
    Replies:
    0
    Views:
    408
    Steve Williams
    Sep 16, 2003
  4. gregarican

    Anyone, anyone...Bueller?

    gregarican, Jun 22, 2007, in forum: Ruby
    Replies:
    2
    Views:
    113
    gregarican
    Jun 22, 2007
  5. Replies:
    1
    Views:
    3,406
    Arne Vajhøj
    Jul 31, 2012
Loading...

Share This Page