Jump to content

  • Log In with Google      Sign In   
  • 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.

  • You cannot reply to this topic
24 replies to this topic

#1 black_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)
Posted Image

Now after implementing my algorithm it looks like this.
Posted Image


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.


Sponsor:

#2 Luis 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

#3 black_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.

#4 Cornstalks   Crossbones+   -  Reputation: 6966

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 ]

#5 Brother Bob   Moderators   -  Reputation: 7746

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


#6 black_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.

#7 black_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.

#8 Cornstalks   Crossbones+   -  Reputation: 6966

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 ]

#9 fastcall22   Crossbones+   -  Reputation: 3633

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. :(

WW91J3ZlIGdvdCBhIHNlY3JldCBib251cyBwb2ludCE=


#10 black_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.

Posted Image

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


#11 Cornstalks   Crossbones+   -  Reputation: 6966

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 ]

#12 fastcall22   Crossbones+   -  Reputation: 3633

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.

WW91J3ZlIGdvdCBhIHNlY3JldCBib251cyBwb2ludCE=


#13 black_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++;


#14 black_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.
Posted Image

#15 Álvaro   Crossbones+   -  Reputation: 11710

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

// ...


#16 Yrjö P.   Crossbones+   -  Reputation: 1412

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. Posted Image
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 jrh2365   Members   -  Reputation: 579

Like
2Likes
Like

Posted 13 December 2012 - 08:13 PM

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

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


#18 Cornstalks   Crossbones+   -  Reputation: 6966

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 Posted Image
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 Posted Image)
// 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 ]

#19 Khatharr   Crossbones+   -  Reputation: 2773

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.

#20 Cornstalks   Crossbones+   -  Reputation: 6966

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