A Random Walk on a grid

Question

LinDoc 0 Newbie Poster

13 Years Ago

Hi!
I am learning C, and am at very introductory level, using this book called C Programming: A Modern Approach. I have just studied about arrays, and while tackling the programming exercises,i got stuck in Que 9 in Chapter 8.

This is what the question says
Write a program that generates a "random walk" across a 10 x 10 array. The array will contain characters (all '.' initially).The program must "walk" from element to element, always going up,down,left, or right by one element. The elements visited will be labelled with the letters A through Z, in the order visited. Here is an example of the desired output.

see it at the topmost comment

HINT:Use srand and rand functions to generate random numbers. After generating a number, look at its remainder when divided by 4. There are four possibile values: 0,1,2,3 - indicating the direction of next move. Before perfoming a move, check that it doesn't go outside the array and that it doesn't take us to an element already with a letter.If all the four direction are blocked, the program must terminate.

Here is many failed trial. (Though i arrived at this after my trials. Am just not getting it right :sad:)

/*
This is the desired output:

. . U V W . . . . . 
. . T . X Y Z . . . 
Q R S . . . . . . . 
P O N . H G F . . . 
. . M . I . E . . . 
. . L K J . D C B A 
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . . . 
. . . . . . . . . . 


*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#define ROW 10
#define COL 10

int main(){
    char grid [ROW][COL];
    int ro,co;
    char letters = 'A';

    //fill the grid with '.' characters
    for(int r=0; r < ROW; r++){
        for (int c=0;c< COL;c++){
            grid[r][c]='.';
        }
    }

    srand((unsigned)time(NULL));
    //pick starting point
    ro = rand() % ROW;
    co = rand() % COL;
    grid[ro][co]= letters;

    /*
     * Now, taking the random walk.
     * There are 4 possible moves at maximum. I shall consider each at a time
     * I shall label the moves  0, 1 , 2 , 3
     * each reperesents a direcition as follows:
     *
     *          move    direction
     *              0   row++
     *              1   column++
     *              2   row--
     *              3   column--
     */

    //temporary positions for row and column points

    int row = ro;
    int col = co;
    bool blocked = false;

    while(!blocked){              
        int move = rand() % 4;
        switch (move){
            case 0:
                if (grid[++row][col] == '.' && row < ROW ){ //unoccupied position
                    ++ro;
                    grid[ro][co] = ++letters;                 
                    break;
                }
                else{
                    blocked = true;
                    break;
                }
            case 1:
                if (grid[row][++col] == '.' && col < COL){ //unoccupied position
                    ++co;
                    grid[ro][co] = ++letters;
                    
                    break;
                }else{
                    blocked = true;
                    break;
                }
            case 2:
                if (grid[--row][col] == '.' && row < ROW){ //unoccupied position
                    --ro;
                    grid[ro][co] = ++letters;
                    
                    break;
                }else{
                    blocked = true;
                    break;
                }
            case 3:
                if (grid[row][--co] == '.' & col < COL){ //unoccupied position
                    --co;
                    grid[ro][co] = ++letters;
                    
                    break;
                }else{
                    blocked = true;
                    break;
                }
        }
        if (blocked)
            break;
    }  
    //print the walk
    for(int r=0; r < ROW; r++){
        for (int c=0;c< COL;c++){
            printf("%c ",grid[r][c]);
        }
        printf("\n");
    }

    return 0;
}

Please, give me a better approach. Limit the approach to arrays and control structures. No functions.

c multidimensional random walk

3 Contributors
13 Replies
2K Views
1 Year Discussion Span
Latest Post 11 Years Ago Latest Post by pizFunk

All 13 Replies

WaltP 2,905 Posting Sage w/ dash of thyme

13 Years Ago

if ro=0 and co=5, if (grid[ro-1][co] == '.' && ro-1 < ROW) will first test grid(-1,5). Is that a valid test?

WaltP 2,905 Posting Sage w/ dash of thyme

13 Years Ago

It's still stupid of you. You didn't even bother to read what I posted.

