• Create Account

# 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   -  Reputation: 280

Like
3Likes
Like

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   -  Reputation: 231

Like
3Likes
Like

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   -  Reputation: 280

Like
1Likes
Like

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  Crossbones+   -  Reputation: 6866

Like
4Likes
Like

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   -  Reputation: 7141

Like
4Likes
Like

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   -  Reputation: 280

Like
1Likes
Like

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   -  Reputation: 280

Like
1Likes
Like

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  Crossbones+   -  Reputation: 6866

Like
2Likes
Like

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  Crossbones+   -  Reputation: 2705

Like
4Likes
Like

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.

### #10black_darkness  Members   -  Reputation: 280

Like
0Likes
Like

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  Crossbones+   -  Reputation: 6866

Like
6Likes
Like

Posted 13 December 2012 - 05:47 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.
[ 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  Crossbones+   -  Reputation: 2705

Like
3Likes
Like

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.

### #13black_darkness  Members   -  Reputation: 280

Like
0Likes
Like

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   -  Reputation: 280

Like
1Likes
Like

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  Crossbones+   -  Reputation: 9886

Like
5Likes
Like

Posted 13 December 2012 - 06:08 PM

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.  Crossbones+   -  Reputation: 1408

Like
5Likes
Like

Posted 13 December 2012 - 07:57 PM

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.

### #17jrh2365  Members   -  Reputation: 568

Like
2Likes
Like

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  Crossbones+   -  Reputation: 6866

Like
2Likes
Like

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  Crossbones+   -  Reputation: 2589

Like
2Likes
Like

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  Crossbones+   -  Reputation: 6866

Like
5Likes
Like

Posted 13 December 2012 - 09:42 PM

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.

PARTNERS