Random walk across array

Discussion in 'C Programming' started by XLR3204S, Jul 16, 2010.

  1. XLR3204S

    XLR3204S Guest

    So I'm going through K.N. King's C Programming: A Modern Approach, a
    book with which most of you are familiar, as far as I can tell, and
    Chapter 8 (Arrays) has this Programming Project (#9) requiring the
    following:
    ---------------
    Write a program that generates a "random walk" across a 10 x 10 array.
    The array will contain characters (all '.' initially). The program
    must randomly "walk" from element to element, always going up, down,
    left, or right by one element. The elements visited by the program
    will be labeled with the letters A through Z, in the order visited.
    Here's an example of the desired output:
    http://drp.ly/1nvue4
    [the formatting is poor, so I hope this will do]

    Hint: Use the srand() and rand() functions to generate random numbers.
    After generating a number, look at its remainder when divided by 4.
    There are four possible values for the remainder -- 0, 1, 2, and 3 --
    indicating the direction of the next move. Before performing a move,
    check that (a) it won't go outside the array, and (b) it doesn't take
    us to an element that already has a letter assigned. If either
    condition is violated, try moving in another direction. If all four
    directions are blocked, the program must terminate.
    ---------------

    I've got a code which works, except for the last part: if all the
    directions are blocked, it keeps looking for a possible one. I know
    I'll have to change the entire loop, but here is how I've nailed it
    down. Any comments on the code are greatly appreciated, but do note
    that I'm not _supposed_ to know how to write custom functions or make
    use of pointers.

    ----------------
    /* Include the standard I/O library */
    #include<stdio.h>
    /* Include the time library */
    #include<time.h>
    /* Include the standard C library */
    #include<stdlib.h>

    /* Define main */
    int main(void) {

    /* Declare a 10x10 array of characters, initializing it to '.' */
    char array[10][10] = {
    {'A', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    };

    /* Declare the loop counters, as well as the direction */
    unsigned short int i, j, dir, x = 0, y = 0;

    /* Declare a placeholder for the current character, initially 'A'
    */
    char c = 'A';

    /**
    * Seed the current time as the initial value for the random
    numbers
    * generator
    */
    srand((unsigned) time(NULL));

    /**
    * As long as the current character isn't Z (the last letter of
    the
    * alphabet), keep moving randomly across the array
    */
    while(c != 'Z') {

    /**
    * Get the remainder of a random number divided by 4 and use
    it as
    * the direction of the next move
    */
    dir = rand() % 4;

    /**
    * Directions:
    * 0 -- up
    * 1 -- right
    * 2 -- down
    * 3 -- left
    */
    if(dir == 0) {
    /* If everything's OK, make the move */
    if(x - 1 >= 0 && array[x - 1][y] == '.') {

    array[--x][y] = ++c;
    } else { /* Otherwise, try the next direction */

    dir = 1;
    }
    }

    if(dir == 1) {
    /* If everything's OK, make the move */
    if(y + 1 < 10 && array[x][y + 1] == '.') {

    array[x][++y] = ++c;
    } else { /* Otherwise, try the next direction */

    dir = 2;
    }
    }

    if(dir == 2) {
    /* If everything's OK, make the move */
    if(x + 1 < 10 && array[x + 1][y] == '.') {

    array[++x][y] = ++c;
    } else { /* Otherwise, try the next direction */

    dir = 3;
    }
    }

    if(dir == 3) {
    /* If everything's OK, make the move */
    if(y - 1 >= 0 && array[x][y - 1] == '.') {

    array[x][--y] = ++c;
    } else { /* Otherwise, try the next direction */

    dir = 1;
    }
    }
    }

    /* Print the multi-dimensional array */
    for(i = 0; i < 10; i++) {
    for(j = 0; j < 10; j++) {

    printf(" %c ", array[j]); /* Print the current
    character */
    }

    printf("\n"); /* Print a new line */
    }

    /* Return 0 upon success */
    return 0;
    }
    ----------------
    XLR3204S, Jul 16, 2010
    #1
    1. Advertising

  2. XLR3204S

    Eric Sosman Guest

    On 7/16/2010 2:30 PM, XLR3204S wrote:
    > So I'm going through K.N. King's C Programming: A Modern Approach, a
    > book with which most of you are familiar, as far as I can tell, and
    > Chapter 8 (Arrays) has this Programming Project (#9) requiring the
    > following:
    > ---------------
    > Write a program that generates a "random walk" across a 10 x 10 array.
    > The array will contain characters (all '.' initially). The program
    > must randomly "walk" from element to element, always going up, down,
    > left, or right by one element. The elements visited by the program
    > will be labeled with the letters A through Z, in the order visited.
    > Here's an example of the desired output:
    > http://drp.ly/1nvue4
    > [the formatting is poor, so I hope this will do]
    >
    > Hint: Use the srand() and rand() functions to generate random numbers.
    > After generating a number, look at its remainder when divided by 4.
    > There are four possible values for the remainder -- 0, 1, 2, and 3 --
    > indicating the direction of the next move. Before performing a move,
    > check that (a) it won't go outside the array, and (b) it doesn't take
    > us to an element that already has a letter assigned. If either
    > condition is violated, try moving in another direction. If all four
    > directions are blocked, the program must terminate.


    Just as a side-note for future reference: `rand() % N' is not a
    particularly good way to get random numbers 0<=r<N; see Question
    13.16 on the comp.lang.c Frequently Asked Questions (FAQ) page at
    <http://www.c-faq.com/>. Perhaps your book is keeping things simple
    in the early going and will describe better ways later -- but in any
    case, it's something to remember.

    > ---------------
    >
    > I've got a code which works, except for the last part: if all the
    > directions are blocked, it keeps looking for a possible one. I know
    > I'll have to change the entire loop, but here is how I've nailed it
    > down. Any comments on the code are greatly appreciated, but do note
    > that I'm not _supposed_ to know how to write custom functions or make
    > use of pointers.


    The reason your program keeps on trying when it's completely
    blocked is that you've done nothing to detect the "I'm stuck" condition
    and respond to it. The computer has no common sense whatever, and is
    so stupid it will keep on trying to do what it's told even when it's
    been told to do the impossible.

    (I once tried to get this point across to a class of beginners by
    asking them to come up with a precise set of instructions for tying
    one's shoelaces. Lots of useful discussion ensued, and after a good
    deal of class wrangling some sort of recipe found its way to the
    blackboard. I then showed them one of my own shoes, a laceless loafer
    that I had carefully worn to class that day, and asked "Now what?"
    I think they got the point -- but the example took too much class
    time, and I decided I needed to find another way. Instead, I found
    another job ...)

    > ----------------
    > /* Include the standard I/O library */
    > #include<stdio.h>
    > /* Include the time library */
    > #include<time.h>
    > /* Include the standard C library */
    > #include<stdlib.h>
    >
    > /* Define main */
    > int main(void) {
    >
    > /* Declare a 10x10 array of characters, initializing it to '.' */
    > char array[10][10] = {
    > {'A', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    > {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    > {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    > {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    > {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    > {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    > {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    > {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    > {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    > {'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
    > };


    Consider doing this initialization with a loop instead of writing
    it out in longhand. The computer is much better at repetitive work
    than you are; let it shine while you relax.

    > /* Declare the loop counters, as well as the direction */
    > unsigned short int i, j, dir, x = 0, y = 0;


    Since you're making tests like `x-1 >= 0', the fact that `x' and
    `y' are unsigned could get you into trouble if `x-1' gets calculated
    according to the rules of unsigned arithmetic (which would make the
    test vacuously true). Alternatives: Make them plain signed ints, or
    (better) change the test to `x >= 1', or (best) change to `x > 0'.

    > /* Declare a placeholder for the current character, initially 'A'
    > */
    > char c = 'A';
    >
    > /**
    > * Seed the current time as the initial value for the random
    > numbers
    > * generator
    > */
    > srand((unsigned) time(NULL));
    >
    > /**
    > * As long as the current character isn't Z (the last letter of
    > the
    > * alphabet), keep moving randomly across the array
    > */
    > while(c != 'Z') {


    Instead of having the initialization to `A' in one place, the
    test for `Z' in another, and the advance from letter to letter in yet
    a third, consider putting all three into a single `for' statement,
    something like `for (c = 'A'+1; c != 'Z'; ++c)'.

    Also, you're assuming that the letters 'A' through 'Z' have
    consecutive numeric codes. This is true of a great many machines,
    but not of all. To cater to the others, you could put the letters
    into an array like `char alpha[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";'
    and then step an index across the array.

    Now to the problem: This would be a great place to test whether
    you're stuck, and to exit the loop if you are. A move is possible
    if there's a '.' next to the current position, hence impossible if
    there's no such '.':

    if (! ( (x > 0 && array[x-1][y] == '.')
    || (x < 9 && array[x+1][y] == '.')
    || (y > 0 && array[x][y-1] == '.')
    || (y < 9 && array[x][y+1] == '.') ) )
    break;

    This may look formidable, but it really isn't: Each of the innermost
    tests checks for a neighboring '.' and comes up "true" if it finds one,
    and if any test comes up "true" then the OR of all four is also "true,"
    so the NOT of that is "true" only if all four came up "false" -- in
    which case there's no place to go, and you should bail out.

    Another side-note: Sometimes tests of this kind can be simplified
    by putting a "boundary" around the active field of play. For example,
    you could surround the 10x10 array with two rows and two columns of
    '#', that is, your program could use a 12x12 array with '#' around
    the edges and '.' in the active area (whose indices would now run
    from 1 through 10 instead of 0 through 9). This technique lets you
    discard all those `x > 0' and `y < 9' tests: You'll just look at the
    neighboring cell and find either '.' or non-'.', and that's that.
    When you print the results, of course, print only the [1..10][1..10]
    portion. (You don't *have* to do this, but it's a helpful trick to
    remember. Extra credit: Why might a chess program use a 12x12 board?)

    > /**
    > * Get the remainder of a random number divided by 4 and use
    > it as
    > * the direction of the next move
    > */
    > dir = rand() % 4;
    >
    > /**
    > * Directions:
    > * 0 -- up
    > * 1 -- right
    > * 2 -- down
    > * 3 -- left
    > */


    Have you learned about the `switch' statement yet? This situation
    simply cries out for a `switch'.

    > if(dir == 0) {
    > /* If everything's OK, make the move */
    > if(x - 1>= 0&& array[x - 1][y] == '.') {
    >
    > array[--x][y] = ++c;
    > } else { /* Otherwise, try the next direction */
    >
    > dir = 1;


    Well-intentioned, perhaps, but it's not very random: If only
    the UP direction is blocked, why should you always go RIGHT and
    never DOWN or LEFT? Better, maybe, to just give up on this attempt
    and roll another random number -- which puts my recommendation of
    `for' into doubt, since you might traverse this chunk of code several
    times before depositing a letter and moving on to another. So, what
    you really need is an outer loop that runs through the letters, and
    an inner loop that rolls the dice until it finds a legal move:

    for (c = 'A'; c != 'Z'; ) {
    break out if no move is possible;
    for (rolling = 1; rolling; ) {
    switch (rand() % 4) {
    case 0:
    if (x > 0 && array[x-1][y] == '.') {
    --x;
    rolling = 0;
    }
    break;
    ...
    }
    }
    array[x][y] = ++c;
    }

    There are, of course, many other ways to arrange this. The `do' loop
    is fairly rarely used, but would be convenient for the inner loop,
    and there are other possibilities as well.

    > }
    > }
    >
    > if(dir == 1) {
    > /* If everything's OK, make the move */
    > if(y + 1< 10&& array[x][y + 1] == '.') {
    >
    > array[x][++y] = ++c;
    > } else { /* Otherwise, try the next direction */
    >
    > dir = 2;
    > }
    > }
    >
    > if(dir == 2) {
    > /* If everything's OK, make the move */
    > if(x + 1< 10&& array[x + 1][y] == '.') {
    >
    > array[++x][y] = ++c;
    > } else { /* Otherwise, try the next direction */
    >
    > dir = 3;
    > }
    > }
    >
    > if(dir == 3) {
    > /* If everything's OK, make the move */
    > if(y - 1>= 0&& array[x][y - 1] == '.') {
    >
    > array[x][--y] = ++c;
    > } else { /* Otherwise, try the next direction */
    >
    > dir = 1;
    > }
    > }
    > }
    >
    > /* Print the multi-dimensional array */
    > for(i = 0; i< 10; i++) {
    > for(j = 0; j< 10; j++) {
    >
    > printf(" %c ", array[j]); /* Print the current
    > character */
    > }
    >
    > printf("\n"); /* Print a new line */
    > }
    >
    > /* Return 0 upon success */
    > return 0;
    > }
    > ----------------



    --
    Eric Sosman
    lid
    Eric Sosman, Jul 16, 2010
    #2
    1. Advertising

  3. XLR3204S

    Jorgen Grahn Guest

    On Fri, 2010-07-16, Eric Sosman wrote:
    > On 7/16/2010 2:30 PM, XLR3204S wrote:
    >> So I'm going through K.N. King's C Programming: A Modern Approach, a
    >> book with which most of you are familiar, as far as I can tell, and
    >> Chapter 8 (Arrays) has this Programming Project (#9) requiring the
    >> following:

    ....
    >>
    >> Hint: Use the srand() and rand() functions to generate random numbers.
    >> After generating a number, look at its remainder when divided by 4.
    >> There are four possible values for the remainder -- 0, 1, 2, and 3 --
    >> indicating the direction of the next move.

    ....
    > Just as a side-note for future reference: `rand() % N' is not a
    > particularly good way to get random numbers 0<=r<N; see Question
    > 13.16 on the comp.lang.c Frequently Asked Questions (FAQ) page at
    > <http://www.c-faq.com/>.


    I have brought this up before, but I question if there are C libraries
    where this is still true. The FAQ entry is based on a text from 1993,
    and even there no specific implementations are mentioned.

    (But the "RAND_MAX+1 cannot always be evenly divvied up into N
    buckets" problem mentioned in the FAQ is of course a problem no matter
    how good rand() is.)

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, Jul 29, 2010
    #3
  4. On 16 July, 19:30, XLR3204S <> wrote:

    > ----------------
    > /* Include the standard I/O library */


    I *hate* comments like this

    > #include<stdio.h>
    > /* Include the time library */
    > #include<time.h>
    > /* Include the standard C library */
    > #include<stdlib.h>
    >
    > /* Define main */
    > int main(void) {


    <snip>

    >     /**
    >      * Seed the current time as the initial value for the random
    > numbers
    >      * generator
    >      */
    >     srand((unsigned) time(NULL));


    this is a really heavy level of commenting. I actually find it hard to
    find the code. I wouldn't normally comment somethign that could be
    discovered in 10s with a manual. Assume your reader has a basic
    understanding of C.

    <snip>
    Nick Keighley, Jul 29, 2010
    #4
  5. XLR3204S

    Eric Sosman Guest

    On 7/29/2010 5:08 AM, Jorgen Grahn wrote:
    > On Fri, 2010-07-16, Eric Sosman wrote:
    >> On 7/16/2010 2:30 PM, XLR3204S wrote:
    >>> So I'm going through K.N. King's C Programming: A Modern Approach, a
    >>> book with which most of you are familiar, as far as I can tell, and
    >>> Chapter 8 (Arrays) has this Programming Project (#9) requiring the
    >>> following:

    > ...
    >>>
    >>> Hint: Use the srand() and rand() functions to generate random numbers.
    >>> After generating a number, look at its remainder when divided by 4.
    >>> There are four possible values for the remainder -- 0, 1, 2, and 3 --
    >>> indicating the direction of the next move.

    > ...
    >> Just as a side-note for future reference: `rand() % N' is not a
    >> particularly good way to get random numbers 0<=r<N; see Question
    >> 13.16 on the comp.lang.c Frequently Asked Questions (FAQ) page at
    >> <http://www.c-faq.com/>.

    >
    > I have brought this up before, but I question if there are C libraries
    > where this is still true. The FAQ entry is based on a text from 1993,
    > and even there no specific implementations are mentioned.
    >
    > (But the "RAND_MAX+1 cannot always be evenly divvied up into N
    > buckets" problem mentioned in the FAQ is of course a problem no matter
    > how good rand() is.)


    Right -- and that's why `rand() % N' isn't very good, even
    with a "good" rand(). For small N the unevenness of the result
    may be tolerable in some applications. But when N is large (more
    than RAND_MAX/20, say), the bias is likely to be objectionable.
    A rejection technique (like the one shown in the FAQ) will help.

    --
    Eric Sosman
    lid
    Eric Sosman, Jul 29, 2010
    #5
  6. Eric Sosman <> writes:
    > On 7/29/2010 5:08 AM, Jorgen Grahn wrote:
    >> On Fri, 2010-07-16, Eric Sosman wrote:

    [...]
    >>> Just as a side-note for future reference: `rand() % N' is not a
    >>> particularly good way to get random numbers 0<=r<N; see Question
    >>> 13.16 on the comp.lang.c Frequently Asked Questions (FAQ) page at
    >>> <http://www.c-faq.com/>.

    >>
    >> I have brought this up before, but I question if there are C libraries
    >> where this is still true. The FAQ entry is based on a text from 1993,
    >> and even there no specific implementations are mentioned.
    >>
    >> (But the "RAND_MAX+1 cannot always be evenly divvied up into N
    >> buckets" problem mentioned in the FAQ is of course a problem no matter
    >> how good rand() is.)

    >
    > Right -- and that's why `rand() % N' isn't very good, even
    > with a "good" rand(). For small N the unevenness of the result
    > may be tolerable in some applications. But when N is large (more
    > than RAND_MAX/20, say), the bias is likely to be objectionable.
    > A rejection technique (like the one shown in the FAQ) will help.


    There are two different reasons why rand() % N might not be very
    good. One is, as you say, the bucket problem that applies to all
    possible rand() implementations. But the FAQ specifically mentions
    another problem: "because the low-order bits of many random number
    generators are distressingly non-random"; 13.18 covers this in
    more depth.

    Jorgen's question, whether any current C libraries have this problem
    (rand()%2 alternating 0, 1, 0, 1, ...), is an interesting one,
    and the answer could affect the best way to work around the bucket
    problem.

    And the answer appears to be yes. On most systems, the following
    program:

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

    const char hex[] = "0123456789abcdef";

    int main(void)
    {
    int i;
    int bits;

    srand(time(NULL));

    for (bits = 1; bits <= 4; bits ++) {
    for (i = 0; i < 64; i ++) {
    putchar(hex[rand() % (1<<bits)]);
    }
    putchar('\n');
    }

    return 0;
    }

    produces the kind of random digits you'd expect:

    0101000011101001100010010101111101001000000100010111111001111001
    0223222202303033101232031322020002330111011311221301110303101102
    3050165576407361276002301053255552570240110047166766216323641316
    5f5e12623eb7d45bcc9ed017b8343d39c87dad0dbb49fa4b6e93ebb93ee6b1f7

    But on Solaris, when compiled with /usr/ucb/cc I get this:

    1010101010101010101010101010101010101010101010101010101010101010
    1230123012301230123012301230123012301230123012301230123012301230
    1674523016745230167452301674523016745230167452301674523016745230
    1674d2309efc5ab81674d2309efc5ab81674d2309efc5ab81674d2309efc5ab8

    which is exactly the behavior described in FAQ 13.18.

    /usr/ucb/cc is quite an old compiler, and not intended for general
    use. For that matter, I'm not sure it's even C89-conforming.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Jul 29, 2010
    #6
  7. XLR3204S

    Guest

    Keith Thompson <> wrote:
    >
    > But on Solaris, when compiled with /usr/ucb/cc I get this:
    >
    > 1010101010101010101010101010101010101010101010101010101010101010
    > 1230123012301230123012301230123012301230123012301230123012301230
    > 1674523016745230167452301674523016745230167452301674523016745230
    > 1674d2309efc5ab81674d2309efc5ab81674d2309efc5ab81674d2309efc5ab8
    >
    > which is exactly the behavior described in FAQ 13.18.


    Which isn't surprising given that the UCB (mis)implementation of rand()
    is the original source of the "distressingly non-random" lower bits that
    the FAQ refers to. As you note:

    > /usr/ucb/cc is quite an old compiler, and not intended for general
    > use. For that matter, I'm not sure it's even C89-conforming.


    So I wouldn't call it's library a "current" C library -- it's provided
    specifically for backward compatibility to ancient times.
    --
    Larry Jones

    Talk about someone easy to exploit! -- Calvin
    , Jul 30, 2010
    #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. Raterus
    Replies:
    2
    Views:
    951
    Raterus
    Jun 30, 2004
  2. Marcus Alves Grando
    Replies:
    7
    Views:
    451
    Marcus Alves Grando
    Nov 14, 2007
  3. globalrev
    Replies:
    4
    Views:
    734
    Gabriel Genellina
    Apr 20, 2008
  4. Amir  Michail
    Replies:
    10
    Views:
    386
    Carl Banks
    Mar 4, 2009
  5. VK
    Replies:
    15
    Views:
    1,090
    Dr J R Stockton
    May 2, 2010
Loading...

Share This Page