10001 - Garden of Eden

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

Moderator: Board moderators

npelly
New poster
Posts: 2
Joined: Mon Sep 02, 2002 2:58 pm

10001 - Garden of Eden

Post by npelly » Mon Sep 02, 2002 3:20 pm

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
New poster
Posts: 14
Joined: Tue Jun 25, 2002 8:50 am

Post by tenshi » Tue Sep 17, 2002 1:13 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!

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

Post by oracle » Tue Sep 17, 2002 6:33 pm

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
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

10001---I can't understand this problem,please help

Post by hujialie » Mon Jun 23, 2003 12: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.

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

10001 Why WA ?

Post by pingus » Sat Sep 06, 2003 9:49 pm

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]

User avatar
DemonCris
New poster
Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan

10001 Garden of Eden

Post by DemonCris » Wed Sep 24, 2003 1:11 pm

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Sep 24, 2003 9:51 pm

It's circular.

User avatar
DemonCris
New poster
Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan

Post by DemonCris » Thu Sep 25, 2003 5:41 am

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Sep 25, 2003 9:36 am

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

User avatar
DemonCris
New poster
Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan

Post by DemonCris » Thu Sep 25, 2003 2:44 pm

Thanks Larry :)
I have mistaken the problem meaning. ^^

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

Post by hujialie » Sat Nov 08, 2003 5:38 pm

Can anybody give a help?
I still got stuck with this problem. :(
Retired from SJTU Accelerator 2004

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

10001 Garden of Eden - Bad Apple?

Post by mooseelkdog » Sun Nov 30, 2003 10:53 pm

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

Post by mooseelkdog » Mon Dec 01, 2003 4:22 am

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

Thanks

User avatar
deneb
New poster
Posts: 6
Joined: Mon Nov 17, 2003 3:39 pm

10001

Post by deneb » Thu Dec 11, 2003 3:18 am

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
New poster
Posts: 4
Joined: Wed Oct 15, 2003 11:42 pm
Contact:

Post by Eobyn » Fri Dec 12, 2003 4:51 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 :o! 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.

Post Reply

Return to “Volume 100 (10000-10099)”