Again, what are you testing when ro = 0?

WaltP 2,905 Posting Sage w/ dash of thyme

13 Years Ago

Last time. What is the value of grid[-1][0] ? You are checking that location. Same with grid[0][-1]

Edited 13 Years Ago by WaltP because: n/a

WaltP 2,905 Posting Sage w/ dash of thyme

13 Years Ago

How does the && prevent it?

If you have A && B ,
1) how can you guarantee A is not evaluated because B is FALSE?
2) how do you know A isn't evaluated first?
3) how do you know they both aren't evaluated, then the && is performed at the end?

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

LinDoc 0 Newbie Poster · Answer 1 · 2011-03-02T21:07:22+00:00

I have made a few corrections "walking stage" . I generates a more sensible output, although the "walk" is very brief or rather incomplete, Take a look.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#define ROW 10
#define COL 10

int main(){
    char grid [ROW][COL];
    int ro,co;
    char letters = 'A';

    //fill the grid with '.' characters
    for(int r=0; r < ROW; r++){
        for (int c=0;c< COL;c++){
            grid[r][c]='.';
        }
    }

    srand((unsigned)time(NULL));

    //pick starting point
    ro = rand() % ROW;
    co = rand() % COL;
    grid[ro][co]= letters;

    /*
     * Now, taking the random walk.
     * There are 4 possible moves at maximum. I shall consider each at a time
     * I shall label the moves  0, 1 , 2 , 3
     * each reperesents a direcition as follows:
     *
     *          move    direction
     *              0   row++
     *              1   column++
     *              2   row--
     *              3   column--
     */

    

    
    bool blocked = false;

    while(!blocked){
        
        
        int move = rand() % 4;
        switch (move){
            case 0:
                if (grid[ro +1][co] == '.' && ro +1 < ROW ){ //unoccupied position
                    ++ro;
                    grid[ro][co] = ++letters;
                    
                    break;
                }
                else{
                    blocked = true;
                    break;
                }
            case 1:
                if (grid[ro][co+1] == '.' && co + 1 < COL){ //unoccupied position
                    ++co;
                    grid[ro][co] = ++letters;
                    
                    break;
                }else{
                    blocked = true;
                    break;
                }
            case 2:
                if (grid[ro-1][co] == '.' && ro-1 < ROW){ //unoccupied position
                    --ro;
                    grid[ro][co] = ++letters;
                    
                    break;
                }else{
                    blocked = true;
                    break;
                }
            case 3:
                if (grid[ro][co-1] == '.' & co-1 < COL){ //unoccupied position
                    --co;
                    grid[ro][co] = ++letters;
                    
                    break;
                }else{
                    blocked = true;
                    break;
                }

        }
        if (blocked)
            break;

    }
  


    //print the walk
    for(int r=0; r < ROW; r++){
        for (int c=0;c< COL;c++){
            printf("%c ",grid[r][c]);
        }
        printf("\n");
    }

    return 0;
}

LinDoc 0 Newbie Poster · Answer 2 · 2011-03-02T22:35:09+00:00

if ro=0 and co=5, if (grid[ro-1][co] == '.' && ro-1 < ROW) will first test grid(-1,5). Is that a valid test?

That was stupid of me. It should be if

(grid[ro-1][co] == '.' && ro-1 > 0)

I just got the whole thing working, though i can't handle dead end situations, only situations that Z is reached. I will post for you to have a look.

LinDoc 0 Newbie Poster · Answer 3 · 2011-03-05T00:56:58+00:00

When ro = 0, then i know that i shouldn't move in that direction.

Anyway, here is my working one, please check it out and point out better approaches in you can

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#define ROW 10
#define COL 10
#define LEFT 0
#define UP 1
#define RIGHT 2
#define DOWN 3

