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);
}
A simple but puzzling algorithm
Author
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....
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 :'-(
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:
where width in your case would be 10.
You could then iterate through the grid like so:
Obviously there are better ways of traversing through the grid, but hopefully this should give you an idea as to how to start.
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.
//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.
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.
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.
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;}
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.
Quote:Original post by Zahlman
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;}
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); }
Quote:Original post by NotAYakk
Your 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 :-).
Quote:Original post by MaulingMonkeyQuote:Original post by NotAYakk
Your 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; }This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement