Preliminary attempt at a zfind-like oscillator searcher

For scripts to aid with computation or simulation in cellular automata.
Post Reply
User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Preliminary attempt at a zfind-like oscillator searcher

Post by praosylen » May 29th, 2017, 4:29 pm

Code: Select all

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * osrc.cpp version 0.1 (2017-05-29 rev #01)                                             *
 * A search program for low-period oscillators and "short-wide" spaceships,              *
 *  written in cross-platform C++.                                                       *
 * It probably could just be in C, but 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 spaceships by offsetting the first           *
 *                       generation and last generation by 1 relative to each other.     *
 *                                                                                       *
 *                                                                                       *
 * Known limitations:                                                                    *
 *                                                                                       *
 *     Full-period testing for composite periods is incomplete.                          *
 *                                                                                       *
 *     Extremely high memory usage for relatively high widths.                           *
 *                                                                                       *
 *     Requires a moderate degree of effort and ntzfind-setup.cpp to change the rule.    *
 *                                                                                       *
 *     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 once in each 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>
//* 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 6
#define MAX_LENGTH 100 //Not guaranteed to be exact
#define FULL_PD_BY 1 //Do not set this to zero
#define MIN_ROTOR_WIDTH 0
#define MAX_SOLUTIONS 0x7FFFFFFF
#define SYMMETRY NONE //NONE, GUTTER, ODD, EVEN
//Uncomment this to search for c/PERIOD spaceships instead. Do not use the SYMMETRY option.
//#define SHIFT

//Don't change things here:
//For that matter, don't pay attention to the awful parameter names either.
#if SYMMETRY == GUTTER
#undef SYM //Avoid pointless warning
#define SYM true
#elif SYMMETRY == ODD
#undef GAP //Avoid another pointless warning
#define GAP 2
#elif SYMMETRY == EVEN
#undef GAP //Avoid yet another pointless warning
#define GAP 1
#endif

//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/S2-i34q). If you have ntzfind, it's fairly simple to generate one of these for any rule you want.
inline int stepcell(int o, int a, int b, int c, int d, int e, int f, int g, int h){
	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))))));
}

//*/#include "settings.cpp"
inline int steprow(int r1, int r2, int r3){
	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.
}
//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)];
#define LMASK 1<<(WIDTH-1)
#define RMASK 1
#define RNULL 1<<WIDTH
void make_tables(){
    long r1, r2, r3, r4, ind;
    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;
	}
	//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
		//Check edge cases:                  !NOTE! This only works in rules with B3i and none of B1e, B2a, and B2c.
		if(!(!GAP && (r1 & r2 & r3 & LMASK)) && !(!SYM && (r1 & r2 & r3 & RMASK))){
			main_table[r1 << (WIDTH*2) | r2 << WIDTH  | r4]++; //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
		ind = r1 << (WIDTH*2) | r2 << WIDTH  | r4; //Index in count, extension tables
		//Check edge cases:                  !NOTE! This only works in rules with B3i and none of B1e, B2a, and B2c.
		if(!(!GAP && (r1 & r2 & r3 & LMASK)) && !(!SYM && (r1 & r2 & r3 & RMASK))){
			//Populate table of extensions
			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.
			for(temp = table_of_tables[ind]; *temp != RNULL; temp++);
			*temp = r3;
			//Null-terminate it!
			*(temp+1) = RNULL;
		}
	}
}

//Main search subroutines start here.

//Convert a row of Bits inTO a plaintext String
inline std::string btos(int b){
	std::string rtn = "";
	for(int i = 0; i < WIDTH; i++){
		rtn += ((b >> i) & 1) ? 'O' : '.';
	}
	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;

//Figure out if it's an exciting, full-periodic, wide-rotor solution or if it's just a boring old still life or something.
bool handle_solution(int length){
	int test = 0, q = 0;
	bool test2 = false;
	
	//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;
	}
	
	//Yippee! It's a solution!
	scount++;
	std::cout << "Solution found (#" << scount << "); "
	          << "length = " << length-2 << ":" << std::endl; //A patent falsehood, but oh well.
	//Output it in plaintext
	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 << std::endl;
	return true;
}

//Basically what it says.
inline bool test_full_pd(int length){
	int test = 0;
	bool test2 = false;
	for(int i = 0; i < length; i++){
		test = rows[i][0];
		for(int j = 1; j < PERIOD; j++){
//And here. Did I mention here?
#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;
			}
		}
	}
	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";
}

//Do everything.
int main(){
	int length = 2, 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;
	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;
		}
	}
	//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 > 8+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-16){//If search has shortened significantly
			max_partial_length = length;//Reset expectations
		}//endif
		if(length < 2) break; //Search complete
		rind[length][phase]++; //Advance
