## 10001 - Garden of Eden

Moderator: Board moderators

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
He-he...

Exaustive search is my favorite method to solve problems, especially if it is necessary to use some tricky prunings!!

Of course this problem can be solved a better way - I'm only on 124'th place in the ranklist with 1.941 time... But...

A small hint: you needn't generate all bits of the state. I generated only two bits of each triple and then recovered the others.

Bye.
Andrey.

deneb
New poster
Posts: 6
Joined: Mon Nov 17, 2003 3:39 pm
ok tnx very much

JuaingFall
New poster
Posts: 13
Joined: Tue Aug 03, 2004 4:24 am
Location: CHINA

### 10001 help me

I don't understand some words,below:
To further simplify the problem each cell state will depend only on its previous state and that of its immediate neighbors (the one to the left and the one to the right).
The Identity automaton (every state evolves to itself) has identifier 204.

who can explain this words,thank you in advance!

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

### the meaning is..

"To further simplify the problem each cell state will depend only on its previous state and that of its immediate neighbors (the one to the left and the one to the right). "

the paragraph above means that each of the node/cell will change its state to a new state according to its own state, the state of the left and right neighbor. for ex : if you got a cell with a 0 state, and the left is also 0 and the right one is 1 (from the sample automaton in the problem) the cell will change its state from 0 to 1

"The Identity automaton (every state evolves to itself) has identifier 204."

Now, this means that if the automaton has an identifier 204.. the table will look like this

Left Cell Right New
[i-1] [i + 1] State
0 0 0 0 0 * 1
0 0 1 0 0 * 2
0 1 0 1 1 * 4
0 1 1 1 1 * 8
1 0 0 0 0 * 16
1 0 1 0 0 * 32
1 1 0 1 1 * 64
1 1 1 1 1 * 128
204 = Automaton Identifier

every cell with 0 state will evolve into 0 again, and every cell with 1 change to 1..
so the state 10111001100101011 will also become 10111001100101011

liuchangacm
New poster
Posts: 3
Joined: Wed Mar 09, 2005 1:28 pm

### 10001

Could anyone tell me what does the Problem 10001 mean?
I can't understand the evolution rules and how it makes 204 to be an Identity automaton.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Basically the problem wants you to find the "parent" of given pattern, that is the pattern which will evolute into the given one. If there exists a parent, you print "REACHABLE", otherwise it's "GARDEN OF EDEN". You need backtracking to solve this.

Encoding of the rules is demonstrated in the table in the statement.
Each cell is evaluated, depending on its current state and the state of both its neighbors. Each possible combination (there are just 8 of them) is listed in the table, along with the arbitrarily-chosen new state, which the cell must turn into after the application of the rule. This table is then encoded as 8-bit number by interpreting the numbers in "New state" column as binary digits.

The corresponsing table for identity is:
Left, Cell, Right, New
0 0 0 -> 0
0 0 1 -> 0
0 1 0 -> 1
0 1 1 -> 1
1 0 0 -> 0
1 0 1 -> 0
1 1 0 -> 1
1 1 1 -> 1

Note that the value in "New" column is the same as in the "Cell".
In binary the "New" column is (from bottom to top): 11001100 = 204 (decimal).

liuchangacm
New poster
Posts: 3
Joined: Wed Mar 09, 2005 1:28 pm
I get it. Thank you very much!

jGlass314
New poster
Posts: 1
Joined: Tue May 17, 2005 7:57 am

Larry wrote: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...
Actually, I (almost) agree with DemonCris' original posting--or am unclear in the same way. 154 = 10100100, so shouldn't
000 -> 0
001 -> 0
010 -> 1
011 -> 0
100 -> 0
101 -> 1
110 -> 0
111 -> 1
and therefore 110001 -> 100000 because
111 -> 1
110 -> 0
100 -> 0
000 -> 0
001 -> 0
011 -> 0 ??

ironfist
New poster
Posts: 1
Joined: Wed May 18, 2005 5:00 am

### 10001 Garden of Eden Question

Hi guys,

