• 11
• 15
• 19
• 27
• 9

# A simple but puzzling algorithm

This topic is 4301 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I have a 10 * 10 grid labelled like this: 00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21......etc. Later on I want to travers the grid square by square. However, instead of going in the traditional way: --------> --------> --------> --------> I want to go like this: -------> <------- -------> <------- Basically, I'm having trouble with the algorithm to do it, but it's giving me a headache. I was hoping someone might help. So far I have this....
gridPosition = 0;

while (gridPosition < 100) {

if (gridPosition != 0 && gridPosition % 10 == 0) {

gridPosition += 10;

}

else if ((gridPosition+1) % 10 == 0) {

gridPosition += 10;

}

row = int(gridPosition / ROWS);
col = gridPosition - row * COLUMNS;

if (row % 2 == 0) {

gridPosition++;
}

else if (row % 2 != 0){

gridPosition--;
}

printf(gridPosition);

}


Essentially, what it does is.....starts at n = 0. If the row is odd n is increased by 1. If the row is even n is decremented. if n is on the left/right edges it jumps to the next line immediately beneath it (i.e. n += 10). However, the edges are not printed since n jumps befre being printed. I've spent the last hour or so fiddling with it. Now, forgive me for being thick, but am I missing something completely obvious here.....it seems so to me :-) Can some advise me please...I have a bad ear :'-(

##### Share on other sites
In my opinion, it would be easier to think about it in terms of X and Y in 2D space. You can then convert the X and Y coordinate into an index by using:
idx = (y * width) + x;

where width in your case would be 10.

You could then iterate through the grid like so:
flip = false;for (y = 0; y < 10; y++){    if (flip == false)    {        for (x = 0; x < 10; x++)        {            gridPosition = (y * 10) + x;            // ...do something with gridPosition...        }    }    else    {        for (x = 9; x >= 0; x--)        {            gridPosition = (y * 10) + x;            // ...do something with gridPosition...        }    }    flip = !flip;}

Obviously there are better ways of traversing through the grid, but hopefully this should give you an idea as to how to start.

##### Share on other sites
//Here is how you compute row and column for your grid based on cell number:  row = cell / columns  col = row % 2 ? columns - cell % columns - 1  : cell % columns//So you can traverse the cells like this:  int rows = 10;  int cols = 10;  for(int cell = 0; cell < rows * cols; ++cell) {    int row = cell / cols;    int col = row % 2 ? cols - cell % cols - 1  : cell % cols;  }//You can also make a function:  void get_grid_coords(int cell int rows, int cols, int &row, int &col) {    row = cell / cols;    col = row % 2 ? cols - cell % cols - 1  : cell % cols;  }//And use it like this:  int rows = 10;  int cols = 10;  for(int cell = 0; cell < rows * cols; ++cell) {    int row, col;    get_grid_coords(cell, rows, cols, row, col);  }

Simple isnt it.

##### Share on other sites
Your basic problem seems to be that, when you reach an edge, you update twice - once to get to the next row, and then once to begin traversing that row. Your numbers are actually going through the square in the right order, but the nines and zeroes are not getting printed because you update again before you reach the print statement. Try printing every time you change your position, and see if that doesn't help.

##### Share on other sites
int dir = 1;for (int y = 0; y < 10; y++) {    for (int x = ((dir == 1) ? 0 : 9); x >= 0 && x <= 9; x += dir) {        // Whatver you want to do at x, y    }        // Swap the x traverse direction    dir = -dir;}

That's nice and clean I think.

##### Share on other sites
In a similar vein (because I feel clever today):

for (int y = 0; y < rows; ++y) {  int start = 0, limit = columns, dir = 1;  for (int x = start; x != limit; x += dir) {    // do whatever  }  dir = -dir;  std::swap(start, limit);  start += dir; limit += dir;}

##### Share on other sites
It is said that you are trying to traverse the grid boustrophedonically. If you check the dictionary, chances are you won't find this particular adverb, but you will find the base word "boustrophedon" which is an ancient form of writing wherein every second line is written backwards. It should be noted, however, that this term in not limited to writing. It is suitable for describing any occurance of this pattern.

##### Share on other sites
Quote:
 Original post by ZahlmanIn a similar vein (because I feel clever today):for (int y = 0; y < rows; ++y) { int start = 0, limit = columns, dir = 1; for (int x = start; x != limit; x += dir) { // do whatever } dir = -dir; std::swap(start, limit); start += dir; limit += dir;}

Your code does not do what you think it does.

You will always iterate forward under your code.

Better:
int sgn( int v ) { return v<0?-1:1; }// ...  // intial open bounds for the interval in "x":  int x_left = -1, x_right = columns;  // start looping:  for (int y = 0; y < rows; ++y) {    // loop between the ordered open bounds x_left and x_right:    int dir = sgn( x_right - x_left );    for (int x = (x_left+dir); (x*dir)<(x_right*dir); x += dir) {      // do whatever    }    // change the order:    std::swap(x_left, x_right);  }

##### Share on other sites
Quote:
 Original post by NotAYakkYour code does not do what you think it does.

Should've posted why :-).

Instead of rewriting the whole durn thing, just bump the variable declarations outside the y loop so they persist :-).

##### Share on other sites
Quote:
Original post by MaulingMonkey
Quote:
 Original post by NotAYakkYour code does not do what you think it does.

Should've posted why :-).

Instead of rewriting the whole durn thing, just bump the variable declarations outside the y loop so they persist :-).

I led the horse to water. Drinking is up to the horse.

Plus, Zahlman's implementation fails catastrophically when the width of a column is negative.

Mine fails less catetrophically! (I mean, if the client says the width of the column is -4, they do want you to iterate over -2 then -3, right? Right? ...)

To improve mine and make it extra robust:

  // intial open bounds for the interval in "x":  int x_left = -1, x_right = columns;  int dir = 1;  // start looping:  for (int y = 0; y < rows; ++y) {    // loop between the ordered open bounds x_left and x_right:    for (int x = (x_left+dir); (x*dir)<(x_right*dir); x += dir) {      // do whatever    }    // change the order:    std::swap(x_left, x_right);    dir*=-1;  }