10001 - Garden of Eden
Moderator: Board moderators
10001 - Garden of Eden
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
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
10001---I can't understand this problem,please help
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.
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.
10001 Why WA ?
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]
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]
10001 Garden of Eden
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
Because 110 can become 100, thus state 1100000000000000 can become 1000000000000000.
Can anyone tell me why^^ .. thx
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:)
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:)
-
- New poster
- Posts: 18
- Joined: Fri Oct 10, 2003 8:46 am
- Location: Airway Heights
10001 Garden of Eden - Bad Apple?
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
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
-
- New poster
- Posts: 18
- Joined: Fri Oct 10, 2003 8:46 am
- Location: Airway Heights
10001 Garden OF Eden
Look, can anyone just tell me if a discrete state is bound by the binary size of the identity or not?
Thanks
Thanks
10001
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
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
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.

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.