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.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int w, h;
int a, b, c;
unsigned combs;
typedef struct self_life {
struct self_life *next; // Linked list
unsigned prev; // Link to last generation
} t_life;
int grid[7][6] = {0};
t_life *lives[1048576] = {NULL}; // 2^(4*5) = 1048576
int chalk[1048576] = {0};
int merge(int x, int y) {
if(!x) return y;
if(!y) return x;
return x < y ? x : y;
}
int get_shortest(unsigned n) {
int shortest = 0;
if (chalk[n]) return 0;
chalk[n] = 1;
t_life *life = lives[n];
if (!life) return 1;
while (life) {
shortest = merge(get_shortest(life->prev), shortest);
life = life->next;
}
return (shortest) ? (shortest+1) : (0);
}
unsigned nextgen() {
unsigned comb = 0;
int x, y, n;
for(y=1;y<=h;y++) {
for(x=1;x<=w;x++) {
comb = (comb << 1);
n = grid[x-1][y-1] + grid[x][y-1] + grid[x+1][y-1] +
grid[x-1][y] + grid[x+1][y] +
grid[x-1][y+1] + grid[x][y+1] + grid[x+1][y+1];
if ( grid
[x
][y
] && n<a
) continue;
else if ( grid[x][y] && n>b) continue;
else if (!grid[x][y] && n>c) comb += 1;
else comb += grid[x][y];
}
}
return comb;
}
void clean(t_life *node) {
if(!node)return;
clean(node->next);
free(node);
}
int main() {
unsigned n, t;
int x, y;
char l;
t_life *next_life;
freopen("s5.in", "rt", stdin);
// freopen("s5.out", "wt", stdout);
scanf("%d %d %d %d %d\n", &h, &w, &a, &b, &c);
combs = pow(2, w*h);
for(n=0;n<combs;n++) {
t=n;
for(y=h;y>0;y--) {
for(x=w;x>0;x--) {
grid[x][y] = (n & 1);
n = (n >> 1);
}
}
n=t;
t = nextgen();
next_life = (t_life *)malloc(sizeof(t_life));
next_life->prev = n;
next_life->next = lives[t];
lives[t] = next_life;
}
n = 0;
for(y=0;y<h;y++) {
for(x=0;x<w;x++) {
scanf("%c", &l);
n = (n << 1);
n += (l == '*');
}
scanf("\n");
}
printf("%d\n", get_shortest(n)-1);
for(n=0;n<combs;n++) clean(lives[n]);
return 0;
}
Input File 1
4 5 2 3 2
.****
.****
.****
.****
Output File 1
Input File 2
4 5 2 3 2
**...
*...*
.*..*
**...
Output File 2
Input File 3
4 5 2 3 2
*..**
*....
**..*
.*.*.
Output File 3
Input File 4
Output File 4
Input File 5
Output File 5