• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Could someone give me feedback on my algorithm?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

24 replies to this topic

### #1black_darkness  Members

Posted 13 December 2012 - 04:43 PM

Hello. I am writing an algorithm that paints an 8 x 8 checkerboard red, and white. However the algorithm at this moment is 87 lines long. Sadly It would be only 64 lines to individually color all 64 squares. Please give me feedback.

Here is some more relevant information. At first I tried to paint every other square red. However it looked like this. (rough illustration)

Now after implementing my algorithm it looks like this.

Variable k represents the current square. j is the counter. So I use it to run a % on in order to determine even or odd.

if(rects.size()<=8)
{
if(j%2 == 0  )
{
(*rects[(k)]).set_fill_color(Color::red);
}
else if(j%2 == 1)
{
(*rects[(k)]).set_fill_color(Color::white);
}
}
else if(rects.size()<=16)
{
if(j%2 == 1  )
{
(*rects[(k)]).set_fill_color(Color::red);
}
else if(j%2 == 0)
{
(*rects[(k)]).set_fill_color(Color::white);
}
}
else if(rects.size()<=24)
{
if(j%2 == 0  )
{
(*rects[(k)]).set_fill_color(Color::red);
}
else if(j%2 == 1)
{
(*rects[(k)]).set_fill_color(Color::white);
}
}
else if(rects.size()<=32)
{
if(j%2 == 1  )
{
(*rects[(k)]).set_fill_color(Color::red);
}
else if(j%2 == 0)
{
(*rects[(k)]).set_fill_color(Color::white);
}
}
else if(rects.size()<=40)
{
if(j%2 == 0  )
{
(*rects[(k)]).set_fill_color(Color::red);
}
else if(j%2 == 1)
{
(*rects[(k)]).set_fill_color(Color::white);
}
}
else if(rects.size()<=48)
{
if(j%2 == 1  )
{
(*rects[(k)]).set_fill_color(Color::red);
}
else if(j%2 == 0)
{
(*rects[(k)]).set_fill_color(Color::white);
}
}
else if(rects.size()<=56)
{
if(j%2 == 0  )
{
(*rects[(k)]).set_fill_color(Color::red);
}
else if(j%2 == 1)
{
(*rects[(k)]).set_fill_color(Color::white);
}
}
else if(rects.size()<=64)
{
if(j%2 == 1  )
{
(*rects[(k)]).set_fill_color(Color::red);
}
else if(j%2 == 0)
{
(*rects[(k)]).set_fill_color(Color::white);
}
}


Edited by black_darkness, 13 December 2012 - 04:47 PM.

### #2Luis Guimaraes  Members

Posted 13 December 2012 - 04:53 PM

I don't understand much of what you're doing or working with, but it looks like, without changing the logic of how you wanna paint it, you could use a for loops instead of repeating 8,16,24...64 you could make it 8 * i where i = 1,2,3...8

### #3black_darkness  Members

Posted 13 December 2012 - 05:01 PM

I don't understand much of what you're doing or working with, but it looks like, without changing the logic of how you wanna paint it, you could use a for loops instead of repeating 8,16,24...64 you could make it 8 * i where i = 1,2,3...8

Here is an explanation of the goal.

I have this information for my algorithm to work with.

* current square (or k)
* j is a counter. So it changes from even to odd every turn, letting me know if current square is even or odd. (I could use k to do this and make simpler though I think)
* I have the rects.size() (This is the size of the vector)

I want to use this information to paint a checkerboard pattern. In order to do this the first 8 must have odds painted white, and evens painted red. The second 8 must have odds painted red and evens painted white. This will alternate line by line until I get to the bottom.

I couldn't think of how to do this without manually switching every time k increases by 8.

### #4Cornstalks  Members

Posted 13 December 2012 - 05:05 PM

I think you could immediately shorten that to:

// This if statement might seem kind of magical
if (((rects.size()  / 8) % 2) == 0) // if <= 16, 32, 48, 64
{
if(j%2 == 1  )
{
(*rects[(k)]).set_fill_color(Color::red);
}
else if(j%2 == 0)
{
(*rects[(k)]).set_fill_color(Color::white);
}
}
else // <= 8, 24, 40, 56
{
if(j%2 == 0  )
{
(*rects[(k)]).set_fill_color(Color::red);
}
else if(j%2 == 1)
{
(*rects[(k)]).set_fill_color(Color::white);
}
}


