// *****************************************************************
// *****************************************************************
// Emergent Self-Replicating Rules
//                                         written by Hui-Hsien Chou
// *****************************************************************
// *****************************************************************
// 
// This Trend rule set defines a CA space which allows arbitrarily
// chosen initial CA configurations to generate self-replicating loops
// over time.
//
// Four fields are used in the CA model, each has its functions as
// listed below:
//
// component: this is the field which acts very similarly to the
//	original self-replicating loop cells. Basically all structures
//	are formed by active states in this field. The encoded state 
//	symbols and their meanings are listed below:
//
//	. The quiescent state.
//	> The extrude signal, which is a weak rotational symbol and
//	  is represented by four state values.
//	L The left turn signal, which will turn the direction of
//	  extruding left 90 degrees.
//	O The building block, which allows safe passage of other
//	  signals through it.
//	E & F These two signals help to branch a new arm at the loop
//	  corner. They are generated when a new loop has been formed
//	  and the replicating arm is moving to the next corner of the
//	  loop. 
//	B Birth state, generated by the > signal over quiescent
//	  space.
//	C Corner state, generated by the L signal at the end of an
//	  arm. 
//	D Dissociation state, generated when a new loop closes on
//	  itself and can be splited from the parent loop.
//
// special: this is a field which helps to encode special situations
//	which will change the normal behavior on the component field.
//
//	. The quiescent state, no influence on component field.
//	- The clear mark. When overlaying with an O block on the
//	  component field, it will disable the passage of other
//	  signals through the O, thus clearing up signals. It is used
//	  when a hybrid growth situation is happening, where a smaller
//	  loop is generating a bigger loop. Because of the timing
//	  difference, an incomplete signal sequence will get copied
//	  into the new loop too, together with a correct, complete signal
//	  sequence. We need this - mark to clear the incomplete
//	  signal sequence to make the new loop a healthy one.
//	* The branch mark. The mark helps to generate a new copy of
//	  the E and F signal on the component field, thus braching a
//	  new arm in the other corner of the loop. It is used when
//	  seeing the Detach D on the component field.
//	# The dissolve mark. It will turn a bound component into an
//	  unbound component. It is generated when something wrong has
//	  happend in the replicating process of a loop, say, like a
//	  collision with anther loop, or being unable to brach a new
//	  arm, etc. This mark is fast infective, making all
//	  neighboring bound cells into the same state in the next
//	  epoch, thus totally dissolving a loop in a short time.
//
// growth: this is a one bit field which encodes the stimulus to
//	generate a new > signal in a loop while the loop is branching
//	out a new arm, thus making a smaller loop "mutate" and will 
//	generate a bigger loop in its next replication cycle. This bit
//	itself was set when a bound L signal in a loop dissolves. Saying
//	in another way, a dying loop will leave a growth bit somewhere on
//	the CA space to stimulate the others to grow.
//
//	. The quiescent state, no influence on the component field.
//	+ The growth mark. 
//
// bound: this is a one bit field which denotes if a cell belongs
//	to a multi-cell structure, or is just a monomer. When belonging
//	to a structure the cell changes according to the 
//	self-replicating rules. When it is a monomer the cell
//	changes according to the monomer rules.
//
//	. The quiescent state, denoting a monomer.
//	! The bound mark, denoting a bound structure component.
//
// The standard Moore neighborhood template was used in this rule set.
// To shorten the writing, each of the position in this template has
// been shortened to use two letters, as shown below:
//
//	North: no	NorthEast: ne	East: ea	SouthEast: se
//	South: so	SouthWest: sw	West: we	NorthWest: nw
//
// The Center cell was denoted by ce but usually we don't need to use
// it since when no position designator is given the default position
// is the center.

// *****************************************************************
// *****************     Default  Rules          *******************
// *****************************************************************
// The default action is to maintain no change if none of the rule 
// changes the next state value for each field. Therefore, the current
// values are copied over to the next state for each field.

default component=component;
default growth=growth;
default bound=bound;

// A special rule for the arm extrude flag. Whenever a cell
// sees the Detach D and it itself is a corner cell (note: not the 
// Corner C component), the arm extrude flag * will
// always be set, no matter what component the cell is. 

default	rot if (component && special=='.' &&
		(ea:component=='D' && no:component && we:component ||
		 we:component=='D' && no:component && ea:component))
	    special='*';
	else
	    special=special;


// *****************************************************************
// ***********   Variable and Function Declarations  ***************
// *****************************************************************
// count: a temporary variable used to store count for neighbors which
//	fit a certain condition.
// value: a temporary variable used to accumulate values from the
//	neighbors. Used to determine the signal for a new monomer if
//	birth is occurring.
// y: a nbr variable used for looping through all neighbors.

int count, value; nbr y;

// StrangeNeighbor is a function which determines if a bound cell may
//	have run into a fail situation where too many or too few
//	neighbors are around it. This usually means that a collision
//	with another loop has occurred. If that's the case a dissolve
//	mark will be generated next (in the main code).

int StrangeNeighbor() {
	count=0;  	// clear the counter

			// count the no. of non-quiescent neighbors.
	over each other y:
		if (y:component) count++; 

			// if zero or more than 5, it's strange!
	if (count && count<=5)
		return 0;
	else return 1;
}


// Main program starts here!

if (bound==0) {

// *****************************************************************
// ***************        Rules for Monomers!      *****************
// *****************************************************************

    // A cell is obeying the rules for monomers when its bound field
    // is set to zero. In this mode the monomer cell basically obeys
    // a Game-of-Life-like rule set, except that some additional rules
    // to deal with non-monomer cells are included.

    // First the neighbor situation are scanned and the result
    // accumulated in variables count and value.

    count=0; value=0;			 // reset to zero
    over each other y: {
	if (y:component) {
	    count++;			 // count the no. of active neighbor
	    value = value + y:component; // and accumulate their values
	}

	// see if a bound cell is in the neighbor, if yes, the current
	// cell must be returned to quiescent state and the bound flag
	// marked. This is to make a shield around bound cells (loops)
	// to protect them. The magic value 99 was stored in count for
	// checking below. Note that the only case a bound neighbor
	// cell won't cause problem to the current cell is when it
	// itself is in the dissolve mode. See the rules for loops for
	// details about dissolve mode. It is maked by a # mark in
	// the special field.

	if (y:bound && y:component && y:special!='#') {
	    count = 99;			// make a special flag in count
	    break;			// then stop scanning.
	}
    }

    // After the scanning of neighbor cells, various actions are taken
    // to determine the next state values for the current cell.

    // case 1: if there is a bound cell in the neighbor, the current
    // cell should return to quiescent state and it's bound bit set.
    
    if (count==99) {
	component='.';
	bound='!';
    }

    // case 2: if the current cell is just dissolving from a loop (by
    // having a non-zero special field), we make one more epoch delay
    // so that it won't be killed by its own fellow cells which are
    // also dissolving from the same loop.

    else if (special)
	special=0;

    // case 3: A particular configuration has been designed to be the
    // birth stimuli configuration. When such a configuration of
    // monomers occurs in the CA space, it will form a 2x2 bound loop in the
    // next epoch. The configuration is (note that rotation is possible):
    //
    // 			OO
    //			L>
    //
    // Since each member of this "Adam" configuration can see each
    // other within its own neighbors, we just need three different
    // checks for the different components >, L and O to make them do their
    // own "change to bound mode" work. Signal > has one more work of
    // setting the special field to * to extrude an arm later, so
    // replication can begin.

    else rot if (component=='>' && we:component=='L' && nw:component=='O' &&
			no:component=='O') {
	bound='!'; special='*';
    } 
    else rot if (component=='L' && ea:component=='>' && no:component=='O' &&
			ne:component=='O') 
	bound=1;
    else rot if (component=='O' && 
		(so:component=='L' && se:component=='>' && ea:component=='O'||
		 so:component=='>' && sw:component=='L' && we:component=='O'))
	bound=1;

    // other than above special cases, the current cell will just
    // follow a tranditional Game of Life rule. If a birth will occur
    // the new value of the birth cell will be determined by the
    // accumulated value in the value variable.

    else if (count<2 || count>3)		// the death rule
	component='.';
    else if (component=='.' && count==3)	// the birth rule
	component = (value+1)%6+1;

} else {

// *****************************************************************
// ****************        Rules for Loops!      *******************
// *****************************************************************

    // If a bound cell is in dissolving mode, it will dissolve to
    // monomer (i.e., losing bound bit) in next epoch, no matter
    // what happens in the neighborhood.

    if (special=='#') bound=0;
    
    // If a bound cell sees a dissolving cell in its neighborhood,
    // it itself will be going into that mode too. This dissolving 
    // mark was represented by a # in the special field of the
    // neighboring cells, and is given the highest priority to
    // consider. Thus when one cell in a loop structure goes into this
    // mode, the whole loop will be taken into that mode in a very
    // short time, and the whole structure dissolves.
    // The only exception is the D component. It is used to separate
    // newly formed loops from their parents. Since this is a
    // separating component, it is considered not part of a loop, so the
    // dissolve mark # won't pass through it. Speaking in another way,
    // the dissolving of parent and child loops are independent. This
    // helps to preserve the parent loop even when the replicating is
    // unsuccessful or vice versa.

    else rot if (component && component!='D' && 
			(no:special=='#' || ne:special=='#')) {
        special='#';

	// The only time the system will generate the growth
	// stimulation bit on the growth field is when a L signal is
	// dissolving. If this line is disabled no growth stimulation
	// bit will be generated, thus no bigger loop will be generated.

	if (component=='L') growth='+';
    }
    
    // One of the way the system checks for collision of loops is to
    // check if a cell has too many or too few neighbors (<1 or >5). 
    // If these situations happen the cell must be in a wrong
    // structure and must be dissolved.

    else if (component && StrangeNeighbor()) 
	special='#';
    
    else {

	// When none of the three special cases above applys, the bound
	// cell is in a healthy loop, and should perform normal loop
	// replicating functions according to its component type. 

	// ***************** Block O rules ****************
	// Block O is the building block of loops. Normally it will
	// allow the other signals like > or L to pass through it,
	// unless it is in a special clear mode denote by a - mark
	// in the special field. In this special mode it will not copy
	// other signals through it, thus cleaning up the signals.
	// This special mode occurs when a hybrid replication
	// situation happens where a smaller loop is generating a
	// bigger loop. Because of the timing difference, an
	// incomplete signal sequence will be copied into the new loop,
	// together with a complete and normal sequence. This
	// incomplete signal sequence must be destroyed.

	if (component=='O') {
	    if (special!='-') {

		// Here the Block O isn't in the clear mode, so normal
		// operations will be done.

		// First check to see if it's in the closing of a hybrid
		// replication by looking at the closing Birth B and all
		// relevant neighbor positions which signify a hybrid
		// replication. If yes, set the special clear mark.

		rot if (no:component=='B' && nw:component=='.' &&
			(we:component=='O' || ea:component=='L'))
		    special='-';

		// Otherwise, it should pass signals. First check if there
		// is a > signal which wants to pass through. If so, copy
		// it over here. 
		// But if there is more than one > signal which wants to
		// pass though, this must be a collision situation, so the
		// special dissolve mode is entered.

		else rot if (we:component=='>') // > signal which wants to
						// pass.

		    // check for no other signal wants to pass too.
		    if (no:component!='>,1' && no:component!='>,2' && 
			    ea:component!='>,2' && ea:component!='>,3' && 
			    so:component!='>,3' && so:component!='>')
			component='>';	// copy it
		    else
			special='#';	// otherwise, set dissolve mode

		// This is similiar, but for 90 degree passing of > in O.
		// Check for collision too.

		else rot if (so:component=='>') // > signal which wants to
						// pass .

		    // check for no other signal wants to pass too.
		    if (we:component!='>,1' && we:component!='>' && 
			    no:component!='>,2' && no:component!='>,1' && 
			    ea:component!='>,3' && ea:component!='>,2')
			component='>,3';	// copy it
		    else
			special='#';	// otherwise, set dissolve mode

		// Extrude by F to complete a new arm. When O is in the tip
		// of a new arm, it will get a > signal when seeing the F
		// signal. This will complete the arm extraction step by
		// forming a standard two-cell arm in two steps.
		//						  O <arm
		//        O			^                 O
		//     <LOF		     LOOO              OOOO
		//        O       ---->         O     ---->       O
		//        O                     O                 O

		else rot if (so:component=='F' && se:component=='.' && 
				no:component=='.' && ea:component=='.'
				&& we:component=='.') 
		    component='>,3'; 

		// Check to see if it's in the gap between a parent and a
		// child loop and the replication cycle has just
		// completed, by looking at the closing Birth B or the
		// opposite direction of signal flows on both side, and
		// relevant neighbor positions which signify a closing
		// replication cycle. If yes, change to D to disconnect 
		// these two loops.

		else rot if ((nw:component=='>,3' || nw:component=='O') &&
				(ne:component=='B' || ne:component=='>,1')
				&& no:component=='.' && ea:component
				&& we:component ) 
		    component='D'; 
	    } else

		// if the Block O sees the clear flag -, the flag
		// will be changed to the arm extrude flag when all
		// signals has been cleared (L is the last signal).

		rot if (we:component=='L')
		    special='*';
	}

	// ***************** Signal > rules ****************
	// Signal > is the extruding signal command. When at the tip
	// of a replicating arm, it will cause the adjacent quiescent
	// space it points to to change to a Birth B in the next epoch.
	// Usually > signals are going in a squence with a trailing L,
	// so it must copy the signal behind it, be it a > or a L, to
	// its own current position, unless there is no L or >
	// after it, in that case it will change back to O. Note that
	// changing back to O doesn't mean its signal disappears.
	// Remember that the cell before it will be copying it too
	// (be it an O or another > signal), thus signal > is flowing
	// in the loops normally, unless something special happens.

	else rot if (component=='>') {

	    // One special condition is that it may be in the gap
	    // between a parent and a child loop when the replication
	    // cycle has just completed. By looking at the closing B
	    // or the opposite direction of signal flows on both
	    // side, and the relevant neighbor positions which signify
	    // a closing replication cycle, it can tell if it's in
	    // that position. If yes, it will change to Detach D to
	    // disconnect these two loops. This is very similar to the
	    // last statement for the Block O above.

	    if ((nw:component=='>,3' || nw:component=='O') &&
		(ne:component=='B' || ne:component=='>,1') &&
		no:component=='.' && ea:component && we:component) 
		component='D'; 

	    // Otherwise, see if L is behind it. If so, it should copy
	    // the L signal. One very interesting special case here is
	    // that if the growth field is set, it will stimulate the
	    // growth of signal sequence by one during arm extrusion
	    // time. This is achieved by NOT copying the L signal and
	    // stay as > for one more cycle. Since > signal is always
	    // copied, this will actually insert one more > into the
	    // sequence. Yes, the L signal will disappear in the next
	    // epoch, but since the growth field is still set, that L
	    // signal will be recovered in one more epoch. See the
	    // rule below. 
	    // Another special case is when a 2x2 loop has just
	    // completed generating a 3x3 loop and is about to extrude
	    // its new arm. Since the signals L>> and EF is more than
	    // four, the number of cells in a 2x2 loop, there must be
	    // some way this L>> signal can be regained after the
	    // transient E and F signal that extruding a new arm. This
	    // is achieved by utilizing the growth field. Yes, that
	    // way, no matter what's the status of the growth field we
	    // will always set it to on, so you can't get more >'s in
	    // the signal sequence within a 2x2 loop.

	    else if (we:component=='L') 
		if (nw:component=='E' && 
			(growth || no:component=='>,3'))
		    growth='+';
		else 
		    component='L';

	    // With the two special cases considered, all the rest is
	    // just simple copying and doesn't need further
	    //explanation. 

	    // copying the L signal, for four cell special case
	    else if (no:component=='L') 
		component='L';

	    // copying the > signal
	    else if (we:component=='>') 
		component='>';

	    // copying the > signal through the corner
	    else if (we:component=='>,1') 
		component='>';

	    // copying the > signal through the corner, in arm tip
	    else if (no:component=='>,1') 
		component='>';

	    // Now here is the special case companion rule, see
	    // above. If the growth field is set on and L is not
	    // following >, the > will change back to L again to
	    // regain it.
	    else if (growth && nw:component=='F') { 
		component='L'; growth=0; 
	    }

	    // otherwise > always chages to O
	    else 
		component='O';
	}

	// **************** Birth B rules *****************
	// Birth B is generated when a quiescent bound cell is
	// pointed by a > signal. This is the way how loops grow.
	// Functionally B is very similar to Block O in that it just
	// copy signals through it. The reason we need the Birth B is
	// that it is easier to decide if a replication arm is closing
	// in itself by spotting the B at the periphery.

	else if (component=='B') {

	    // In the closing of 2x2 loops the B should change to L
	    // immediate to preserve the signal sequence.

	    rot if (we:component=='L' && no:component=='O') 
		component='L';

	    // Otherwise B usually change to a corner cell when seeing L
	    else rot if (we:component=='L') 
		component='C';

	    // If > is behind B will just copy it. Note that this is
	    // one of the two places where a monomer can kill a loop
	    // since the > signal is not checked to be bound or not. So if
	    // a monomer > signal is facing the Birth B it will
	    // influence the normal operation of the loops and kill it.

	    else rot if (we:component=='>') 
		component='>';

	    // B can't be in a line of bound cells unless it's a
	    // collision. 

	    else rot if (no:component && so:component) 
		special='#';

	    // Finally B always changes to O. This occurs when
	    // extruding a new arm.

	    else 
		component='O';
	}

	// **************** Signal L rules *****************
	// Signal L gives the command of turning the growth direction
	// 90 degree counterclockwise at the tip of the replicating arm.
	// Signal L will also help generating a new replicating arm
	// when closing with the current replication cycle.

	else if (component=='L') {

	    // L will change to extrude signal E if seeing the special
	    // extrude mark on the speicial field. This extrude mark
	    // itself was set when seeing Detach D, the disconnect
	    // component, in its neighbor.

	    if (special=='*') 
		component='E';

	    // if > catch up with L, the signal sequence must have
	    // some problems (possibly due to too many growth stimuli
	    // +), and must be destroyed.

	    else rot if (we:component=='>')
		special='#';

	    // copying the E after the L, unless it's already at the
	    // corner (thus sw:component=='F', since F always follows E).

	    else rot if (so:component=='E' && sw:component!='F' 
			&& (no:component=='.' || we:component=='.')) 
		component='E';

	    // otherwise L always changes to O
	    else component='O';
	}

	// **************** Component . rules *****************
	// . might not be called component at all since it's the
	// quiescent state for the component field. It will be changed
	// to a non-quiescent state if seeing either the > or E
	// signal, or it may fall back to monomer state if none of its
	// neighbor is a bounded non-quiescent cell.
	// Note that a monomer can kill a loop by inhibiting the
	// generation of the arm when standing beside the potential
	// "O" position. This is the second way a monomer can kill a loop.

	else if (component=='.') {

	    // When seeing signal > pointed to itself, it will change
	    // to the Birth B.

	    rot if (we:bound && we:component=='>' && 
			(nw:component=='.' || nw:component=='>,1' ||
			 nw:component=='L')) 
		component='B';

	    // Or it will extrude the arm at the corner when seeing E.
	    // If north is occupied (no matter it is a bound cell or
	    // monomer), the extrusion will fail.

	    else rot if (so:special==0 && so:component=='E' && 
				se:component=='.' && no:component=='.') 
		component='O';

	    // Otherwise, see if no bound neighbor nearby. If so,
	    // change back to unbound mode.

	    else {
		count=0;
		over each other y:
		    if (y:bound && y:component && y:special==0)
			count++;
		if (count==0) bound=0;
	   }
	}

	// **************** Corner C rules *****************
	// C is the corner component generated by L signal at the tip of
	// a replicating arm. It will turn an incoming > signal 90
	// degree counterclockwise, thus changing the direction of
	// replication. 

	else if (component=='C') {

	    // First check for fail situation. E or F shouldn't meet C in
	    // anyway. If they meet C that means something must have gone
	    // wrong so the current loop must be destroyed.

	    rot if (no:component=='E' || no:component=='F')
		special='#';

	    // turn > at the corner, four cell case considered, too.
	
	    else rot if (we:component=='>' || we:component=='>,1') 
		component='>,3';
	}

	// **************** Detach D rules *****************
	// Detach D is the blocking component. It is generated when a
	// replicating arm has fallen back to itself, thus making a new
	// child loop. This component can block the dissolve flag # in the
	// special field to preserve either the child or parent loop
	// from the death of each other. This component is erased when
	// the two loops has seen it and has generated the arm
	// extruding flag.

	else if (component=='D') {

	    // removing of the blocking cell when seeing special field set
	    // in the neighbor.

	    rot if (ea:special) component='.';

	}

	// **************** Signal E rules *****************
	// E always followed by F, so it always changes to F. It is
	// part of the two signal EF extruding sequence which extrudes
	// a new arm.

	else if (component=='E') {

	    component='F'; 

	    // always reset the arm extrude special flag so only one EF
	    // sequence is generated.

	    special='.';
	}

	// **************** Signal F rules *****************
	// Signal F is part of the EF sequence to extrude a new arm.
	// When it sees no new arm generated by its predecessor E, it
	// will set the dissovle flag since extrusion fails.

	else if (component=='F') {

	    // extrude testing for 2x2 loop special case

	    rot if (no:component=='>,2' && ea:component) 

		// copying the > signal or set the dissolve mode
		if (ea:component=='E' || so:component=='O') 
		    component='>,1';
		else 
		    special='#';

	    // if arm extrude fails, self-destruction will begin

	    else rot if (no:component=='O' && 
			    (ea:component=='O' || ea:component=='L') && 
			    so:component=='.' && we:component=='.')
		special='#';

	    // otherwise F always change to O
	    else component='O';
	}
    }
}