Programming Forums

Programming Forums (http://www.programmingforums.org/forumindex.php)
-   Software Design and Algorithms (http://www.programmingforums.org/forum64.html)
-   -   Conway's Game Of Life - Programming Challenge (http://www.programmingforums.org/showthread.php?t=15104)

Sane Feb 1st, 2008 6:18 PM
Conway's Game Of Life - Programming Challenge
 
You've all heard of the game of life right? If you haven't, head on over to ol' Wikipedia.

I stumbled across a very interesting, and difficult, programming problem.

Page 12, Origin of Life) http://cemc.math.uwaterloo.ca/ccc/2006/senior.pdf

The only solution I could think up was brute-force. This is due to the fact that there does not seem to be any logical way to find a board's previous setup. Each board only has one next generation, but every generation could have come from a large number of previous generations.

So instead of working backwards from a setup, I worked forwards for each setup. I generated every possible 5x4 grid, by identifying the set and unset bits in every number from 1 to 1048576 (2^(5x4)). For each setup, I computed the next generation, and stored the current generation in a list of possible previous generations for the next generation. Then finally, I ran a depth first search through the backpointers, to find the closest node that contained no backpointer.

Have any ideas for a better way to do it? I'd like to see what you guys and gals got.

:
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5. int w, h;
  6. int a, b, c;
  7. unsigned combs;
  8.  
  9. typedef struct self_life {
  10.     struct self_life *next; // Linked list 
  11.     unsigned prev; // Link to last generation
  12. } t_life;
  13.  
  14. int grid[7][6] = {0};
  15. t_life *lives[1048576] = {NULL}; // 2^(4*5) = 1048576
  16. int chalk[1048576] = {0};
  17.  
  18. int merge(int x, int y) {
  19.     if(!x) return y;
  20.     if(!y) return x;
  21.     return x < y ? x : y;
  22. }
  23.  
  24. int get_shortest(unsigned n) {
  25.     int shortest = 0;
  26.     if (chalk[n]) return 0;
  27.     chalk[n] = 1;
  28.  
  29.     t_life *life = lives[n];
  30.     if (!life) return 1;
  31.  
  32.     while (life) {
  33.         shortest = merge(get_shortest(life->prev), shortest);
  34.         life = life->next;
  35.     }
  36.     return (shortest) ? (shortest+1) : (0);
  37. }
  38.  
  39. unsigned nextgen() {
  40.     unsigned comb = 0;
  41.     int x, y, n;
  42.     for(y=1;y<=h;y++) {
  43.         for(x=1;x<=w;x++) {
  44.             comb = (comb << 1);
  45.             n = grid[x-1][y-1] + grid[x][y-1] + grid[x+1][y-1] + 
  46.                 grid[x-1][y]   +                grid[x+1][y]   + 
  47.                 grid[x-1][y+1] + grid[x][y+1] + grid[x+1][y+1];
  48.             if      ( grid[x][y] && n<a) continue;
  49.             else if ( grid[x][y] && n>b) continue;
  50.             else if (!grid[x][y] && n>c) comb += 1;
  51.             else                         comb += grid[x][y];
  52.         }
  53.     }
  54.     return comb;
  55. }
  56.  
  57. void clean(t_life *node) {
  58.     if(!node)return;
  59.     clean(node->next);
  60.     free(node);
  61. }
  62.  
  63. int main() {
  64.  
  65.     unsigned n, t;
  66.     int x, y;
  67.     char l;
  68.     t_life *next_life;
  69.  
  70.     freopen("s5.in", "rt", stdin);
  71.     // freopen("s5.out", "wt", stdout);
  72.     scanf("%d %d %d %d %d\n", &h, &w, &a, &b, &c);
  73.  
  74.     combs = pow(2, w*h);
  75.     for(n=0;n<combs;n++) {
  76.         t=n;
  77.         for(y=h;y>0;y--) {
  78.             for(x=w;x>0;x--) {
  79.                 grid[x][y] = (n & 1);
  80.                 n = (n >> 1); 
  81.             } 
  82.         }
  83.         n=t;
  84.  
  85.         t = nextgen();
  86.         next_life = (t_life *)malloc(sizeof(t_life));
  87.         next_life->prev = n;
  88.         next_life->next = lives[t];
  89.         lives[t] = next_life;
  90.     }
  91.  
  92.     n = 0;
  93.     for(y=0;y<h;y++) {
  94.         for(x=0;x<w;x++) {
  95.             scanf("%c", &l);
  96.             n = (n << 1);
  97.             n += (l == '*');
  98.         }
  99.         scanf("\n");
  100.     }
  101.     printf("%d\n", get_shortest(n)-1);
  102.  
  103.     for(n=0;n<combs;n++) clean(lives[n]);
  104.     return 0;
  105.  
  106. }

Input File 1
:
4 5 2 3 2
.****
.****
.****
.****

Output File 1
:
2

Input File 2
:
4 5 2 3 2
**...
*...*
.*..*
**...

Output File 2
:
0

Input File 3
:
4 5 2 3 2
*..**
*....
**..*
.*.*.

Output File 3
:
1

Input File 4
:
3 4 3 4 3
.**.
....
.**.

Output File 4
:
4

Input File 5
:
3 2 2 3 2
**
*.
**

Output File 5
:
-1

Sane Feb 3rd, 2008 12:02 PM
Re: Conway's Game Of Life - Programming Challenge
 
I noticed there aren't any replies yet. But I have some added discussion material. Ideas for an improved algorithm.
  1. Take the starting position
  2. Generate all permutations of boards that differ by adjacent squares (to live cells)
  3. See which permutations have a next generation equal to the current generation
  4. Mark each valid permutation as a previous generation for the current generation
  5. Recurse again to step 2 for every valid permutation from step 4
  6. Stop when a setup has no previous generations, or cycles back to a previously visited generation

It would be difficult, but much more optimal since only the setups relevant to the problem are computed.

Only I'm not sure if that would work. Because previous generations can have other live cells in unadjacent cells to the next generation. Sometimes a bunch of cells can simply die out.


Then I thought of a further optimization:

Every setup has 3 symmetrical buddies, which will all result in next generations that are symmetrical to each other.

:
@@..
@@..
.@..
....

..@@
..@@
..@.
....

....
.@..
@@..
@@..

....
..@.
..@@
..@@

The next generation of each of those setups will be symmetrical to each other.

:
@@..
..@.
@@..
....

..@@
.@..
..@@
....

....
@@..
..@.
@@..

....
..@@
.@..
..@@

Therefore, only a bit over 1/4 of the generations need to be computed if we test for symmetry. Haven't yet delved completely into this idea, but there should be a very optimal way to test if the "comb" value is symmetrical.

Thoughts?

The Dark Feb 5th, 2008 8:31 AM
Re: Conway's Game Of Life - Programming Challenge
 
I didn't reply because I couldn't think of an better algorithm and didn't have the time to put in any real effort.
I think, given the 5x4 size limit, computing the results for all possible layouts would be the simplest way and probably would have been best for a time limited problem. Using the mirroring would make it even faster to calculate the next-gen map.

The only other idea I was toying with was trying to determine the possible parents by marking each position with the number of surrounding objects it must have had in the previous generation (possibly including itself). Then you end up with a sort of minesweeper problem to work out where the parent objects were.

Just thought I'd reply to let you know that at least someone was reading this, even if there were no replies. Keep the problems coming when you find good ones, I find them interesting. Thanks.

Sane Feb 5th, 2008 3:00 PM
Re: Conway's Game Of Life - Programming Challenge
 
Thanks for the shout. I was feeling pretty lonely here. :)

