A Random Walk on a grid

[LinDoc]

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.

[LinDoc]

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;
}

[WaltP]

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?

[LinDoc]

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.

[WaltP]

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

Again, what are you testing when ro = 0?

[LinDoc]

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;
}

[WaltP]

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

[LinDoc]

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

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

[LinDoc]

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

[WaltP]

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?

[LinDoc]

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]

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]

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]

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");
}