src/make-ruletable.cpp

   1                         /*** /
   2
   3 This file is part of Golly, a Game of Life Simulator.
   4 Copyright (C) 2008 Andrew Trevorrow and Tomas Rokicki.
   5
   6 This program is free software; you can redistribute it and/or
   7 modify it under the terms of the GNU General Public License
   8 as published by the Free Software Foundation; either version 2
   9 of the License, or (at your option) any later version.
  10
  11 This program is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with this program; if not, write to the Free Software
  18 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  19
  20  Web site:  http://sourceforge.net/projects/golly
  21  Authors:   rokicki@gmail.com  andrew@trevorrow.com
  22
  23                         / ***/
  24 #include <math.h>
  25 #include <time.h>
  26
  27 #include <iostream>
  28 #include <set>
  29 #include <fstream>
  30 #include <vector>
  31 #include <map>
  32 #include <sstream>
  33 #include <algorithm>
  34 using namespace std;
  35
  36 /*
  37
  38 Makes a rule-table for your transition function.
  39
  40 To compile:
  41 g++ -O5 -o make-ruletable make-ruletable.cpp
  42 or in Microsoft Visual Studio, add to an empty CLR project.
  43
  44 To use:
  45 1) fill slowcalc with your own transition function.
  46 2) set the parameters in main() at the bottom.
  47 3) execute the program from the command line (no options taken)
  48
  49 For a 32-state 5-neighbourhood rule it took 16mins on a 2.2GHz machine.
  50 For a 4-state 9-neighbourhood rule it took 4s.
  51
  52 The merging is very simple - if a transition is compatible with the first rule,
  53 then merge the transition into the rule. If not, try the next rule. If there are
  54 no more rules, add a new rule containing just the transition.
  55
  56 === Worked example: ===
  57 Transitions:
  58 1,0,0->3
  59 1,2,0->3
  60 2,0,0->3
  61 2,2,0->1
  62 Start. First transition taken as first rule:
  63 rule 1: 1,0,0->3
  64 Next transition - is it compatible with rule 1?
  65 i.e. is 1,[0,2],0->3 valid for all permutations? Yes.
  66 rule 1 now: 1,[0,2],0->3
  67 Next transition - is it compatible with rule 1?
  68 i.e. is [1,2],[0,2],0->3 valid for all permutations?
  69 no - because 2,2,0 ->1, not ->3. so add the transition as a new rule:
  70 rule 1 still: 1,[0,2],0 -> 3
  71 rule 2 now : 2,0,0->3
  72 Next transition - is it compatible with rule 1? no - output is different.
  73 Is it compatible with rule 2? no - output is different.
  74 Final output:
  75 1,[0,2],0 -> 3
  76 2,0,0 -> 3
  77 2,2,0 -> 1
  78 Written with variables:
  79 var a={0,2}
  80 1,a,0,3
  81 2,0,0,3
  82 2,2,0,1
  83 ===============
  84
  85 In the function produce_rule_table, the state space is exhaustively traversed.
  86 If your transition function consists of transition rules already then you can
  87 optimise by running through the transitions instead. You might also want to
  88 turn off the optimisation in rule::can_merge, to see if it gives you better
  89 compression.
  90
  91 Also note: I feel sure there are better ways to compress rule tables than this...
  92
  93 Contact: Tim Hutton <tim.hutton@gmail.com>
  94
  95 */
  96
  97 // some typedefs and compile-time constants
  98 typedef unsigned short state;
  99 enum TSymm { none, rotate4, rotate8, reflect, rotate4reflect, rotate8reflect };
 100 static const string symmetry_strings[] = {"none","rotate4","rotate8","reflect","rotate4reflect","rotate8reflect"};
 101
 102 // fill in this function with your desired transition rules
 103 // (for von Neumann neighbourhoods, just ignore the nw,se,sw,ne inputs)
 104 state slowcalc(state nw,state n,state ne,state w,state c,state e,state sw,state s,state se)
 105 {
 106    int neighbours = nw+n+ne+e+se+s+sw+w;
 107    // Conway:
 108    switch (c)
 109    {
 110      case 0:
 111         if (neighbours == 3) {
 112             return 1;
 113         } else {
 114             return 0;
 115         }
 116      case 1:
 117         if (neighbours == 2 || neighbours == 3) {
 118             return 1;
 119         } else {
 120             return 0;
 121         }
 122      default:
 123         return 0 ; // should throw an error here
 124    }
 125 }
 126
 127 vector<state> rotate_inputs(const vector<state>& inputs,int rot)
 128 {
 129    vector<state> rotinp(inputs);
 130    rotate_copy(inputs.begin()+1,inputs.begin()+1+rot,inputs.end(),rotinp.begin()+1);
 131    return rotinp;
 132 }
 133
 134 vector<state> reflect_inputs(const vector<state>& inputs,int neighbourhood_size)
 135 {
 136    vector<state> refinp(inputs);
 137    if(neighbourhood_size==5) // CNESW
 138    {
 139       refinp[2]=inputs[4]; // swap E and W
 140       refinp[4]=inputs[2];
 141    }
 142    else // neighbourhood_size==9 (C,N,NE,E,SE,S,SW,W,NW)
 143    {
 144       refinp[2]=inputs[8];
 145       refinp[8]=inputs[2];
 146       refinp[3]=inputs[7];
 147       refinp[7]=inputs[3];
 148       refinp[4]=inputs[6];
 149       refinp[6]=inputs[4]; // swap all E and W
 150    }
 151    return refinp;
 152 }
 153
 154 // simple rule structure, e.g. 1,2,[4,5],8,2 -> 0
 155 class rule {
 156
 157 public:
 158    set<state> inputs[9]; // c,n,ne,e,se,s,sw,w,nw  or  c,n,e,s,w
 159    state ns; // new state
 160
 161    int n_inputs; // 5: von Neumann; 9: Moore
 162    TSymm symm;
 163
 164 public:
 165    // constructors
 166    rule(const rule& r) : ns(r.ns),n_inputs(r.n_inputs),symm(r.symm)
 167    {
 168       for(int i=0;i<n_inputs;i++)
 169          inputs[i]=r.inputs[i];
 170    }
 171    rule& operator=(const rule& r)
 172    {
 173       n_inputs=r.n_inputs;
 174       symm = r.symm;
 175       ns = r.ns;
 176       for(int i=0;i<n_inputs;i++)
 177          inputs[i]=r.inputs[i];
 178       return *this;
 179    }
 180    rule(const vector<state>& inputs,int n_inputs,state ns1,TSymm symm1)
 181       : ns(ns1),n_inputs(n_inputs),symm(symm1)
 182    {
 183       merge(inputs);
 184    }
 185
 186    // if we merge the rule and the supplied transition, will the rule remain true for all cases?
 187    bool can_merge(const vector<state>& test_inputs,state ns1) const
 188    {
 189       if(ns1!=ns) return false; // can't merge if the outputs are different
 190
 191       // If you are running through your own transitions, or for small state spaces,
 192       // you might want to turn off this optimisation, to get better compression.
 193       // On JvN29 it doesn't make any difference but on Nobili32 it does.
 194       const bool forbid_multiple_input_differences = true;
 195
 196       if(forbid_multiple_input_differences)
 197       {
 198          // optimisation: we skip this rule if more than 2 entries are different, we
 199          // assume we will have considered the relevant one-change rules before this.
 200          int n_different=0;
 201          for(int i=0;i<n_inputs;i++)
 202             if(inputs[i].find(test_inputs[i])==inputs[i].end())
 203                if(++n_different>1)
 204                   return false;
 205          // just check the new permutations
 206          for(int i=0;i<n_inputs;i++)
 207          {
 208             if(inputs[i].find(test_inputs[i])==inputs[i].end())
 209             {
 210                rule r1(*this);
 211                r1.inputs[i].clear(); // (since we don't need to re-test all the other permutations)
 212                r1.inputs[i].insert(test_inputs[i]);
 213                if(!r1.all_true()) return false;
 214             }
 215          }
 216       }
 217       else
 218       {
 219          // need to check all combinations - this can be very slow for large state spaces
 220          for(int i=0;i<n_inputs;i++)
 221          {
 222             if(inputs[i].find(test_inputs[i])==inputs[i].end())
 223             {
 224                rule r1(*this);
 225                r1.merge(test_inputs); // this is what makes it slow, we may introduce many new permutations
 226                r1.inputs[i].clear(); // (since we don't need to re-test all the old permutations)
 227                r1.inputs[i].insert(test_inputs[i]);
 228                if(!r1.all_true()) return false;
 229             }
 230          }
 231       }
 232       return true;
 233    }
 234    // merge the inputs with this rule
 235    void merge(const vector<state>& new_inputs)
 236    {
 237       for(int i=0;i<n_inputs;i++)
 238          inputs[i].insert(new_inputs[i]); // may already exist, set ignores if so
 239    }
 240
 241    // is this set of inputs a match for the rule, for the given symmetry?
 242    bool matches(const vector<state>& test_inputs) const
 243    {
 244       int n_rotations,rotation_skip;
 245       bool do_reflect;
 246       switch(symm)
 247       {
 248          default:
 249          case none: n_rotations=1; rotation_skip=1; do_reflect=false; break;
 250          case rotate4:
 251             if(n_inputs==5)
 252             {
 253                n_rotations=4; rotation_skip=1; do_reflect=false;
 254             }
 255             else
 256             {
 257                n_rotations=4; rotation_skip=2; do_reflect=false;
 258             }
 259             break;
 260          case rotate8: n_rotations=8; rotation_skip=1; do_reflect=false; break;
 261          case reflect: n_rotations=1; rotation_skip=1; do_reflect=true; break;
 262          case rotate4reflect:
 263             if(n_inputs==5)
 264             {
 265                n_rotations=4; rotation_skip=1; do_reflect=true;
 266             }
 267             else
 268             {
 269                n_rotations=4; rotation_skip=2; do_reflect=true;
 270             }
 271             break;
 272          case rotate8reflect: n_rotations=8; rotation_skip=1; do_reflect=true; break;
 273       }
 274       for(int iRot=0;iRot<n_rotations;iRot++)
 275       {
 276          if(nosymm_matches(rotate_inputs(test_inputs,iRot*rotation_skip)))
 277             return true;
 278          if(do_reflect && nosymm_matches(reflect_inputs(rotate_inputs(test_inputs,iRot*rotation_skip),n_inputs)))
 279             return true;
 280       }
 281       return false; // no match found
 282    }
 283
 284 protected:
 285
 286    // ignoring symmetry, does this set of inputs match the rule?
 287    bool nosymm_matches(const vector<state>& test_inputs) const
 288    {
 289       for(int i=0;i<n_inputs;i++)
 290          if(inputs[i].find(test_inputs[i])==inputs[i].end())
 291             return false;
 292       return true;
 293    }
 294
 295    // is the rule true in all permutations?
 296    bool all_true() const
 297    {
 298       set<state>::const_iterator c_it,n_it,ne_it,e_it,se_it,s_it,sw_it,w_it,nw_it;
 299       if(n_inputs==9)
 300       {
 301          for(c_it = inputs[0].begin();c_it!=inputs[0].end();c_it++)
 302             for(n_it = inputs[1].begin();n_it!=inputs[1].end();n_it++)
 303                for(ne_it = inputs[2].begin();ne_it!=inputs[2].end();ne_it++)
 304                   for(e_it = inputs[3].begin();e_it!=inputs[3].end();e_it++)
 305                      for(se_it = inputs[4].begin();se_it!=inputs[4].end();se_it++)
 306                         for(s_it = inputs[5].begin();s_it!=inputs[5].end();s_it++)
 307                            for(sw_it = inputs[6].begin();sw_it!=inputs[6].end();sw_it++)
 308                               for(w_it = inputs[7].begin();w_it!=inputs[7].end();w_it++)
 309                                  for(nw_it = inputs[8].begin();nw_it!=inputs[8].end();nw_it++)
 310                                     if(slowcalc(*nw_it,*n_it,*ne_it,*w_it,*c_it,*e_it,*sw_it,*s_it,*se_it)!=ns)
 311                                        return false;
 312       }
 313       else
 314       {
 315          for(c_it = inputs[0].begin();c_it!=inputs[0].end();c_it++)
 316             for(n_it = inputs[1].begin();n_it!=inputs[1].end();n_it++)
 317                for(e_it = inputs[2].begin();e_it!=inputs[2].end();e_it++)
 318                   for(s_it = inputs[3].begin();s_it!=inputs[3].end();s_it++)
 319                      for(w_it = inputs[4].begin();w_it!=inputs[4].end();w_it++)
 320                         if(slowcalc(0,*n_it,0,*w_it,*c_it,*e_it,0,*s_it,0)!=ns)
 321                            return false;
 322       }
 323       return true;
 324    }
 325 };
 326
 327 // makes a unique variable name for a given value
 328 string get_variable_name(unsigned int iVar)
 329 {
 330    const char VARS[52]={'a','b','c','d','e','f','g','h','i','j',
 331       'k','l','m','n','o','p','q','r','s','t','u','v','w','x',
 332       'y','z','A','B','C','D','E','F','G','H','I','J','K','L',
 333       'M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
 334    ostringstream oss;
 335    if(iVar<52)
 336       oss << VARS[iVar];
 337    else if(iVar<52*52)
 338       oss << VARS[(iVar-(iVar%52))/52 - 1] << VARS[iVar%52];
 339    else
 340       oss << "!"; // we have a 52*52 limit ("should be enough for anyone")
 341    return oss.str();
 342 }
 343
 344 void print_rules(const vector<rule>& rules,ostream& out)
 345 {
 346    // first collect all variables (makes reading easier)
 347    map< string , set<state> > vars;
 348    ostringstream rules_out;
 349    for(vector<rule>::const_iterator r_it=rules.begin();r_it!=rules.end();r_it++)
 350    {
 351       vector<string> variables_used;
 352       for(int i=0;i<r_it->n_inputs;i++)
 353       {
 354          // if more than one state for this input, we need a variable
 355          if(r_it->inputs[i].size()>1)
 356          {
 357             string var;
 358             // is there a variable that matches these inputs, and that we haven't used?
 359             bool found_unused_var=false;
 360             for(map<string, set<state> >::const_iterator v_it=vars.begin();v_it!=vars.end();v_it++)
 361             {
 362                if(v_it->second==r_it->inputs[i] && find(variables_used.begin(),variables_used.end(),v_it->first)==variables_used.end())
 363                {
 364                   found_unused_var = true;
 365                   var = v_it->first;
 366                   break;
 367                }
 368             }
 369             if(!found_unused_var)
 370             {
 371                // we need to make a new one for this set of inputs
 372                var = get_variable_name(vars.size());
 373                // add it to the list of made variables
 374                vars[var] = r_it->inputs[i];
 375                // print it
 376                out << "var " << var << "={";
 377                set<state>::const_iterator it=r_it->inputs[i].begin();
 378                while(true)
 379                {
 380                   out << (int)*it;
 381                   it++;
 382                   if(it!=r_it->inputs[i].end()) out << ",";
 383                   else break;
 384                }
 385                out << "}\n";
 386             }
 387             // add the variable to the list of used ones
 388             variables_used.push_back(var);
 389             rules_out << var << ",";
 390          }
 391          else
 392          {
 393             // just a state, output it
 394             rules_out << (int)*r_it->inputs[i].begin() << ",";
 395          }
 396       }
 397       rules_out << (int)r_it->ns << endl;
 398    }
 399    out << rules_out.str();
 400 }
 401
 402 void produce_rule_table(vector<rule>& rules,int N,int nhood_size,TSymm symm,bool remove_stasis)
 403 {
 404    int n_rotations,rotation_skip;
 405    bool do_reflect;
 406    switch(symm)
 407    {
 408       default:
 409       case none: n_rotations=1; rotation_skip=1; do_reflect=false; break;
 410       case rotate4:
 411          if(nhood_size==5)
 412          {
 413             n_rotations=4; rotation_skip=1; do_reflect=false;
 414          }
 415          else
 416          {
 417             n_rotations=4; rotation_skip=2; do_reflect=false;
 418          }
 419          break;
 420       case rotate8: n_rotations=8; rotation_skip=1; do_reflect=false; break;
 421       case reflect: n_rotations=1; rotation_skip=1; do_reflect=true; break;
 422       case rotate4reflect:
 423          if(nhood_size==5)
 424          {
 425             n_rotations=4; rotation_skip=1; do_reflect=true;
 426          }
 427          else
 428          {
 429             n_rotations=4; rotation_skip=2; do_reflect=true;
 430          }
 431          break;
 432       case rotate8reflect: n_rotations=8; rotation_skip=1; do_reflect=true; break;
 433    }
 434
 435    state c,n,ne,nw,sw,s,se,e,w,ns;
 436    vector<rule>::iterator it;
 437    bool merged;
 438    for(c=0;c<N;c++)
 439    {
 440       cout << "\nProcessing for c=" << (int)c << ", " << rules.size() << " rules so far." << endl;
 441
 442       if(nhood_size==9)
 443       {
 444          vector<state> inputs(9);
 445          inputs[0]=c;
 446          for(n=0;n<N;n++)
 447          {
 448             cout << ".";
 449             cout.flush();
 450             inputs[1]=n;
 451             for(ne=0;ne<N;ne++)
 452             {
 453                inputs[2]=ne;
 454                for(e=0;e<N;e++)
 455                {
 456                   inputs[3]=e;
 457                   for(se=0;se<N;se++)
 458                   {
 459                      inputs[4]=se;
 460                      for(s=0;s<N;s++)
 461                      {
 462                         inputs[5]=s;
 463                         for(sw=0;sw<N;sw++)
 464                         {
 465                            inputs[6]=sw;
 466                            for(w=0;w<N;w++)
 467                            {
 468                               inputs[7]=w;
 469                               for(nw=0;nw<N;nw++)
 470                               {
 471                                  ns = slowcalc(nw,n,ne,w,c,e,sw,s,se);
 472                                  if(remove_stasis && ns == c)
 473                                     continue; // we can ignore stasis transitions
 474                                  // can we merge this transition with any existing rule?
 475                                  inputs[8]=nw;
 476                                  merged = false;
 477                                  for(it=rules.begin();!merged && it!=rules.end();it++)
 478                                  {
 479                                     rule &r = *it;
 480                                     for(int iRot=0;!merged && iRot<n_rotations;iRot++)
 481                                     {
 482                                        if(r.can_merge(rotate_inputs(inputs,iRot*rotation_skip),ns))
 483                                        {
 484                                           r.merge(rotate_inputs(inputs,iRot*rotation_skip));
 485                                           merged = true;
 486                                        }
 487                                        else if(do_reflect && r.can_merge(reflect_inputs(rotate_inputs(inputs,iRot*rotation_skip),nhood_size),ns))
 488                                        {
 489                                           r.merge(reflect_inputs(rotate_inputs(inputs,iRot*rotation_skip),nhood_size));
 490                                           merged = true;
 491                                        }
 492                                     }
 493                                  }
 494                                  if(!merged)
 495                                  {
 496                                     // need to make a new rule starting with this transition
 497                                     rule r(inputs,nhood_size,ns,symm);
 498                                     rules.push_back(r);
 499                                  }
 500                               }
 501                            }
 502                         }
 503                      }
 504                   }
 505                }
 506             }
 507          }
 508       }
 509       else // nhood_size==5
 510       {
 511          vector<state> inputs(5);
 512          inputs[0]=c;
 513          for(n=0;n<N;n++)
 514          {
 515             cout << ".";
 516             cout.flush();
 517             inputs[1]=n;
 518             for(e=0;e<N;e++)
 519             {
 520                inputs[2]=e;
 521                for(s=0;s<N;s++)
 522                {
 523                   inputs[3]=s;
 524                   for(w=0;w<N;w++)
 525                   {
 526                      ns = slowcalc(0,n,0,w,c,e,0,s,0);
 527                      if(remove_stasis && ns == c)
 528                         continue; // we can ignore stasis transitions
 529
 530                      // can we merge this transition with any existing rule?
 531                      inputs[4]=w;
 532                      merged = false;
 533                      for(it=rules.begin();!merged && it!=rules.end();it++)
 534                      {
 535                         rule &r = *it;
 536                         for(int iRot=0;!merged && iRot<n_rotations;iRot++)
 537                         {
 538                            if(r.can_merge(rotate_inputs(inputs,iRot*rotation_skip),ns))
 539                            {
 540                               r.merge(rotate_inputs(inputs,iRot*rotation_skip));
 541                               merged = true;
 542                            }
 543                            else if(do_reflect && r.can_merge(reflect_inputs(rotate_inputs(inputs,iRot*rotation_skip),nhood_size),ns))
 544                            {
 545                               r.merge(reflect_inputs(rotate_inputs(inputs,iRot*rotation_skip),nhood_size));
 546                               merged = true;
 547                            }
 548                         }
 549                      }
 550                      if(!merged)
 551                      {
 552                         // need to make a new rule starting with this transition
 553                         rule r(inputs,nhood_size,ns,symm);
 554                         rules.push_back(r);
 555                      }
 556                   }
 557                }
 558             }
 559          }
 560       }
 561    }
 562 }
 563
 564 // here we use the computed rule table as a replacement slowcalc, for checking correctness
 565 state new_slowcalc(const vector<rule>& rules,const vector<state>& inputs)
 566 {
 567    for(vector<rule>::const_iterator it=rules.begin();it!=rules.end();it++)
 568       if(it->matches(inputs))
 569          return it->ns;
 570     return inputs[0]; // default: no change
 571 }
 572
 573 bool is_correct(const vector<rule>&rules,int N,int neighbourhood_size)
 574 {
 575    // exhaustive check
 576    state c,n,ne,nw,sw,s,se,e,w;
 577    if(neighbourhood_size==9)
 578    {
 579       vector<state> inputs(9);
 580       for(c=0;c<N;c++)
 581       {
 582          inputs[0]=c;
 583          for(n=0;n<N;n++)
 584          {
 585             inputs[1]=n;
 586             for(ne=0;ne<N;ne++)
 587             {
 588                inputs[2]=ne;
 589                for(e=0;e<N;e++)
 590                {
 591                   inputs[3]=e;
 592                   for(se=0;se<N;se++)
 593                   {
 594                      inputs[4]=se;
 595                      for(s=0;s<N;s++)
 596                      {
 597                         inputs[5]=s;
 598                         for(sw=0;sw<N;sw++)
 599                         {
 600                            inputs[6]=sw;
 601                            for(w=0;w<N;w++)
 602                            {
 603                               inputs[7]=w;
 604                               for(nw=0;nw<N;nw++)
 605                               {
 606                                  inputs[8]=nw;
 607                                  if(new_slowcalc(rules,inputs)
 608                                     != slowcalc(nw,n,ne,w,c,e,sw,s,se))
 609                                        return false;
 610                               }
 611                            }
 612                         }
 613                      }
 614                   }
 615                }
 616             }
 617          }
 618       }
 619    }
 620    else
 621    {
 622       vector<state> inputs(5);
 623       for(c=0;c<N;c++)
 624       {
 625          inputs[0]=c;
 626          for(n=0;n<N;n++)
 627          {
 628             inputs[1]=n;
 629             for(e=0;e<N;e++)
 630             {
 631                inputs[2]=e;
 632                for(s=0;s<N;s++)
 633                {
 634                   inputs[3]=s;
 635                   for(w=0;w<N;w++)
 636                   {
 637                      inputs[4]=w;
 638                      if(new_slowcalc(rules,inputs)
 639                         != slowcalc(0,n,0,w,c,e,0,s,0))
 640                         return false;
 641                   }
 642                }
 643             }
 644          }
 645       }
 646    }
 647    return true;
 648 }
 649
 650 int main()
 651 {
 652    // parameters for use:
 653    const int N_STATES = 2;
 654    const TSymm symmetry = none;
 655    const int nhood_size = 9;
 656    const string output_filename = "life.table";
 657    const bool remove_stasis_transitions = false;
 658
 659    vector<rule> rules;
 660    time_t t1,t2;
 661    time(&t1);
 662    produce_rule_table(rules,N_STATES,nhood_size,symmetry,remove_stasis_transitions);
 663    time(&t2);
 664    int n_secs = (int)difftime(t2,t1);
 665    cout << "\nProcessing took: " << n_secs << " seconds." << endl;
 666
 667    {
 668       ofstream out(output_filename.c_str());
 669       out << "# rules: " << rules.size() << "\n#";
 670       out << "\n# Golly rule-table format.\n# Each rule: C,";
 671       if(nhood_size==5)
 672          out << "N,E,S,W";
 673       else
 674          out << "N,NE,E,SE,S,SW,W,NW";
 675       out << ",C'";
 676       out << "\n# N.B. Where the same variable appears multiple times in a transition,\n# it takes the same value each time.\n#";
 677       if(remove_stasis_transitions)
 678          out << "\n# Default for transitions not listed: no change\n#";
 679       else
 680          out << "\n# All transitions should be included below, including no-change ones.\n#";
 681       out << "\nn_states:" << N_STATES;
 682       out << "\nneighborhood:" << ((nhood_size==5)?("vonNeumann"):("Moore"));
 683       out << "\nsymmetries:" << symmetry_strings[symmetry] << "\n";
 684       print_rules(rules,out);
 685    }
 686    cout << rules.size() << " rules written." << endl;
 687
 688    // optional: run through the entire state space, checking that new_slowcalc matches slowcalc
 689    cout << "Verifying is correct (can abort if you're confident)...";
 690    cout.flush();
 691    if(is_correct(rules,N_STATES,nhood_size))
 692       cout << "yes." << endl;
 693    else
 694       cout << "no! Either there's a bug in the code, or the transition function does not have the symmetry you selected." << endl;
 695 }