The minesweeper idea is neat. But I'm not sure how well it could work, because the number of objects it could have previously had adjacent to any square is not an exact number. It is a always less than or greater than a certain amount, rarely equal. It would make the (already difficult) challenge of a minesweeper algorithm even more complicated I think.

OpenLoop Feb 6th, 2008 10:25 PM
Re: Conway's Game Of Life - Programming Challenge
 
I've never heard of Conway's game of life before you mentionned. The output is rather amuzing. Here's my code with a Diehard starting pattern which will generate 129 different paterns before dying on the 130th. It's not build for speed or readability, just for fun:

:
  1. #include <iostream>
  2. #include <string>
  3.  
  4. #define COLS 60
  5. #define ROWS 25
  6.  
  7. using namespace std;
  8.  
  9. char inpGen[ROWS][COLS] = {
  10. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  11. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  12. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  13. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  14. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  15. {"00000000000000000010000000000000000000000000000000000000000"},                                                   
  16. {"00000000000011000000000000000000000000000000000000000000000"},                                                   
  17. {"00000000000001000111000000000000000000000000000000000000000"},                                                   
  18. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  19. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  20. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  21. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  22. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  23. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  24. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  25. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  26. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  27. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  28. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  29. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  30. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  31. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  32. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  33. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  34. {"00000000000000000000000000000000000000000000000000000000000"} 
  35. };
  36.  
  37. int curGen[ROWS][COLS];
  38. int nxtGen[ROWS][COLS];
  39. int evalCell(int i, int j);
  40. int getInt(char c){return ((c=='1')?1:0);}
  41. void printArray(){for(int i=0;i<ROWS; i++){for(int j=0;j<COLS; j++){cout<<(curGen[i][j]?"@":".");}cout<<endl;}}
  42. void swapArrays(){for(int i=0;i<ROWS; i++){for(int j=0;j<COLS;j++) curGen[i][j]=nxtGen[i][j];}}
  43. void parseInput(){for(int i=0;i<ROWS; i++){for(int j=0;j<COLS;j++) curGen[i][j]=getInt(inpGen[i][j]);}}
  44.  
  45. int main()
  46. {
  47.         int i = 0, j = 0, k = 1;        
  48.         parseInput();
  49.         printArray();        
  50.         cout<<"\n";
  51.  
  52.         while(1)
  53.         {
  54.                 for (i = 1; i < ROWS-1; i++)                
  55.                         for(j = 1; j < COLS-1; j++)
  56.                                 nxtGen[i][j] = evalCell(i,j);                                                
  57.                 swapArrays();
  58.                 cout<<"\n\nIteration "<<k++<<endl;
  59.                 printArray();                
  60.                 for(i = 1; i < 100000000; i++);  //artificial delay
  61.         }
  62.         return 0;
  63. }
  64.  
  65. int evalCell(int i, int j)
  66. {
  67.         int liveNeighbors=curGen[i-1][j-1]+curGen[i-1][j]+curGen[i-1][j+1]+curGen[i][j-1]+curGen[i][j+1]+curGen[i+1][j-1]+curGen[i+1][j]+curGen[i+1][j+1];    
  68.         return (curGen[i][j]&&((liveNeighbors<2)||(liveNeighbors>3)))?0:(liveNeighbors==3?1:curGen[i][j]);                 
  69. }

