Programming Forums
User Name Password Register
 

RSS Feed
FORUM INDEX | TODAY'S POSTS | UNANSWERED THREADS | ADVANCED SEARCH

Reply
 
Thread Tools Display Modes
Old Feb 1st, 2008, 7:18 PM   #1
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Waterloo, Ontario
Posts: 2,035
Rep Power: 6 Sane will become famous soon enough
Send a message via MSN to Sane
Smile 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.

C Syntax (Toggle Plain Text) 
  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
(Toggle Plain Text) 
4 5 2 3 2
.****
.****
.****
.****

Output File 1
(Toggle Plain Text) 
2

Input File 2
(Toggle Plain Text) 
4 5 2 3 2
**...
*...*
.*..*
**...

Output File 2
(Toggle Plain Text) 
0

Input File 3
(Toggle Plain Text) 
4 5 2 3 2
*..**
*....
**..*
.*.*.

Output File 3
(Toggle Plain Text) 
1

Input File 4
(Toggle Plain Text) 
3 4 3 4 3
.**.
....
.**.

Output File 4
(Toggle Plain Text) 
4

Input File 5
(Toggle Plain Text) 
3 2 2 3 2
**
*.
**

Output File 5
(Toggle Plain Text) 
-1
Sane is offline   Reply With Quote
Old Feb 3rd, 2008, 1:02 PM   #2
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Waterloo, Ontario
Posts: 2,035
Rep Power: 6 Sane will become famous soon enough
Send a message via MSN to Sane
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.

(Toggle Plain Text) 
@@..
@@..
.@..
....

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

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

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

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

(Toggle Plain Text) 
@@..
..@.
@@..
....

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

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

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

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?
Last edited by Sane; Feb 3rd, 2008 at 1:14 PM.
Sane is offline   Reply With Quote
Old Feb 5th, 2008, 9:31 AM   #3
The Dark
Expert Programmer
 
Join Date: Jun 2005
Posts: 882
Rep Power: 4 The Dark is on a distinguished road
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.
The Dark is offline   Reply With Quote
Old Feb 5th, 2008, 4:00 PM   #4
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Waterloo, Ontario
Posts: 2,035
Rep Power: 6 Sane will become famous soon enough
Send a message via MSN to Sane
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.
Sane is offline   Reply With Quote
Old Feb 6th, 2008, 11:25 PM   #5
OpenLoop
Expert Programmer
 
OpenLoop's Avatar
 
Join Date: May 2005
Location: East Lansing, MI
Posts: 663
Rep Power: 4 OpenLoop is on a distinguished road
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:

c Syntax (Toggle Plain Text) 
  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. }
OpenLoop is offline   Reply With Quote
Old Feb 7th, 2008, 12:22 AM   #6
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Waterloo, Ontario
Posts: 2,035
Rep Power: 6 Sane will become famous soon enough
Send a message via MSN to Sane
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.

(Toggle Plain Text) 
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"} 
};
Sane is offline   Reply With Quote
Old Feb 7th, 2008, 8:13 AM   #7
OpenLoop
Expert Programmer
 
OpenLoop's Avatar
 
Join Date: May 2005
Location: East Lansing, MI
Posts: 663
Rep Power: 4 OpenLoop is on a distinguished road
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.
c Syntax (Toggle Plain Text) 
  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. };
OpenLoop is offline   Reply With Quote
Old Feb 7th, 2008, 4:59 PM   #8
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Waterloo, Ontario
Posts: 2,035
Rep Power: 6 Sane will become famous soon enough
Send a message via MSN to Sane
Re: Conway's Game Of Life - Programming Challenge
Quote:
Originally Posted by OpenLoop View Post
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 is offline   Reply With Quote
Old Mar 1st, 2008, 3:04 PM   #9
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Waterloo, Ontario
Posts: 2,035
Rep Power: 6 Sane will become famous soon enough
Send a message via MSN to Sane
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.

C Syntax (Toggle Plain Text) 
  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"            ;}
__________________
Looking for tough programming challenges? Try participating in Sane's Monthly Algorithms Challenges!
Composing Techno is a little side hobby of mine. Techno by DJ Sane. All free for download.
Last edited by Sane; Mar 1st, 2008 at 3:28 PM.
Sane is offline   Reply With Quote
Reply

Bookmarks

« Previous Thread in Forum | Next Thread in Forum »

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes
Linear Mode Linear Mode

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
BB code is On
Smilies are On
[IMG] code is On
HTML code is Off