#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))){ //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
			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; //Be sneaky and account for the annoying increment at the beginning of the loop
			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
		//Yay, it works!
		//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.";
	/*
	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;
}
If anyone has any comments, questions, suggestions, or improvements, feel free to reply and/or post modified versions of my code.

Currently configured for tlife. To configure for B3/S23, replace lines 95-97 with the following:

Code: Select all

int stepcell(int o, int a, int b, int c, int d, int e, int f, int g, int h){
	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)))))));
}
EDIT: EDIT 2: The previous edit is now obsolete due to the phpBB update.
Last edited by praosylen on July 19th, 2021, 11:01 am, edited 2 times in total.
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Preliminary attempt at a zfind-like oscillator searcher

Post by wildmyron » May 30th, 2017, 5:47 am

I haven't had a look at the program yet, but based on what I presume are results from this program in the tlife thread I'm going to say: Nice work! :)
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: Preliminary attempt at a zfind-like oscillator searcher

Post by praosylen » May 30th, 2017, 9:17 am

wildmyron wrote:I haven't had a look at the program yet, but based on what I presume are results from this program in the tlife thread I'm going to say: Nice work! :)
Thank you very much! I will say it's not very user-friendly yet...

Anyway, a few Life results:

Code: Select all

x = 350, y = 29, rule = B3/S23
133b3o195bob2o9bob2o$15b2o96bo10b3o10bo191b2o4bo6b2o4bo$16b2o13bo32b3o
7bobo36bo11b2o5bo4bo20bo11b3obo10b3obo13bobo9b3o10b3o10b3o10bo52bob2o
7bo2bo9bo12bo$2o14b2o13bo41bo3bo20b2o13bo10b2o6bo3bo9b3o8bob2o12bobo
12bobo11bo3bo6bo18bo6bo14bo13bo11bo24b2o4bo6bobob2o7bob3o8bob3o$bob2o
12bo13b2o34bo6bo3bo5b2o3bo8bo4b2o7b2o10bob2o5bo16b2o5bo3b2o11bo14bo13b
o3bo5bo4bo8bo4bo6b2o13bo13bo10bob2o11b3o10bo10bo3b2o$4b3o8bo30b3o27b2o
6bobo3bo9b2obo20bo8bo2bo10bob3o4b2obo12bo15bo16b2o7bo2bobo7bo3bo10bobo
9b2o12bo10bo27bob3o10bo10bo12bo$2bo4bo7bo3bo11bo2bo29b2obo22bo8b2o8b2o
3bo9b3o7b3o10bo3bo7bo2bo10b4o9bo31bo9bo10b5obo22bo9b2o2bobo8bo25b2o10b
2o2bo8b2o2bo$6b2o8bobobo10bobo15bob2o9b3o2bo7bo9b2obo9bo3bo6bo11bo11bo
25bobo14bo9b2o16bo12bo10bo2bo6bo6bo7bo3b2o10b2o11b2obo7bo3b2o10bo20bo
5bo6bo4bo$2bobobo12bo15bo13bobo10bobobo8bo8bob2o10bo4bo6b4o7b5o9b4o6b
3obo21bobobo11b2o13bobo10b3o8bob4o7b3obob2o11bo7bo4b2o5b2obob2o9bobobo
8b2o10b3o9b3obo7bo3bo$b2o3b2o12bo9bob3ob2o9bo3bo9b3o2b2o6b2obo6b2o2bo
10b5o30b2o3bo9bo10bobo7bob2ob2o11b3o10bo3b2o19b2o13b2obo9b4o8bo3bo8bob
o10bobobo9bo11bo26bo$b2o3b2o12bo9bo3bo11bob2obob2o9bo12b2o9b3o21b3o6b
2o3bo6bo3bobo5bo4b2o11bo6bobobo11bo4bo9b2o3bo22bo14bo21bo4bo7bo11bobob
2o8bob2ob2o6bobo8b4o12bobo$2bobo12bo3bo9b2obobo9bo5bobo8bo10bo9b4o3bo
9bo9bo10bo2bobo4bobo2b2o7b2obo12b2o5b2obobo13bob2o12b2o9b3o8b3obo13b2o
7b3o11bo3bo8b3obo6bo5b2o6bo6bo16bo$17b4o11bob2o11b5o10b2o10b2o8bo2bo2b
2o8bobo9bo2bo4bo4bobo4bobo35bob2o10bobo13bob2o13bo8bo2bo26bo8b2o4bo11b
2o7b5o2bo6bobobobo6bobo8bo2bo12bobo$2bo2bo24bo3bo14bo23b2o26bo11bobo4b
2o4bo6bo36bo13b2o14b2obo13bo9b2o24bob2o10b2o11b2o12bo3b2o7b2ob2o8b2o9b
obo15bo$3bobo11b2o11b2o2bobo23bobo10b3o38bo54b2o45bobo32bobobo13bo10bo
51bo15b2o$4bo12b2o16b2o23b2o155bo33b2o2bo13bo11bo$255b2o12bo10b2o$185b
3obo79bo$188bobo$189bo$188bo$186bo$186b2o2b2o$187b2o2bo$188b3o$186bo$
188bo$184bobo$184b2o!
Just a bunch of relatively small p3s that may or may not be known. The smallest ones probably are. My favorite is the nearly-statorless p3 about four-fifths of the way to the right.
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: Preliminary attempt at a zfind-like oscillator searcher

Post by Saka » June 19th, 2017, 11:56 pm

I need help compiling:

Code: Select all

osrc.cpp: In function ‘void make_tables()’:
osrc.cpp:120:28: error: ‘nullptr’ was not declared in this scope
       table_of_tables[i] = nullptr;
                            ^
osrc.cpp:144:37: error: ‘nullptr’ was not declared in this scope
          if(table_of_tables[ind] == nullptr){
                                     ^

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: Preliminary attempt at a zfind-like oscillator searcher

Post by Sokwe » June 20th, 2017, 1:47 am

Saka wrote:I need help compiling
I googled this error and this was the first result. It seems that you are not compiling with the C++11 standard. Try compiling with either the flag -std=c++0x or the flag -std=c++11. If that doesn't work, try replacing each instance of "nullptr" in the code with "0".
-Matthias Merzenich

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: Preliminary attempt at a zfind-like oscillator searcher

Post by praosylen » March 8th, 2020, 2:10 pm

After 2 and a half years, I finally got around to updating this:

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;
}
New options and features:
  • STATOR_LEFT, STATOR_RIGHT, STATOR_FRONT
    • Set the leftmost, rightmost and/or front two rows to be composed only of stator cells. Stability isn't tested for the outermost rows, which means the width and/or length of the required stabilization is usually larger than the search width.
  • OUTPUT_ALL_PHASES
    • Solutions are now output in only the first phase by default. Set this option to output them in all phases.
  • FILTER_DUPLICATES
    • Hashes and eliminates duplicate rotors. Hash collisions may occasionally occur, causing false eliminations. Different phases of the same rotor are not yet eliminated.
  • PHOENIX
    • Requires that all live cells die in the subsequent generation. The P2_LEFT and P2_RIGHT options, which do not yet work, may in the future be used along with this to search directly for p4 phoenixes in Life. (It may prove possible to modify other programs, such as WLS/JLS, to perform a similar task.)
  • RULE
    • The most important new feature. All isotropic 2-state Moore-neighborhood rules without any of B012ac are allowed. (The B2c exclusion may be relaxed in future versions.)
      • EDIT: Now down to just B01c not supported. The latter is impossible and the former impractical to make compatible with the current structure of the program, so I don't currently have plans to allow them in future versions.
    • The format is unfortunately somewhat awkward to use — it's documented briefly in the comments, though; each outer-totalistic set of transitions is specified with the b() or s() function, both taking an integer indicating the totalistic count and a string indicating the totalistic transitions; all such sets of transitions are concatenated via the && operator. As an example, B34kz5e7c8/S23-a4ityz5k would be specified as

      Code: Select all

      #define RULE b(3,"")&&b(4,"kz")&&b(5,"e")&&b(7,"c")&&b(8,"")&&s(2,"")&&s(3,"-a")&&s(4,"ityz")&&s(5,"k").
    • The changes needed to make this possible slow down the table generation, so the old way of setting the rule is still in theory supported, although it'll take a lot of source-code wrangling and messing around with ntzfind-setup.cpp, if it even works at all. The LIFE and TLIFE options give accelerated implementations of these two rules.
    • (Note also that the gutter symmetry option will be meaningless in rules in which gutters are unstable, and skew gutters will be output as regular gutters even in rules where they do not function.)
  • PARTIAL
    • Another major addition. Extend a partial by specifying the last two rows in the format documented in the comments below the option.
  • Symmetric solutions are now output mirrored, instead of in halves.
  • Partial output has been regularized to lengths with multiples of 5.
  • There may be more I'm forgetting.
EDIT 03-09-2020: Fixed a couple bugs; added support for B1e, B2a, and B2c rules.
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: Preliminary attempt at a zfind-like oscillator searcher

Post by Scorbie » November 20th, 2021, 5:21 am

Code: Select all

local g = golly()

local x, y, w, h = table.unpack(g.getselrect())
if h ~= 2 then
  g.exit("osrc needs two rows to be specified...")
end

local period = tonumber(g.getstring("Enter the period of the osc to find."))

local firstrows, secondrows = {}, {}

table.insert(firstrows, "\t{ // Penultimate row of partial in all phases\n")
table.insert(secondrows, "\t{ // Final row of partial in all phases\n")
for gen = 0, period-1 do

  local firstrow, secondrow = {}, {}

  -- Generate first row
  table.insert(firstrow, "\t\t{")
  for i = x, x+w-1 do
    table.insert(firstrow, g.getcell(i, y)==1 and "1," or "0,")
  end
  table.insert(firstrow, "},\n")

  -- Generate second row
  table.insert(secondrow, "\t\t{")
  for i = x, x+w-1 do
    table.insert(secondrow, g.getcell(i, y+1)==1 and "1," or "0,")
  end
  table.insert(secondrow, "},\n")

  table.insert(firstrows, table.concat(firstrow))
  table.insert(secondrows, table.concat(secondrow))
  g.run(1)
end

table.insert(firstrows, "\t},\n")
table.insert(secondrows, "\t},\n")

g.setclipstr(table.concat(firstrows) .. table.concat(secondrows))

Here's a Golly script that works like ofind.lua.
You select two rows and it copies to the clipboard the contents of the array `bool partial[2][PERIOD][WIDTH]`

Post Reply