However, I wouldn't actually recommend the above, and if I were you, I'd do something more like:
for (int i = 0; i < rects.size(); ++i)
{
if (((i + i / 8) % 2) == 0)
{
rects[i]->set_fill_color(Color::red);
}
else
{
rects[i]->set_fill_color(Color::white);
}
}


Edited: sorry, I messed up the above the first time. I think it's good now...

Edit again: Another alternative is the below double loop:

bool white = false;
for (int i = 0; i < rects.size(); i += 8)
{
for (int k = 0; k < 8; ++k)
{
if (white)
{
rects[i + k]->set_fill_color(Color::white);
}
else
{
rects[i + k]->set_fill_color(Color::red);
}

white = !white;
}

white = !white;
}


Edited by Cornstalks, 13 December 2012 - 05:13 PM.

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

### #5Brother Bob  Moderators

Posted 13 December 2012 - 05:10 PM

First step is to obtain the 2-dimensional coordinate of a square. For example, if k is what you call the current square is a 1-dimensional sequential index (for example you number the squares sequentially along a row, and column by column), then you can obtain the (x,y) coordinate as x=k%8 and y=k/8.

Once you have a 2-dimensional coordinate into the checker board, you can color it according to:
if(x%2 == y%2)
red square
else
white square


### #6black_darkness  Members

Posted 13 December 2012 - 05:12 PM

I think you could immediately shorten that to:

// This if statement might seem kind of magical
if (((rects.size()  / 8) % 2) == 0) // if <= 16, 32, 48, 64
{
if(j%2 == 1  )
{
(*rects[(k)]).set_fill_color(Color::red);
}
else if(j%2 == 0)
{
(*rects[(k)]).set_fill_color(Color::white);
}
}
else // <= 8, 24, 40, 56
{
if(j%2 == 0  )
{
(*rects[(k)]).set_fill_color(Color::red);
}
else if(j%2 == 1)
{
(*rects[(k)]).set_fill_color(Color::white);
}
}


Yeah I kind of want to avoid another solution like this.

However, I wouldn't actually recommend the above, and if I were you, I'd do something more like:

for (int i = 0; i < rects.size(); ++i)
{
if ((i % 2) == 0)
{
rects[i]->set_fill_color(Color::red);
}
else
{
rects[i]->set_fill_color(Color::white);
}
}


I tried that at first but since the first square on the left is always even it made a red and white stripe pattern. So that is why I was forced to switch every time k increased by 8.

### #7black_darkness  Members

Posted 13 December 2012 - 05:14 PM

First step is to obtain the 2-dimensional coordinate of a square. For example, if k is what you call the current square is a 1-dimensional sequential index (for example you number the squares sequentially along a row, and column by column), then you can obtain the (x,y) coordinate as x=k%8 and y=k/8.

Once you have a 2-dimensional coordinate into the checker board, you can color it according to:

if(x%2 == y%2)
red square
else
white square


This seems like it will work thank you. I will try to implement a 2d system.

### #8Cornstalks  Members

Posted 13 December 2012 - 05:14 PM

*snip*
I tried that at first but since the first square on the left is always even it made a red and white stripe pattern. So that is why I was forced to switch every time k increased by 8.

Sorry, yeah, I forgot to watch out for that. I've edited that post just barely to fix that and add another alternative way of doing it.

Edit: Holy ninja'ing fest... We're all replying at once ha

Edited by Cornstalks, 13 December 2012 - 05:15 PM.

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

### #9fastcall22  Moderators

Posted 13 December 2012 - 05:16 PM

Can be reduced further:
int sqIdx = 0;
for ( row = 0; row < rowCount; ++row ) { // Each row in checkerboard
for ( col = 0; col < colCount; ++col ) { // Each cell in column
Color clr;
if ( (row+col)%2 == 1 )
clr = Color::red;
else
clr = Color::white;
rects[sqIdx++]->set_fill_color(clr); // Or "row*colCount+col" in place of "sqIdx++"
}
}