Sane Feb 6th, 2008 11:22 PM
Re: Conway's Game Of Life - Programming Challenge
 
Hehe. Amusing huh? :)

Quite a fascinating game. Probably the most interesting game that you can't "play".

One thing you might want to think about adding is a test to see if all the cells are dead. If they are, then stop, and output how many generations the cells survived for.

Edit:

And while we're on the topic, here is one I invented. I like to call it "Napalm". This little devil explodes quite spectacularly out from the center, and then continues to emit small explosions, until eventually settling and leaving behind two small craters in the middle. Run at maximum speed for full effect. :)

Copyright Sane. ;)

:
char inpGen[ROWS][COLS] = {
{"00000000000000000000000000000000000000000000000000000000000"},                                         
{"00000000000000000000000000000000000000000000000000000000000"},                                         
{"00000000000000000000000000000000000000000000000000000000000"},                                         
{"00000000000000000000000000000000000000000000000000000000000"},                                         
{"00000000000000000000000000000000000000000000000000000000000"},                                         
{"00000000000000000000000000000000000000000000000000000000000"},                                         
{"00000000000000000000000000000000000000000000000000000000000"},                                         
{"00000000000000000000000000000000000000000000000000000000000"},                                         
{"00000000000000000000000000000000000000000000000000000000000"},                                         
{"00000000000000000000000000000000000000000000000000000000000"},                                         
{"00000000000000000000000001000000000000000000000000000000000"},                                                 
{"00000000000000000000000010100000000000000000000000000000000"},                         
{"00000000000000000000000100010000000000000000000000000000000"},                                                 
{"00000000000000000000000100010000000000000000000000000000000"},                                                 
{"00000000000000000000000000000000000000000000000000000000000"},                                                 
{"00000000000000000000000000000000000000000000000000000000000"},                                                 
{"00000000000000000000000000000000000000000000000000000000000"},                                                 
{"00000000000000000000000000000000000000000000000000000000000"},                                                 
{"00000000000000000000000000000000000000000000000000000000000"},                                                 
{"00000000000000000000000000000000000000000000000000000000000"},                                                 
{"00000000000000000000000000000000000000000000000000000000000"},                                                 
{"00000000000000000000000000000000000000000000000000000000000"},                                                 
{"00000000000000000000000000000000000000000000000000000000000"},                                                 
{"00000000000000000000000000000000000000000000000000000000000"},                                                 
{"00000000000000000000000000000000000000000000000000000000000"}
};

