## 10001 - Garden of Eden

All about problems in Volume C. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

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
npelly
New poster

Posts: 2
Joined: Mon Sep 02, 2002 2:58 pm

exhausted search is OK if you prune some impossible status. my program run very fast
http://www.ioiforum.org/en/

A problem discussing forum.
Welcome to discuss problems in it!
tenshi
New poster

Posts: 14
Joined: Tue Jun 25, 2002 8:50 am

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.
oracle
New poster

Posts: 4
Joined: Tue Sep 17, 2002 6:21 pm

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.
hujialie
New poster

Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

### 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)
{
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;

top++;
}

ici:;

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

}

return 0;

}[/c]
pingus
New poster

Posts: 18
Joined: Sat May 03, 2003 10:33 pm

### 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

DemonCris
New poster

Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan

It's circular.
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

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:)

DemonCris
New poster

Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan

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...
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

Thanks Larry
I have mistaken the problem meaning. ^^

DemonCris
New poster

Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan

Can anybody give a help?
I still got stuck with this problem.
Retired from SJTU Accelerator 2004
hujialie
New poster

Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

### 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
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
mooseelkdog
New poster

Posts: 18
Joined: Fri Oct 10, 2003 8:46 am
Location: Airway Heights

### 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

deneb
New poster

Posts: 6
Joined: Mon Nov 17, 2003 3:39 pm

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.
Eobyn
New poster

Posts: 4
Joined: Wed Oct 15, 2003 11:42 pm

Next