And reduced further:
Color lookup[2] = { Color::red, Color::white };
for ( row = 0; row < rowCount; ++row )
for ( col = 0; col < colCount; ++col )
rects[row*colCount+col] = lookup[(row+col)&1];


Also, ninja'd to the floor.
zlib: eJzVVLsSAiEQ6/1qCwoK i7PxA/2S2zMOZljYB1TO ZG7OhUtiduH9egZQCJH9 KcJyo4Wq9t0/RXkKmjx+ cgU4FIMWHhKCU+o/Nx2R LEPgQWLtnfcErbiEl0u4 0UrMghhZewgYcptoEF42 YMj+Z1kg+bVvqxhyo17h nUf+h4b2W4bR4XO01TJ7 qFNzA7jjbxyL71Avh6Tv odnFk4hnxxAf4w6496Kd OgH7/RxC

### #10black_darkness  Members

Posted 13 December 2012 - 05:36 PM

Hey Cornstalks I wrote a test and it works but It is switching 1 square too soon.

Here is the test I wrote.
#include <iostream>
int main()
{
using namespace std;
int ooo_test = (1+1/8) % 2;
cout<<"square 1 is: "<<ooo_test<<"\n";
ooo_test = (2+2/8) % 2;
cout<<"square 2 is: "<<ooo_test<<"\n";
ooo_test = (3+3/8) % 2;
cout<<"square 3 is: "<<ooo_test<<"\n";
ooo_test = (4+4/8) % 2;
cout<<"square 4 is: "<<ooo_test<<"\n";
ooo_test = (5+6/8) % 2;
cout<<"square 5 is: "<<ooo_test<<"\n";
ooo_test = (6+6/8) % 2;
cout<<"square 6 is: "<<ooo_test<<"\n";
ooo_test = (7+7/8) % 2;
cout<<"square 7 is: "<<ooo_test<<"\n";
ooo_test = (8+8/8) % 2;
cout<<"square 8 is: "<<ooo_test<<"\n";
cin>>ooo_test;
}


### #11Cornstalks  Members

Posted 13 December 2012 - 05:47 PM

POPULAR