int main(){
    char grid [ROW][COL];
    int ro,co;
    char letters = 'A';

    //fill the grid with '.' characters
    for(int r=0; r < ROW; r++){
        for (int c=0;c< COL;c++){
            grid[r][c]='.';
        }
    }

    srand((unsigned)time(NULL));

    //pick starting point
    ro = rand() % ROW;
    co = rand() % COL;
    grid[ro][co]= letters;

    /*
     * Now, taking the random walk.
     * There are 4 possible moves at maximum. I shall consider each at a time
     * I shall label the moves  0, 1 , 2 , 3
     * each reperesents a direcition as follows:
     *
     *          move    direction
     *              0   row++
     *              1   column++
     *              2   row--
     *              3   column--
     */

    //temporary positions for row and column points

    
    
    
    bool blocked = false;

    while( 1){
        int move = rand() % 4;

        switch (move){
            case RIGHT:
                if (grid[ro+1][co] == '.' && ro+1 < ROW){ //unoccupied position
                    ++ro;
                    grid[ro][co] = ++letters;
                    break;
                }else if (grid[ro][co+1] == '.' && co + 1 < COL){ //unoccupied position
                        ++co;
                        grid[ro][co] = ++letters;
                        break;
                }else if (grid[ro-1][co] == '.' && ro-1 >= 0){ //unoccupied position
                        --ro;
                        grid[ro][co] = ++letters;
                        break;
                }else if (grid[ro][co-1] == '.' && co-1 >=0){ //unoccupied position
                        --co;
                        grid[ro][co] = ++letters;
                        break;
                }else{
                    blocked = true;
                    break;
                }
            
            case UP: 
                if (grid[ro][co+1] == '.' && co + 1 < COL){ //unoccupied position
                        ++co;
                        grid[ro][co] = ++letters;
                        break;
                }else if (grid[ro+1][co] == '.' && ro+1 < ROW){ //unoccupied position
                    ++ro;
                    grid[ro][co] = ++letters;
                    break;
                }else if (grid[ro-1][co] == '.' && ro-1 >= 0){ //unoccupied position
                        --ro;
                        grid[ro][co] = ++letters;
                        break;
                }else if (grid[ro][co-1] == '.' && co-1 >=0){ //unoccupied position
                        --co;
                        grid[ro][co] = ++letters;
                        break;
                }else{
                    blocked = true;
                    break;
                }
            
            case LEFT:
                if (grid[ro-1][co] == '.' && ro-1 >= 0){ //unoccupied position
                        --ro;
                        grid[ro][co] = ++letters;
                        break;
                }else if (grid[ro][co-1] == '.' && co-1 >=0){ //unoccupied position
                        --co;
                        grid[ro][co] = ++letters;
                        break;
                } else if (grid[ro][co+1] == '.' && co + 1 < COL){ //unoccupied position
                        ++co;
                        grid[ro][co] = ++letters;
                        break;
                }else if (grid[ro+1][co] == '.' && ro+1 < ROW){ //unoccupied position
                    ++ro;
                    grid[ro][co] = ++letters;
                    break;
                }else{
                    blocked = true;
                    break;
                }
            
         case DOWN:
            if (grid[ro][co-1] == '.' && co-1 >=0){ //unoccupied position
                        --co;
                        grid[ro][co] = ++letters;
                        break;
                } else if (grid[ro+1][co] == '.' && ro+1 < ROW){ //unoccupied position
                    ++ro;
                    grid[ro][co] = ++letters;
                    break;
                }else if (grid[ro][co+1] == '.' && co + 1 < COL){ //unoccupied position
                        ++co;
                        grid[ro][co] = ++letters;
                        break;
                }else if (grid[ro-1][co] == '.' && ro-1 >= 0){ //unoccupied position
                        --ro;
                        grid[ro][co] = ++letters;
                        break;
                }else {
                    blocked = true;
                    break;
                }

        }
        if (blocked || letters > 'Y')
            break;
        }
  


    //print the walk
    for(int r=0; r < ROW; r++){
        for (int c=0;c< COL;c++){
            printf("%c ",grid[r][c]);
        }
        printf("\n");
    }

    return 0;
}

LinDoc 0 Newbie Poster · Answer 4 · 2011-03-05T01:31:24+00:00