I have been working on the garden of eden problem for 2 days now, and I cannot seem to get the correct answer.

I am using a recursive algorithm that tries to find the parent state, and backtracks once it runs into a dead end. For a while I was getting TLE, but after adding more prunning, i managed to get my solution in under the alloted time.

However, now i keep on getting WA, but every test case that I throw at it, appears to be correct to me. I was wondering if somone who has gotten the Correct solution could provide me with some test cases and their output? So that I can figure out the problem with my code.

Thanks,

iron.

backslashnull
New poster
Posts: 3
Joined: Tue Dec 02, 2003 5:02 pm

### 10001 WA?

hi everybody,
i need some test cases for this problem.i managed to solve it in 3 sec using backtracking,but got WA.

thanks.

backslashnull
New poster
Posts: 3
Joined: Tue Dec 02, 2003 5:02 pm
oh bythe way here is my code:

Code: Select all

``````#include "fstream"
#include "string.h"
using namespace std;

int rule_table[8][4]={{0,0,0,0},{0,0,1,0},{0,1,0,0},{0,1,1,0},{1,0,0,0},{1,0,1,0},{1,1,0,0},{1,1,1,0}};
int cells;
char current_state[33];
int    making[33];

void set_rules(int a){
register int i;
for(i=0;i<8;i++){
if (a& 1)
rule_table[i][3]=1;
else
rule_table[i][3]=0;
a>>=1;
}
}

bool applyable(int r_number,int index){
if (making[index]==-1)
return true;
if (making[(((index-1)%cells)+cells)%cells]==rule_table[r_number][0] && making[index]==rule_table[r_number][1] && (making[(index+1)%cells]==-1 ||  making[(index+1)%cells]==rule_table[r_number][2]))
return true;
return false;
}

void apply_rule(int rule,int index){
making[(((index-1)%cells)+cells)%cells]=rule_table[rule][0];
making[index]				=rule_table[rule][1];
making[(index+1)%cells]=rule_table[rule][2];
}

void clear(int index){
if(index==0)
making[0]=making[1]=making[cells-1]=-1;
else
making[(index+1)%cells]=-1;
}

bool process(int index){
register int i;
if (index==cells-1){
for(i=0;i<8;i++)
if (rule_table[i][3]==current_state[index]-'0' && applyable(i,index))
return true;
return false;
}
for(i=0;i<8;i++){
if (rule_table[i][3]!=current_state[index]-'0')
continue;
if (applyable(i,index)){
apply_rule(i,index);
if (process(index+1))
return true;
clear(index);
}
}
return false;
}

int main(){
int automaton;
while (!cin.eof()){
memset(current_state,0,sizeof(current_state));
memset(making,-1,sizeof(making));
cin >> automaton;
if (cin.eof())
break;
cin >> cells;
cin >> current_state;
set_rules(automaton);
if (process(0))
cout <<"REACHABLE"<<endl;
else
cout <<"GARDEN OF EDEN"<<endl;
}
return 0;
}
``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
154 = 10011010
164 = 10100100

I think you have got your error.
Ami ekhono shopno dekhi...
HomePage

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

### 10001

hi all..........
i've got some problem in solving 10001 garden of eden...
would anyone pls send me some i/o for both possible or impossible cases???
i would be highly greatful to you..
thanks a lot...

New poster
Posts: 16
Joined: Mon Jun 26, 2006 9:33 am
Contact:

### 10001: TLE? but why?

hi. ive thoroughly checked my prog with my own input (on top of what is provided by the question online). ive used backtracking to find the existence of a predecessor. if its not found, then its a GARDEN OF EDEN. also tried with a few random 32 size inputs (which are most probably GARDEN OF EDENs), and it ran in a blink of an eye (right after ive pressed enter). But it was judged as TLE on the OJ. Below is my code. My guess is some form of devious input which will cause it to run extra slow

Code: Select all

``````removed after AC
``````
Last edited by gradientcurl on Wed Apr 18, 2007 4:51 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Try this input

Code: Select all

``0 32 00000000000000000000000000000001``