Random walk in 10X10 grid array

Question

I have to print a random walk (letters A-Z) in a 10X10 grid array, moving in either direction so long as the move doesn't exit the array and doesn't overlap with existing letter.

My output is a full grid of '.' with no letter save the 'A' to mark the start.

I saw the solution and concerning the conditional tests and cases I see no difference with my own.

I've tried to comment out the tests and check if the loop puts a random direction number and next letter correctly and it does so. However, it seems the issue lies on the test, but I insist that the answer doesn't (in appearance at least) differ from mine.

Here is my program:

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

main()
{
    char t[10][10] = {0}, c;
    int i, j, dir;

    srand((unsigned) time(NULL));
    t[0][0] = 'A';

    for (c='B'; c <= 'Z'; c++) {
        dir = rand() % 4;
        // printf("%c\t%d\n\n", c, dir);  // Here proves to be correct if tests are omitted

        if (dir == 0 && i+1 < 10 && t[i+1][j] == '.')
            t[++i][j] = c;
        else if (dir == 1 && j+1 < 10 && t[i][j+1] == '.')
            t[i][++j] = c;
        else if (dir == 2 && i-1 >= 0 && t[i-1][j] == '.')
            t[--i][j] = c;
        else if (dir == 3 && j-1 >= 0 && t[i][j-1] == '.')
            t[i][--j] = c;
        else 
            break; 
    }

    for (i = 0; i < 10; i++) {
        for (j = 0; j < 10; j++) {
            if (t[i][j] == 0) 
                t[i][j] = '.';
            printf("%c ", t[i][j]);
        }
        printf("\n");
    }

    return 0;
} 

Answer 1

Paraphrasing existing review comments of OP's code:

1. char t[][] is not initialised to satisfy later expectations.
2. int i, j are not initialised, so cannot be trusted and UB is possible.
3. No provision for trying alternative "direction" if first was not possible.
4. Entry point should be int main( void ) {, not simply main() {.

---

Here is an approach that solves this challenge.

Departing from OP's 10x10 grid, this uses a 12x12 grid that simplifies "boundary checking".
All cells set to '.', then edge cells set to SP.
Simplifies conditional that evaluates legal moves.

All 24 permutations of 'N', 'E', 'S' and 'W' are available.
Each substring is a terminated C string.
Code randomly selects one of the 24 unique permutations.
(Previously posted version started with a random direction, but always tested 2nd, 3rd and 4th possibilities in the same sequence.)

The rest should be somewhat self-evident. Pleased post questions as comments below.

"Tracing" (left active) shows each direction tested as trials are made.

This sort of challenge is a textbook application of do/while; the first iteration is always executed before the loop conditional needs to be tested.

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

void play( void ) {
    const int SZ = (1 + 10 + 1); // SP, 10x dots, SP
    char g[ SZ ][ SZ ]; // the 12x12 grid
    int i; // general purpose

    memset( g, '.', sizeof g ); // fill grid with '.'
    for( i = 0; i < SZ; i++ )
        g[0][i] = g[ SZ-1 ][i] = // top & bottom ...
        g[i][0] = g[i][ SZ-1 ] = ' '; // left & right cells to SP

    char ch = 'A', *d, *gp = &g[5][5]; // initial location
    do {
        char *drs = // 24 unique permutations
            "NESW\0" "NEWS\0" "NSEW\0" "NSWE\0" "NWES\0" "NWSE\0"
            "ENSW\0" "ENWS\0" "ESNW\0" "ESWN\0" "EWNS\0" "EWSN\0"
            "SENW\0" "SEWN\0" "SNEW\0" "SNWE\0" "SWEN\0" "SWNE\0"
            "WENS\0" "WESN\0" "WNES\0" "WNSE\0" "WSEN\0" "WSNE\0";
        d = drs + (rand() % 24) * (4+1); // random select
        do {
            // decode alpha to pointer adjustment
            i = *d=='N' ? -SZ : *d=='S' ? SZ : *d=='E' ? 1 : /*'W'*/ -1;
            putchar( *d ); // tracing (optional)
        } while( gp[i] != '.' && *(++d) ); // unavailable? try next direction
        if( *d ) { // have not exhausted list of 4 directions?
            printf( ":%c ", ch ); // tracing (optional)
            *(gp += i) = ch; // update ptr; assign letter to cell
        }
    } while( *d && ++ch <= 'Z' ); // succeeded and more to go
    printf( " == last('%c')\n", ch - 1 ); // tracing (optional)

    for( i = 1; i <= SZ-2; i++ )
        printf( "%.*s\n", SZ-2, &g[i][1] ); // report 10x10
}

int main( void ) { // simple repeated testing
    srand( time( NULL ) );

    do { play(); puts( "Again?" ); } while( getchar() != EOF );

    return 0;
}

Result:

// continuous (tracing) lines broken for easy reading
E:A N:B SE:C WS:D S:E NW:F S:G \
E:H E:I S:J W:K NW:L NS:M NE:N \
S:O E:P N:Q WSNE:R             \ // tried 4 dirs to place 'R'
S:S WSE:T SEN:U N:V SN:W EN:X  \
SN:Y SN:Z == last('Z')           // completed to end
..........
..........
..........
.....BC..Z
.....AD..Y
.....FE..X
.....GHI.W
.....LKJ.V
.....MNQRU
......OPST
Again?

W:A E:B S:C S:D S:E NW:F W:G \
N:H E:I N:J SENW:K           \ // 'K' was difficult
SW:L W:M S:N S:O WE:P EN:Q   \
SWEN == last('Q')              // could not place 'R' (next)
..........
..........
..........
..........
...AB.....
MLKJC.....
NQHID.....
OPGFE.....
..........
..........
Again?

W:A W:B EW:C S:D NS:E E:F N:G NWSE:H \
WS:I NWE:J WE:K WS:L S:M W:N S:O E:P \
SWE:Q E:R SE:S SE:T EWSN:U W:V N:W N:X N:Y N:Z  == last('Z')
..........
..........
..........
..........
.CBA....Z.
.DGH....Y.
.EFIJK..X.
.....L..W.
....NM..VU
....OPQRST
Again?

Answer 2

There are two major issues apart from the erroneous main signature (that should be int main(void)) and the variables i and j that are read while having indeterminate values:

• You never put a '.' in your t array so all tests for '.' will fail.

This is in response to "if there is an existing path with no previous letters you may continue and not break":

• Your loop exits as soon as it has tried to move in one direction but failed. There are three other directions to try so you need to keep track of untested directions.

Example:

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

enum { down, right, up, left };

void Seed(void) {
    struct timespec ts = {0};
    timespec_get(&ts, TIME_UTC);
    srand(ts.tv_sec * 1000000000ull + ts.tv_nsec);
}

int main(void) {
    Seed();

    const int moves[][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    char t[10][10];
    memset(t, '.', sizeof t);  // fill the array with `.`
    int i = 0, j = 0;

    t[0][0] = 'A';

    for (char c = 'B'; c <= 'Z'; c++) {
        // candidate directions:
        int dirs[] = {down, right, up, left};
        int sel = 4;  // start with 4 possible directions to select

        for (;;) {
            int s = rand() % sel;  // pick one
            int dir = dirs[s];

            int ii = i + moves[dir][0];  // add the selected move to
            int jj = j + moves[dir][1];  // get a candidate position

            // is this position valid?
            if (ii >= 0 && ii < 10 && jj >= 0 && jj < 10 && t[ii][jj] == '.') {
                // it's valid, move there and put the letter in it
                i = ii;
                j = jj;
                t[i][j] = c;
                break;  //
            } else if (--sel) {
                // invalid position, remove this direction from the
                // candidates and reduce the number of directions to test
                dirs[s] = dirs[sel];
            } else {
                break;  // we got stuck, give up
            }
        }
        if (sel == 0) break;  // we've given up
    }

    for (i = 0; i < 10; i++) {
        for (j = 0; j < 10; j++) {
            printf("%c ", t[i][j]);
        }
        putchar('\n');
    }
}

Answer 3

As others have identified the core issues with your code, it may be instructive to see an implementation that removes the use of "magic numbers" and allows for the grid size to be readily altered by means of compile time constants.

By having an array of the four possible directions, we can shuffle this to get random directions in deterministic time, then iterate over those until we find a suitable direction to move (or until we don't).

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

#define WIDTH 10
#define HEIGHT 10
#define NUM_DIRS 4

enum Dir {
    UP, DOWN, LEFT, RIGHT
};

enum Edge {
    TOP_EDGE, BOTTOM_EDGE,
    LEFT_EDGE, RIGHT_EDGE
};

enum Dir dirs[NUM_DIRS] = {UP, DOWN, LEFT, RIGHT};

void shuffle_dirs();
bool at_edge(size_t x, size_t y, enum Edge e);
bool position_used(char grid[HEIGHT][WIDTH], size_t x, size_t y);

int main(void) {
    srand(time(NULL));

    char *alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    size_t x = 0;
    size_t y = 0;

    char grid[HEIGHT][WIDTH] = {0};

    grid[y][x] = alphabet[0];

    for (char *ch = &alphabet[1]; *ch; ch++) {
        shuffle_dirs();

        bool move_possible = false;

        for (size_t i = 0; i < NUM_DIRS && !move_possible; i++) {
            switch (dirs[i]) {
                case UP:
                if (at_edge(x, y, TOP_EDGE)) continue;
                if (position_used(grid, x, y - 1)) continue;
                grid[--y][x] = *ch;
                move_possible = true;
                break;

                case DOWN:
                if (at_edge(x, y, BOTTOM_EDGE)) continue;
                if (position_used(grid, x, y + 1)) continue;
                grid[++y][x] = *ch;
                move_possible = true;
                break;

                case LEFT:
                if (at_edge(x, y, LEFT_EDGE)) continue;
                if (position_used(grid, x - 1, y)) continue;
                grid[y][--x] = *ch;
                move_possible = true;
                break;

                case RIGHT:
                if (at_edge(x, y, RIGHT_EDGE)) continue;
                if (position_used(grid, x + 1, y)) continue;
                grid[y][++x] = *ch;
                move_possible = true;
                break;
            }
        }

        if (!move_possible) {
            fprintf(stderr, "Could not complete walk.\n");
            return 1;
        }
    }

    for (size_t i = 0; i < HEIGHT; i++) {
        for (size_t j = 0; j < WIDTH; j++) {
            if (!grid[i][j]) printf(".");
            else printf("%c", grid[i][j]);
        }
        printf("\n");
    }

    return 0;
}

void shuffle_dirs() {
    for (size_t i = 0; i < NUM_DIRS - 1; i++) {
        size_t j = rand() % (NUM_DIRS - i - 1) + i + 1;

        enum Dir temp = dirs[i];
        dirs[i] = dirs[j];
        dirs[j] = temp;
    }
}

bool at_edge(size_t x, size_t y, enum Edge e) {
    switch (e) {
        case TOP_EDGE:
        return y == 0;

        case BOTTOM_EDGE:
        return y == HEIGHT - 1;

        case LEFT_EDGE:
        return x == 0;

        case RIGHT_EDGE:
        return x == WIDTH - 1;
    }
}

bool position_used(char grid[HEIGHT][WIDTH], size_t x, size_t y) {
    return grid[y][x] != 0;
}

Example runs:

$ ./a.out
ABC....RS.
.ED...PQTU
.FG..NOXWV
..HIJM.Y..
....KL.Z..
..........
..........
..........
..........
..........
$ ./a.out
AB........
DC..LMPQR.
EFGJKNOTS.
..HI.WVU..
.....XY...
......Z...
..........
..........
..........
..........
$ ./a.out
ABC..TU...
.ED.RSV...
GFOPQ.WX..
HINM...Y..
.JKL...Z..
..........
..........
..........
..........
..........
$ ./a.out
Could not complete walk.
$ ./a.out
AB.TUV....
.CDSRWZ...
.FEPQXY...
HGNO......
ILM.......
JK........
..........
..........
..........
..........
$ ./a.out
ABC.......
..D.......
..E.......
.GF.......
IH........
J.........
K.........
LM...UV...
.NO.STWX..
..PQR.ZY..
$ ./a.out
Could not complete walk.
$ ./a.out
ABEF......
.CDG......
...HI...ST
....J..QRU
....KNOP.V
....LM.YXW
.......Z..
..........
..........
..........

Answer 4

Here ...

    char t[10][10] = {0}, c;

... you intialize all the elements of t to 0.

Here ...

        if (dir == 0 && i+1 < 10 && t[i+1][j] == '.')
            t[++i][j] = c;
        else if (dir == 1 && j+1 < 10 && t[i][j+1] == '.')
            t[i][++j] = c;
        else if (dir == 2 && i-1 >= 0 && t[i-1][j] == '.')
            t[--i][j] = c;
        else if (dir == 3 && j-1 >= 0 && t[i][j-1] == '.')
            t[i][--j] = c;
        else 
            break; 

..., while all the elements of t except [0][0] are still 0, you take a step only if the destination cell contains the value '.', which is not 0. As a result, you will never take a step.

Moreover, you apparently assume that i and j initially contain 0 and 0, but they are not initialized, so their values are in fact indeterminate. The program might happen to behave as if they were initially zero, but it is in no way constrained to do so. Initialize these to 0, corresponding to the initial position.

Note also that you break out of the loop if a step cannot be taken in the randomly-chosen direction. Perhaps this is the required behavior, but since you start in a corner, it means that 50% of the time you won't take any steps at all, and another 25% of the time you'll take only one. Perhaps you're meant to instead to start somewhere in the middle? Or to break out of the loop only when there are no directions in which a step could be taken?