Sign in to follow this  
Thomo

A simple but puzzling algorithm

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
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);
}

Share this post


Link to post
Share on other sites
Quote:
Original post by MaulingMonkey
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 :-).


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;
}

Share this post


Link to post
Share on other sites
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;
}
If you move the variables outside both loops, the code performs like so:
Loop from X = 0 to (Col-1)
Loop from X = (Col-1) to -1
Loop from X = 0 to (Col-1)
Loop from X = (Col-1) to -1
Loop from X = 0 to (Col-1)

You need to add in Col somewhere, so that successive loops actually make progress.

Share this post


Link to post
Share on other sites
Quote:
Original post by Extrarius
If you move the variables outside both loops,


Yeah, yeah, guys, I *get* it already :D

Quote:
You need to add in Col somewhere, so that successive loops actually make progress.


"progress" is acheived by incrementing y. The intent is that y and x are used to index into a 2D array[columns][rows]. :s

Share this post


Link to post
Share on other sites
All you need is a simple algorithm to return the square number based on a linear index:


#define ROW_WIDTH 10
int square_index( int linear ) {
int row = linear / ROW_WIDTH;
int col = linear % ROW_WIDTH;
return (row & 1) ?
(row+1) * ROW_WIDTH - col - 1 :
row*ROW_WIDTH + col;
}


Call this in a loop from 0 to 99 and you'll get the appropriate value out (unless I made a typo :-)

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman

Yeah, yeah, guys, I *get* it already :D


Hehe, I've nothing but respect for Zahlman as he has always appeared to be one of the most knowledgable posters on this board. Having said that, it's nice to see him get something wrong for a change ;);)

Share this post


Link to post
Share on other sites
Correctness and efficiency not guaranteed:
#include <iterator>

template < typename base_iterator_type, typename std::iterator_traits< base_iterator_type >::difference_type width >
class boustrophedonic_iterator
:
public std::iterator
<
typename std::iterator_traits< base_iterator_type >::iterator_category,
typename std::iterator_traits< base_iterator_type >::value_type,
typename std::iterator_traits< base_iterator_type >::difference_type,
typename std::iterator_traits< base_iterator_type >::pointer,
typename std::iterator_traits< base_iterator_type >::reference
>
{

public:

typedef std::iterator_traits< base_iterator_type > iterator_traits;
typedef typename iterator_traits::iterator_category iterator_category;
typedef typename iterator_traits::value_type value_type;
typedef typename iterator_traits::difference_type difference_type;
typedef typename iterator_traits::pointer pointer;
typedef typename iterator_traits::reference reference;

boustrophedonic_iterator()
:
offset_(0),
forward_(true)
{
}

explicit boustrophedonic_iterator(base_iterator_type const & base_iterator)
:
base_iterator_(base_iterator),
offset_(0),
forward_(true)
{
}

base_iterator_type base() const
{
return base_iterator_;
}

reference operator*() const
{
return *base_iterator_;
}

pointer operator->() const
{
return &*base_iterator_;
}

boustrophedonic_iterator & operator++()
{
if (forward_)
{
++base_iterator_;
++offset_;
if (offset_ % width == 0)
{
base_iterator_ += width - 1;
offset_ += width - 1;
forward_ = false;
}
}
else
{
--base_iterator_;
--offset_;
if (offset_ % width == width - 1)
{
base_iterator_ += width + 1;
offset_ += width + 1;
forward_ = true;
}
}
return *this;
}

boustrophedonic_iterator operator++(int)
{
boustrophedonic_iterator pre_increment(*this);
++*this;
return pre_increment;
}

boustrophedonic_iterator & operator--()
{
if (forward_)
{
--base_iterator_;
--offset_;
if (offset_ % width == width - 1)
{
base_iterator_ -= width - 1;
forward_ = false;
}
}
else
{
++base_iterator_;
++offset_;
if (offset_ % width == 0)
{
base_iterator_ -= width + 1;
forward_ = true;
}
}
return *this;
}

boustrophedonic_iterator operator--(int)
{
boustrophedonic_iterator pre_decrement(*this);
--*this;
return pre_decrement;
}

boustrophedonic_iterator operator+(difference_type distance) const
{
return boustrophedonic_iterator< base_iterator_type, width >(*this) += distance;
}

boustrophedonic_iterator & operator+=(difference_type distance)
{
base_iterator_ += (distance / (width * 2)) * width * 2;
offset_ += (distance / (width * 2)) * width * 2;
distance %= width * 2;
if (forward_)
{
difference_type first_line = std::min((width - 1) - (offset_ % width), distance);
distance -= first_line;
base_iterator_ += first_line;
offset_ += first_line;
if (distance == 0)
{
return *this;
}
difference_type second_line = std::min(width, distance);
distance -= second_line;
base_iterator_ += (width + 1) - second_line;
offset_ += (width + 1) - second_line;
if (distance == 0)
{
forward_ = false;
return *this;
}
base_iterator_ += (width - 1) + distance;
offset_ += (width - 1) + distance;
return *this;
}
else
{
difference_type first_line = std::min(offset_ % width, distance);
distance -= first_line;
base_iterator_ -= first_line;
offset_ -= first_line;
if (distance == 0)
{
return *this;
}
difference_type second_line = std::min(width, distance);
distance -= second_line;
base_iterator_ += (width - 1) + second_line;
offset_ += (width - 1) + second_line;
if (distance == 0)
{
forward_ = true;
return *this;
}
base_iterator_ += (width - 1) + distance;
offset_ += (width - 1) + distance;
return *this;
}
}

boustrophedonic_iterator operator-(difference_type distance) const
{
return boustrophedonic_iterator< base_iterator_type, width >(*this) -= distance;
}

boustrophedonic_iterator & operator-=(difference_type distance)
{
base_iterator_ -= (distance / (width * 2)) * width * 2;
offset_ -= (distance / (width * 2)) * width * 2;
distance %= width * 2;
if (forward_)
{
difference_type first_line = std::min(offset_ % width, distance);
distance -= first_line;
base_iterator_ -= first_line;
offset_ -= first_line;
if (distance == 0)
{
return *this;
}
difference_type second_line = std::min(width, distance);
distance -= second_line;
base_iterator_ -= (width + 1) - second_line;
offset_ -= (width + 1) - second_line;
if (distance == 0)
{
forward_ = false;
return *this;
}
base_iterator_ -= (width - 1) + distance;
offset_ -= (width - 1) + distance;
return *this;
}
else
{
difference_type first_line = std::min((width - 1) - (offset_ % width), distance);
distance -= first_line;
base_iterator_ += first_line;
offset_ += first_line;
if (distance == 0)
{
return *this;
}
difference_type second_line = std::min(width, distance);
distance -= second_line;
base_iterator_ -= (width - 1) + second_line;
offset_ -= (width - 1) + second_line;
if (distance == 0)
{
forward_ = true;
return *this;
}
base_iterator_ -= (width + 1) - distance;
offset_ -= (width + 1) - distance;
return *this;
}
}

reference operator[](difference_type index) const
{
return *(boustrophedonic_iterator< base_iterator_type, width >(*this) + index);
}

bool forward_row() const
{
return forward_;
}

protected:

base_iterator_type base_iterator_;
difference_type offset_;
bool forward_;

};

