10001 - Garden of Eden

[Andrey Mokhov]

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]

ok tnx very much

[JuaingFall]

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]

"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]

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]

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

See also mathworld's article: http://mathworld.wolfram.com/Elementary ... maton.html

[liuchangacm]

I get it. Thank you very much!

[jGlass314]

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]

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]

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]

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]

154 = 10011010
164 = 10100100

I think you have got your error.

[ayeshapakhi]

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

[gradientcurl]

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

[mf]

Try this input

Code: Select all

0 32 00000000000000000000000000000001