Skip to content

Instantly share code, notes, and snippets.

@paultag
Created February 22, 2011 06:07
Show Gist options
  • Save paultag/838285 to your computer and use it in GitHub Desktop.
Save paultag/838285 to your computer and use it in GitHub Desktop.
Goofy Game of Life impl
#include <iostream>
#include <limits.h>
#include <math.h>
using namespace std;
int WORLD = 0;
int LASTWORLD = 0;
int NEWWORLD = 0;
const int ROW_L = sqrt(log2(INT_MAX));
const int set[3] = { -1, 0, 1 };
int offset( int x, int y ) {
int offset_bit = (y*ROW_L)+x;
int numeric_val = pow(2,offset_bit);
return numeric_val;
}
int getX( int offset ) {
return ( offset % ROW_L );
}
int getY( int offset ) {
return ( offset / ROW_L );
}
int pokeCell( int x, int y ) {
if (
x >= 0 && y >= 0 &&
x < ROW_L && y < ROW_L
) {
int bit = offset(x, y);
return ( WORLD & bit ) != 0;
} else {
return -1;
}
}
void setCell(int x, int y) {
int bit = offset(x,y);
WORLD += bit;
}
void unsetCell(int x, int y) {
int bit = offset(x,y);
WORLD -= bit;
}
int getDelta() {
int ret = (WORLD & LASTWORLD);
return (WORLD-ret);
}
int getNextOffset( int MIDWORLD ) {
int oldmidworld = MIDWORLD;
MIDWORLD = ((MIDWORLD) & (MIDWORLD-1));
if ( MIDWORLD == 0 )
if ( oldmidworld != 0 )
return oldmidworld;
else
return 0;
else
return oldmidworld^MIDWORLD;
}
void processNode( int x, int y ) {
int nCount = 0;
for ( int i = 0; i < 3; ++i )
for ( int n = 0; n < 3; ++n )
if ( pokeCell(x+set[i], y+set[n]) == 1 )
if (!( set[i] == 0 && set[n] == 0 ))
nCount++;
int bitflag = offset(x,y);
if ( nCount < 2 || nCount > 3 )
if ( ( NEWWORLD & bitflag ) > 0 )
NEWWORLD -= bitflag;
if ( nCount == 3 )
if ( ( NEWWORLD & bitflag ) == 0 )
NEWWORLD += bitflag;
}
void processNode( int x, int y, int flag ) {
if ( flag )
for ( int i = 0; i < 3; ++i )
for ( int n = 0; n < 3; ++n )
processNode(x+set[i], y+set[n]);
}
void renderWorld() {
for ( int i = 0; i < ROW_L; ++i ) {
for ( int n = 0; n < ROW_L; ++n )
if ( pokeCell(i,n) )
std::cout << " O";
else
std::cout << " X";
std::cout << std::endl;
}
std::cout << std::endl;
}
int main( int argc, char ** argv ) {
setCell(2,1);
setCell(2,2);
setCell(2,3);
while ( WORLD != LASTWORLD ) {
renderWorld();
NEWWORLD = WORLD;
int delt = getDelta();
int next = getNextOffset(delt);
delt -= next;
while ( next != 0 ) {
int x = getX(log2(next));
int y = getY(log2(next));
processNode(x,y,1);
next = getNextOffset(delt);
delt -= next;
}
if ( NEWWORLD == LASTWORLD ) {
std::cout << "Hey! This loops! Cool!" << std::endl;
LASTWORLD = NEWWORLD;
WORLD = NEWWORLD;
}
LASTWORLD = WORLD;
WORLD = NEWWORLD;
}
std::cout << "All set. This is the final state." << std::endl << std::endl;
renderWorld();
}
@agamez
Copy link

agamez commented Dec 31, 2011

int numeric_val = pow(2,offset_bit);
pow, really? I will assume it's killing all the performance you're trying to get with all the bit management!
why not
int numeric_val = 1 << offset_bit;
This should be just one or two CPU instructions, you will leave out math.h and save one function call.

I think I should say the same about using C++ std:cout << instead of simply puts(). Not that it matters to the algorithm itself, but seems like overkill.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment