10001 - Garden of Eden

[npelly]

Ok I am trying to solve 10001 (Garden of Eden)

My current algorithm is an exhaustive search through all possible previous states to find one which evolves to the current state. Of course worst case is 2^32 possible previous states which just takes too long to iterate through and test.

I must need another algorithm?

Or perhaps an exhaustive search is the way to go but I am not implementing it efficiently enough? has anyone completed the problem with an exhaustive search?

Thanks
-Nick

[tenshi]

exhausted search is OK if you prune some impossible status. my program run very fast

[oracle]

I think this problem should'n solved by exhausted search. My algorithm is to find all posible cases of first 3 digit of possible previous states and then use dynamic algorithm to check if with those 3 first digit can lead to a whole previous state or not.

[hujialie]

What does the table show?
I can't understand;

As far as I can see, since cell[]={0,0,1,1,0,0,1,1}
then left[] should =={1,0,0,1,1,0,0,1};
and right[] shoule =={0,1,1,0,0,1,1,0};
and thus new state[] should be xor(left[],right[])=={1,1,1,1,1,1,1,1}?

why left[] is {0,0,0,0,1,1,1,1} ;right[] is {0,1,0,1,0,1,0,1},and new state[] has been changed into {0,1,0,1,1,0,1,0}?

and I can't understand why in the sample input,
there is N==5 and N==6 while the cellular automaton is larger than 2^5||2^6??
What does cellular automaton mean?
Please explain it to me,I'll be very thankful.

[pingus]

Hello

I think that is right , but I get WA ?

[c] #include <stdio.h>

int main()
{
unsigned int liste[20000];
int top;

unsigned int op[2][2][2];

unsigned int i, j, n, a;
int left, right, cell, eden;
unsigned int bin, mask, next;

char initial[38];

while (scanf("%u",&a) == 1)
{

op[0][0][0] = ((a & 1) >> 0);
op[0][0][1] = ((a & 2) >> 1);
op[0][1][0] = ((a & 4) >> 2);
op[0][1][1] = ((a & 8 ) >> 3);
op[1][0][0] = ((a & 16) >> 4);
op[1][0][1] = ((a & 32) >> 5);
op[1][1][0] = ((a & 64) >> 6);
op[1][1][1] = ((a & 128) >> 7);

scanf("%u",&n);
scanf("%s",initial);

bin = 0;
for(i = 0; i < n; i++)
if (initial[n-i-1] == '1') bin += (1 << i);

top = 0;
eden = 0;
next = bin;

while(1)
{
mask = 0;
for(j = 0; j < n; j++)
{
if (j == 0) right = n-1; else right = j - 1;
if (j == n - 1) left = 0; else left = j + 1;

if (((1 << left ) & (next)) != 0) left = 1;
else left = 0;
if (((1 << right) & (next)) != 0) right = 1;
else right = 0;
if (((1 << j ) & (next)) != 0) cell = 1;
else cell = 0;

mask += (op[left][cell][right]) * (1 << j);
}

if (mask == bin)
{
eden = 1;
break;
}

for(j = 0; j < top; j++)
if (liste[j] == mask) goto ici;

liste[top] = mask;
top++;
next = mask;
}

ici:;

if (eden) printf("REACHABLE\n");
else printf("GARDEN OF EDEN\n");

}

return 0;

}[/c]

[DemonCris]

I have wondered why the forth test case in the sample input is "GARDEN OF EDEN"

Because 110 can become 100, thus state 1100000000000000 can become 1000000000000000.

Can anyone tell me why^^ .. thx

[Larry]

It's circular.

[DemonCris]

I don't know what you say, Larry.
I mean "the circular" is not concerned with the transformation between
state 1100000000000000 and 1000000000000000.

Obviously, because the state 1100000000000000 can become
1000000000000000, the output for this input is "REACHABLE".

But, it is not. I think I have some mistakes for this problem that I'm not
aware. Thanks again:)

[Larry]

Let's just say it's
110000

011 -> 1
110 -> 0
100 -> 1
000 -> 0
000 -> 0
001 -> 1

so basically, we get
101001 from 110000 on rule 154.

I'm not too sure how you would get to 100000...

[DemonCris]

Thanks Larry
I have mistaken the problem meaning. ^^

[hujialie]

Can anybody give a help?
I still got stuck with this problem.

[mooseelkdog]

I want to know why or how, discrete states are displayed that are larger than one byte, like the example given of 2 bytes, if I may ask how the XOR results extend?

Does each byte reflect results identical to the first byte?

Say state one has automaton value identity 9, and number of cells 5, the binary representation of that number should be 01001 as I see it, meaning the number of bits represented can contain the automaton identity.

Do results of larger identities (whose bits are more than that of the state, like say 156, for state 0011) cut off at the end of the state, the bits nonsignificant?

Are the bits xor'd with left and right only encompass the bits that are overlapped (156 having byte value 1001 1100, and the bits overlapping with 4 digit state 0011 being 1100)?

OK, now for the 2 byte example, the automaton identity is 154, does the binary representation duplicate from one byte to the next?

Does it stretch to fit (padded zeroes)?

Like say 10011010 10011010 (binary 154, binary 154) or 00000000 10011010 (padded zeroes)?

I think I can solve this if this is clarified as to what the identity looks like in binary for the multi-byte states..

Thanks

mooseelkdog

[mooseelkdog]

Look, can anyone just tell me if a discrete state is bound by the binary size of the identity or not?

Thanks

[deneb]

Hi:
I am trying to solve this problem by exhaustive search. To do it, i try to prune some states. I mean: I generate sequences like (for 4 cells):
0000
0001
0010
0011
0100
.....

while i am generating next state for every cell, if i find some state which doesn't match i don't follow generating and i try with the next.
Is there any other forms to prune in order to not to get a "time limit error"?

Tnx

[Eobyn]

You cannot solve this problem by making an exaustive search. For 32 bit states that would mean searching all (2^32 - 1) different states ! That uses to much time.
The idea is to look at the automaton, look at the state and somehow compute if there is any possible predecessor state. If there isn't any, then it is a GARDEN OF EDEN.

Eobyn.