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    // wireworld:
 107    switch (c)
 108    {
 109      case 0: return 0 ;
 110      case 1: return 2 ;
 111      case 2: return 3 ;
 112      case 3:
 113         if ((((1+(nw==1)+(n==1)+(ne==1)+(w==1)+(e==1)+(sw==1)+
 114            (s==1)+(se==1))) | 1) == 3)
 115            return 1 ;
 116         else
 117            return 3 ;
 118      default:
 119         return 0 ; // should throw an error here
 120    }
 121 }
 122
 123 vector<state> rotate_inputs(const vector<state>& inputs,int rot)
 124 {
 125    vector<state> rotinp(inputs);
 126    rotate_copy(inputs.begin()+1,inputs.begin()+1+rot,inputs.end(),rotinp.begin()+1);
 127    return rotinp;
 128 }
 129
 130 vector<state> reflect_inputs(const vector<state>& inputs,int neighbourhood_size)
 131 {
 132    vector<state> refinp(inputs);
 133    if(neighbourhood_size==5) // CNESW
 134    {
 135       refinp[2]=inputs[4]; // swap E and W
 136       refinp[4]=inputs[2];
 137    }
 138    else // neighbourhood_size==9 (C,N,NE,E,SE,S,SW,W,NW)
 139    {
 140       refinp[2]=inputs[8];
 141       refinp[8]=inputs[2];
 142       refinp[3]=inputs[7];
 143       refinp[7]=inputs[3];
 144       refinp[4]=inputs[6];
 145       refinp[6]=inputs[4]; // swap all E and W
 146    }
 147    return refinp;
 148 }
 149
 150 // simple rule structure, e.g. 1,2,[4,5],8,2 -> 0
 151 class rule {
 152
 153 public:
 154    set<state> inputs[9]; // c,n,ne,e,se,s,sw,w,nw  or  c,n,e,s,w
 155    state ns; // new state
 156
 157    int n_inputs; // 5: von Neumann; 9: Moore
 158    TSymm symm;
 159
 160 public:
 161    // constructors
 162    rule(const rule& r) : ns(r.ns),n_inputs(r.n_inputs),symm(r.symm)
 163    {
 164       for(int i=0;i<n_inputs;i++)
 165          inputs[i]=r.inputs[i];
 166    }
 167    rule& operator=(const rule& r)
 168    {
 169       n_inputs=r.n_inputs;
 170       symm = r.symm;
 171       ns = r.ns;
 172       for(int i=0;i<n_inputs;i++)
 173          inputs[i]=r.inputs[i];
 174       return *this;
 175    }
 176    rule(const vector<state>& inputs,int n_inputs,state ns1,TSymm symm1)
 177       : ns(ns1),n_inputs(n_inputs),symm(symm1)
 178    {
 179       merge(inputs);
 180    }
 181
 182    // if we merge the rule and the supplied transition, will the rule remain true for all cases?
 183    bool can_merge(const vector<state>& test_inputs,state ns1) const
 184    {
 185       if(ns1!=ns) return false; // can't merge if the outputs are different
 186
 187       // If you are running through your own transitions, or for small state spaces,
 188       // you might want to turn off this optimisation, to get better compression.
 189       // On JvN29 it doesn't make any difference but on Nobili32 it does.
 190       const bool forbid_multiple_input_differences = true;
 191
 192       if(forbid_multiple_input_differences)
 193       {
 194          // optimisation: we skip this rule if more than 2 entries are different, we
 195          // assume we will have considered the relevant one-change rules before this.
 196          int n_different=0;
 197          for(int i=0;i<n_inputs;i++)
 198             if(inputs[i].find(test_inputs[i])==inputs[i].end())
 199                if(++n_different>1)
 200                   return false;
 201          // just check the new permutations
 202          for(int i=0;i<n_inputs;i++)
 203          {
 204             if(inputs[i].find(test_inputs[i])==inputs[i].end())
 205             {
 206                rule r1(*this);
 207                r1.inputs[i].clear(); // (since we don't need to re-test all the other permutations)
 208                r1.inputs[i].insert(test_inputs[i]);
 209                if(!r1.all_true()) return false;
 210             }
 211          }
 212       }
 213       else
 214       {
 215          // need to check all combinations - this can be very slow for large state spaces
 216          for(int i=0;i<n_inputs;i++)
 217          {
 218             if(inputs[i].find(test_inputs[i])==inputs[i].end())
 219             {
 220                rule r1(*this);
 221                r1.merge(test_inputs); // this is what makes it slow, we may introduce many new permutations
 222                r1.inputs[i].clear(); // (since we don't need to re-test all the old permutations)
 223                r1.inputs[i].insert(test_inputs[i]);
 224                if(!r1.all_true()) return false;
 225             }
 226          }
 227       }
 228       return true;
 229    }
 230    // merge the inputs with this rule
 231    void merge(const vector<state>& new_inputs)
 232    {
 233       for(int i=0;i<n_inputs;i++)
 234          inputs[i].insert(new_inputs[i]); // may already exist, set ignores if so
 235    }
 236
 237    // is this set of inputs a match for the rule, for the given symmetry?
 238    bool matches(const vector<state>& test_inputs) const
 239    {
 240       int n_rotations,rotation_skip;
 241       bool do_reflect;
 242       switch(symm)
 243       {
 244          default:
 245          case none: n_rotations=1; rotation_skip=1; do_reflect=false; break;
 246          case rotate4:
 247             if(n_inputs==5)
 248             {
 249                n_rotations=4; rotation_skip=1; do_reflect=false;
 250             }
 251             else
 252             {
 253                n_rotations=4; rotation_skip=2; do_reflect=false;
 254             }
 255             break;
 256          case rotate8: n_rotations=8; rotation_skip=1; do_reflect=false; break;
 257          case reflect: n_rotations=1; rotation_skip=1; do_reflect=true; break;
 258          case rotate4reflect:
 259             if(n_inputs==5)
 260             {
 261                n_rotations=4; rotation_skip=1; do_reflect=true;
 262             }
 263             else
 264             {
 265                n_rotations=4; rotation_skip=2; do_reflect=true;
 266             }
 267             break;
 268          case rotate8reflect: n_rotations=8; rotation_skip=1; do_reflect=true; break;
 269       }
 270       for(int iRot=0;iRot<n_rotations;iRot++)
 271       {
 272          if(nosymm_matches(rotate_inputs(test_inputs,iRot*rotation_skip)))
 273             return true;
 274          if(do_reflect && nosymm_matches(reflect_inputs(rotate_inputs(test_inputs,iRot*rotation_skip),n_inputs)))
 275             return true;
 276       }
 277       return false; // no match found
 278    }
 279
 280 protected:
 281
 282    // ignoring symmetry, does this set of inputs match the rule?
 283    bool nosymm_matches(const vector<state>& test_inputs) const
 284    {
 285       for(int i=0;i<n_inputs;i++)
 286          if(inputs[i].find(test_inputs[i])==inputs[i].end())
 287             return false;
 288       return true;
 289    }
 290
 291    // is the rule true in all permutations?
 292    bool all_true() const
 293    {
 294       set<state>::const_iterator c_it,n_it,ne_it,e_it,se_it,s_it,sw_it,w_it,nw_it;
 295       if(n_inputs==9)
 296       {
 297          for(c_it = inputs[0].begin();c_it!=inputs[0].end();c_it++)
 298             for(n_it = inputs[1].begin();n_it!=inputs[1].end();n_it++)
 299                for(ne_it = inputs[2].begin();ne_it!=inputs[2].end();ne_it++)
 300                   for(e_it = inputs[3].begin();e_it!=inputs[3].end();e_it++)
 301                      for(se_it = inputs[4].begin();se_it!=inputs[4].end();se_it++)
 302                         for(s_it = inputs[5].begin();s_it!=inputs[5].end();s_it++)
 303                            for(sw_it = inputs[6].begin();sw_it!=inputs[6].end();sw_it++)
 304                               for(w_it = inputs[7].begin();w_it!=inputs[7].end();w_it++)
 305                                  for(nw_it = inputs[8].begin();nw_it!=inputs[8].end();nw_it++)
 306                                     if(slowcalc(*nw_it,*n_it,*ne_it,*w_it,*c_it,*e_it,*sw_it,*s_it,*se_it)!=ns)
 307                                        return false;
 308       }
 309       else
 310       {
 311          for(c_it = inputs[0].begin();c_it!=inputs[0].end();c_it++)
 312             for(n_it = inputs[1].begin();n_it!=inputs[1].end();n_it++)
 313                for(e_it = inputs[2].begin();e_it!=inputs[2].end();e_it++)
 314                   for(s_it = inputs[3].begin();s_it!=inputs[3].end();s_it++)
 315                      for(w_it = inputs[4].begin();w_it!=inputs[4].end();w_it++)
 316                         if(slowcalc(0,*n_it,0,*w_it,*c_it,*e_it,0,*s_it,0)!=ns)
 317                            return false;
 318       }
 319       return true;
 320    }
 321 };
 322
 323 // makes a unique variable name for a given value
 324 string get_variable_name(unsigned int iVar)
 325 {
 326    const char VARS[52]={'a','b','c','d','e','f','g','h','i','j',
 327       'k','l','m','n','o','p','q','r','s','t','u','v','w','x',
 328       'y','z','A','B','C','D','E','F','G','H','I','J','K','L',
 329       'M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
 330    ostringstream oss;
 331    if(iVar<52)
 332       oss << VARS[iVar];
 333    else if(iVar<52*52)
 334       oss << VARS[(iVar-(iVar%52))/52 - 1] << VARS[iVar%52];
 335    else
 336       oss << "!"; // we have a 52*52 limit ("should be enough for anyone")
 337    return oss.str();
 338 }
 339
 340 void print_rules(const vector<rule>& rules,ostream& out)
 341 {
 342    // first collect all variables (makes reading easier)
 343    map< string , set<state> > vars;
 344    ostringstream rules_out;
 345    for(vector<rule>::const_iterator r_it=rules.begin();r_it!=rules.end();r_it++)
 346    {
 347       vector<string> variables_used;
 348       for(int i=0;i<r_it->n_inputs;i++)
 349       {
 350          // if more than one state for this input, we need a variable
 351          if(r_it->inputs[i].size()>1)
 352          {
 353             string var;
 354             // is there a variable that matches these inputs, and that we haven't used?
 355             bool found_unused_var=false;
 356             for(map<string, set<state> >::const_iterator v_it=vars.begin();v_it!=vars.end();v_it++)
 357             {
 358                if(v_it->second==r_it->inputs[i] && find(variables_used.begin(),variables_used.end(),v_it->first)==variables_used.end())
 359                {
 360                   found_unused_var = true;
 361                   var = v_it->first;
 362                   break;
 363                }
 364             }
 365             if(!found_unused_var)
 366             {
 367                // we need to make a new one for this set of inputs
 368                var = get_variable_name(vars.size());
 369                // add it to the list of made variables
 370                vars[var] = r_it->inputs[i];
 371                // print it
 372                out << "var " << var << "={";
 373                set<state>::const_iterator it=r_it->inputs[i].begin();
 374                while(true)
 375                {
 376                   out << (int)*it;
 377                   it++;
 378                   if(it!=r_it->inputs[i].end()) out << ",";
 379                   else break;
 380                }
 381                out << "}\n";
 382             }
 383             // add the variable to the list of used ones
 384             variables_used.push_back(var);
 385             rules_out << var << ",";
 386          }
 387          else
 388          {
 389             // just a state, output it
 390             rules_out << (int)*r_it->inputs[i].begin() << ",";
 391          }
 392       }
 393       rules_out << (int)r_it->ns << endl;
 394    }
 395    out << rules_out.str();
 396 }
 397
 398 void produce_rule_table(vector<rule>& rules,int N,int nhood_size,TSymm symm,bool remove_stasis)
 399 {
 400    int n_rotations,rotation_skip;
 401    bool do_reflect;
 402    switch(symm)
 403    {
 404       default:
 405       case none: n_rotations=1; rotation_skip=1; do_reflect=false; break;
 406       case rotate4:
 407          if(nhood_size==5)
 408          {
 409             n_rotations=4; rotation_skip=1; do_reflect=false;
 410          }
 411          else
 412          {
 413             n_rotations=4; rotation_skip=2; do_reflect=false;
 414          }
 415          break;
 416       case rotate8: n_rotations=8; rotation_skip=1; do_reflect=false; break;
 417       case reflect: n_rotations=1; rotation_skip=1; do_reflect=true; break;
 418       case rotate4reflect:
 419          if(nhood_size==5)
 420          {
 421             n_rotations=4; rotation_skip=1; do_reflect=true;
 422          }
 423          else
 424          {
 425             n_rotations=4; rotation_skip=2; do_reflect=true;
 426          }
 427          break;
 428       case rotate8reflect: n_rotations=8; rotation_skip=1; do_reflect=true; break;
 429    }
 430
 431    state c,n,ne,nw,sw,s,se,e,w,ns;
 432    vector<rule>::iterator it;
 433    bool merged;
 434    for(c=0;c<N;c++)
 435    {
 436       cout << "\nProcessing for c=" << (int)c << ", " << rules.size() << " rules so far." << endl;
 437
 438       if(nhood_size==9)
 439       {
 440          vector<state> inputs(9);
 441          inputs[0]=c;
 442          for(n=0;n<N;n++)
 443          {
 444             cout << ".";
 445             cout.flush();
 446             inputs[1]=n;
 447             for(ne=0;ne<N;ne++)
 448             {
 449                inputs[2]=ne;
 450                for(e=0;e<N;e++)
 451                {
 452                   inputs[3]=e;
 453                   for(se=0;se<N;se++)
 454                   {
 455                      inputs[4]=se;
 456                      for(s=0;s<N;s++)
 457                      {
 458                         inputs[5]=s;
 459                         for(sw=0;sw<N;sw++)
 460                         {
 461                            inputs[6]=sw;
 462                            for(w=0;w<N;w++)
 463                            {
 464                               inputs[7]=w;
 465                               for(nw=0;nw<N;nw++)
 466                               {
 467                                  ns = slowcalc(nw,n,ne,w,c,e,sw,s,se);
 468                                  if(remove_stasis && ns == c)
 469                                     continue; // we can ignore stasis transitions
 470                                  // can we merge this transition with any existing rule?
 471                                  inputs[8]=nw;
 472                                  merged = false;
 473                                  for(it=rules.begin();!merged && it!=rules.end();it++)
 474                                  {
 475                                     rule &r = *it;
 476                                     for(int iRot=0;!merged && iRot<n_rotations;iRot++)
 477                                     {
 478                                        if(r.can_merge(rotate_inputs(inputs,iRot*rotation_skip),ns))
 479                                        {
 480                                           r.merge(rotate_inputs(inputs,iRot*rotation_skip));
 481                                           merged = true;
 482                                        }
 483                                        else if(do_reflect && r.can_merge(reflect_inputs(rotate_inputs(inputs,iRot*rotation_skip),nhood_size),ns))
 484                                        {
 485                                           r.merge(reflect_inputs(rotate_inputs(inputs,iRot*rotation_skip),nhood_size));
 486                                           merged = true;
 487                                        }
 488                                     }
 489                                  }
 490                                  if(!merged)
 491                                  {
 492                                     // need to make a new rule starting with this transition
 493                                     rule r(inputs,nhood_size,ns,symm);
 494                                     rules.push_back(r);
 495                                  }
 496                               }
 497                            }
 498                         }
 499                      }
 500                   }
 501                }
 502             }
 503          }
 504       }
 505       else // nhood_size==5
 506       {
 507          vector<state> inputs(5);
 508          inputs[0]=c;
 509          for(n=0;n<N;n++)
 510          {
 511             cout << ".";
 512             cout.flush();
 513             inputs[1]=n;
 514             for(e=0;e<N;e++)
 515             {
 516                inputs[2]=e;
 517                for(s=0;s<N;s++)
 518                {
 519                   inputs[3]=s;
 520                   for(w=0;w<N;w++)
 521                   {
 522                      ns = slowcalc(0,n,0,w,c,e,0,s,0);
 523                      if(remove_stasis && ns == c)
 524                         continue; // we can ignore stasis transitions
 525
 526                      // can we merge this transition with any existing rule?
 527                      inputs[4]=w;
 528                      merged = false;
 529                      for(it=rules.begin();!merged && it!=rules.end();it++)
 530                      {
 531                         rule &r = *it;
 532                         for(int iRot=0;!merged && iRot<n_rotations;iRot++)
 533                         {
 534                            if(r.can_merge(rotate_inputs(inputs,iRot*rotation_skip),ns))
 535                            {
 536                               r.merge(rotate_inputs(inputs,iRot*rotation_skip));
 537                               merged = true;
 538                            }
 539                            else if(do_reflect && r.can_merge(reflect_inputs(rotate_inputs(inputs,iRot*rotation_skip),nhood_size),ns))
 540                            {
 541                               r.merge(reflect_inputs(rotate_inputs(inputs,iRot*rotation_skip),nhood_size));
 542                               merged = true;
 543                            }
 544                         }
 545                      }
 546                      if(!merged)
 547                      {
 548                         // need to make a new rule starting with this transition
 549                         rule r(inputs,nhood_size,ns,symm);
 550                         rules.push_back(r);
 551                      }
 552                   }
 553                }
 554             }
 555          }
 556       }
 557    }
 558 }
 559
 560 // here we use the computed rule table as a replacement slowcalc, for checking correctness
 561 state new_slowcalc(const vector<rule>& rules,const vector<state>& inputs)
 562 {
 563    for(vector<rule>::const_iterator it=rules.begin();it!=rules.end();it++)
 564       if(it->matches(inputs))
 565          return it->ns;
 566     return inputs[0]; // default: no change
 567 }
 568
 569 bool is_correct(const vector<rule>&rules,int N,int neighbourhood_size)
 570 {
 571    // exhaustive check
 572    state c,n,ne,nw,sw,s,se,e,w;
 573    if(neighbourhood_size==9)
 574    {
 575       vector<state> inputs(9);
 576       for(c=0;c<N;c++)
 577       {
 578          inputs[0]=c;
 579          for(n=0;n<N;n++)
 580          {
 581             inputs[1]=n;
 582             for(ne=0;ne<N;ne++)
 583             {
 584                inputs[2]=ne;
 585                for(e=0;e<N;e++)
 586                {
 587                   inputs[3]=e;
 588                   for(se=0;se<N;se++)
 589                   {
 590                      inputs[4]=se;
 591                      for(s=0;s<N;s++)
 592                      {
 593                         inputs[5]=s;
 594                         for(sw=0;sw<N;sw++)
 595                         {
 596                            inputs[6]=sw;
 597                            for(w=0;w<N;w++)
 598                            {
 599                               inputs[7]=w;
 600                               for(nw=0;nw<N;nw++)
 601                               {
 602                                  inputs[8]=nw;
 603                                  if(new_slowcalc(rules,inputs)
 604                                     != slowcalc(nw,n,ne,w,c,e,sw,s,se))
 605                                        return false;
 606                               }
 607                            }
 608                         }
 609                      }
 610                   }
 611                }
 612             }
 613          }
 614       }
 615    }
 616    else
 617    {
 618       vector<state> inputs(5);
 619       for(c=0;c<N;c++)
 620       {
 621          inputs[0]=c;
 622          for(n=0;n<N;n++)
 623          {
 624             inputs[1]=n;
 625             for(e=0;e<N;e++)
 626             {
 627                inputs[2]=e;
 628                for(s=0;s<N;s++)
 629                {
 630                   inputs[3]=s;
 631                   for(w=0;w<N;w++)
 632                   {
 633                      inputs[4]=w;
 634                      if(new_slowcalc(rules,inputs)
 635                         != slowcalc(0,n,0,w,c,e,0,s,0))
 636                         return false;
 637                   }
 638                }
 639             }
 640          }
 641       }
 642    }
 643    return true;
 644 }
 645
 646 int main()
 647 {
 648    // parameters for use:
 649    const int N_STATES = 4;
 650    const TSymm symmetry = rotate8;
 651    const int nhood_size = 9;
 652    const string output_filename = "wireworld.table";
 653    const bool remove_stasis_transitions = true;
 654
 655    vector<rule> rules;
 656    time_t t1,t2;
 657    time(&t1);
 658    produce_rule_table(rules,N_STATES,nhood_size,symmetry,remove_stasis_transitions);
 659    time(&t2);
 660    int n_secs = (int)difftime(t2,t1);
 661    cout << "\nProcessing took: " << n_secs << " seconds." << endl;
 662
 663    {
 664       ofstream out(output_filename.c_str());
 665       out << "# rules: " << rules.size() << "\n#";
 666       out << "\n# Golly rule-table format.\n# Each rule: C,";
 667       if(nhood_size==5)
 668          out << "N,E,S,W";
 669       else
 670          out << "N,NE,E,SE,S,SW,W,NW";
 671       out << ",C'";
 672       out << "\n# N.B. Where the same variable appears multiple times in a transition,\n# it takes the same value each time.\n#";
 673       if(remove_stasis_transitions)
 674          out << "\n# Default for transitions not listed: no change\n#";
 675       else
 676          out << "\n# All transitions should be included below, including no-change ones.\n#";
 677       out << "\nn_states:" << N_STATES;
 678       out << "\nneighborhood:" << ((nhood_size==5)?("vonNeumann"):("Moore"));
 679       out << "\nsymmetries:" << symmetry_strings[symmetry] << "\n";
 680       print_rules(rules,out);
 681    }
 682    cout << rules.size() << " rules written." << endl;
 683
 684    // optional: run through the entire state space, checking that new_slowcalc matches slowcalc
 685    cout << "Verifying is correct (can abort if you're confident)...";
 686    cout.flush();
 687    if(is_correct(rules,N_STATES,nhood_size))
 688       cout << "yes." << endl;
 689    else
 690       cout << "no! Either there's a bug in the code, or the transition function does not have the symmetry you selected." << endl;
 691 }