Code: Select all
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* osrc.cpp version 0.3 (2020-03-08 rev #01) *
* A simple search program for low-period oscillators and "short-wide" spaceships, *
* written in cross-platform C++. *
* It probably could just be in C, but I don't know much C so I didn't want to go there. *
* *
* Options: *
* *
* PERIOD: Sets the period of the search (from 1 to 10, or higher prime *
* periods). Higher composite periods supported incompletely. *
* *
* WIDTH: Sets the width of the search (from 1 to 9). *
* *
* WARNING: A width-9 search uses slightly over 2 GB. A width-8 *
* search uses approximately 270 MB. Width-10 searches *
* are possible in principle, but likely require at least *
* 17 GB available. Memory usage may be reduced in future *
* versions. *
* *
* MAX_LENGTH: Sets the maximum length of the search. *
* *
* FULL_PD_BY: Requires all partials to have their first full-period row by *
* this length. *
* *
* MIN_ROTOR_WIDTH: Requires all solutions to have at least this many rows between *
* their first and last full-period rows (inclusive). *
* *
* MAX_SOLUTIONS: After this many solutions have been found, stop search. *
* *
* SYMMETRY: Asymmetric, odd, even, and gutter modes supported. *
* *
* SHIFT: Allows searches for c/n spaceships by offsetting the first *
* generation and last generation by 1 relative to each other. *
* *
* STATOR_LEFT: Allows non-empty stator to the left of the search area. Reduces *
* the effective width by 2. *
* *
* STATOR_RIGHT: Allows non-empty stator to the right of the search area. Reduces *
* the effective width by 2. *
* *
* STATOR_FRONT: Allows non-empty stator in front of the search area. Reduces the *
* effective length by 1 (IIRC). *
* *
* P2_LEFT*: Allows non-empty p2 region to the left of the search area. *
* Reduces the effective width by 2. *
* *
* P2_RIGHT*: Allows non-empty p2 region to the right of the search area. *
* Reduces the effective width by 2. *
* *
* OUTPUT_ALL_PHASES: Outputs all phases of solutions, not just partials. *
* *
* FILTER_DUPLICATES: Eliminates duplicate rotors. Hash collisions will occasionally *
* occur, so this option will occasionally filter rotors that *
* should not be filtered. Does not filter different phases of the *
* same rotors. *
* *
* PHOENIX: Requires that all live cells die in the subsequent generation. *
* *
* RULE: Sets the rule used. Rule should be specified in the format *
* briefly documented in the nearby comments. *
* Alternatively, custom bitwise expressions can be created for *
* specific rules to accelerate table generation. This is only *
* recommended for "advanced" users during high-width searches. *
* The LIFE and TLIFE options (replacing the RULE option) use *
* prepackaged custom bitwise expressions for B3/S23 and *
* B3/S2-i34q, respectively. Setting one is equivalent to *
* specifying the corresponding rule with the RULE option. *
* The file ntzfind-setup.cpp, packaged with an older isotropic *
* non-totalistic version of the zfind spaceship search program, *
* is capable of generating these custom bitwise expressions for *
* some, but not all, rules, due to bugs in its implementation. *
* *
* PARTIAL: Extends a partial result. The final two rows of the partial *
* should be entered into the initializer lists for the "partial" *
* triply nested array as briefly documented in the nearby *
* comments. *
* *
* (*An asterisk indicates a feature under development *
* that probably won't work correctly.) *
* *
* *
* Known limitations: *
* *
* Full-period testing for composite periods is incomplete. *
* *
* Extremely high memory usage for relatively high widths. *
* *
* The format to specify the rule is fairly unintuitive to use. *
* *
* Changes to the source code and recompilation are required to change the search *
* settings. *
* *
* Much slower than zfind for equivalent periods and widths. *
* *
* Does no stator optimization, and only rudimentary support for eliminating *
* duplicate-rotor solutions. Outputs each solution in every phase once per phase. *
* *
* This comment box is very difficult to format. *
* *
* By praosylen and whoever else wants to get rid of any of the above limitations and/or *
* add new functionality. *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include <iostream>
#include <string>
#include <vector>
//* Get rid of the first / if you've figured out how to accept command-line parameters and autogenerate this part into a file called settings.cpp.
//Don't change things here:
#define SYM false
#define GAP 0
#define NONE 0
#define GUTTER 1
#define ODD 2
#define EVEN 3
//Change things here:
#define PERIOD 4
#define WIDTH 7
#define MAX_LENGTH 20 //Not guaranteed to be exact
#define FULL_PD_BY 5 //Do not set this to zero
#define MIN_ROTOR_WIDTH 0
#define MAX_SOLUTIONS 0x7FFFFFFF
#define SYMMETRY NONE //NONE, GUTTER, ODD, EVEN
#define STATOR_LEFT false
#define STATOR_RIGHT false
#define STATOR_FRONT false
#define PHOENIX false
#define P2_LEFT false
#define P2_RIGHT false
//Rule format: type(n, hensel)
// type -- b/s
// n -- number of on cells
// hensel -- string after transition in Hensel notation (e.g. "ackr"; "-n")
//Use && as the separator between transitions.
#define RULE b(2,"n")&&b(3,"")&&s(2,"")&&s(3,"-q")
//Alternatively, uncomment one of these two lines for faster table generation for specific rules:
//#define LIFE
//#define TLIFE
//Uncomment this to search for c/PERIOD spaceships instead. The SYMMETRY, STATOR_LEFT, and STATOR_RIGHT options will be ignored.
//#define SHIFT
//Uncomment this to output all phases of solutions, not just partials.
//#define OUTPUT_ALL_PHASES
//Uncomment this to filter duplicate rotors (with occasional extraneous filtering).
#define FILTER_DUPLICATES
//Uncomment this to extend a partial.
//#define PARTIAL
#ifdef PARTIAL
//Enter the last two rows of the partial here.
//For even/odd symmetry, the central row will be on the right.
//For gutter symmetry, the central row will be to the left.
//Phase order is first to last.
//Row order is front to back.
bool partial[2][PERIOD][WIDTH] = {
{
//Penultimate row of partial in all phases
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0}
},
{
//Final row of partial in all phases
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},
{0,0,0,1,0,0,0}
}
};
#endif
//Don't change things here:
//For that matter, don't pay attention to the awful parameter names either.
#ifdef SHIFT
#undef SYMMETRY
#define SYMMETRY NONE
#undef STATOR_LEFT
#undef STATOR_RIGHT
#undef STATOR_FRONT
#define STATOR_LEFT false
#define STATOR_RIGHT false
#define STATOR_FRONT false
#undef P2_LEFT
#undef P2_RIGHT
#define P2_LEFT false
#define P2_RIGHT false
#endif
#if SYMMETRY == GUTTER
#undef SYM //Avoid pointless warning
#define SYM true
#undef STATOR_RIGHT
#define STATOR_RIGHT false
#undef P2_RIGHT
#define P2_RIGHT false
#elif SYMMETRY == ODD
#undef GAP //Avoid another pointless warning
#define GAP 2
#undef STATOR_LEFT
#define STATOR_LEFT false
#undef P2_LEFT
#define P2_LEFT false
#elif SYMMETRY == EVEN
#undef GAP //Avoid yet another pointless warning
#define GAP 1
#undef STATOR_LEFT
#define STATOR_LEFT false
#undef P2_LEFT
#define P2_LEFT false
#endif
#if SYMMETRY % 2
#undef P2_LEFT
#undef P2_RIGHT
#define P2_LEFT false
#define P2_RIGHT false
#endif
#ifdef LIFE
#undef RULE
#define RULE 0
#define CUSTOM_RULE
#endif
#ifdef TLIFE
#undef RULE
#define RULE 0
#define CUSTOM_RULE
#endif
//Map from 9-bit neighbor/center-cell states to subsequent state
//Bit ordering from right to left is N, NE, E, SE, S, SW, W, NW, center.
bool ruletable[512];
//Combos of neighboring states with 0-8 neighbors
//Bit ordering from right to left is N, NE, E, SE, S, SW, W, NW.
int states0[1] = {0};
int states1[8] = {1,2,4,8,16,32,64,128};
int states2[28] = {3,5,6,9,10,12,17,18,20,24,33,34,36,40,48,65,66,68,72,80,96,129,130,132,136,144,160,192};
int states3[56] = {7,11,13,14,19,21,22,25,26,28,35,37,38,41,42,44,49,50,52,56,67,69,70,73,74,76,81,82,84,88,97,98,100,104,112,131,133,134,137,138,140,145,146,148,152,161,162,164,168,176,193,194,196,200,208,224};
int states4[70] = {15,23,27,29,30,39,43,45,46,51,53,54,57,58,60,71,75,77,78,83,85,86,89,90,92,99,101,102,105,106,108,113,114,116,120,135,139,141,142,147,149,150,153,154,156,163,165,166,169,170,172,177,178,180,184,195,197,198,201,202,204,209,210,212,216,225,226,228,232,240};
int states5[56] = {31,47,55,59,61,62,79,87,91,93,94,103,107,109,110,115,117,118,121,122,124,143,151,155,157,158,167,171,173,174,179,181,182,185,186,188,199,203,205,206,211,213,214,217,218,220,227,229,230,233,234,236,241,242,244,248};
int states6[28] = {63,95,111,119,123,125,126,159,175,183,187,189,190,207,215,219,221,222,231,235,237,238,243,245,246,249,250,252};
int states7[8] = {127,191,223,239,247,251,253,254};
int states8[1] = {255};
//Add (or remove) up to 8 nonzero states to (from) the rule table
void addstates(unsigned long long states, bool b_or_s, bool mode){
for(int i = 0; i < 8; i++){
if(states & 0xFF){
ruletable[b_or_s * 0x100 + (states & 0xFF)] = !mode;
//Uncomment to figure out why the heck it isn't working right.
//std::cout << (states & 0xFF) << " " << i << " " << b_or_s << " " << mode << " " << (b_or_s * 0x100 + (states & 0xFF)) << " " << ruletable[b_or_s * 0x100 + (states & 0xFF)] << std::endl;
}
states >>= 8;
}
}
//Set states in ruletable for a particular neighbor count and given Hensel-notation transitions. Both functions b() and s() return true for success, false for failure.
//Most of this function was procedurally generated with a Python script. Edit at your own risk.
bool b(int n, const char* hensel){
bool mode = hensel[0] == '-' || hensel[0] == '\0'; //Are we adding or removing non-totalistic transitions?
bool totalistic = hensel[0] == '\0'; //*Are* there even any non-totalistic transitions?
unsigned long long states = 0;
switch(n){
case 0:
ruletable[states0[0]] = mode;
break;
case 1:
if(mode){
for(int i = 0; i < 8; ruletable[states1[i++]] = true);
}
if(!totalistic){
for(int i = mode; hensel[i] != '\0'; i++){
switch(hensel[i]){
case 'c':
states = 2308097559956031490ull;
break;
case 'e':
states = 4616194021471028225ull;
break;
default:
std::cout << "Fatal error: unrecognized transition in Hensel notation." << std::endl;
return false;
}
addstates(states, false, mode);
}
}
break;
case 2:
if(mode){
for(int i = 0; i < 28; ruletable[states2[i++]] = true);
}
if(!totalistic){
for(int i = mode; hensel[i] != '\0'; i++){
switch(hensel[i]){
case 'a':
states = 6924291581427059715ull;
break;
case 'c':
states = 2885262137182136330ull;
break;
case 'e':
states = 5770242800395228165ull;
break;
case 'i':
states = 4904776310130295825ull;
break;
case 'k':
states = 5193358598697133065ull;
break;
case 'n':
states = 2488276763917060130ull;
break;
default:
std::cout << "Fatal error: unrecognized transition in Hensel notation." << std::endl;
return false;
}
addstates(states, false, mode);
}
}
break;
case 3:
if(mode){
for(int i = 0; i < 56; ruletable[states3[i++]] = true);
}
if(!totalistic){
for(int i = mode; hensel[i] != '\0'; i++){
switch(hensel[i]){
case 'a':
states = 8078340360351259655ull;
break;
case 'c':
states = 3065441341143164970ull;
break;
case 'e':
states = 6058825089054495765ull;
break;
case 'i':
states = 16156679622756929155ull;
break;
case 'j':
states = 7014381183609081155ull;
break;
case 'k':
states = 5950422004356256805ull;
break;
case 'n':
states = 7501456158653164555ull;
break;
case 'q':
states = 7104470785388088355ull;
break;
case 'r':
states = 7212873870086327315ull;
break;
case 'y':
states = 5373537802658161705ull;
break;
default:
std::cout << "Fatal error: unrecognized transition in Hensel notation." << std::endl;
return false;
}
addstates(states, false, mode);
}
}
break;
case 4:
if(mode){
for(int i = 0; i < 70; ruletable[states4[i++]] = true);
}
if(!totalistic){
for(int i = mode; hensel[i] != '\0'; i++){
switch(hensel[i]){
case 'a':
states = 8655504937577364495ull;
break;
case 'c':
states = 12297829382473034410ull;
break;
case 'e':
states = 6148914691236517205ull;
break;
case 'i':
states = 7790038447312432155ull;
break;
case 'j':
states = 7302963472268348755ull;
break;
case 'k':
states = 7591545760835185995ull;
break;
case 'n':
states = 16733844199983033995ull;
break;
case 'q':
states = 8258519564312288295ull;
break;
case 'r':
states = 8366922649010527255ull;
break;
case 't':
states = 16445261911416196755ull;
break;
case 'w':
states = 7194560387570109795ull;
break;
case 'y':
states = 7681635362614193195ull;
break;
case 'z':
states = 7393053074047355955ull;
break;
default:
std::cout << "Fatal error: unrecognized transition in Hensel notation." << std::endl;
return false;
}
addstates(states, false, mode);
}
}
break;
case 5:
if(mode){
for(int i = 0; i < 56; ruletable[states5[i++]] = true);
}
if(!totalistic){
for(int i = mode; hensel[i] != '\0'; i++){
switch(hensel[i]){
case 'a':
states = 17887892978907233935ull;
break;
case 'c':
states = 8457012251192548695ull;
break;
case 'e':
states = 16914023403944062635ull;
break;
case 'i':
states = 8944087226236632095ull;
break;
case 'j':
states = 8835684141538393135ull;
break;
case 'k':
states = 7771724964796214635ull;
break;
case 'n':
states = 8745594539759385935ull;
break;
case 'q':
states = 8547101852971555895ull;
break;
case 'r':
states = 7970217651273460795ull;
break;
case 'y':
states = 7880128049494453595ull;
break;
default:
std::cout << "Fatal error: unrecognized transition in Hensel notation." << std::endl;
return false;
}
addstates(states, false, mode);
}
}
break;
case 6:
if(mode){
for(int i = 0; i < 28; ruletable[states6[i++]] = true);
}
if(!totalistic){
for(int i = mode; hensel[i] != '\0'; i++){
switch(hensel[i]){
case 'a':
states = 9124266430197660735ull;
break;
case 'c':
states = 9034176828418653535ull;
break;
case 'e':
states = 18068072182868262575ull;
break;
case 'i':
states = 17202605692603330235ull;
break;
case 'k':
states = 8925773743720414575ull;
break;
case 'n':
states = 8637191455153577335ull;
break;
default:
std::cout << "Fatal error: unrecognized transition in Hensel notation." << std::endl;
return false;
}
addstates(states, false, mode);
}
}
break;
case 7:
if(mode){
for(int i = 0; i < 8; ruletable[states7[i++]] = true);
}
if(!totalistic){
for(int i = mode; hensel[i] != '\0'; i++){
switch(hensel[i]){
case 'c':
states = 9214356032379682175ull;
break;
case 'e':
states = 18356654471527530175ull;
break;
default:
std::cout << "Fatal error: unrecognized transition in Hensel notation." << std::endl;
return false;
}
addstates(states, false, mode);
}
}
break;
case 8:
ruletable[states8[0]] = mode;
break;
default:
std::cout << "Fatal error: malformed birth transition." << std::endl;
}
if(ruletable[0] || ruletable[2]){
std::cout << "Fatal error: B0 and B1c transitions not supported." << std::endl;
return false;
}
return true;
}
//Most of this function was procedurally generated with a Python script. Edit at your own risk.
bool s(int n, const char* hensel){
bool mode = hensel[0] == '-' || hensel[0] == '\0'; //Are we adding or removing non-totalistic transitions?
bool totalistic = hensel[0] == '\0'; //*Are* there even any non-totalistic transitions?
unsigned long long states;
switch(n){
case 0:
ruletable[states0[0]+256] = mode;
break;
case 1:
if(mode){
for(int i = 0; i < 8; ruletable[states1[i++]+256] = true);
}
if(!totalistic){
for(int i = mode; hensel[i] != '\0'; i++){
switch(hensel[i]){
case 'c':
states = 2308097559956031490ull;
break;
case 'e':
states = 4616194021471028225ull;
break;
default:
std::cout << "Fatal error: unrecognized transition in Hensel notation." << std::endl;
return false;
}
addstates(states, true, mode);
}
}
break;
case 2:
if(mode){
for(int i = 0; i < 28; ruletable[states2[i++]+256] = true);
}
if(!totalistic){
for(int i = mode; hensel[i] != '\0'; i++){
switch(hensel[i]){
case 'a':
states = 6924291581427059715ull;
break;
case 'c':
states = 2885262137182136330ull;
break;
case 'e':
states = 5770242800395228165ull;
break;
case 'i':
states = 4904776310130295825ull;
break;
case 'k':
states = 5193358598697133065ull;
break;
case 'n':
states = 2488276763917060130ull;
break;
default:
std::cout << "Fatal error: unrecognized transition in Hensel notation." << std::endl;
return false;
}
addstates(states, true, mode);
}
}
break;
case 3:
if(mode){
for(int i = 0; i < 56; ruletable[states3[i++]+256] = true);
}
if(!totalistic){
for(int i = mode; hensel[i] != '\0'; i++){
switch(hensel[i]){
case 'a':
states = 8078340360351259655ull;
break;
case 'c':
states = 3065441341143164970ull;
break;
case 'e':
states = 6058825089054495765ull;
break;
case 'i':
states = 16156679622756929155ull;
break;
case 'j':
states = 7014381183609081155ull;
break;
case 'k':
states = 5950422004356256805ull;
break;
case 'n':
states = 7501456158653164555ull;
break;
case 'q':
states = 7104470785388088355ull;
break;
case 'r':
states = 7212873870086327315ull;
break;
case 'y':
states = 5373537802658161705ull;
break;
default:
std::cout << "Fatal error: unrecognized transition in Hensel notation." << std::endl;
return false;
}
addstates(states, true, mode);
}
}
break;
case 4:
if(mode){
for(int i = 0; i < 70; ruletable[states4[i++]+256] = true);
}
if(!totalistic){
for(int i = mode; hensel[i] != '\0'; i++){
switch(hensel[i]){
case 'a':
states = 8655504937577364495ull;
break;
case 'c':
states = 12297829382473034410ull;
break;
case 'e':
states = 6148914691236517205ull;
break;
case 'i':
states = 7790038447312432155ull;
break;
case 'j':
states = 7302963472268348755ull;
break;
case 'k':
states = 7591545760835185995ull;
break;
case 'n':
states = 16733844199983033995ull;
break;
case 'q':
states = 8258519564312288295ull;
break;
case 'r':
states = 8366922649010527255ull;
break;
case 't':
states = 16445261911416196755ull;
break;
case 'w':
states = 7194560387570109795ull;
break;
case 'y':
states = 7681635362614193195ull;
break;
case 'z':
states = 7393053074047355955ull;
break;
default:
std::cout << "Fatal error: unrecognized transition in Hensel notation." << std::endl;
return false;
}
addstates(states, true, mode);
}
}
break;
case 5:
if(mode){
for(int i = 0; i < 56; ruletable[states5[i++]+256] = true);
}
if(!totalistic){
for(int i = mode; hensel[i] != '\0'; i++){
switch(hensel[i]){
case 'a':
states = 17887892978907233935ull;
break;
case 'c':
states = 8457012251192548695ull;
break;
case 'e':
states = 16914023403944062635ull;
break;
case 'i':
states = 8944087226236632095ull;
break;
case 'j':
states = 8835684141538393135ull;
break;
case 'k':
states = 7771724964796214635ull;
break;
case 'n':
states = 8745594539759385935ull;
break;
case 'q':
states = 8547101852971555895ull;
break;
case 'r':
states = 7970217651273460795ull;
break;
case 'y':
states = 7880128049494453595ull;
break;
default:
std::cout << "Fatal error: unrecognized transition in Hensel notation." << std::endl;
return false;
}
addstates(states, true, mode);
}
}
break;
case 6:
if(mode){
for(int i = 0; i < 28; ruletable[states6[i++]+256] = true);
}
if(!totalistic){
for(int i = mode; hensel[i] != '\0'; i++){
switch(hensel[i]){
case 'a':
states = 9124266430197660735ull;
break;
case 'c':
states = 9034176828418653535ull;
break;
case 'e':
states = 18068072182868262575ull;
break;
case 'i':
states = 17202605692603330235ull;
break;
case 'k':
states = 8925773743720414575ull;
break;
case 'n':
states = 8637191455153577335ull;
break;
default:
std::cout << "Fatal error: unrecognized transition in Hensel notation." << std::endl;
return false;
}
addstates(states, true, mode);
}
}
break;
case 7:
if(mode){
for(int i = 0; i < 8; ruletable[states7[i++]+256] = true);
}
if(!totalistic){
for(int i = mode; hensel[i] != '\0'; i++){
switch(hensel[i]){
case 'c':
states = 9214356032379682175ull;
break;
case 'e':
states = 18356654471527530175ull;
break;
default:
std::cout << "Fatal error: unrecognized transition in Hensel notation." << std::endl;
return false;
}
addstates(states, true, mode);
}
}
break;
case 8:
ruletable[511] = mode;
break;
default:
std::cout << "Fatal error: malformed survival transition." << std::endl;
return false;
}
return true;
}
bool setrule(){
for(int i = 0; i < 512; ruletable[i++] = 0);
return !(RULE); //True indicates there was an error setting the rule.
}
//Change this if you dare (at least to any rule with B3i and without B2a, B2c, or B1e): P.S. Don't bother even thinking about B0 or B1c rules.
//Randomly copied from ntzfind (B3/S23). If you have ntzfind (at least the older version), it's fairly simple to generate one of these for any rule you want (not taking bugs into account).
int stepcell(int o, int a, int b, int c, int d, int e, int f, int g, int h){
#ifdef LIFE
return (~o&((0x0)|((a^b^c^d^e^f^g^h)&(((a|b|c|d)&(e|f|g|h))|((a|b|e|f)&(c|d|g|h)))&~(((a|b)&(c|d)&(e|f)&(g|h))|(~((a&b)^(c&d)^(e&f)^(g&h))&((a&b)|(c&d)|(e&f)|(g&h)))))))|(o&((0x0)|(~(a^b^c^d^e^f^g^h)&(a|b|c|d|e|f|g|h)&~(((a|b|c)&(d|e|f)&(g|h))|(a&b&c)|(d&e&f)|((a|b|c)&(d|e|f)&(~(a^b^c)|~(d^e^f)))|(g&h&(a|b|c|d|e|f))))|((a^b^c^d^e^f^g^h)&(((a|b|c|d)&(e|f|g|h))|((a|b|e|f)&(c|d|g|h)))&~(((a|b)&(c|d)&(e|f)&(g|h))|(~((a&b)^(c&d)^(e&f)^(g&h))&((a&b)|(c&d)|(e&f)|(g&h)))))));
#endif
#ifdef TLIFE
return (~o&((0x0)|((a^b^c^d^e^f^g^h)&(((a|b|c|d)&(e|f|g|h))|((a|b|e|f)&(c|d|g|h)))&~(((a|b)&(c|d)&(e|f)&(g|h))|(~((a&b)^(c&d)^(e&f)^(g&h))&((a&b)|(c&d)|(e&f)|(g&h)))))))|(o&((0x0)|(~(a^b^c^d^e^f^g^h)&(a|b|c|d|e|f|g|h)&~(((a|b|c)&(d|e|f)&(g|h))|(a&b&c)|(d&e&f)|((a|b|c)&(d|e|f)&(~(a^b^c)|~(d^e^f)))|(g&h&(a|b|c|d|e|f)))&~(~(b|d|f|h)&~((a^e)|(c^g))))|((a^b^c^d^e^f^g^h)&(((a|b|c|d)&(e|f|g|h))|((a|b|e|f)&(c|d|g|h)))&~(((a|b)&(c|d)&(e|f)&(g|h))|(~((a&b)^(c&d)^(e&f)^(g&h))&((a&b)|(c&d)|(e&f)|(g&h)))))|(0x0|(((~b&~f)&~((~c^~e)|(~a^~g))&(~e^~g)&~(~d|~h))|((~d&~h)&~((~e^~g)|(~a^~c))&(~c^~e)&~(~b|~f))))));
#endif
return 0; //Silence a warning. Execution should never get here.
}
//Fall back on (slower) wimpmode for rules without custom-built bitwise step functions
int stepcell2(int i, int o, int a, int b, int c, int d, int e, int f, int g, int h){
int cs[9] = {a,b,c,d,e,f,g,h,o}, t = 0;
for(int j = 0; j < 9; j++){
t += !!(cs[j] & 1<<i) << j;
}
return ruletable[t] << i;
}
//*/#include "settings.cpp"
inline int steprow(int r1, int r2, int r3){
#ifdef CUSTOM_RULE
return stepcell(r2, r1, r1 >> 1 | (((r1 >> (WIDTH-GAP)) & 1) << (WIDTH-1)), r2 >> 1 | (((r2 >> (WIDTH-GAP)) & 1) << (WIDTH-1)), r3 >> 1 | (((r3 >> (WIDTH-GAP)) & 1) << (WIDTH-1)), r3, r3 << 1, r2 << 1, r1 << 1) & ((1 << WIDTH) - 1); //It's magic. Don't ask. So is the last function.
#else
int rtn = 0;
for(int i = 0; i < WIDTH; i++){
rtn |= stepcell2(i, r2, r1, r1 >> 1 | (((r1 >> (WIDTH-GAP)) & 1) << (WIDTH-1)), r2 >> 1 | (((r2 >> (WIDTH-GAP)) & 1) << (WIDTH-1)), r3 >> 1 | (((r3 >> (WIDTH-GAP)) & 1) << (WIDTH-1)), r3, r3 << 1, r2 << 1, r1 << 1) & ((1 << WIDTH) - 1);
}
return rtn;
#endif
}
//The search state
int rows[MAX_LENGTH][PERIOD];
//Search metadata for lookup in table_of_tables
int rind[MAX_LENGTH][PERIOD];
//Holds counts of possible matching extensions to combinations of rows
int main_table[1<<(WIDTH*3)];
//Holds the extensions themselves
int* table_of_tables[1<<(WIDTH*3)];
//Bitmasks for the edges of rows
#define LMASK (1<<(WIDTH-1))
#define RMASK 1
//Bitmasks for stator or p2 cells (if using)
#define SLMASK (1<<(WIDTH-2))
#define SRMASK 2
//Sentinel value
#define RNULL 1<<WIDTH
//Populate table of extensions after it has been constructed
void populate(long ind, long r3){
int* temp;
if(table_of_tables[ind] == nullptr){
table_of_tables[ind] = new int[main_table[ind]+1];//Add 1 for null-terminated array
table_of_tables[ind][0] = RNULL;
}
//Find first unfilled index with SNEAKY POINTER MATH!!!
//I'm exaggerating; it's not that interesting. It's quite useless, in fact, and less safe than it could be.
//In a previous version of this, I could have sworn that there was a point to the pointers. See what I did there? Eh? Eh?
for(temp = table_of_tables[ind]; *temp != RNULL; temp++);
*temp = r3;
//Null-terminate it!
*(temp+1) = RNULL;
}
void make_tables(){
long r1, r2, r3, r4, ind, edges, b1e, b2a, b2c, b3i;
//int* temp; //Pointless, on second thought, but I don't feel like fixing it now.
//Initialize counts to 0
for(long long i = 0; i < 1<<(WIDTH*3); i++){
main_table[i] = 0;
table_of_tables[i] = nullptr;
}
b1e = -ruletable[1];
b2a = -ruletable[3];
b2c = -ruletable[10];
b3i = -ruletable[14];
//Generate counts
for(long long i = 0; i < 1<<(WIDTH*3); i++){
r1 = i >> (WIDTH*2); //Top row
r2 = (i >> WIDTH) & ((1 << WIDTH) - 1); //Middle row
r3 = i & ((1 << WIDTH) - 1); //Bottom row
r4 = steprow(r1, r2, r3); //Result
edges = 0;
edges |= (~r1 & r2 & ~r3) & b1e;
edges |= (r2 & (r1 ^ r3)) & b2a;
edges |= (r1 & ~r2 & r3) & b2c;
edges |= (r1 & r2 & r3) & b3i;
//Check edge cases and stators:
if(!(!GAP && !(STATOR_LEFT || P2_LEFT) && (edges & LMASK)) && !(!SYM && !(STATOR_RIGHT || P2_RIGHT) && (edges & RMASK)) && !(STATOR_LEFT && ((r2 ^ r4) & SLMASK)) && !(STATOR_RIGHT && ((r2 ^ r4) & SRMASK))){
//std::cout << r1 << " " << r2 << " " << r3 << " " << r4 << " " << ((r2 ^ r4) & SRMASK) << std::endl;
#if STATOR_LEFT || P2_LEFT
r4 = (r4 & ~LMASK) | (r2 & LMASK);
#endif
#if STATOR_RIGHT || P2_RIGHT
r4 = (r4 & ~RMASK) | (r2 & RMASK);
#endif
main_table[r1 << (WIDTH*2) | r2 << WIDTH | r4] += 1 << (P2_LEFT + P2_RIGHT); //Increment extension count for r124 combo
}
}
//Do all that again to populate the extension table
for(long long i = 0; i < 1<<(WIDTH*3); i++){
r1 = i >> (WIDTH*2); //Top row
r2 = (i >> WIDTH) & ((1 << WIDTH) - 1); //Middle row
r3 = i & ((1 << WIDTH) - 1); //Bottom row
r4 = steprow(r1, r2, r3); //Result
edges = 0;
edges |= (~r1 & r2 & ~r3) & b1e;
edges |= (r2 & (r1 ^ r3)) & b2a;
edges |= (r1 & ~r2 & r3) & b2c;
edges |= (r1 & r2 & r3) & b3i;
ind = r1 << (WIDTH*2) | r2 << WIDTH | r4; //Index in count, extension tables
//Check edge cases and stators: !NOTE! This only works in rules with B3i and none of B1e, B2a, and B2c.
if(!(!GAP && !(STATOR_LEFT || P2_LEFT) && (edges & LMASK)) && !(!SYM && !(STATOR_RIGHT || P2_RIGHT) && (edges & RMASK)) && !(STATOR_LEFT && ((r2 ^ r4) & SLMASK)) && !(STATOR_RIGHT && ((r2 ^ r4) & SRMASK))){
#if STATOR_LEFT || P2_LEFT
r4 = (r4 & ~LMASK) | (r2 & LMASK);
#endif
#if STATOR_RIGHT || P2_RIGHT
r4 = (r4 & ~RMASK) | (r2 & RMASK);
#endif
#if STATOR_LEFT || STATOR_RIGHT || P2_LEFT || P2_RIGHT
ind = r1 << (WIDTH*2) | r2 << WIDTH | r4;
#endif
populate(ind, r3);
#if P2_LEFT && P2_RIGHT
populate(ind, r3 ^ LMASK);
populate(ind, r3 ^ RMASK);
populate(ind, r3 ^ LMASK ^ RMASK);
#elif P2_LEFT
populate(ind, r3 ^ LMASK);
#elif P2_RIGHT
populate(ind, r3 ^ RMASK);
#endif
}
}
}
//Main search subroutines start here.
//Convert a row of Bits inTO a plaintext String
inline std::string btos(int b){
std::string rtn = "";
#if SYMMETRY == GUTTER
for(int i = WIDTH-1; i > -1; i--){
rtn += ((b >> i) & 1) ? 'O' : '.';
}
rtn += "."
#endif
for(int i = 0; i < WIDTH; i++){
rtn += ((b >> i) & 1) ? 'O' : '.';
}
#if SYMMETRY == ODD
for(int i = WIDTH-2; i > -1; i--){
rtn += ((b >> i) & 1) ? 'O' : '.';
}
#elif SYMMETRY == EVEN
for(int i = WIDTH-1; i > -1; i--){
rtn += ((b >> i) & 1) ? 'O' : '.';
}
#endif
return rtn;
}
unsigned long rotor_hash(int length){
unsigned long rtn = 0;
int b;
for(int i = 0; i < length; i++){
for(int j = 0; j < WIDTH; j++){
b = 0;
for(int k = 0; k < PERIOD; k++){
b <<= 1;
b |= !!(rows[i][k] & (1 << j));
}
if(b && b < ((1<<PERIOD) - 1)){
rtn += b + (rtn*b)%37;
rtn <<= 1;
}
}
rtn++;
}
return rtn;
}
//const int subperiods[9][3] = {{1,1,1},{1,1,1},{1,1,2},{1,1,1},{1,2,3},{1,1,1},{1,2,4},{1,1,3},{1,2,5}};
int max_full_pd_length = MAX_LENGTH;
int scount = 0;
std::vector<unsigned long> rotors;
//Figure out if it's an exciting, full-period, wide-rotor solution or if it's just a boring old still life or something. Also filter duplicate rotors.
bool handle_solution(int length){
int test = 0, q = 0;
bool test2 = false;
unsigned long hash;
//Test for first full-periodic row
for(int i = 0; i < length; i++, q+=!test2){
test = rows[i][0];
for(int j = 1; j < PERIOD; j++){
//There MUST be a better way.
#if PERIOD == 4
if(j != 2) continue;
#endif
#if PERIOD == 6
if(j != 3) continue;
#endif
#if PERIOD == 8
if(j != 4) continue;
#endif
#if PERIOD == 9
if(j != 3) continue;
#endif
#if PERIOD == 10
if(j != 5) continue;
#endif
if(rows[i][j] != test){
test2 = true;
}
}
}
if(!test2) return false; //If there aren't any, why bother?
//Test for last full-periodic row
for(int i = length-1; i >= 0; i--){
test = rows[i][0];
for(int j = 1; j < PERIOD; j++){
//Here, too.
#if PERIOD == 4
if(j != 2) continue;
#endif
#if PERIOD == 6
if(j != 3) continue;
#endif
#if PERIOD == 8
if(j != 4) continue;
#endif
#if PERIOD == 9
if(j != 3) continue;
#endif
#if PERIOD == 10
if(j != 5) continue;
#endif
if(rows[i][j] != test){
test2 = false;
max_full_pd_length = i;
break;
}
}
if(!test2){
break;
}
}
//Minus 1 for "inclusive".
if(max_full_pd_length - q < MIN_ROTOR_WIDTH - 1){
return false;
}
#ifdef FILTER_DUPLICATES
//Now let's see if the rotor has been found before
hash = rotor_hash(length);
for(unsigned long i : rotors){
if(i == hash){
std::cout << "Duplicate rotor found: hash = " << hash << "." << std::endl;
return true;
}
}
#endif
//Yippee! It's a solution!
scount++;
std::cout << "Solution found (#" << scount << "); "
<< "length = " << length-2 << ":" << std::endl; //A patent falsehood, but oh well.
//Add it to the collection of rotors
rotors.push_back(hash);
std::cout << "Rotor hash: " << hash << std::endl;
//Output it in plaintext
for(int i = 0; i < length; i++){
#ifdef OUTPUT_ALL_PHASES
for(int j = 0; j < PERIOD; j++){
std::cout << btos(rows[i][j]) << " ";
}
#else
std::cout << btos(rows[i][0]) << " ";
#endif
std::cout << "\n";
}
std::cout << std::endl;
return true;
}
//Basically what it says.
inline bool test_full_pd(int length){
int test = 0;
bool test2 = false;
#if PERIOD > 3 && PERIOD != 5 && PERIOD != 7 && PERIOD < 11
bool test3 = false;
#endif
for(int i = 0; i < length; i++){
test = rows[i][0];
#if PERIOD > 3 && PERIOD != 5 && PERIOD != 7 && PERIOD < 11
test2 = true;
#endif
for(int j = 1; j < PERIOD; j++){
//And here. Did I mention here?
#if PERIOD == 4
if(j != 2) continue;
test3 = true;
for(int k = 0; k < PERIOD - j; k++){
if(rows[i][j+k] != rows[i][k]){
test3 = false;
}
}
if(test3) test2 = false;
#elif PERIOD == 6
if(j != 2 && j != 3) continue;
test3 = true;
for(int k = 0; k < PERIOD - j; k++){
if(rows[i][j+k] != rows[i][k]){
test3 = false;
}
}
if(test3) test2 = false;
#elif PERIOD == 8
if(j != 4) continue;
test3 = true;
for(int k = 0; k < PERIOD - j; k++){
if(rows[i][j+k] != rows[i][k]){
test3 = false;
}
}
if(test3) test2 = false;
#elif PERIOD == 9
if(j != 3) continue;
test3 = true;
for(int k = 0; k < PERIOD - j; k++){
if(rows[i][j+k] != rows[i][k]){
test3 = false;
}
}
if(test3) test2 = false;
#elif PERIOD == 10
if(j != 2 && j != 5) continue;
test3 = true;
for(int k = 0; k < PERIOD - j; k++){
if(rows[i][j+k] != rows[i][k]){
test3 = false;
}
}
if(test3) test2 = false;
#else
if(rows[i][j] != test){
//Test to see if given phase is earliest in search ordering; accelerates search PERIOD-fold -- in development
/*if(!test2 && !test4){
test4 = true;
for(int k = 1; k < PERIOD; k++){
if(rows[i][k] < rows[i][0]) return false;
else if(rows[i][k] == rows[i][0]) test4 = false;
}
}*/
test2 = true;
}
#endif
}
if(test2) break;
}
return !test2;
}
//Basically what it says.
void output_partial(int length){
std::cout << "Partial (length = " << length << "):" << "\n";
for(int i = 0; i < length; i++){
for(int j = 0; j < PERIOD; j++){
std::cout << btos(rows[i][j]) << " ";
}
std::cout << "\n";
}
std::cout << "\n";
}
#define STATOR_MASK ((STATOR_LEFT && (LMASK|SLMASK)) | (STATOR_RIGHT && (RMASK|SRMASK)))
#define P2_MASK ((P2_LEFT && (LMASK|SLMASK)) | (P2_RIGHT && (RMASK|SRMASK)))
//Do everything.
int main(){
int length = 2 + STATOR_FRONT, phase = 0, max_partial_length = 0;
long long prev = 0; //Lookup key for the previous two rows, or at least the relevant rowphases within them.
bool thing = false, thing2 = false;
#ifndef CUSTOM_RULE
if(setrule()) return 0;
//Uncomment to figure out what the heck else is going wrong:
//for(int i = 0; i < 512; i++) std::cout << i << " " << ruletable[i] << std::endl;
#endif
make_tables();
//Initialize search space (may or may not be necessary).
for(int i = 0; i < MAX_LENGTH; i++){
for(int j = 0; j < PERIOD; j++){
rows[i][j] = 0;
rind[i][j] = 0;
}
}
#ifdef PARTIAL
for(int i = 0; i < 2; i++){
for(int j = 0; j < PERIOD; j++){
for(int k = 0; k < WIDTH; k++){
rows[i][j] |= partial[i][j][k] << k;
}
}
}
thing2 = true;
#endif
//Main loop
for(;;){//It's infinite
//handle_solution(MAX_LENGTH);
beginning_of_infinite_loop: //This irritating language doesn't allow continues for outer loops
//std::cout << "Q";
//std::cout << length << " " << phase << "\n";
if(length >= 5+max_partial_length){//If search has advanced significantly
output_partial(length);//I guess I'll comment this
//std::cout << length;
max_partial_length = length;//Reset expectations
}//endif
if(length <= max_partial_length-10){//If search has shortened significantly
max_partial_length = length;//Reset expectations
}//endif
#if STATOR_FRONT
if(length < 2){ //Have reached very front stator cells
//output_partial(2);
rows[1][0]++; //Advance to next configuration
if(rows[1][0] & (1<<WIDTH)) break; //Search complete
for(int i = 1; i < PERIOD; i++){ //Make all generations match
rows[1][i] = rows[1][0]; //Set this rowphase to the one that's just changed
} //Endfor
phase = 0; //Time resets
length++; //Move on to the rotor section of the search
rind[length][phase] = -1; //Reset row config counter
} //endif
#else
if(length < 2) break; //Search complete
#endif
if(!thing2) rind[length][phase]++; //Advance unless it's the first iteration and we're extending a partial
thing2 = false;
#ifdef SHIFT //If we're searching for spaceships
if(phase == 1 && rows[length][0] & 1){//If there's a cell out of range, trim search to avoid segfaults
phase--; //Backtrack in time
if(phase < 0){ //If this is impossible
length--; //Backtrack in space
phase = PERIOD-1; //Return to the end of time
} //Endif
continue; //Nothing more to do here
} //Endif
prev = (rows[length-2][phase] << (2*WIDTH)) + (rows[length-1][phase] << WIDTH) + (rows[length-1][(phase+1)%PERIOD] >> (phase == PERIOD-1)); //Store lookup key
#else //If not
prev = (rows[length-2][phase] << (2*WIDTH)) + (rows[length-1][phase] << WIDTH) + rows[length-1][(phase+1)%PERIOD]; //Store lookup key
#endif //Endelse
//std::cout << rind[length][phase] << " " << main_table[prev] << "\n";
if(rind[length][phase] >= main_table[prev] || length > MAX_LENGTH-2 || ((length == FULL_PD_BY + 2) && test_full_pd(length)) || (phase > 1 && ((rows[length][phase-1] ^ rows[length][phase-2]) & STATOR_MASK)) || (phase > 1 && ((rows[length-1][phase] ^ rows[length-1][phase-2]) & P2_MASK)) || (length == 2 && STATOR_FRONT && phase > 1 && rows[length][phase-1] != rows[length][phase-2]) || (PHOENIX && ((phase && (rows[length-1][phase] & rows[length-1][phase-1])) || (phase == PERIOD-1 && (rows[length-1][phase] & rows[length-1][0]))))){ //If options exhausted for current rowphase, or search otherwise needs to be pruned
phase--; //Backtrack in time
if(phase < 0){ //If this is impossible
length--; //Backtrack in space
phase = PERIOD-1; //Return to the end of time
} //Endif
continue; //Nothing more to do here
} //Endif
//std::cout << "R";
rows[length][phase] = table_of_tables[prev][rind[length][phase]]; //Advance the current rowphase to the next option
phase++; //Time moves forwards unless otherwise noted (above or below)
if(phase == PERIOD){ //The universe has already ended
length++; //Advance in space
phase = 0; //Reset to beginning of time
rind[length][phase] = -1; //Be sneaky and account for the annoying increment at the beginning of the loop -- this is (maybe|sort of|not really) one advantage to using signed integers.
if(length == MAX_LENGTH) break; //Sanity check: somehow our check above for MAX_LENGTH being approached failed, so we better quit so as not to segfault.
} else { //TMC: Too Many Comments
rind[length][phase] = -1; //See above.
continue; //Help with solution handling at beginning of search
} //Endelse
for(int i = 0; i < PERIOD; i++){ //Iterate over all generations of the previous two rows
//std::cout << rows[length-1][phase] << " " << rows[length-2][phase] << "\n";
if(rows[length-1][i] || rows[length-2][i]){ //If they're non-empty
goto beginning_of_infinite_loop; //Never mind, not a solution; nothing to see here, move along
} //Endif
} //Endfor
//It seems to be a solution
//std::cout << length << " ";
thing = handle_solution(length); //They dissolve quite well, actually (at least in sulfuric acid)
if(scount > MAX_SOLUTIONS) break; //TMS: Too Many Solutions
//std::cout << length << " ";
if(!thing) output_partial(length); //If it is, in fact, nothing, output it anyways, but no false advertising it as a solution
length = ((max_full_pd_length!=MAX_LENGTH) ? max_full_pd_length : (length-2)); //Skips a few things, but oh well.
//std::cout << length << " " << max_full_pd_length;
phase = PERIOD-1; //Return to the end of time again
}//End the infinite loop
std::cout << "Search complete: " << scount << " solution" << (scount == 1 ? "" : "s") << " found."; //This is a proper grammar zone; all rules of grammar shall be enforced unless otherwise noted.
/*
for(int i = 0; i < 1 << (WIDTH*3); i++){
std::cout << "\n" << i << "\n" << main_table[i] << "\n";
for(int j = 0; j < main_table[i]; j++){
std::cout << table_of_tables[i][j] << "\n";
}
}//*/
std::cout << std::endl; //Just because.
return 0;
}
EDIT 03-09-2020: Fixed a couple bugs; added support for B1e, B2a, and B2c rules.