template < typename base_iterator_type, typename std::iterator_traits< base_iterator_type >::difference_type width >
bool operator==(boustrophedonic_iterator< base_iterator_type, width > const & lhs, boustrophedonic_iterator< base_iterator_type, width > const & rhs)
{
return lhs.base() == rhs.base();
}

template < typename base_iterator_type, typename std::iterator_traits< base_iterator_type >::difference_type width >
bool operator<(boustrophedonic_iterator< base_iterator_type, width > const & lhs, boustrophedonic_iterator< base_iterator_type, width > const & rhs)
{
return lhs.base() < rhs.base();
}

template < typename base_iterator_type, typename std::iterator_traits< base_iterator_type >::difference_type width >
bool operator!=(boustrophedonic_iterator< base_iterator_type, width > const & lhs, boustrophedonic_iterator< base_iterator_type, width > const & rhs)
{
return lhs.base() != rhs.base();
}

template < typename base_iterator_type, typename std::iterator_traits< base_iterator_type >::difference_type width >
bool operator>(boustrophedonic_iterator< base_iterator_type, width > const & lhs, boustrophedonic_iterator< base_iterator_type, width > const & rhs)
{
return lhs.base() > rhs.base();
}

template < typename base_iterator_type, typename std::iterator_traits< base_iterator_type >::difference_type width >
bool operator>=(boustrophedonic_iterator< base_iterator_type, width > const & lhs, boustrophedonic_iterator< base_iterator_type, width > const & rhs)
{
return lhs.base() >= rhs.base();
}

template < typename base_iterator_type, typename std::iterator_traits< base_iterator_type >::difference_type width >
bool operator<=(boustrophedonic_iterator< base_iterator_type, width > const & lhs, boustrophedonic_iterator< base_iterator_type, width > const & rhs)
{
return lhs.base() <= rhs.base();
}

template < typename base_iterator_type, typename std::iterator_traits< base_iterator_type >::difference_type width >
typename boustrophedonic_iterator< base_iterator_type, width >::difference_type operator-(boustrophedonic_iterator< base_iterator_type, width > const & lhs, boustrophedonic_iterator< base_iterator_type, width > const & rhs)
{
return lhs.base() - rhs.base();
}

template < typename base_iterator_type, typename std::iterator_traits< base_iterator_type >::difference_type width >
boustrophedonic_iterator< base_iterator_type, width > operator+(typename boustrophedonic_iterator< base_iterator_type, width >::difference_type distance, boustrophedonic_iterator< base_iterator_type, width > const & iterator)
{
return boustrophedonic_iterator< base_iterator_type, width >(iterator.base() + distance);
}

Usage example:
#include <iostream>
#include <vector>
#include "boustrophedonic_iterator.h"

int main()
{
std::vector< int > container;
for (int i = 0; i < 120; ++i)
{
container.push_back(i);
}
boustrophedonic_iterator< std::vector< int >::iterator, 12 > iterator(container.begin());
boustrophedonic_iterator< std::vector< int >::iterator, 12 > iteratorEnd(container.end());
while (iterator != iteratorEnd)
{
std::cout << *iterator << ' ';
if ((iterator.forward_row() && (iterator.base() - container.begin()) % 12 == 11) || (!iterator.forward_row() && (iterator.base() - container.begin()) % 12 == 0))
{
std::cout << '\n';
}
++iterator;
}
}

Σnigma

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this