In C++, indices start at zero, not one, so your first one should be 0 + 0 / 8, your second 1 + 1 / 8, third 2 + 2 / 8, etc.
[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

### #12fastcall22  Moderators

Posted 13 December 2012 - 05:49 PM

Hey Cornstalks I wrote a test and it works but It is switching 1 square too soon.

The test actually works, but you are misinterpreting the results. Square 1 is the second square of the first row, and square 8 is the first square of the second row. Both square 1 and square 8 should be red. Square 0, the first square of the first row, on the other hand, should be (and is) white.
zlib: eJzVVLsSAiEQ6/1qCwoK i7PxA/2S2zMOZljYB1TO ZG7OhUtiduH9egZQCJH9 KcJyo4Wq9t0/RXkKmjx+ cgU4FIMWHhKCU+o/Nx2R LEPgQWLtnfcErbiEl0u4 0UrMghhZewgYcptoEF42 YMj+Z1kg+bVvqxhyo17h nUf+h4b2W4bR4XO01TJ7 qFNzA7jjbxyL71Avh6Tv odnFk4hnxxAf4w6496Kd OgH7/RxC

### #13black_darkness  Members

Posted 13 December 2012 - 05:52 PM

In C++, indices start at zero, not one, so your first one should be 0 + 0 / 8, your second 1 + 1 / 8, third 2 + 2 / 8, etc.

Thank you for the algorithm. I will have to keep this in mind. Is there a formal name for this type of algorithm?

anyways look how elegant you made it look. I am very pleased.

if((k+k/8)%2 == 0) {
(*rects[(k)]).set_fill_color(Color::red);
}
else if((k+k/8)%2 == 1) {
(*rects[(k)]).set_fill_color(Color::white);
}
k++;


### #14black_darkness  Members

Posted 13 December 2012 - 06:01 PM

Hey Cornstalks I wrote a test and it works but It is switching 1 square too soon.

The test actually works, but you are misinterpreting the results. Square 1 is the second square of the first row, and square 8 is the first square of the second row. Both square 1 and square 8 should be red. Square 0, the first square of the first row, on the other hand, should be (and is) white.

I always thought that if you wrote a for loop it added one then ran what was inside the curly braces. oops. You were right. I wrote this test. I always did get a lot of 1 off errors.

#include <iostream>;
int main()
{
using namespace std;
for(int i=0;i<5;i++)
{
cout<<i<<"\n";
}
return 0;
}


and this was the output.

### #15Álvaro  Members

Posted 13 December 2012 - 06:08 PM

POPULAR

bool is_red(int x, int y) {

return (x+y)%2 == 0;

}

// ...

rects[k]->set_fill_color(is_red(k,k/8) ? Color::red : Color::white);

// ...

### #16Yrjö P.  Members

Posted 13 December 2012 - 07:57 PM

POPULAR

Couldn't resist bringing this thread to its logical conclusion by one-lining Álvaro's code. 87-fold code compression relative to the initial post.
rects[k]->set_fill_color(!((k+k/8)%2) ? Color::red : Color::white);
edit: and since it's a beginner thread, public service announcement: mangling code like I just did is evil and has absolutely no point besides comedic purposes; don't do this if you intend to actually use the code for something.

Edited by Stroppy Katamari, 13 December 2012 - 08:06 PM.

### #17/Jeff/  Members

Posted 13 December 2012 - 08:13 PM

Well then at least remove the "!" by switching the colors around

rects[k]->set_fill_color((k+k/8)%2 ? Color::white : Color::red);


### #18Cornstalks  Members

Posted 13 December 2012 - 09:12 PM

Thank you for the algorithm. I will have to keep this in mind. Is there a formal name for this type of algorithm?

Yes, the formal name is the Cornstalks Algorithm
Just kidding, there isn't a formal name for it. It might be possible to generalize it to a larger, more complex algorithm that has a formal name, but I just came up with this off the top of my head. Years of programming will do that to you...

I always thought that if you wrote a for loop it added one then ran what was inside the curly braces. oops. You were right. I wrote this test. I always did get a lot of 1 off errors.

I'll break down a for loop like this:
for (A; B; C)
D;

Step 1: A is done (A is usually creating and setting a variable, like int i = 0). Step 2: B is checked (B is the looping condition, and as long as it's true the loop is run). Step 3: D is run. Step 4: C is run (which is usually what updates the loop counter). Then it goes back to step 2 and repeats until B is false.

Couldn't resist bringing this thread to its logical conclusion by one-lining Álvaro's code.

One liner? (Added the loop )
// This:
for (int y = 0; y < 8; ++y) for (int x = 0; x < 8; ++x) rects[x + y * 8]->set_fill_color(((x + y) % 2) ? Color::white : Color::red);

// Or:
for (int i = 0; i < rects.size(); ++i) rects[i]->set_fill_color(((i + i / 8) % 2) ? Color::white : Color::red);

// But seriously, I hope no one ever does this in real life. Use *at least* two lines...


Edited by Cornstalks, 13 December 2012 - 09:13 PM.

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

### #19Khatharr  Members

Posted 13 December 2012 - 09:30 PM

To test for odd vs even don't use modulation. Just binary-and with 1.

0 & 1 = 0
1 & 1 = 1
2 & 1 = 0
3 & 1 = 1
4 & 1 = 0
5 & 1 = 1

Edited by Khatharr, 13 December 2012 - 09:30 PM.

void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

### #20Cornstalks  Members

Posted 13 December 2012 - 09:42 PM

POPULAR

To test for odd vs even don't use modulation. Just binary-and with 1.

This is what I sometimes do, but I'm going to mention this for future readers because I know someone's going to do this and spend some good time debugging:
Operator precedence for & is different than it is for %. % has the same precedence as * and /, but & has precedence just below == and !=. Just be aware of this, all you readers.

Example:
if (8 & 1 == 0) // uh oh.. this actually reads as (8 & (1 == 0)), so you better use parentheses!
if (8 % 2 == 0) // this does what you expect and reads as ((8 % 2) == 0)


[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.