am not checking those locations.....there is the other "&& part" that prevents that e.g

grid[ro][co-1] == '.' && co-1 >=0

LinDoc 0 Newbie Poster · Answer 5 · 2011-03-05T02:03:32+00:00

Or what is it that am not seeing.Please elaborate.

LinDoc 0 Newbie Poster · Answer 6 · 2011-03-05T12:05:14+00:00

Then I suppose the expression should be co-1 >=0 && grid[ro][co-1] == '.' so that am assured that the points being tested are within the array. Is that not so?

WaltP 2,905 Posting Sage w/ dash of thyme Team Colleague · Answer 7 · 2011-03-05T12:57:36+00:00

Then I suppose the expression should be co-1 >=0 && grid[ro][co-1] == '.' so that am assured that the points being tested are within the array. Is that not so?

Please turn your brain on and read and think about what I said:

If you have A && B ,
1) how can you guarantee A is not evaluated because B is FALSE?
2) how do you know A isn't evaluated first?
3) how do you know they both aren't evaluated, then the && is performed at the end?

And to corollary of #2
2') how do you know B isn't evaluated first?

LinDoc 0 Newbie Poster · Answer 8 · 2011-03-05T13:22:00+00:00

Well, this is what i know in my limited knowledge...
Considering A && B If A is true, then B is returned.
If A is false, then A is returned.

About your questions,

If you have A && B ,
1) how can you guarantee A is not evaluated because B is FALSE?
2) how do you know A isn't evaluated first?
3) how do you know they both aren't evaluated, then the && is performed at the end?

A will be evaluated first, always. If it is true, then B is returned, whether true or false. And, I don't get what you mean by the third question.

I still believe that co-1 >=0 && grid[ro][co-1] == '.' is OK.

PS: With all due respect, my brain is not off. I appreciate your knowledge, but i would rather you stop commenting on this thread than continue insulting me.

pizFunk 0 Newbie Poster · Answer 9 · 2013-01-01T22:09:12+00:00

The previous comments seemed way too complicated so I decided to post mine. Also, the other code seemed to be stopping when any direction was blocked, whereas the solution was to only terminate when all directions were blocked. My solution:

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

#define GRID_SIZE 10

int main(int argc, char *argv[])
{
    char grid[GRID_SIZE][GRID_SIZE];
    bool direction_tried[4] = {false};
    int direction, i, j, i2, j2;
    char letter = 'A';

    for (i = 0; i < GRID_SIZE; i++)
    {
        for (j = 0; j < GRID_SIZE; j++)
        {
            grid[i][j] = '.';
        }
    }
    srand((unsigned) time(NULL));

    i = j = 0;
    grid[i][j] = letter++;
    while (letter <= 'Z')
    {
        i2 = i;
        j2 = j;
        direction = rand() % 4;
        switch (direction)
        {
            case 0: i2++;direction_tried[0] = true;break;
            case 1: j2++;direction_tried[1] = true;break;
            case 2: i2--;direction_tried[2] = true;break;
            case 3: j2--;direction_tried[3] = true;break;
        }
        if (i2 > -1 && j2 > -1 && i2 < GRID_SIZE && j2 < GRID_SIZE && grid[i2][j2] == '.')
        {
            i = i2;
            j = j2;
            grid[i][j] = letter++;
            direction_tried[0] = direction_tried[1] = direction_tried[2] = direction_tried[3] = 0;
        }
        else if (direction_tried[0] && direction_tried[1] && direction_tried[2] && direction_tried[3])
        {
            printf("blocked in all directions! %d, %d\n", i2, j2);
            break;
        }
        else
        {
            printf("blocked! %d, %d\n", i2, j2);
        }
    }
    for (i = 0; i < GRID_SIZE; i++)
    {
        for (j = 0; j < GRID_SIZE; j++)
        {
            printf("%c ", grid[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

A Random Walk on a grid

Recommended Answers Collapse Answers

All 13 Replies

Recommended Answers