Program that generates a "random walk" across 10*10 array

**iMalc** · 07-20-2011

If you want to shorten the code, how about moving these duplicated lines out of the switch statement?:

Code:

          if (board[i][j + 1] != '.' && board[i + 1][j] != '.' && board[i - 1][j] != '.' && board[i][j - 1] != '.')
              k = 27;

Oh and guess what, then using a simple break will have the desired effect of actually breaking out of the loop!

Here's another tip:if you increment j before this line, then you wont have to add one to j inside the []:

Code:

             board[i][j +1] = letters[k];  //move right

Do the same kind of thing inside each case and then, surprise surprise, all four cases would have the same line of code just using board[i][j]. Once again we move that line of code out of the switch statement.

Waiting for the "OMG it's so much shorter now!". But wait, there's still more. Sooner or later it will be short enough to spot the bug amoung the few lines remaining.

**Adak** · 07-21-2011

On your array, can't the walk go in any of eight different directions? Up, down, left, right, and also four diagonals?

When I did a program like this, I created two random numbers. One for the new column direction, and one for the new row direction. Side edge locations could not walk over the nearest side edge, and top and bottom edge locations could not go over their respective edge. Each new direction was either +1 from the current row, or column, 0, or -1, if all directions were available. If the random directions were 0 for the first number, the second number couldn't be 0, since that would result in no movement.

The code wasn't shorter, as I recall, but shorter code wasn't a goal.

There are a couple other ways to do this, adapted from chess and checkers programming, this is one of them:

Make your array 12 x 12, and put an "off the board" value in all the edge array locations (like -99). Just something unique. Now it's easy to detect when your move would take you off the board, just by testing the value of that location. #define OFF -99, above main(), and it can help make the logic you need, clearer.

If you put all your generation into one block of code, so nothing but legal moves can be created, then your move code itself can be made shorter and simpler. Redundant code gets eliminated this way.

This is a good little exercise, imo.

**danieldcc** · 07-21-2011

ok. Thanks iMAC for the suggestions, i think i finally got what i wanted....

Code:

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

#define ROWS 10
#define COLS 10
int main (void) {

int i, j, k, direction;
char board[ROWS][COLS];
const char letters[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};

srand ((unsigned) time(NULL));

for (i = 0; i < ROWS; i++)
  for (j = 0; j < COLS; j++)
    board[i][j] = '.';

i = 0;
j = 0;    
k = 1;
board[i][j] = letters[0];  //set array[0][0] to first element 
while (k < 26) {
  direction = rand() % 4;
  
if (board[i][j] == '.')
board[i][j] = letters[k++];  
if (board[i][j + 1] != '.' && board[i + 1][j] != '.' && board[i - 1][j] != '.' && board[i][j - 1] != '.')
break;
    switch (direction) {
      case 0: if (j < ROWS - 1 && board[i][j + 1] == '.'){
              j++;
              break;     }
      case 1: if (i < COLS -1 && board[i + 1][j] == '.') {
              i++;
              break; }
      case 2: if (i > 0 && board[i - 1][j] == '.'){
              i--;
              break;  }    
      case 3: if (j > 0 && board[i][j - 1] == '.') { //move left
              j--;
              break; }
}
}
for (i = 0; i < ROWS; i++) {
  for (j = 0; j < COLS; j++)
    printf ("%4c", board[i][j]);
  printf ("\n");
}

return 0;

}

**danieldcc** · 07-21-2011

NOPE, just run a whole bunch of tests and still hangs sometime

**tabstop** · 07-21-2011

Code:

if (board[i][j + 1] != '.' && board[i + 1][j] != '.' && board[i - 1][j] != '.' && board[i][j - 1] != '.')
break;

There are not always four neighbors to check.

**danieldcc** · 07-21-2011

so how do I modify the code to make sure that it doesn't go out of bounds?

**iMalc** · 07-21-2011

Oh yeah that's a good point, and this is slightly more visible than it was before.

There are two main ways to do it.
1. You could 'or' a bounds test in with each 'anded' test for a dot in that spot.
2. Or you could make the array bigger by two rows and two cols and then start using one-based indexing. Then the top, left, bottom, and rightmost rows and columns are all perfectly valid to access. Of course you'd have to fill them with something other than .

**~~CommonTater~~** · 07-21-2011

You can also mod (%) your array bounds...

Code:

int rows = 10, cols = 10;
int array[rows,cols];

// when walking
x = (x + 1) % rows;
y = (y + 1) % cols;

That way, going off the right side brings you back on the left, going off the bottom takes you to the top, and visa versa.

