home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1890 / search.c < prev   
Encoding:
C/C++ Source or Header  |  1990-12-28  |  24.1 KB  |  1,108 lines
  1. /*
  2.  * Life search program - actual search routines.
  3.  * Author: David I. Bell.
  4.  * Based on the algorithms by Dean Hickerson that were
  5.  * included with the "xlife 2.0" distribution.  Thanks!
  6.  */
  7.  
  8. #include "lifesrc.h"
  9.  
  10.  
  11. /*
  12.  * IMPLIC flag values.
  13.  */
  14. typedef    unsigned char    FLAGS;
  15. #define    N0IC0    ((FLAGS) 0x01)    /* new cell 0 ==> current cell 0 */
  16. #define    N0IC1    ((FLAGS) 0x02)    /* new cell 0 ==> current cell 1 */
  17. #define    N1IC0    ((FLAGS) 0x04)    /* new cell 1 ==> current cell 0 */
  18. #define    N1IC1    ((FLAGS) 0x08)    /* new cell 1 ==> current cell 1 */
  19. #define    N0ICUN0    ((FLAGS) 0x10)    /* new cell 0 ==> current unknown neighbors 0 */
  20. #define    N0ICUN1    ((FLAGS) 0x20)    /* new cell 0 ==> current unknown neighbors 1 */
  21. #define    N1ICUN0    ((FLAGS) 0x40)    /* new cell 1 ==> current unknown neighbors 0 */
  22. #define    N1ICUN1    ((FLAGS) 0x80)    /* new cell 1 ==> current unknown neighbors 1 */
  23.  
  24.  
  25. /*
  26.  * Table of transitions.
  27.  * Given the state of a cell and its neighbors in one generation,
  28.  * this table determines the state of the cell in the next generation.
  29.  * The table is indexed by the descriptor value of a cell.
  30.  */
  31. static STATE    transit[256];
  32.  
  33.  
  34. /*
  35.  * Table of implications.
  36.  * Given the state of a cell and its neighbors in one generation,
  37.  * this table determines deductions about the cell and its neighbors
  38.  * in the previous generation.
  39.  * The table is indexed by the descriptor value of a cell.
  40.  */
  41. static FLAGS    implic[256];
  42.  
  43.  
  44. /*
  45.  * Data about the cells.
  46.  */
  47. CELL    *celltable[MAXCELLS];    /* table of usual cells */
  48. CELL    *auxtable[AUXCELLS];    /* table of auxillary cells */
  49. CELL    *settable[MAXCELLS];    /* table of cells whose value is set */
  50. CELL    **newset;        /* where to add new cells into setting table */
  51. CELL    **nextset;        /* next cell in setting table to examine */
  52. CELL    **baseset;        /* base of changeable part of setting table */
  53. CELL    *searchlist;        /* current list of cells to search */
  54. CELL    *fullsearchlist;    /* complete list of cells to search */
  55. CELL    *newcells;        /* cells ready for allocation */
  56. CELL    *deadcell;        /* boundary cell value */
  57. int    newcellcount;        /* number of cells ready for allocation */
  58. int    auxcellcount;        /* number of cells in auxillary table */
  59.  
  60.  
  61. /*
  62.  * Current parameter values for the program.
  63.  */
  64. BOOL    debug;            /* enable debugging output (if compiled so) */
  65. BOOL    nowait;            /* don't wait for commands after loading */
  66. BOOL    setall;            /* set all cells from initial file */
  67. BOOL    rowsym;            /* enable row symmetry */
  68. BOOL    colsym;            /* enable column symmetry */
  69. BOOL    parent;            /* only look for parents */
  70. BOOL    allobjects;        /* look for all objects including subperiods */
  71. STATUS    curstatus;        /* current status for display */
  72. int    curgen;            /* current generation for display */
  73. int    rowmax;            /* maximum number of rows */
  74. int    colmax;            /* maximum number of columns */
  75. int    genmax;            /* maximum number of generations */
  76. int    rowtrans;        /* translation of rows */
  77. int    coltrans;        /* translation of columns */
  78. int    maxcount;        /* maximum number of cells in generation 0 */
  79. int    cellcount;        /* number of live cells in generation 0 */
  80. long    dumpfreq;        /* how often to perform dumps */
  81. long    dumpcount;        /* counter for dumps */
  82. long    viewfreq;        /* how often to view results */
  83. long    viewcount;        /* counter for viewing */
  84. long    foundcount;        /* number of objects found */
  85. char    *dumpfile;        /* dump file name */
  86. char    *initfile;        /* file containing initial cells */
  87. char    *loadfile;        /* file to load state from */
  88. char    *outputfile;        /* file to output results to */
  89.  
  90.  
  91. static STATE    states[NSTATES] = {OFF, ON, UNK};
  92.  
  93.  
  94. /*
  95.  * Local procedures
  96.  */
  97. static void    inittransit();
  98. static void    initimplic();
  99. static void    linkcell();
  100. static STATE    transition();
  101. static STATE    choose();
  102. static FLAGS    implication();
  103. static CELL    *symcell();
  104. static CELL    *allocatecell();
  105. static CELL    *backup();
  106. static CELL    *getunknown();
  107. static STATUS    setcell();
  108. static STATUS    consistify();
  109. static STATUS    consistify10();
  110. static STATUS    examinenext();
  111. static STATUS    go();
  112. static int    getdesc();
  113. static int    sumtodesc();
  114.  
  115.  
  116. /*
  117.  * Initialize the table of cells.
  118.  * Each cell in the active area is set to unknown state.
  119.  * Boundary cells are set to zero state.
  120.  */
  121. void
  122. initcells()
  123. {
  124.     int    row, col, gen;
  125.     int    nrow, ncol;
  126.     int    i;
  127.     BOOL    edge;
  128.     CELL    *cell;
  129.  
  130.     if ((rowmax <= 0) || (rowmax > ROWMAX) ||
  131.         (colmax <= 0) || (colmax > COLMAX) ||
  132.         (genmax <= 0) || (genmax > GENMAX) ||
  133.         (rowtrans < 0) || (rowtrans > TRANSMAX) ||
  134.         (coltrans < 0) || (coltrans > TRANSMAX))
  135.     {
  136.         ttyclose();
  137.         fprintf(stderr, "ROW, COL, GEN, or TRANS out of range\n");
  138.         exit(1);
  139.     }
  140.  
  141.     /*
  142.      * The first allocation of a cell MUST be deadcell.
  143.      * Then allocate the cells in the cell table.
  144.      */
  145.     deadcell = allocatecell();
  146.     for (i = 0; i < MAXCELLS; i++)
  147.         celltable[i] = allocatecell();
  148.  
  149.     /*
  150.      * Link the cells together.
  151.      */
  152.     for (col = 0; col <= colmax+1; col++) {
  153.         for (row = 0; row <= rowmax+1; row++) {
  154.             for (gen = 0; gen < genmax; gen++) {
  155.                 edge = ((row == 0) || (col == 0) ||
  156.                     (row > rowmax) || (col > colmax));
  157.  
  158.                 cell = findcell(row, col, gen);
  159.                 cell->gen = gen;
  160.                 cell->row = row;
  161.                 cell->col = col;
  162.  
  163.                 /*
  164.                  * If this is not an edge cell, then its state
  165.                  * is unknown and it needs linking to its
  166.                  * neighbors.
  167.                  */
  168.                 if (!edge) {
  169.                     linkcell(cell);
  170.                     cell->state = UNK;
  171.                     cell->free = TRUE;
  172.                 }
  173.  
  174.                 /*
  175.                  * Map time forwards and backwards,
  176.                  * wrapping around at the ends.
  177.                  */
  178.                 cell->past = findcell(row, col,
  179.                     (gen+genmax-1) % genmax);
  180.                 cell->future = findcell(row, col,
  181.                     (gen+1) % genmax);
  182.  
  183.                 /*
  184.                  * If this is not an edge cell, then
  185.                  * set up symmetry for it.
  186.                  */
  187.                 if ((rowsym || colsym) && !edge)
  188.                     cell->csym = symcell(cell);
  189.  
  190.             }
  191.         }
  192.     }
  193.  
  194.     /*
  195.      * If there is a translation, then implement it.
  196.      */
  197.     if (rowtrans || coltrans) {
  198.         for (col = 0; col <= colmax+1; col++) {
  199.             for (row = 0; row <= rowmax+1; row++) {
  200.                 cell = findcell(row, col, genmax-1);
  201.                 nrow = row + rowtrans;
  202.                 ncol = col + coltrans;
  203.                 cell->future = findcell(nrow, ncol, 0);
  204.                 linkcell(cell->future);
  205.  
  206.                 cell = findcell(row, col, 0);
  207.                 nrow = row - rowtrans;
  208.                 ncol = col - coltrans;
  209.                 cell->past = findcell(nrow, ncol, genmax-1);
  210.                 linkcell(cell->past);
  211.             }
  212.         }
  213.     }
  214.  
  215.     /*
  216.      * Build the search table list.
  217.      * This list is built backwards from the intended search order.
  218.      * Do searches from the middle row outwards, and from the left
  219.      * to the right columns.  However, since we try OFF cells first,
  220.      * reverse the row order again to try to make thin objects.
  221.      */
  222.     searchlist = NULL;
  223.     for (gen = genmax - 1; gen >= 0; gen--) {
  224.         for (col = colmax; col > 0; col--) {
  225.             for (row = (rowmax + 1) / 2; row > 0; row--) {
  226.                 cell = findcell(row, col, gen);
  227.                 cell->search = searchlist;
  228.                 searchlist = cell;
  229.                 if (rowsym || (row * 2 == rowmax + 1))
  230.                     continue;
  231.                 cell = findcell(rowmax + 1 - row, col, gen);
  232.                 cell->search = searchlist;
  233.                 searchlist = cell;
  234.             }
  235.         }
  236.     }
  237.     fullsearchlist = searchlist;
  238.  
  239.     newset = settable;
  240.     nextset = settable;
  241.     baseset = settable;
  242.  
  243.     curgen = 0;
  244.     curstatus = OK;
  245.     inittransit();
  246.     initimplic();
  247. }
  248.  
  249.  
  250. /*
  251.  * Set the state of a cell to the specified state.
  252.  * The state is either ON or OFF.
  253.  * Returns ERROR if the setting is inconsistent.
  254.  * If the cell is newly set, then it is added to the set table.
  255.  */
  256. static STATUS
  257. setcell(cell, state, free)
  258.     CELL    *cell;
  259.     STATE    state;
  260.     BOOL    free;
  261. {
  262.     if (cell->state == state) {
  263.         DPRINTF4("setcell %d %d %d to state %s already set\n",
  264.             cell->row, cell->col, cell->gen,
  265.             (state == ON) ? "on" : "off");
  266.         return OK;
  267.     }
  268.  
  269.     if (cell->state != UNK) {
  270.         DPRINTF4("setcell %d %d %d to state %s inconsistent\n",
  271.             cell->row, cell->col, cell->gen,
  272.             (state == ON) ? "on" : "off");
  273.         return ERROR;
  274.     }
  275.  
  276.     if ((state == ON) && (cell->gen == 0)) {
  277.         if (maxcount && (cellcount >= maxcount)) {
  278.             DPRINTF2("setcell %d %d 0 on exceeds maxcount\n",
  279.                 cell->row, cell->col);
  280.             return ERROR;
  281.         }
  282.         cellcount++;
  283.     }
  284.  
  285.     DPRINTF5("setcell %d %d %d to %s, %s successful\n",
  286.         cell->row, cell->col, cell->gen,
  287.         (free ? "free" : "forced"), ((state == ON) ? "on" : "off"));
  288.  
  289.     cell->state = state;
  290.     cell->free = free;
  291.     *newset++ = cell;
  292.  
  293.     return OK;
  294. }
  295.  
  296.  
  297. /*
  298.  * Calculate the current descriptor for a cell.
  299.  */
  300. static int
  301. getdesc(cell)
  302.     register CELL    *cell;
  303. {
  304.     int    sum;
  305.  
  306.     sum = cell->cul->state + cell->cu->state + cell->cur->state;
  307.     sum += cell->cdl->state + cell->cd->state + cell->cdr->state;
  308.     sum += cell->cl->state + cell->cr->state;
  309.  
  310.     return ((sum & 0x88) ? (sum + cell->state * 2 + 0x11) :
  311.         (sum * 2 + cell->state));
  312. }
  313.  
  314.  
  315. /*
  316.  * Return the descriptor value for a cell and the sum of its neighbors.
  317.  */
  318. static int
  319. sumtodesc(state, sum)
  320.     STATE    state;
  321. {
  322.     return ((sum & 0x88) ? (sum + state * 2 + 0x11) : (sum * 2 + state));
  323. }
  324.  
  325.  
  326. /*
  327.  * Consistify a cell.
  328.  * This means examine this cell in the previous generation, and
  329.  * make sure that the previous generation can validly produce the
  330.  * current cell.  Returns ERROR if the cell is inconsistent.
  331.  */
  332. static STATUS
  333. consistify(cell)
  334.     CELL    *cell;
  335. {
  336.     CELL    *prevcell;
  337.     int    desc;
  338.     STATE    state;
  339.     FLAGS    flags;
  340.  
  341.     /*
  342.      * If we are searching for parents and this is generation 0, then
  343.      * the cell is consistent with respect to the previous generation.
  344.      */
  345.     if (parent && (cell->gen == 0))
  346.         return OK;
  347.  
  348.     /*
  349.      * First check the transit table entry for the previous
  350.      * generation.  Make sure that this cell matches the ON or
  351.      * OFF state demanded by the transit table.  If the current
  352.      * cell is unknown but the transit table knows the answer,
  353.      * then set the now known state of the cell.
  354.      */
  355.     prevcell = cell->past;
  356.     desc = getdesc(prevcell);
  357.     state = transit[desc];
  358.     if (state != cell->state) {
  359.         switch (state) {
  360.             case ON:
  361.                 if (cell->state == OFF) {
  362.                     DPRINTF3("Transit inconsistently forces cell %d %d %d on\n",
  363.                         cell->row, cell->col,
  364.                         cell->gen);
  365.                     return ERROR;
  366.                 }
  367.  
  368.                 if (cell->gen == 0) {
  369.                     if (maxcount &&
  370.                         (cellcount >= maxcount))
  371.                     {
  372.                         DPRINTF2("Transit forcing cell %d %d 0 exceeds maxcount\n",
  373.                         cell->row, cell->col);
  374.                         return ERROR;
  375.                     }
  376.                     cellcount++;
  377.                 }
  378.  
  379.                 DPRINTF3("Transit forces cell %d %d %d on\n",
  380.                     cell->row, cell->col, cell->gen);
  381.                 cell->state = ON;
  382.                 cell->free = FALSE;
  383.                 *newset++ = cell;
  384.                 break;
  385.  
  386.             case OFF:
  387.                 if (cell->state == ON) {
  388.                     DPRINTF3("Transit inconsistently forces cell %d %d %d off\n",
  389.                         cell->row, cell->col,
  390.                         cell->gen);
  391.                     return ERROR;
  392.                 }
  393.                 DPRINTF3("Transit forces cell %d %d %d off\n",
  394.                     cell->row, cell->col, cell->gen);
  395.                 cell->state = OFF;
  396.                 cell->free = FALSE;
  397.                 *newset++ = cell;
  398.                 break;
  399.         }
  400.     }
  401.  
  402.     /*
  403.      * Now look up the previous generation in the implic table.
  404.      * If this cell implies anything about the cell or its neighbors
  405.      * in the previous generation, then handle that.
  406.      */
  407.     flags = implic[desc];
  408.     if ((flags == 0) || (cell->state == UNK))
  409.         return OK;
  410.  
  411.     DPRINTF1("Implication flags %x\n", flags);
  412.  
  413.     if ((flags & N0IC0) && (cell->state == OFF) &&
  414.         (setcell(prevcell, OFF, FALSE) != OK))
  415.             return ERROR;
  416.  
  417.     if ((flags & N1IC1) && (cell->state == ON) &&
  418.         (setcell(prevcell, ON, FALSE) != OK))
  419.             return ERROR;
  420.  
  421.     state = UNK;
  422.     if (((flags & N0ICUN0) && (cell->state == OFF))
  423.         || ((flags & N1ICUN0) && (cell->state == ON)))
  424.             state = OFF;
  425.  
  426.     if (((flags & N0ICUN1) && (cell->state == OFF))
  427.         || ((flags & N1ICUN1) && (cell->state == ON)))
  428.             state = ON;
  429.  
  430.     if (state == UNK) {
  431.         DPRINTF0("Implications successful\n");
  432.         return OK;
  433.     }
  434.  
  435.     /*
  436.      * For each unknown neighbor, set its state as indicated.
  437.      * Return an error if any neighbor is inconsistent.
  438.      */
  439.     DPRINTF4("Forcing unknown neighbors of cell %d %d %d %s\n",
  440.         prevcell->row, prevcell->col, prevcell->gen,
  441.         ((state == ON) ? "on" : "off"));
  442.  
  443.     if ((prevcell->cul->state == UNK) &&
  444.         (setcell(prevcell->cul, state, FALSE) != OK))
  445.             return ERROR;
  446.  
  447.     if ((prevcell->cu->state == UNK) &&
  448.         (setcell(prevcell->cu, state, FALSE) != OK))
  449.             return ERROR;
  450.  
  451.     if ((prevcell->cur->state == UNK) &&
  452.         (setcell(prevcell->cur, state, FALSE) != OK))
  453.             return ERROR;
  454.  
  455.     if ((prevcell->cl->state == UNK) &&
  456.         (setcell(prevcell->cl, state, FALSE) != OK))
  457.             return ERROR;
  458.  
  459.     if ((prevcell->cr->state == UNK) &&
  460.         (setcell(prevcell->cr, state, FALSE) != OK))
  461.             return ERROR;
  462.  
  463.     if ((prevcell->cdl->state == UNK) &&
  464.         (setcell(prevcell->cdl, state, FALSE) != OK))
  465.             return ERROR;
  466.  
  467.     if ((prevcell->cd->state == UNK) &&
  468.         (setcell(prevcell->cd, state, FALSE) != OK))
  469.             return ERROR;
  470.  
  471.     if ((prevcell->cdr->state == UNK) &&
  472.         (setcell(prevcell->cdr, state, FALSE) != OK))
  473.             return ERROR;
  474.  
  475.     DPRINTF0("Implications successful\n");
  476.  
  477.     return OK;
  478. }
  479.  
  480.  
  481. /*
  482.  * See if a cell and its neighbors are consistent with the cell and its
  483.  * neighbors in the next generation.
  484.  */
  485. static STATUS
  486. consistify10(cell)
  487.     CELL    *cell;
  488. {
  489.     if (consistify(cell) != OK)
  490.         return ERROR;
  491.  
  492.     cell = cell->future;
  493.     if (consistify(cell) != OK)
  494.         return ERROR;
  495.     if (consistify(cell->cul) != OK)
  496.         return ERROR;
  497.     if (consistify(cell->cu) != OK)
  498.         return ERROR;
  499.     if (consistify(cell->cur) != OK)
  500.         return ERROR;
  501.     if (consistify(cell->cl) != OK)
  502.         return ERROR;
  503.     if (consistify(cell->cr) != OK)
  504.         return ERROR;
  505.     if (consistify(cell->cdl) != OK)
  506.         return ERROR;
  507.     if (consistify(cell->cd) != OK)
  508.         return ERROR;
  509.     if (consistify(cell->cdr) != OK)
  510.         return ERROR;
  511.     return OK;
  512. }
  513.  
  514.  
  515. /*
  516.  * Examine the next choice of cell settings.
  517.  */
  518. static STATUS
  519. examinenext()
  520. {
  521.     CELL    *cell;
  522.  
  523.     /*
  524.      * If there are no more cells to examine, then what we have
  525.      * is consistent.
  526.      */
  527.     if (nextset == newset)
  528.         return CONSISTENT;
  529.  
  530.     /*
  531.      * Get the next cell to examine, and check it out for symmetry
  532.      * and for consistency with its previous and next generations.
  533.      */
  534.     cell = *nextset++;
  535.  
  536.     DPRINTF4("Examining saved cell %d %d %d (%s) for consistency\n",
  537.         cell->row, cell->col, cell->gen,
  538.         (cell->free ? "free" : "forced"));
  539.  
  540.     if ((rowsym || colsym) &&
  541.         (setcell(cell->csym, cell->state, FALSE) != OK))
  542.             return ERROR;
  543.  
  544.     return consistify10(cell);
  545. }
  546.  
  547.  
  548. /*
  549.  * Set a cell to the specified value and determine all consequences we
  550.  * can from the choice.  Consequences are a contradiction or a consistency.
  551.  */
  552. STATUS
  553. proceed(cell, state, free)
  554.     CELL    *cell;
  555.     STATE    state;
  556.     BOOL    free;
  557. {
  558.     int    status;
  559.  
  560.     if (setcell(cell, state, free) != OK)
  561.         return ERROR;
  562.  
  563.     for (;;) {
  564.         status = examinenext();
  565.         if (status == ERROR)
  566.             return ERROR;
  567.         if (status == CONSISTENT)
  568.             return OK;
  569.     }
  570. }
  571.  
  572.  
  573. /*
  574.  * Back up the list of set cells to undo choices.
  575.  * Returns the cell which is to be tried for the other possibility.
  576.  * Returns NULL_CELL on an "object cannot exist" error.
  577.  */
  578. static CELL *
  579. backup()
  580. {
  581.     CELL    *cell;
  582.  
  583.     searchlist = fullsearchlist;
  584.  
  585.     while (newset != baseset) {
  586.         cell = *--newset;
  587.  
  588.         DPRINTF5("backing up cell %d %d %d, was %s, %s\n",
  589.             cell->row, cell->col, cell->gen,
  590.             ((cell->state == ON) ? "on" : "off"),
  591.             (cell->free ? "free": "forced"));
  592.  
  593.         if ((cell->state == ON) && (cell->gen == 0))
  594.             cellcount--;
  595.  
  596.         if (!cell->free) {
  597.             cell->state = UNK;
  598.             cell->free = TRUE;
  599.             continue;
  600.         }
  601.         nextset = newset;
  602.         return cell;
  603.     }
  604.     nextset = baseset;
  605.     return NULL_CELL;
  606. }
  607.  
  608.  
  609. /*
  610.  * Do checking based on setting the specified cell.
  611.  * Returns ERROR if an inconsistency was found.
  612.  */
  613. static STATUS
  614. go(cell, state, free)
  615.     CELL    *cell;
  616.     STATE    state;
  617.     BOOL    free;
  618. {
  619.     STATUS    status;
  620.  
  621.     for (;;) {
  622.         status = proceed(cell, state, free);
  623.         if (status == OK)
  624.             return OK;
  625.  
  626.         cell = backup();
  627.         if (cell == NULL_CELL)
  628.             return ERROR;
  629.  
  630.         free = FALSE;
  631.         state = 1 - cell->state;
  632.         cell->state = UNK;
  633.     }
  634. }
  635.  
  636.  
  637. /*
  638.  * Find another unknown cell.
  639.  * Returns NULL_CELL if there are no more unknown cells.
  640.  */
  641. static CELL *
  642. getunknown()
  643. {
  644.     register CELL     *cell;
  645.  
  646.     for (cell = searchlist; cell; cell = cell->search) {
  647.         if (cell->state == UNK) {
  648.             searchlist = cell;
  649.             return cell;
  650.         }
  651.     }
  652.     return NULL_CELL;
  653. }
  654.  
  655.  
  656. /*
  657.  * Choose a state for an unknown cell, either OFF or ON.
  658.  * For billiard table stuff, this can be changed to choose the same state
  659.  * as the majority of other generations.
  660.  */
  661. static STATE
  662. choose(cell)
  663.     CELL    *cell;
  664. {
  665.     return    OFF;
  666. }
  667.  
  668.  
  669. /*
  670.  * The top level search routine.
  671.  * Returns if an object is found, or is impossible.
  672.  */
  673. STATUS
  674. search()
  675. {
  676.     CELL    *cell;
  677.     BOOL    free;
  678.     STATE    state;
  679.  
  680.     cell = getunknown();
  681.     if (cell == NULL_CELL) {
  682.         cell = backup();
  683.         if (cell == NULL_CELL)
  684.             return ERROR;
  685.         free = FALSE;
  686.         state = 1 - cell->state;
  687.         cell->state = UNK;
  688.     } else {
  689.         state = choose(cell);
  690.         free = TRUE;
  691.     }
  692.  
  693.     for (;;) {
  694.         if (go(cell, state, free) != OK)
  695.             return NOTEXIST;
  696.  
  697.         if (dumpfreq && (++dumpcount >= dumpfreq)) {
  698.             dumpcount = 0;
  699.             dumpstate(dumpfile);
  700.         }
  701.  
  702.         if (viewfreq && (++viewcount >= viewfreq)) {
  703.             viewcount = 0;
  704.             printgen(curgen);
  705.         }
  706.  
  707.         if (ttycheck())
  708.             getcommands();
  709.  
  710.         cell = getunknown();
  711.         if (cell == NULL_CELL)
  712.             return FOUND;
  713.  
  714.         state = choose(cell);
  715.         free = TRUE;
  716.     }
  717. }
  718.  
  719.  
  720. /*
  721.  * Check to see if any other generation is identical to generation 0.
  722.  * This is used to detect and weed out all objects with subperiods.
  723.  * (For example, stable objects or period 2 objects when using -g4.)
  724.  * Returns TRUE if there is an identical generation.
  725.  */
  726. BOOL
  727. subperiods()
  728. {
  729.     int    row;
  730.     int    col;
  731.     int    gen;
  732.     CELL    *cellg0;
  733.     CELL    *cellgn;
  734.  
  735.     for (gen = 1; gen < genmax; gen++) {
  736.         if (genmax % gen)
  737.             continue;
  738.         for (row = 1; row <= rowmax; row++) {
  739.             for (col = 1; col <= colmax; col++) {
  740.                 cellg0 = findcell(row, col, 0);
  741.                 cellgn = findcell(row, col, gen);
  742.                 if (cellg0->state != cellgn->state)
  743.                     goto nextgen;
  744.             }
  745.         }
  746.         return TRUE;
  747. nextgen:;
  748.     }
  749.     return FALSE;
  750. }
  751.  
  752.  
  753. /*
  754.  * Return a cell which is symmetric to the given cell.
  755.  * It is not necessary to know all symmetric cells to a single cell,
  756.  * as long as all symmetric cells are chained in a loop.  Thus a single
  757.  * pointer is good enough even for the case of both row and column symmetry.
  758.  * Returns NULL_CELL if there is no symmetry.
  759.  */
  760. static CELL *
  761. symcell(cell)
  762.     CELL    *cell;
  763. {
  764.     int    row;
  765.     int    col;
  766.     int    nrow;
  767.     int    ncol;
  768.  
  769.     if (!rowsym && !colsym)
  770.         return NULL_CELL;
  771.  
  772.     row = cell->row;
  773.     col = cell->col;
  774.     nrow = rowmax + 1 - row;
  775.     ncol = colmax + 1 - col;
  776.  
  777.     /*
  778.      * If there is symmetry on only one axis, then this is easy.
  779.      */
  780.     if (!colsym)
  781.         return findcell(nrow, col, cell->gen);
  782.  
  783.     if (!rowsym)
  784.         return findcell(row, ncol, cell->gen);
  785.  
  786.     /*
  787.      * Here is there is both row and column symmetry.
  788.      * First see if the cell is in the middle row or middle column,
  789.      * and if so, then this is easy.
  790.      */
  791.     if ((nrow == row) || (ncol == col))
  792.         return findcell(nrow, ncol, cell->gen);
  793.  
  794.     /*
  795.      * The cell is really in one of the four quadrants, and therefore
  796.      * has four cells making up the symmetry.  Link this cell to the
  797.      * symmetrical cell in the next quadrant clockwise.
  798.      */
  799.     if ((row < nrow) == (col < ncol))
  800.         return findcell(row, ncol, cell->gen);
  801.     else
  802.         return findcell(nrow, col, cell->gen);
  803. }
  804.  
  805.  
  806. /*
  807.  * Link a cell to its eight neighbors in the same generation, and also
  808.  * link those neighbors back to this cell.
  809.  */
  810. static void
  811. linkcell(cell)
  812.     CELL    *cell;
  813. {
  814.     int    row;
  815.     int    col;
  816.     int    gen;
  817.     CELL    *paircell;
  818.  
  819.     row = cell->row;
  820.     col = cell->col;
  821.     gen = cell->gen;
  822.  
  823.     paircell = findcell(row - 1, col - 1, gen);
  824.     cell->cul = paircell;
  825.     paircell->cdr = cell;
  826.  
  827.     paircell = findcell(row - 1, col, gen);
  828.     cell->cu = paircell;
  829.     paircell->cd = cell;
  830.  
  831.     paircell = findcell(row - 1, col + 1, gen);
  832.     cell->cur = paircell;
  833.     paircell->cdl = cell;
  834.  
  835.     paircell = findcell(row, col - 1, gen);
  836.     cell->cl = paircell;
  837.     paircell->cr = cell;
  838.  
  839.     paircell = findcell(row, col + 1, gen);
  840.     cell->cr = paircell;
  841.     paircell->cl = cell;
  842.  
  843.     paircell = findcell(row + 1, col - 1, gen);
  844.     cell->cdl = paircell;
  845.     paircell->cur = cell;
  846.  
  847.     paircell = findcell(row + 1, col, gen);
  848.     cell->cd = paircell;
  849.     paircell->cu = cell;
  850.  
  851.     paircell = findcell(row + 1, col + 1, gen);
  852.     cell->cdr = paircell;
  853.     paircell->cul = cell;
  854. }
  855.  
  856.  
  857. /*
  858.  * Find a cell given its coordinates.
  859.  * Most coordinates range from 0 to colmax+1, 0 to rowmax+1, and 0 to genmax-1.
  860.  * Cells within this range are quickly found by indexing into celltable.
  861.  * Cells outside of this range are handled by searching an auxillary table,
  862.  * and are dynamically created as necessary.
  863.  */
  864. CELL *
  865. findcell(row, col, gen)
  866. {
  867.     register CELL    *cell;
  868.     int        i;
  869.  
  870.     /*
  871.      * If the cell is a normal cell, then we know where it is.
  872.      */
  873.     if ((row >= 0) && (row <= rowmax + 1) &&
  874.         (col >= 0) && (col <= colmax + 1) &&
  875.         (gen >= 0) && (gen < genmax))
  876.     {
  877.         return celltable[(col * (rowmax + 2) + row) * genmax + gen];
  878.     }
  879.  
  880.     /*
  881.      * See if the cell is already allocated in the auxillary table.
  882.      */
  883.     for (i = 0; i < auxcellcount; i++) {
  884.         cell = auxtable[i];
  885.         if ((cell->row == row) && (cell->col == col) &&
  886.             (cell->gen == gen))
  887.                 return cell;
  888.     }
  889.  
  890.     /*
  891.      * Need to allocate the cell and add it to the auxillary table.
  892.      */
  893.     cell = allocatecell();
  894.     cell->row = row;
  895.     cell->col = col;
  896.     cell->gen = gen;
  897.  
  898.     auxtable[auxcellcount++] = cell;
  899.  
  900.     return cell;
  901. }
  902.  
  903.  
  904. /*
  905.  * Allocate a new cell.
  906.  * The cell is initialized as if it was a boundary cell.
  907.  * Warning: The first allocation MUST be of the deadcell.
  908.  */
  909. static CELL *
  910. allocatecell()
  911. {
  912.     CELL    *cell;
  913.  
  914.     /*
  915.      * Allocate a new chunk of cells if there are none left.
  916.      */
  917.     if (newcellcount <= 0) {
  918.         newcells = (CELL *) malloc(sizeof(CELL) * ALLOCSIZE);
  919.         if (newcells == NULL) {
  920.             ttyclose();
  921.             fprintf(stderr, "Cannot allocate cell structure\n");
  922.             exit(1);
  923.         }
  924.         newcellcount = ALLOCSIZE;
  925.     }
  926.     newcellcount--;
  927.     cell = newcells++;
  928.  
  929.     /*
  930.      * If this is the first allocation, then make deadcell be this cell.
  931.      */
  932.     if (deadcell == NULL)
  933.         deadcell = cell;
  934.  
  935.     /*
  936.      * Fill in the cell as if it was a boundary cell.
  937.      */
  938.     cell->state = OFF;
  939.     cell->free = FALSE;
  940.     cell->gen = -1;
  941.     cell->row = -1;
  942.     cell->col = -1;
  943.     cell->past = deadcell;
  944.     cell->future = deadcell;
  945.     cell->cul = deadcell;
  946.     cell->cu = deadcell;
  947.     cell->cur = deadcell;
  948.     cell->cl = deadcell;
  949.     cell->cr = deadcell;
  950.     cell->cdl = deadcell;
  951.     cell->cd = deadcell;
  952.     cell->cdr = deadcell;
  953.     cell->csym = deadcell;
  954.  
  955.     return cell;
  956. }
  957.  
  958.  
  959. /*
  960.  * Initialize the implication table.
  961.  */
  962. static void
  963. initimplic()
  964. {
  965.     STATE    state;
  966.     int    OFFcount;
  967.     int    ONcount;
  968.     int    sum;
  969.     int    desc;
  970.     int    i;
  971.  
  972.     for (i = 0; i < NSTATES; i++) {
  973.         state = states[i];
  974.         for (OFFcount = 8; OFFcount >= 0; OFFcount--) {
  975.             for (ONcount = 0; ONcount + OFFcount <= 8; ONcount++) {
  976.                 sum = ONcount + (8 - ONcount - OFFcount) * UNK;
  977.                 desc = sumtodesc(state, sum);
  978.                 implic[desc] =
  979.                     implication(state, OFFcount, ONcount);
  980.             }
  981.         }
  982.     }
  983. }
  984.  
  985.  
  986. /*
  987.  * Initialize the transition table.
  988.  */
  989. static void
  990. inittransit()
  991. {
  992.     int    state;
  993.     int    OFFcount;
  994.     int    ONcount;
  995.     int    sum;
  996.     int    desc;
  997.     int    i;
  998.  
  999.     for (i = 0; i < NSTATES; i++) {
  1000.         state = states[i];
  1001.         for (OFFcount = 8; OFFcount >= 0; OFFcount--) {
  1002.             for (ONcount = 0; ONcount + OFFcount <= 8; ONcount++) {
  1003.                 sum = ONcount + (8 - ONcount - OFFcount) * UNK;
  1004.                 desc = sumtodesc(state, sum);
  1005.                 transit[desc] =
  1006.                     transition(state, OFFcount, ONcount);
  1007.             }
  1008.         }
  1009.     }
  1010. }
  1011.  
  1012.  
  1013. /*
  1014.  * Determine the transition of a cell depending on its known neighbor counts.
  1015.  * The unknown neighbor count is implicit since there are eight neighbors.
  1016.  */
  1017. static STATE
  1018. transition(state, OFFcount, ONcount)
  1019.     STATE        state;
  1020.     unsigned int    OFFcount;
  1021.     unsigned int    ONcount;
  1022. {
  1023.     switch (state) {
  1024.         case OFF:
  1025.             if (OFFcount > 5)
  1026.                 return OFF;
  1027.             if (ONcount > 3)
  1028.                 return OFF;
  1029.             if ((ONcount == 3) && (OFFcount == 5))
  1030.                 return ON;
  1031.             return UNK;
  1032.  
  1033.         case ON:
  1034.             if (ONcount > 3)
  1035.                 return OFF;
  1036.             if (OFFcount > 6)
  1037.                 return OFF;
  1038.             if ((ONcount == 2) &&
  1039.                 ((OFFcount == 5) || (OFFcount == 6)))
  1040.                     return ON;
  1041.             if ((ONcount == 3) && (OFFcount == 5))
  1042.                 return ON;
  1043.             return UNK;
  1044.  
  1045.         case UNK:
  1046.             if (ONcount > 3)
  1047.                 return OFF;
  1048.             if (OFFcount > 6)
  1049.                 return OFF;
  1050.             if ((ONcount == 3) && (OFFcount == 5))
  1051.                 return ON;
  1052.             return UNK;
  1053.  
  1054.         default:
  1055.             return UNK;
  1056.     }
  1057. }
  1058.  
  1059.  
  1060. /*
  1061.  * Determine the implications of a cell depending on its known neighbor counts.
  1062.  * The unknown neighbor count is implicit since there are eight neighbors.
  1063.  */
  1064. static FLAGS
  1065. implication(state, OFFcount, ONcount)
  1066.     STATE        state;
  1067.     unsigned int    OFFcount;
  1068.     unsigned int    ONcount;
  1069. {
  1070.     unsigned int    UNKcount;
  1071.     FLAGS        flags;
  1072.  
  1073.     UNKcount = 8 - OFFcount - ONcount;
  1074.     flags = 0;
  1075.     if (ONcount == 3)
  1076.         flags |= N1ICUN0;
  1077.     if ((ONcount == 3) && (UNKcount == 1))
  1078.         flags |= N0ICUN1;
  1079.  
  1080.     switch (state) {
  1081.         case OFF:
  1082.             if ((ONcount == 2) && (UNKcount == 1))
  1083.                 flags |= N0ICUN0;
  1084.             if (OFFcount == 5)
  1085.                 flags |= N1ICUN1;
  1086.             break;
  1087.  
  1088.         case ON:
  1089.             if (OFFcount == 6)
  1090.                 flags |= N1ICUN1;
  1091.             if ((ONcount == 1) && (UNKcount == 1))
  1092.                 flags |= N0ICUN0;
  1093.             break;
  1094.  
  1095.         case UNK:
  1096.             if (OFFcount == 6)
  1097.                 flags |= (N1ICUN1 | N1IC1);
  1098.             if ((ONcount == 2) && (UNKcount == 0))
  1099.                 flags |= (N0IC0 | N1IC1);
  1100.             break;
  1101.     }
  1102.     if (UNKcount == 0)
  1103.         flags &= ~(N0ICUN0 | N0ICUN1 | N1ICUN0 | N1ICUN1);
  1104.     return flags;
  1105. }
  1106.  
  1107. /* END CODE */
  1108.