Path: utzoo!attcan!uunet!decwrl!wuarchive!psuvax1!hydra!anucsd!neccan!dbell
From: dbell@neccan.oz (David I. Bell)
Newsgroups: alt.sources
Subject: Life search program (part 2 of 2)
Keywords: life
Message-ID: <823@neccan.oz>
Date: 28 Sep 90 02:37:36 GMT
Organization: NEC Information Systems Australia, Canberra
Lines: 1558


#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#		"End of archive 2 (of 2)."
# Contents:  ORIGIN search.c
# Wrapped by dbell@elm on Fri Sep 28 12:14:21 1990
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'ORIGIN' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'ORIGIN'\"
else
echo shar: Extracting \"'ORIGIN'\" \(22903 characters\)
sed "s/^X//" >'ORIGIN' <<'END_OF_FILE'
X>> Commentary by dbell
X>> This is the original article included with the xlife 2.0 sources in
X>> which Dean Hickerson described how his life search program works.
X>> Note: His mail address is no longer valid (and he doesn't have one).
X>> Also, the 25 bit period 3 spaceship referred to below is the following:
X>> .............**
X>> .**...*...*....*
X>> *......**..****
X>> .***.**.*.**
X>> .....*.**
X>>
XReturn-path: <HUL@PSUVM.PSU.EDU>
XX-Andrew-Authenticated-as: 0;andrew.cmu.edu;Network-Mail
XReceived: from po3.andrew.cmu.edu via trymail
X          ID </afs/andrew.cmu.edu/usr14/jb7m/Mailbox/0Zft7HK00UkT8HJU8F>;
X          Sat, 13 Jan 90 15:38:45 -0500 (EST)
XMessage-ID: <Added.AZft7Em00UkTQHJU5q@andrew.cmu.edu>
XReceived: from PSUVM.PSU.EDU by po3.andrew.cmu.edu (5.54/3.15) id <AA04945> for jb7m+; Sat, 13 Jan 90 15:38:10 EST
XReceived: from PSUVM.BITNET by PSUVM.PSU.EDU (IBM VM SMTP R1.2.1MX) with BSMTP id 0991; Sat, 13 Jan 90 15:38:55 EST
XReceived: by PSUVM (Mailer R2.03B) id 3407; Sat, 13 Jan 90 15:38:54 EST
XDate:    Sat, 13 Jan 90 15:38 EST
XFrom: "Dean Hickerson" <HUL@PSUVM.PSU.EDU>
XSubject: Search program
XTo: jb7m+@andrew.cmu.edu
X
X>  A number of time you have said that the patterns you were sending had been
X>  found by a search program. I was wondering if you would mind sending me a
X>  copy of it too look at.
X
XThe program is written in 6502 assembly language and Applesoft BASIC and
Xruns on an Apple IIe.  Unless you have a compatible machine, the program
Xitself probably wouldn't help you much.  But here's a fairly detailed
Xdescription of how it works.  I encourage you (or anyone else) to write a
Xsimilar program for a faster machine; I'm sure there are things waiting to
Xbe found that my Apple is slow to find.
X
XIf you really want to see the program itself, let me know and I'll try to
Xfind a way to send it.  (It's not easy, because of incompatible operating
Xsystems and file structures.)
X========================================================================
XGeneral description of the Life search program  (9/6/89)
X
X     This is a general description of the program and some discussion of
Xits behaviour.  A much more detailed description follows.
X
X     I tell the program the desired congruence period T of an object, a
Xrectangle in which generations 0 to T must fit, and an isometry relating
Xgen. 0 to gen. T.  The program creates a 3D array in which each cell is
Xeither on, off, or unknown; initially everything's unknown except for any
Xinitial conditions which I specify.  It then picks an unknown cell, chooses
Xa value for it, and examines the consequences of its choice, working both
Xforward and backward.  If it runs out of consequences, it picks another
Xunknown cell and continues.  If it finds a contradiction, it backs up to
Xits most recent choice, reverses it, marks it as a conclusion rather than a
Xchoice, and continues. Eventually it either runs out of unknown cells and
Xreports that it's found something, or tries to back up past its first
Xchoice and reports that the object doesn't exist.  (Or it would if I let it
Xrun forever; more often I stop it after a while.)  I can have it display
Xthe array at any time; sometimes I can figure out something interesting
Xfrom its partial results.  E.g. I built the 25 bit c/3 spaceship from parts
Xit had found in previous searches; the program found it about an hour
Xlater.
X
X   One problem I sometimes have is that the program finds things with
Xperiods smaller than I want, like 1.  So I usually specify the value of
Xsome particular cell in enough phases to force it to have the desired
Xperiod.  (Of course I may miss something interesting that way.)  Another
Xproblem is that after the program finds something which is smaller than the
Xspecified rectangle, it then finds the same thing with various stable
Xobjects around the unoccupied edges.  So I back it up 'by hand' far enough
Xto get to something new.
X
X   I haven't really settled on the best order in which to select unknown
Xcells.  I usually work in a rectangle which is wide but not very tall and
Xproceed up the columns from left to right, either just in gen. 0 or doing
Xall phases for each position before moving to the next.  I've tried some
Xsearches starting at the center of a square and spiralling
Xoutward, but the program tends to bog down when it's far from the center: a
Xbad choice for a cell may not be detected until the spiral comes back
Xaround to it, so it will try many possibilities for the intervening cells
Xof the spiral before it changes the bad cell.  Probably I should use a
Xself-adjusting search order; when a problem is detected, the program should
Xmove nearby cells closer to the front of the search list.  My first
Ximplementation of this actually made the program slower, since cells which
Xgot moved to the front of the list stayed near there even when they were no
Xlonger a problem.  I have an idea for a better way to do it, but I haven't
Xhad time to implement it yet.
X
X   Another thing I'm still experimenting with is how to decide whether to
Xturn an unknown cell on or off.  If I'm going to let the search run to
Xcompletion it doesn't matter; both choices will be tried eventually.  But
Xfor incomplete searches some heuristics might help.  Usually I choose 'off'
Xfirst, in the hope that an object of small population will be found.
XAnother good choice is to make a location have the same value at time t as
Xat other, already assigned, times; this tends to lead to billiard tables.
X
X   The program is most effective when the period is small; the forward and
Xbackward conclusions tend to wrap around the ends of time and meet, leading
Xto more conclusions or contradictions.  For large periods, that doesn't
Xhappen much, so the program doesn't detect its bad choices soon enough to
Xaccomplish much.  The p5 fumarole and one other p5 are the only things
XI've found so far with a congruence period greater than 4.
X----------------------------------------------------------------------
X
XDetailed description of the Life search program  (9/24/89)
X
X     The program consists of two parts, an assembly language part which
Xdoes the searching and a BASIC program which handles initialization,
Xinterpreting commands from the user, and display.  I'll talk mostly about
Xthe assembly language portion.
X
X     Three constants describe the size of the space being searched:
X
X          TP = time period, length of time until pattern is to reappear;
X          XM = width of rectangle to be searched;
X          YM = height of rectangle to be searched.
X
XThe set of pairs (X,Y) with 0<=X<XM and 0<=Y<YM will be called "the
Xrectangle".
X
X     There are 12 constants which describe how generation 0 is related to
Xgeneration TP:  A, B, C, D, E, F, A', B', C', D', E', F'.  The cell with
Xcoordinates (X, Y) in generation 0 is mapped to the cell with coordinates
X(AX+BY+C, DX+EY+F) in generation TP.  The cell with coordinates (X, Y) in
Xgeneration TP is mapped to the cell (A'X+B'Y+C', D'X+E'Y+F') in generation
X0.  The values of A thru F are specified by the user; the others are given
Xby:
X    A' =  E/Z,   B' = -B/Z,   C' = (BF-CE)/Z,
X    D' = -D/Z,   E' =  A/Z,   F' = (CD-AF)/Z,
Xwhere   Z = AE-BD = 1 or -1.  The mappings are supposed to be isometries,
Xnot general invertible linear maps, so there are severe restrictions on A,
XB, D, and E which I won't bother to write down.  (There is also a boolean
Xvariable, USEMAP, which is normally true.  If it is false, then the
Xmappings are ignored, so the program can be used to search for predecessors
Xof whatever the user puts in generation TP.)
X
X     The current information about generations 0 to TP is kept in a 3
Xdimensional array CELL, with dimensions 0 to TP, 0 to XM-1, and 0 to YM-1.
XEach entry can have one of 3 values, 0=off, 1=on, or UNK=unknown.  (I use a
Xwhole byte for each entry, with UNK=$10.  (Here and later, a dollar sign
Xindicates that a number is in base 16.)  This makes the computation of the
Xneighborhood easy: just add the values of the 8 neighbors; the high nybble
Xis the number of unknown neighbors, and the low nybble is the number which
Xare on.) Initially the edges (all elements with X=0 or XM-1 or Y=0 or YM-1)
Xare turned off, as are the cells in generation 0 which map outside the
Xrectangle in generation TP and vice versa; everything else is initially
Xunknown.  After this initialization, some user-specified cells may be
Xturned on or off, by calling PROCEED (described later).
X
X     In addition to CELL, one other large array is used, the setting list.
XThis is a list of quintuples (T, X, Y, VALUE, FREE) where 0<=T=TP, 0<=X<XM,
X0<=Y<YM, VALUE=0 or 1, and FREE=true or false.  Whenever an element of CELL
Xis changed from UNK to 0 or 1, an entry is added to the list.  FREE is true
Xif the change is a free choice, false if it's forced by some previous
Xchoice.  There are 3 pointers into the list:
X          STNG   points to the beginning;
X          NWSTNG points to the end; new entries are put here;
X          NXSTNG points to the next setting whose consequences are to
X                 be examined.
X
X     There are also two tables which are used to describe the Life
Xtransition rules.  Conceptually, an index into either table consists of a
Xcell value (0, 1, or UNK) and 3 numbers which add up to 8, telling how many
Xneighbors are 0, 1, and UNK; there are 135 (=3*45) possible indices.  In
Xpractice, I use a one byte 'neighborhood descriptor' to encode this, so
Xeach table is 256 bytes long, but only partially used.  To compute the
Xneighborhood descriptor of a cell, add up the 8 neighbors.  If the AND of
Xthe sum and $88 is zero, then the neighborhood descriptor is twice the sum
Xplus the cell.  If the AND is nonzero, the descriptor is the sum plus twice
Xthe cell plus $11.
X
X     The first table is called TRANSIT and tells what the cell should be in
Xthe next generation.  E.g. neighborhood descriptor $25 means that the
Xcell is 1, 5 of its neighbors are 0, 2 are 1, and 1 is unknown,
XTRANSIT[$25] = 1.  Of course, most entries in TRANSIT are UNK, 73 to be
Xexact.  (And 57 are 0 and 5 are 1.)
X
X     The second table is called IMPLIC and contains information about
Ximplications in the other direction.  If we know the neighborhood
Xdescriptor and the value of the cell in the next generation, we may be able
Xto conclude that some unknown cells in this generation must be 0 or 1.
XSuch conclusions exist only if the corresponding entry is UNK, so there are
Xonly 73 entries in IMPLIC.   There are 8 possible implications, each is
Xgiven by one bit in the IMPLIC entry:
X
X     Bit       Meaning
X     $80       If new cell is 0 then current cell should be 0.
X     $40       If new cell is 0 then current cell should be 1.
X     $20       If new cell is 1 then current cell should be 0.
X     $10       If new cell is 1 then current cell should be 1.
X     $08       If new cell is 0 then all unknown neighbors should be 0.
X     $04       If new cell is 0 then all unknown neighbors should be 1.
X     $02       If new cell is 1 then all unknown neighbors should be 0.
X     $01       If new cell is 1 then all unknown neighbors should be 1.
X
X(In Life, bits $40 and $20 are never set, but they may occur for other
Xtransition rules.)  For example, bit $80 is set iff the current cell is
Xunknown, exactly 2 of its neighbors are 1, and at most 1 of its neighbors
Xis unknown, i.e. for neighborhood descriptors $14 and $34.
X
X     The two tables were created by a BASIC program and are now loaded from
Xdisk as part of the initialization.
X
X     The basic operation of the program is as follows: Suppose that CELL is
Xfully consistent; i.e. every cell is consistent with its 9 parents and no
Xcurrently unknown cells have their values forced.  (That is, forced
Xdirectly, either by their parents or their children.)  In this situation,
XNXSTNG = NWSTNG.
X
XStep 0:  ('Pick an unknown cell')  If there are no unknown cells left,
Xreport that an object has been found, let the user display it, save it on
Xdisk, print it, or whatever; then go to step 2.  Otherwise, pick an unknown
Xcell and a value for it.  Change it in CELL and add an entry to the setting
Xlist with FREE=true, updating NWSTNG.  Go to step 1.
X
XStep 1:  ('Examine consequences')  If NXSTNG = NWSTNG, then CELL is fully
Xconsistent; go to step 0.  Otherwise, get the values of T, X, Y, and VALUE
Xpointed to by NXSTNG and increment NXSTNG.  The fact that CELL[T,X,Y] =
XVALUE may directly force some currently unknown cells to be 0 or 1; for
Xeach of these, set its value in CELL and add an entry to the setting list
Xwith FREE=false, incrementing NWSTNG.  Then go to step 1.  We may also
Xdetect a contradiction at this point; in that case go to step 2.  (The
Xforcing in this step is of 4 types:  If T=0 or TP, the mapped cell in
Xgeneration TP or 0 is forced.  Some of the parents of (T,X,Y) may be
Xforced.  Some of the children of (T,X,Y) may be forced.  And some cells may
Xbe forced by additional constraints such as symmetry.)
X
XStep 2:  ('Back up'.  At this point, either a contradiction has been
Xdetected or we've found an object and wish to look for more.)  If NWSTNG =
XSTNG, report that no more objects of the desired type exist and quit.
XOtherwise, decrement NWSTNG and get the values of T, X, Y, VALUE, and FREE
Xpointed to by it.  If FREE = false, set CELL[T,X,Y] to UNK and go to step
X2.  If FREE = true, then either we've found that this free choice led to a
Xcontradiction or we've already found all objects in which the choice was
Xvalid.  So change CELL[T,X,Y] to 1-VALUE, change FREE to false, set NXSTNG
Xto NWSTNG, increment NWSTNG, and go to step 1.
X
X     As described here, part of step 0 involves returning control to the
XBASIC part of the program.  But on my system it's not convenient to have a
Xmachine language routine call a BASIC routine, so I've rearranged things
Xslightly.
X
X     I'll now describe the machine language routines. Unless otherwise
Xindicated, the parameters T, X, Y, VALUE, and FREE are assumed to
Xsatisfy  0<=T<=TP,  0<=X<XM,  0<=Y<YM,  VALUE = 0, 1, or UNK,  FREE = true
Xor false.
X
X     Many of these routines sometimes detect an error; they report this to
Xthe calling routine by setting the carry bit and storing a value in the
Xvariable ERRCODE to tell which error occurred.  (Calling these 'errors' is
Xmisleading, since they can occur during the normal course of events and
Xsome are even desirable.  But 'exceptional conditions' is too long, so I'll
Xcontinue to call them errors.)
X
XLOOKUP(T,X,Y):  Return the address and value of CELL[T,X,Y]. (This routine
Xgets called more often than any other, so should be fast.  I actually
Ximplemented it as an assembly language macro rather than as a subroutine.
XThe duplicated code made the program a bit larger, but also made it about
X10% faster.  I also have faster versions for the special cases in which the
Xcell being looked up is adjacent to the one previously looked up. This
Xspeeds up the neighborhood calculation in GETNBHD.)
X
XMAP(X,Y):  Return the coordinates of the cell in generation TP
Xcorresponding to the cell (0,X,Y).  Report an 'out of bounds' error if the
Xmapped coordinates are not in the rectangle.
X
XINVMAP(X,Y):  Return the coordinates of the cell in generation 0
Xcorresponding to the cell (TP,X,Y). Report an 'out of bounds' error if the
Xmapped coordinates are not in the rectangle.
X
XNWSET(T,X,Y,VALUE,FREE):  Store a quintuple at NWSTNG and increment NWSTNG.
X
XSETCELL(T,X,Y,VALUE,FREE):  (Should not be called with VALUE = UNK.)  Look
Xup CELL[T,X,Y].  If it equals VALUE, do nothing.  If it equals 1-VALUE,
Xreport an 'inconsistency' error.  If it is unknown, set it to VALUE and
Xcall NWSET to add the quintuple to the setting list.
X
XGETNBHD(T,X,Y):  (Should not be called with T=0.)  Return the neighborhood
Xdescriptor for (T-1,X,Y); i.e. describing the parents of (T,X,Y).  Note: If
X(X,Y) is on the boundary of the rectangle, then GETNBHD assumes that the
Xneighbors which are outside are 0.  There are some situations in which it
Xwould be better to assume they are UNK.
X
XCONSISFY(T,X,Y):  (Should not be called with T=0.  X and Y may be out of
Xbounds, in which case the routine does nothing.)  Make (T,X,Y) fully
Xconsistent with its parents.  Specifically:  Compute the neighborhood
Xdescriptor of (T-1,X,Y), and look it up in TRANSIT and IMPLIC.  If the
Xentry in TRANSIT is 0 or 1 and the value of CELL[T,X,Y] is 1 or 0,
Xrespectively, report an 'inconsistency' error.  Otherwise call SETCELL
X(with FREE=false) for any of (T,X,Y) or its parents which are currently
Xunknown but are forced to be 0 or 1.
X
XCONSIS10(T,X,Y):  Call CONSISFY for (T,X,Y) (provided that T>0) and for
Xeach of its 9 children (provided that T<TP).  Report any 'inconsistency'
Xerror found by CONSISFY.
X
XAPPLYMAP(T,X,Y,VALUE):  (Should not be called with VALUE = UNK.)  If USEMAP
X= false, do nothing.  Otherwise, if T = 0 or TP, call MAP or INVMAP.  If
Xthe mapped cell is out of bounds, do nothing.  Otherwise, call SETCELL for
Xthe mapped cell and VALUE, with FREE=false.  Report any 'inconsistency'
Xerror found by SETCELL.
X
XSYMM(T,X,Y,VALUE):  (Should not be called with VALUE = UNK.) This routine
Xdeals with symmetry, billiard tablicity, and other restrictions desired by
Xthe user.  Separate versions of it exist for different situations.  Each
Xone looks at T, X, Y, and VALUE, decides if any other cells are forced, and
Xcalls SETCELL for them, reporting any 'inconsistency' errors.  (Suppose for
Xexample that we want a pattern to have 90 degree rotational symmetry.  Then
XSYMM could compute the coordinates of the cell obtained by rotating (X,Y)
X90 degrees about the center of symmetry and call SETCELL for it.  It is not
Xnecessary to do the same for the 180 and 270 degree
Xrotations; the higher levels of the program will take care of that.)
X
XEXAMNEXT:  If NXSTNG = NWSTNG, report a 'full consistency achieved' error.
XOtherwise, get the values of T, X, Y, and VALUE pointed to by NXSTNG, and
Xincrement NXSTNG. Call APPLYMAP, SYMM, and CONSIS10, reporting any errors
Xfound by them.  (If one of the routines gives an error, it's not necessary
Xto call the others.)
X
XPROCEED(T,X,Y,VALUE,FREE):  Call SETCELL, reporting an 'inconsistency'
Xerror if it finds one.  Otherwise, call EXAMNEXT repeatedly.  Eventually,
Xit will report either an inconsistency or full consistency.  In the first
Xcase, report it.  In the second case, return without reporting an error.
XThis routine is called whenever we either make a free choice for a cell or
Xhave backed up to a free choice and now want to try the other value there;
Xit finds all the (direct or indirect) conclusions (or a contradiction) from
Xthe choice.  It can also be called from the BASIC program to initialize
Xcertain cells.  (Note: After BASIC has done such initialization, it can set
XNXSTNG and NWSTNG equal to STNG in order to save space; since we don't want
Xto back up over the initialized cells, we don't need to remember them in
Xthe setting list.)
X
XBACKUP:  Undo all settings from NWSTNG back to (and including) the most
Xrecent free choice, changing their values in CELL back to UNK.  If we back
Xup all the way to STNG, report an 'object does not exist' error. Otherwise,
Xmake NWSTNG and NXSTNG point to the free choice and return the values of T,
XX, Y, and VALUE from it.  (This corresponds to repeated application of Step
X2 in the program outline above.)
X
XGO(T,X,Y,VALUE,FREE):  [I ran out of good descriptive subroutine names.]
XCall PROCEED(T,X,Y,VALUE,FREE).  If it returns without an error, then full
Xconsistency has been achieved; return without an error.  Otherwise call
XBACKUP, reporting an 'object does not exist' error if BACKUP finds one.
XOtherwise, call PROCEED(T,X,Y,1-VALUE,false).  Continue calling PROCEED and
XBACKUP alternately until either full consistency is achieved or an 'object
Xdoes not exist' error occurs. (This corresponds to repeated application of
XSteps 1 and 2 above.)
X
XGETUNK:  Select an unknown cell.  If none exist, report a no 'more unknown
Xcells' error.  (This means that an object has been found.)  Otherwise,
Xreturn the values of T, X, and Y.  I won't describe this routine in detail
Xbecause I haven't determined the best way for it to make its choice.  We'd
Xlike to choose cells which are most likely to reveal any previous bad
Xchoices.  Choosing cells which are near recently chosen or forced cells is
Xa good idea, but there's a danger that we'll get stuck in one region and
Xnot notice that something chosen long ago was bad.  Currently, I use a list
Xof all cells set up by the BASIC program and just choose the first unknown
Xone on the list.  But even assuming that we're going to do it that way,
Xit's not clear how the list should be arranged.  Usually I proceed up the
Xcolumns from left to right or down slope -1 diagonals from left to right.
X
XCHOOSE(T,X,Y):  Return a value to be assigned to the currently unknown cell
X(T,X,Y), either 0 or 1.  Again, I don't know the best way to do this.  For
Xa complete search, it doesn't matter; both choices will eventually be
Xtried.  For a partial search, it does.  I usually choose 0 first, hoping
Xthat a small object will be found.  Sometimes I choose 1 to prevent the
Xempty object from being found.  Sometimes I look for an already chosen
Xvalue of CELL[T',X,Y], for T' not equal to T, and give CELL[T,X,Y] the same
Xvalue, hoping that a billiard table will be found.  I can specify which of
Xthese methods will be used initially, and can change it in the middle of a
Xsearch.
X
XMAIN:   This is the top level machine language routine which is called from
Xthe BASIC program.  It searches until it either finds an object of the
Xdesired type, decides that there aren't any more, or is interrupted by the
Xuser.  Specifically, it does this:
X
X     Step 0: Call GETUNK.  If it finds an unknown cell (T,X,Y), go to
X             step 1.  Otherwise, we've already found an object and want
X             to look for another one.  So call BACKUP.  If it gives an
X             'object does not exist' error, report it. Otherwise,
X             change VALUE to 1-VALUE, set FREE = false, and go to
X             step 2.
X
X     Step 1: Call CHOOSE to select a VALUE for the unknown cell, set
X             FREE = true, and go to step 2.
X
X     Step 2: Call GO(T,X,Y,VALUE,FREE).  If it gives an 'object does not
X             exist' error, report it.  Otherwise, check to see if the
X             user has typed a key.  If so, return.  (The user can then
X             display the current contents of CELL to observe the
X             progress of the search, and make some changes if desired.
X             Calling MAIN again will continue the search.) If no key
X             has been typed, go to step 3.
X
X     Step 3: Call GETUNK.  If it finds an unknown cell (T,X,Y), go to
X             step 1.  Otherwise, report that an object has been found.
X
X     In addition to MAIN, the user can also call PROCEED and BACKUP; these
Xare sometimes useful for guiding a search in a promising direction.
X===========================================================================
XEND OF FILE
END_OF_FILE
if test 22903 -ne `wc -c <'ORIGIN'`; then
    echo shar: \"'ORIGIN'\" unpacked with wrong size!
fi
# end of 'ORIGIN'
fi
if test -f 'search.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'search.c'\"
else
echo shar: Extracting \"'search.c'\" \(24647 characters\)
sed "s/^X//" >'search.c' <<'END_OF_FILE'
X/*
X * Life search program - actual search routines.
X * Author: David I. Bell.
X * Based on the algorithms by Dean Hickerson that were
X * included with the "xlife 2.0" distribution.  Thanks!
X */
X
X#include "lifesrc.h"
X
X
X/*
X * IMPLIC flag values.
X */
Xtypedef	unsigned char	FLAGS;
X#define	N0IC0	((FLAGS) 0x01)	/* new cell 0 ==> current cell 0 */
X#define	N0IC1	((FLAGS) 0x02)	/* new cell 0 ==> current cell 1 */
X#define	N1IC0	((FLAGS) 0x04)	/* new cell 1 ==> current cell 0 */
X#define	N1IC1	((FLAGS) 0x08)	/* new cell 1 ==> current cell 1 */
X#define	N0ICUN0	((FLAGS) 0x10)	/* new cell 0 ==> current unknown neighbors 0 */
X#define	N0ICUN1	((FLAGS) 0x20)	/* new cell 0 ==> current unknown neighbors 1 */
X#define	N1ICUN0	((FLAGS) 0x40)	/* new cell 1 ==> current unknown neighbors 0 */
X#define	N1ICUN1	((FLAGS) 0x80)	/* new cell 1 ==> current unknown neighbors 1 */
X
X
X/*
X * Table of transitions.
X * Given the state of a cell and its neighbors in one generation,
X * this table determines the state of the cell in the next generation.
X * The table is indexed by the descriptor value of a cell.
X */
Xstatic STATE	transit[256];
X
X
X/*
X * Table of implications.
X * Given the state of a cell and its neighbors in one generation,
X * this table determines deductions about the cell and its neighbors
X * in the previous generation.
X * The table is indexed by the descriptor value of a cell.
X */
Xstatic FLAGS	implic[256];
X
X
X/*
X * Data about the cells.
X */
XCELL	*celltable[MAXCELLS];	/* table of usual cells */
XCELL	*auxtable[AUXCELLS];	/* table of auxillary cells */
XCELL	*settable[MAXCELLS];	/* table of cells whose value is set */
XCELL	**newset;		/* where to add new cells into setting table */
XCELL	**nextset;		/* next cell in setting table to examine */
XCELL	**baseset;		/* base of changeable part of setting table */
XCELL	*searchlist;		/* current list of cells to search */
XCELL	*fullsearchlist;	/* complete list of cells to search */
XCELL	*newcells;		/* cells ready for allocation */
XCELL	*deadcell;		/* boundary cell value */
Xint	newcellcount;		/* number of cells ready for allocation */
Xint	auxcellcount;		/* number of cells in auxillary table */
X
X
X/*
X * Current parameter values for the program.
X */
XBOOL	debug;			/* enable debugging output (if compiled so) */
XBOOL	nowait;			/* don't wait for commands after loading */
XBOOL	setall;			/* set all cells from initial file */
XBOOL	rowsym;			/* enable row symmetry */
XBOOL	colsym;			/* enable column symmetry */
XBOOL	parent;			/* only look for parents */
XBOOL	allobjects;		/* look for all objects including subperiods */
XSTATUS	curstatus;		/* current status for display */
Xint	curgen;			/* current generation for display */
Xint	rowmax;			/* maximum number of rows */
Xint	colmax;			/* maximum number of columns */
Xint	genmax;			/* maximum number of generations */
Xint	rowtrans;		/* translation of rows */
Xint	coltrans;		/* translation of columns */
Xint	maxcount;		/* maximum number of cells in generation 0 */
Xint	cellcount;		/* number of live cells in generation 0 */
Xlong	dumpfreq;		/* how often to perform dumps */
Xlong	dumpcount;		/* counter for dumps */
Xlong	viewfreq;		/* how often to view results */
Xlong	viewcount;		/* counter for viewing */
Xlong	foundcount;		/* number of objects found */
Xchar	*dumpfile;		/* dump file name */
Xchar	*initfile;		/* file containing initial cells */
Xchar	*loadfile;		/* file to load state from */
Xchar	*outputfile;		/* file to output results to */
X
X
Xstatic STATE	states[NSTATES] = {OFF, ON, UNK};
X
X
X/*
X * Local procedures
X */
Xstatic void	inittransit();
Xstatic void	initimplic();
Xstatic void	linkcell();
Xstatic STATE	transition();
Xstatic STATE	choose();
Xstatic FLAGS	implication();
Xstatic CELL	*symcell();
Xstatic CELL	*allocatecell();
Xstatic CELL	*backup();
Xstatic CELL	*getunknown();
Xstatic STATUS	setcell();
Xstatic STATUS	consistify();
Xstatic STATUS	consistify10();
Xstatic STATUS	examinenext();
Xstatic STATUS	go();
Xstatic int	getdesc();
Xstatic int	sumtodesc();
X
X
X/*
X * Initialize the table of cells.
X * Each cell in the active area is set to unknown state.
X * Boundary cells are set to zero state.
X */
Xvoid
Xinitcells()
X{
X	int	row, col, gen;
X	int	nrow, ncol;
X	int	i;
X	BOOL	edge;
X	CELL	*cell;
X
X	if ((rowmax <= 0) || (rowmax > ROWMAX) ||
X		(colmax <= 0) || (colmax > COLMAX) ||
X		(genmax <= 0) || (genmax > GENMAX) ||
X		(rowtrans < 0) || (rowtrans > TRANSMAX) ||
X		(coltrans < 0) || (coltrans > TRANSMAX))
X	{
X		ttyclose();
X		fprintf(stderr, "ROW, COL, GEN, or TRANS out of range\n");
X		exit(1);
X	}
X
X	/*
X	 * The first allocation of a cell MUST be deadcell.
X	 * Then allocate the cells in the cell table.
X	 */
X	deadcell = allocatecell();
X	for (i = 0; i < MAXCELLS; i++)
X		celltable[i] = allocatecell();
X
X	/*
X	 * Link the cells together.
X	 */
X	for (col = 0; col <= colmax+1; col++) {
X		for (row = 0; row <= rowmax+1; row++) {
X			for (gen = 0; gen < genmax; gen++) {
X				edge = ((row == 0) || (col == 0) ||
X					(row > rowmax) || (col > colmax));
X
X				cell = findcell(row, col, gen);
X				cell->gen = gen;
X				cell->row = row;
X				cell->col = col;
X
X				/*
X				 * If this is not an edge cell, then its state
X				 * is unknown and it needs linking to its
X				 * neighbors.
X				 */
X				if (!edge) {
X					linkcell(cell);
X					cell->state = UNK;
X					cell->free = TRUE;
X				}
X
X				/*
X				 * Map time forwards and backwards,
X				 * wrapping around at the ends.
X				 */
X				cell->past = findcell(row, col,
X					(gen+genmax-1) % genmax);
X				cell->future = findcell(row, col,
X					(gen+1) % genmax);
X
X				/*
X				 * If this is not an edge cell, then
X				 * set up symmetry for it.
X				 */
X				if ((rowsym || colsym) && !edge)
X					cell->csym = symcell(cell);
X
X			}
X		}
X	}
X
X	/*
X	 * If there is a translation, then implement it.
X	 */
X	if (rowtrans || coltrans) {
X		for (col = 0; col <= colmax+1; col++) {
X			for (row = 0; row <= rowmax+1; row++) {
X				cell = findcell(row, col, genmax-1);
X				nrow = row + rowtrans;
X				ncol = col + coltrans;
X				cell->future = findcell(nrow, ncol, 0);
X				linkcell(cell->future);
X
X				cell = findcell(row, col, 0);
X				nrow = row - rowtrans;
X				ncol = col - coltrans;
X				cell->past = findcell(nrow, ncol, genmax-1);
X				linkcell(cell->past);
X			}
X		}
X	}
X
X	/*
X	 * Build the search table list.
X	 * This list is built backwards from the intended search order.
X	 * Do searches from the middle row outwards, and from the left
X	 * to the right columns.  However, since we try OFF cells first,
X	 * reverse the row order again to try to make thin objects.
X	 */
X	searchlist = NULL;
X	for (gen = genmax - 1; gen >= 0; gen--) {
X		for (col = colmax; col > 0; col--) {
X			for (row = (rowmax + 1) / 2; row > 0; row--) {
X				cell = findcell(row, col, gen);
X				cell->search = searchlist;
X				searchlist = cell;
X				if (rowsym || (row * 2 == rowmax + 1))
X					continue;
X				cell = findcell(rowmax + 1 - row, col, gen);
X				cell->search = searchlist;
X				searchlist = cell;
X			}
X		}
X	}
X	fullsearchlist = searchlist;
X
X	newset = settable;
X	nextset = settable;
X	baseset = settable;
X
X	curgen = 0;
X	curstatus = OK;
X	inittransit();
X	initimplic();
X}
X
X
X/*
X * Set the state of a cell to the specified state.
X * The state is either ON or OFF.
X * Returns ERROR if the setting is inconsistent.
X * If the cell is newly set, then it is added to the set table.
X */
Xstatic STATUS
Xsetcell(cell, state, free)
X	CELL	*cell;
X	STATE	state;
X	BOOL	free;
X{
X	if (cell->state == state) {
X		DPRINTF4("setcell %d %d %d to state %s already set\n",
X			cell->row, cell->col, cell->gen,
X			(state == ON) ? "on" : "off");
X		return OK;
X	}
X
X	if (cell->state != UNK) {
X		DPRINTF4("setcell %d %d %d to state %s inconsistent\n",
X			cell->row, cell->col, cell->gen,
X			(state == ON) ? "on" : "off");
X		return ERROR;
X	}
X
X	if ((state == ON) && (cell->gen == 0)) {
X		if (maxcount && (cellcount >= maxcount)) {
X			DPRINTF2("setcell %d %d 0 on exceeds maxcount\n",
X				cell->row, cell->col);
X			return ERROR;
X		}
X		cellcount++;
X	}
X
X	DPRINTF5("setcell %d %d %d to %s, %s successful\n",
X		cell->row, cell->col, cell->gen,
X		(free ? "free" : "forced"), ((state == ON) ? "on" : "off"));
X
X	cell->state = state;
X	cell->free = free;
X	*newset++ = cell;
X
X	return OK;
X}
X
X
X/*
X * Calculate the current descriptor for a cell.
X */
Xstatic int
Xgetdesc(cell)
X	register CELL	*cell;
X{
X	int	sum;
X
X	sum = cell->cul->state + cell->cu->state + cell->cur->state;
X	sum += cell->cdl->state + cell->cd->state + cell->cdr->state;
X	sum += cell->cl->state + cell->cr->state;
X
X	return ((sum & 0x88) ? (sum + cell->state * 2 + 0x11) :
X		(sum * 2 + cell->state));
X}
X
X
X/*
X * Return the descriptor value for a cell and the sum of its neighbors.
X */
Xstatic int
Xsumtodesc(state, sum)
X	STATE	state;
X{
X	return ((sum & 0x88) ? (sum + state * 2 + 0x11) : (sum * 2 + state));
X}
X
X
X/*
X * Consistify a cell.
X * This means examine this cell in the previous generation, and
X * make sure that the previous generation can validly produce the
X * current cell.  Returns ERROR if the cell is inconsistent.
X */
Xstatic STATUS
Xconsistify(cell)
X	CELL	*cell;
X{
X	CELL	*prevcell;
X	int	desc;
X	STATE	state;
X	FLAGS	flags;
X
X	/*
X	 * If we are searching for parents and this is generation 0, then
X	 * the cell is consistent with respect to the previous generation.
X	 */
X	if (parent && (cell->gen == 0))
X		return OK;
X
X	/*
X	 * First check the transit table entry for the previous
X	 * generation.  Make sure that this cell matches the ON or
X	 * OFF state demanded by the transit table.  If the current
X	 * cell is unknown but the transit table knows the answer,
X	 * then set the now known state of the cell.
X	 */
X	prevcell = cell->past;
X	desc = getdesc(prevcell);
X	state = transit[desc];
X	if (state != cell->state) {
X		switch (state) {
X			case ON:
X				if (cell->state == OFF) {
X					DPRINTF3("Transit inconsistently forces cell %d %d %d on\n",
X						cell->row, cell->col,
X						cell->gen);
X					return ERROR;
X				}
X
X				if (cell->gen == 0) {
X					if (maxcount &&
X						(cellcount >= maxcount))
X					{
X						DPRINTF2("Transit forcing cell %d %d 0 exceeds maxcount\n",
X						cell->row, cell->col);
X						return ERROR;
X					}
X					cellcount++;
X				}
X
X				DPRINTF3("Transit forces cell %d %d %d on\n",
X					cell->row, cell->col, cell->gen);
X				cell->state = ON;
X				cell->free = FALSE;
X				*newset++ = cell;
X				break;
X
X			case OFF:
X				if (cell->state == ON) {
X					DPRINTF3("Transit inconsistently forces cell %d %d %d off\n",
X						cell->row, cell->col,
X						cell->gen);
X					return ERROR;
X				}
X				DPRINTF3("Transit forces cell %d %d %d off\n",
X					cell->row, cell->col, cell->gen);
X				cell->state = OFF;
X				cell->free = FALSE;
X				*newset++ = cell;
X				break;
X		}
X	}
X
X	/*
X	 * Now look up the previous generation in the implic table.
X	 * If this cell implies anything about the cell or its neighbors
X	 * in the previous generation, then handle that.
X	 */
X	flags = implic[desc];
X	if ((flags == 0) || (cell->state == UNK))
X		return OK;
X
X	DPRINTF1("Implication flags %x\n", flags);
X
X	if ((flags & N0IC0) && (cell->state == OFF) &&
X		(setcell(prevcell, OFF, FALSE) != OK))
X			return ERROR;
X
X	if ((flags & N1IC1) && (cell->state == ON) &&
X		(setcell(prevcell, ON, FALSE) != OK))
X			return ERROR;
X
X	state = UNK;
X	if (((flags & N0ICUN0) && (cell->state == OFF))
X		|| ((flags & N1ICUN0) && (cell->state == ON)))
X			state = OFF;
X
X	if (((flags & N0ICUN1) && (cell->state == OFF))
X		|| ((flags & N1ICUN1) && (cell->state == ON)))
X			state = ON;
X
X	if (state == UNK) {
X		DPRINTF0("Implications successful\n");
X		return OK;
X	}
X
X	/*
X	 * For each unknown neighbor, set its state as indicated.
X	 * Return an error if any neighbor is inconsistent.
X	 */
X	DPRINTF4("Forcing unknown neighbors of cell %d %d %d %s\n",
X		prevcell->row, prevcell->col, prevcell->gen,
X		((state == ON) ? "on" : "off"));
X
X	if ((prevcell->cul->state == UNK) &&
X		(setcell(prevcell->cul, state, FALSE) != OK))
X			return ERROR;
X
X	if ((prevcell->cu->state == UNK) &&
X		(setcell(prevcell->cu, state, FALSE) != OK))
X			return ERROR;
X
X	if ((prevcell->cur->state == UNK) &&
X		(setcell(prevcell->cur, state, FALSE) != OK))
X			return ERROR;
X
X	if ((prevcell->cl->state == UNK) &&
X		(setcell(prevcell->cl, state, FALSE) != OK))
X			return ERROR;
X
X	if ((prevcell->cr->state == UNK) &&
X		(setcell(prevcell->cr, state, FALSE) != OK))
X			return ERROR;
X
X	if ((prevcell->cdl->state == UNK) &&
X		(setcell(prevcell->cdl, state, FALSE) != OK))
X			return ERROR;
X
X	if ((prevcell->cd->state == UNK) &&
X		(setcell(prevcell->cd, state, FALSE) != OK))
X			return ERROR;
X
X	if ((prevcell->cdr->state == UNK) &&
X		(setcell(prevcell->cdr, state, FALSE) != OK))
X			return ERROR;
X
X	DPRINTF0("Implications successful\n");
X
X	return OK;
X}
X
X
X/*
X * See if a cell and its neighbors are consistent with the cell and its
X * neighbors in the next generation.
X */
Xstatic STATUS
Xconsistify10(cell)
X	CELL	*cell;
X{
X	if (consistify(cell) != OK)
X		return ERROR;
X
X	cell = cell->future;
X	if (consistify(cell) != OK)
X		return ERROR;
X	if (consistify(cell->cul) != OK)
X		return ERROR;
X	if (consistify(cell->cu) != OK)
X		return ERROR;
X	if (consistify(cell->cur) != OK)
X		return ERROR;
X	if (consistify(cell->cl) != OK)
X		return ERROR;
X	if (consistify(cell->cr) != OK)
X		return ERROR;
X	if (consistify(cell->cdl) != OK)
X		return ERROR;
X	if (consistify(cell->cd) != OK)
X		return ERROR;
X	if (consistify(cell->cdr) != OK)
X		return ERROR;
X	return OK;
X}
X
X
X/*
X * Examine the next choice of cell settings.
X */
Xstatic STATUS
Xexaminenext()
X{
X	CELL	*cell;
X
X	/*
X	 * If there are no more cells to examine, then what we have
X	 * is consistent.
X	 */
X	if (nextset == newset)
X		return CONSISTENT;
X
X	/*
X	 * Get the next cell to examine, and check it out for symmetry
X	 * and for consistency with its previous and next generations.
X	 */
X	cell = *nextset++;
X
X	DPRINTF4("Examining saved cell %d %d %d (%s) for consistency\n",
X		cell->row, cell->col, cell->gen,
X		(cell->free ? "free" : "forced"));
X
X	if ((rowsym || colsym) &&
X		(setcell(cell->csym, cell->state, FALSE) != OK))
X			return ERROR;
X
X	return consistify10(cell);
X}
X
X
X/*
X * Set a cell to the specified value and determine all consequences we
X * can from the choice.  Consequences are a contradiction or a consistency.
X */
XSTATUS
Xproceed(cell, state, free)
X	CELL	*cell;
X	STATE	state;
X	BOOL	free;
X{
X	int	status;
X
X	if (setcell(cell, state, free) != OK)
X		return ERROR;
X
X	for (;;) {
X		status = examinenext();
X		if (status == ERROR)
X			return ERROR;
X		if (status == CONSISTENT)
X			return OK;
X	}
X}
X
X
X/*
X * Back up the list of set cells to undo choices.
X * Returns the cell which is to be tried for the other possibility.
X * Returns NULL_CELL on an "object cannot exist" error.
X */
Xstatic CELL *
Xbackup()
X{
X	CELL	*cell;
X
X	searchlist = fullsearchlist;
X
X	while (newset != baseset) {
X		cell = *--newset;
X
X		DPRINTF5("backing up cell %d %d %d, was %s, %s\n",
X			cell->row, cell->col, cell->gen,
X			((cell->state == ON) ? "on" : "off"),
X			(cell->free ? "free": "forced"));
X
X		if ((cell->state == ON) && (cell->gen == 0))
X			cellcount--;
X
X		if (!cell->free) {
X			cell->state = UNK;
X			cell->free = TRUE;
X			continue;
X		}
X		nextset = newset;
X		return cell;
X	}
X	nextset = baseset;
X	return NULL_CELL;
X}
X
X
X/*
X * Do checking based on setting the specified cell.
X * Returns ERROR if an inconsistency was found.
X */
Xstatic STATUS
Xgo(cell, state, free)
X	CELL	*cell;
X	STATE	state;
X	BOOL	free;
X{
X	STATUS	status;
X
X	for (;;) {
X		status = proceed(cell, state, free);
X		if (status == OK)
X			return OK;
X
X		cell = backup();
X		if (cell == NULL_CELL)
X			return ERROR;
X
X		free = FALSE;
X		state = 1 - cell->state;
X		cell->state = UNK;
X	}
X}
X
X
X/*
X * Find another unknown cell.
X * Returns NULL_CELL if there are no more unknown cells.
X */
Xstatic CELL *
Xgetunknown()
X{
X	register CELL 	*cell;
X
X	for (cell = searchlist; cell; cell = cell->search) {
X		if (cell->state == UNK) {
X			searchlist = cell;
X			return cell;
X		}
X	}
X	return NULL_CELL;
X}
X
X
X/*
X * Choose a state for an unknown cell, either OFF or ON.
X * For billiard table stuff, this can be changed to choose the same state
X * as the majority of other generations.
X */
Xstatic STATE
Xchoose(cell)
X	CELL	*cell;
X{
X	return	OFF;
X}
X
X
X/*
X * The top level search routine.
X * Returns if an object is found, or is impossible.
X */
XSTATUS
Xsearch()
X{
X	CELL	*cell;
X	BOOL	free;
X	STATE	state;
X
X	cell = getunknown();
X	if (cell == NULL_CELL) {
X		cell = backup();
X		if (cell == NULL_CELL)
X			return ERROR;
X		free = FALSE;
X		state = 1 - cell->state;
X		cell->state = UNK;
X	} else {
X		state = choose(cell);
X		free = TRUE;
X	}
X
X	for (;;) {
X		if (go(cell, state, free) != OK)
X			return NOTEXIST;
X
X		if (dumpfreq && (++dumpcount >= dumpfreq)) {
X			dumpcount = 0;
X			dumpstate(dumpfile);
X		}
X
X		if (viewfreq && (++viewcount >= viewfreq)) {
X			viewcount = 0;
X			printgen(curgen);
X		}
X
X		if (ttycheck())
X			getcommands();
X
X		cell = getunknown();
X		if (cell == NULL_CELL)
X			return FOUND;
X
X		state = choose(cell);
X		free = TRUE;
X	}
X}
X
X
X/*
X * Check to see if any other generation is identical to generation 0.
X * This is used to detect and weed out all objects with subperiods.
X * (For example, stable objects or period 2 objects when using -g4.)
X * Returns TRUE if there is an identical generation.
X */
XBOOL
Xsubperiods()
X{
X	int	row;
X	int	col;
X	int	gen;
X	CELL	*cellg0;
X	CELL	*cellgn;
X
X	for (gen = 1; gen < genmax; gen++) {
X		if (genmax % gen)
X			continue;
X		for (row = 1; row <= rowmax; row++) {
X			for (col = 1; col <= colmax; col++) {
X				cellg0 = findcell(row, col, 0);
X				cellgn = findcell(row, col, gen);
X				if (cellg0->state != cellgn->state)
X					goto nextgen;
X			}
X		}
X		return TRUE;
Xnextgen:;
X	}
X	return FALSE;
X}
X
X
X/*
X * Return a cell which is symmetric to the given cell.
X * It is not necessary to know all symmetric cells to a single cell,
X * as long as all symmetric cells are chained in a loop.  Thus a single
X * pointer is good enough even for the case of both row and column symmetry.
X * Returns NULL_CELL if there is no symmetry.
X */
Xstatic CELL *
Xsymcell(cell)
X	CELL	*cell;
X{
X	int	row;
X	int	col;
X	int	nrow;
X	int	ncol;
X
X	if (!rowsym && !colsym)
X		return NULL_CELL;
X
X	row = cell->row;
X	col = cell->col;
X	nrow = rowmax + 1 - row;
X	ncol = colmax + 1 - col;
X
X	/*
X	 * If there is symmetry on only one axis, then this is easy.
X	 */
X	if (!colsym)
X		return findcell(nrow, col, cell->gen);
X
X	if (!rowsym)
X		return findcell(row, ncol, cell->gen);
X
X	/*
X	 * Here is there is both row and column symmetry.
X	 * First see if the cell is in the middle row or middle column,
X	 * and if so, then this is easy.
X	 */
X	if ((nrow == row) || (ncol == col))
X		return findcell(nrow, ncol, cell->gen);
X
X	/*
X	 * The cell is really in one of the four quadrants, and therefore
X	 * has four cells making up the symmetry.  Link this cell to the
X	 * symmetrical cell in the next quadrant clockwise.
X	 */
X	if ((row < nrow) == (col < ncol))
X		return findcell(row, ncol, cell->gen);
X	else
X		return findcell(nrow, col, cell->gen);
X}
X
X
X/*
X * Link a cell to its eight neighbors in the same generation, and also
X * link those neighbors back to this cell.
X */
Xstatic void
Xlinkcell(cell)
X	CELL	*cell;
X{
X	int	row;
X	int	col;
X	int	gen;
X	CELL	*paircell;
X
X	row = cell->row;
X	col = cell->col;
X	gen = cell->gen;
X
X	paircell = findcell(row - 1, col - 1, gen);
X	cell->cul = paircell;
X	paircell->cdr = cell;
X
X	paircell = findcell(row - 1, col, gen);
X	cell->cu = paircell;
X	paircell->cd = cell;
X
X	paircell = findcell(row - 1, col + 1, gen);
X	cell->cur = paircell;
X	paircell->cdl = cell;
X
X	paircell = findcell(row, col - 1, gen);
X	cell->cl = paircell;
X	paircell->cr = cell;
X
X	paircell = findcell(row, col + 1, gen);
X	cell->cr = paircell;
X	paircell->cl = cell;
X
X	paircell = findcell(row + 1, col - 1, gen);
X	cell->cdl = paircell;
X	paircell->cur = cell;
X
X	paircell = findcell(row + 1, col, gen);
X	cell->cd = paircell;
X	paircell->cu = cell;
X
X	paircell = findcell(row + 1, col + 1, gen);
X	cell->cdr = paircell;
X	paircell->cul = cell;
X}
X
X
X/*
X * Find a cell given its coordinates.
X * Most coordinates range from 0 to colmax+1, 0 to rowmax+1, and 0 to genmax-1.
X * Cells within this range are quickly found by indexing into celltable.
X * Cells outside of this range are handled by searching an auxillary table,
X * and are dynamically created as necessary.
X */
XCELL *
Xfindcell(row, col, gen)
X{
X	register CELL	*cell;
X	int		i;
X
X	/*
X	 * If the cell is a normal cell, then we know where it is.
X	 */
X	if ((row >= 0) && (row <= rowmax + 1) &&
X		(col >= 0) && (col <= colmax + 1) &&
X		(gen >= 0) && (gen < genmax))
X	{
X		return celltable[(col * (rowmax + 2) + row) * genmax + gen];
X	}
X
X	/*
X	 * See if the cell is already allocated in the auxillary table.
X	 */
X	for (i = 0; i < auxcellcount; i++) {
X		cell = auxtable[i];
X		if ((cell->row == row) && (cell->col == col) &&
X			(cell->gen == gen))
X				return cell;
X	}
X
X	/*
X	 * Need to allocate the cell and add it to the auxillary table.
X	 */
X	cell = allocatecell();
X	cell->row = row;
X	cell->col = col;
X	cell->gen = gen;
X
X	auxtable[auxcellcount++] = cell;
X
X	return cell;
X}
X
X
X/*
X * Allocate a new cell.
X * The cell is initialized as if it was a boundary cell.
X * Warning: The first allocation MUST be of the deadcell.
X */
Xstatic CELL *
Xallocatecell()
X{
X	CELL	*cell;
X
X	/*
X	 * Allocate a new chunk of cells if there are none left.
X	 */
X	if (newcellcount <= 0) {
X		newcells = (CELL *) malloc(sizeof(CELL) * ALLOCSIZE);
X		if (newcells == NULL) {
X			ttyclose();
X			fprintf(stderr, "Cannot allocate cell structure\n");
X			exit(1);
X		}
X		newcellcount = ALLOCSIZE;
X	}
X	newcellcount--;
X	cell = newcells++;
X
X	/*
X	 * If this is the first allocation, then make deadcell be this cell.
X	 */
X	if (deadcell == NULL)
X		deadcell = cell;
X
X	/*
X	 * Fill in the cell as if it was a boundary cell.
X	 */
X	cell->state = OFF;
X	cell->free = FALSE;
X	cell->gen = -1;
X	cell->row = -1;
X	cell->col = -1;
X	cell->past = deadcell;
X	cell->future = deadcell;
X	cell->cul = deadcell;
X	cell->cu = deadcell;
X	cell->cur = deadcell;
X	cell->cl = deadcell;
X	cell->cr = deadcell;
X	cell->cdl = deadcell;
X	cell->cd = deadcell;
X	cell->cdr = deadcell;
X	cell->csym = deadcell;
X
X	return cell;
X}
X
X
X/*
X * Initialize the implication table.
X */
Xstatic void
Xinitimplic()
X{
X	STATE	state;
X	int	OFFcount;
X	int	ONcount;
X	int	sum;
X	int	desc;
X	int	i;
X
X	for (i = 0; i < NSTATES; i++) {
X		state = states[i];
X		for (OFFcount = 8; OFFcount >= 0; OFFcount--) {
X			for (ONcount = 0; ONcount + OFFcount <= 8; ONcount++) {
X				sum = ONcount + (8 - ONcount - OFFcount) * UNK;
X				desc = sumtodesc(state, sum);
X				implic[desc] =
X					implication(state, OFFcount, ONcount);
X			}
X		}
X	}
X}
X
X
X/*
X * Initialize the transition table.
X */
Xstatic void
Xinittransit()
X{
X	int	state;
X	int	OFFcount;
X	int	ONcount;
X	int	sum;
X	int	desc;
X	int	i;
X
X	for (i = 0; i < NSTATES; i++) {
X		state = states[i];
X		for (OFFcount = 8; OFFcount >= 0; OFFcount--) {
X			for (ONcount = 0; ONcount + OFFcount <= 8; ONcount++) {
X				sum = ONcount + (8 - ONcount - OFFcount) * UNK;
X				desc = sumtodesc(state, sum);
X				transit[desc] =
X					transition(state, OFFcount, ONcount);
X			}
X		}
X	}
X}
X
X
X/*
X * Determine the transition of a cell depending on its known neighbor counts.
X * The unknown neighbor count is implicit since there are eight neighbors.
X */
Xstatic STATE
Xtransition(state, OFFcount, ONcount)
X	STATE		state;
X	unsigned int	OFFcount;
X	unsigned int	ONcount;
X{
X	switch (state) {
X		case OFF:
X			if (OFFcount > 5)
X				return OFF;
X			if (ONcount > 3)
X				return OFF;
X			if ((ONcount == 3) && (OFFcount == 5))
X				return ON;
X			return UNK;
X
X		case ON:
X			if (ONcount > 3)
X				return OFF;
X			if (OFFcount > 6)
X				return OFF;
X			if ((ONcount == 2) &&
X				((OFFcount == 5) || (OFFcount == 6)))
X					return ON;
X			if ((ONcount == 3) && (OFFcount == 5))
X				return ON;
X			return UNK;
X
X		case UNK:
X			if (ONcount > 3)
X				return OFF;
X			if (OFFcount > 6)
X				return OFF;
X			if ((ONcount == 3) && (OFFcount == 5))
X				return ON;
X			return UNK;
X
X		default:
X			return UNK;
X	}
X}
X
X
X/*
X * Determine the implications of a cell depending on its known neighbor counts.
X * The unknown neighbor count is implicit since there are eight neighbors.
X */
Xstatic FLAGS
Ximplication(state, OFFcount, ONcount)
X	STATE		state;
X	unsigned int	OFFcount;
X	unsigned int	ONcount;
X{
X	unsigned int	UNKcount;
X	FLAGS		flags;
X
X	UNKcount = 8 - OFFcount - ONcount;
X	flags = 0;
X	if (ONcount == 3)
X		flags |= N1ICUN0;
X	if ((ONcount == 3) && (UNKcount == 1))
X		flags |= N0ICUN1;
X
X	switch (state) {
X		case OFF:
X			if ((ONcount == 2) && (UNKcount == 1))
X				flags |= N0ICUN0;
X			if (OFFcount == 5)
X				flags |= N1ICUN1;
X			break;
X
X		case ON:
X			if (OFFcount == 6)
X				flags |= N1ICUN1;
X			if ((ONcount == 1) && (UNKcount == 1))
X				flags |= N0ICUN0;
X			break;
X
X		case UNK:
X			if (OFFcount == 6)
X				flags |= (N1ICUN1 | N1IC1);
X			if ((ONcount == 2) && (UNKcount == 0))
X				flags |= (N0IC0 | N1IC1);
X			break;
X	}
X	if (UNKcount == 0)
X		flags &= ~(N0ICUN0 | N0ICUN1 | N1ICUN0 | N1ICUN1);
X	return flags;
X}
X
X/* END CODE */
END_OF_FILE
if test 24647 -ne `wc -c <'search.c'`; then
    echo shar: \"'search.c'\" unpacked with wrong size!
fi
# end of 'search.c'
fi
echo shar: End of archive 2 \(of 2\).
cp /dev/null ark2isdone
MISSING=""
for I in 1 2 ; do
    if test ! -f ark${I}isdone ; then
	MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked both archives.
    rm -f ark[1-9]isdone
else
    echo You still need to unpack the following archives:
    echo "        " ${MISSING}
fi
##  End of shell archive.
exit 0
D