**danieldcc** · 07-21-2011

oh man, Tater, I think you're too advance for me.

iMalc - i think i want to do it this way
1. You could 'or' a bounds test in with each 'anded' test for a dot in that spot.

can you give me a little more clue on that

**tabstop** · 07-21-2011

Think of what it means to be blocked on the right: EITHER you are on the right-hand edge OR the spot to the right is filled.

Similarly for up, down, and left.

**danieldcc** · 07-21-2011

ok. got that. code finally works. THANKS EVERYONE FOR THE HELP

Code:

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

#define ROWS 10
#define COLS 10
int main (void) {

int i, j, k, direction;
char board[ROWS][COLS];
const char letters[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};

srand ((unsigned) time(NULL));

for (i = 0; i < ROWS; i++)
  for (j = 0; j < COLS; j++)
    board[i][j] = '.';

i = 0;
j = 0;    
k = 1;
board[i][j] = letters[0];  //set array[0][0] to first element 
while (k < 26) {
  direction = rand() % 4;
  
if (board[i][j] == '.')
board[i][j] = letters[k++];  
if ((board[i][j + 1] != '.' || j == ROWS - 1 )&& (board[i + 1][j] != '.' || i == COLS -1) && (board[i - 1][j] != '.' || i == 0) 
    && (board[i][j - 1] != '.' || j == 0))
break;
    switch (direction) {
      case 0: if (j < ROWS - 1 && board[i][j + 1] == '.'){  //move right
              j++;
              break;     }
      case 1: if (i < COLS -1 && board[i + 1][j] == '.') {  //move down
              i++;
              break; }
      case 2: if (i > 0 && board[i - 1][j] == '.'){  //move up
              i--;
              break;  }    
      case 3: if (j > 0 && board[i][j - 1] == '.') { //move left
              j--;
              break; }
}
}
for (i = 0; i < ROWS; i++) {
  for (j = 0; j < COLS; j++)
    printf ("%4c", board[i][j]);
  printf ("\n");
}

return 0;

}

**quzah** · 07-21-2011

Originally Posted by danieldcc

ok. got that. code finally works. THANKS EVERYONE FOR THE HELP

Code:

if ((board[i][j + 1] != '.' || j == ROWS - 1 )&& (board[i + 1][j] != '.' || i == COLS -1) && (board[i - 1][j] != '.' || i == 0) 
    && (board[i][j - 1] != '.' || j == 0))

You still are going to overflow or underflow your array here.

Measure before you cut, not afterward.

Quzah.

**TheBigH** · 07-21-2011

I suggest taking the advice given earlier. If your board is 10x10, make a 12x12 array and surround the board with a border of some special sentinel value.

**quzah** · 07-21-2011

Originally Posted by TheBigH

I suggest taking the advice given earlier. If your board is 10x10, make a 12x12 array and surround the board with a border of some special sentinel value.

You still end up checking to see if you are in bounds. You just do it differently. It's not like you suddenly stop caring about your border.

Code:

switch( dir )
{
    case 0: r--; break;
    case 1: c++; break;
    case 2: r++; break;
    case 3: c--; break;
}
if( block[ r ][ c ] == BORDER )
{
    /* all done, return or something */
}
block[ r ][ c ] = letter++;

Compared with:

Code:

switch( dir )
{
    case 0: r = r > 0 ? r - 1 : -1; break;
    case 1: c = c < COLS-1 ? c + 1 : -1; break;
    case 2: r = r < ROWS-1 ? r + 1 : -1; break;
    case 3: c = c > 0 ? c - 1 : -1; break;
}
if( r < 0 || c < 0 )
{
    /* all done, return or something */
}
block[ r ][ c ] = letter++;

You still have to pay attention to if you are out of bounds or not. Actually, the latter is still safer, because if somehow you write some bizarre value for r or c, you still make sure you are in bounds before you screw with it.

Quzah.

**iMalc** · 07-22-2011

Originally Posted by danieldcc

ok. got that. code finally works. THANKS EVERYONE FOR THE HELP

Code:

if ((board[i][j + 1] != '.' || j == ROWS - 1 )&& (board[i + 1][j] != '.' || i == COLS -1) && (board[i - 1][j] != '.' || i == 0) 
    && (board[i][j - 1] != '.' || j == 0))
break;

Yeah that's pretty much it, except that you again should reverse the two things on each side of the ||'s because currently you're accessing out of bounds and then checking whether you should have accessed that spot or not.
Look up and have a read about "short circuit evaluation", you'll understand it perfectly once you've done that.