OpenLoop Feb 7th, 2008 7:13 AM
Re: Conway's Game Of Life - Programming Challenge
 
What amazes me the most is how you can get so many complex pattern from a mere 5 units pattern. I'm trying to think of a use for this behind the scenes in a processing program but I can't wrap my head around it yet.
Here's one that does 30 different pattern before lapsing into a 3 phase oscillator that goes on forever.
:
  1. char inpGen[ROWS][COLS] = {
  2. {"00000000000000000000000000000000000000000000000000000000000"},                                           
  3. {"00000000000000000000000000000000000000000000000000000000000"},                                           
  4. {"00000000000000000000000000000000000000000000000000000000000"},                                           
  5. {"00000000000000000000000000000000000000000000000000000000000"},                                           
  6. {"00000000000000000000000000000000000000000000000000000000000"},                                           
  7. {"00000000000000000000000000000000000000000000000000000000000"},                                           
  8. {"00000000000000000000000000000000000000000000000000000000000"},                                           
  9. {"00000000000000000000000000000000000000000000000000000000000"},                                           
  10. {"00000000000000000000000000000000000000000000000000000000000"},                                           
  11. {"00000000000000000000000000000000000000000000000000000000000"},                                           
  12. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  13. {"00000000000000000000000000000000000000000000000000000000000"},                           
  14. {"00000000000000000000000100010000000000000000000000000000000"},                                                   
  15. {"00000000000000000000000111110000000000000000000000000000000"},                                                   
  16. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  17. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  18. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  19. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  20. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  21. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  22. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  23. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  24. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  25. {"00000000000000000000000000000000000000000000000000000000000"},                                                   
  26. {"00000000000000000000000000000000000000000000000000000000000"} 
  27. };

Sane Feb 7th, 2008 3:59 PM
Re: Conway's Game Of Life - Programming Challenge
 
Quote:
Originally Posted by OpenLoop (Post 140797)
I'm trying to think of a use for this behind the scenes in a processing program but I can't wrap my head around it yet.
I've always wondered how well the psuedo-randomness would work out in something like a hashing algorithm. Since as far as I can tell from my findings in this thread, a board setup is irreversable. Therefore, a 1000x1000 board with n>30 transformations would need a quantum computer to brute force the source of a hash. One big problem is I don't know how to make it satisfy the Pigeonhole Principle.

Sane Mar 1st, 2008 2:04 PM
Re: Conway's Game Of Life - Programming Challenge
 
I just thought I'd post something I submitted to an Obfuscated Code contest, since it's related to the above few posts.

Note the "glider" embedded in the center of the code.

:
  1. #include                                <stdio.h>
  2. #include                               <stdlib.h>
  3. #include                                 <time.h>
  4. #define v                                     '='
  5. #define i                                 '='+'='
  6. #define w                                   while
  7. #define _()                         system("cls")
  8. int c[0X763]={0},cc[0X763]={0};int cccc,ccccc;ccc
  9. (){for(cccc=1;cccc<0X763;cccc++){ccccc=c[cccc%i*(
  10. cccc/v)-'>']+c[cccc%i*(cccc/v)-v]+c[cccc%v-'<'+v*
  11. (cccc/v)]+c[cccc%v-1+      v*(cccc/v)]+c[cccc%v+1
  12. +v* (cccc/v)]+c[cccc%      v+'<'+v*(cccc/v)]+ c [
  13. cccc%i*(cccc/v)+v]+ c      [cccc%i*(cccc/v)+'>'];
  14. cc[cccc%i*(cccc/v)]=c[cccc%i*(cccc/v)]&&ccccc<2?0
  15. :c[cccc%i*(cccc/v)]&&ccccc>3      ?0:!c[cccc%i* (
  16. cccc/v)]&&ccccc==3?1:c[cccc%      i*(cccc/v)]  ;}
  17. memcpy(c,cc,sizeof(c));for (      cccc=1 ; cccc <
  18. 0X763;cccc++){putchar(c[cccc%i*(cccc/v)]?'#':' ')
  19. ;ccccc=(!(cccc      %      v      ))?putchar(10):
  20. 0;}sleep(0X190      )      ;      _();}main( ) {;
  21. ;{}; c[0X3A2]=      c      [      0X3A3]=c[0X3A4]
  22. =c[0X3A7]=c[0X3A8]=c[0X3E2]=c[0X421]=1;w(c)ccc();
  23. char __[]=  "Conway's Game Of Life"            ;}


All times are GMT -5. The time now is 11:20 PM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC