TarRuleSrc

[islptng]

These scripts are (R1 NM 2-state)INT Rule searchers.

You can find version 1.5 in my sandbox.

TarRuleSrc 1.5

Version 2.2.4 (It's C++ so definitely it's not a Golly script):

Code: Select all

/*
 * TarRuleSrc2.cpp -- Search for rules.
 * Version 2.2.4
 *
 * islptng and EvinZL, 2025
 *
 * Thanks to FWKnightship for parseRLE(), ComparePattern(), and GridPtr.
 */

#include<iostream>
#include<fstream>
#include<cstring>
#include<string>
#include<random>
#include<bitset>
using namespace std;

const string Hensel[51] = { "0","1c","1e","2a","2c","2e","2i","2k","2n","3a","3c","3e","3i","3j","3k","3n","3q","3r","3y",
"4a","4c","4e","4i","4j","4k","4n","4q","4r","4t","4w","4y","4z","5a","5c","5e","5i","5j","5k","5n","5q","5r","5y",
"6a","6c","6e","6i","6k","6n","7c","7e","8" };
const int HenselCnt[9] = { 1,2,6,10,13,10,6,2,1 };
char NLookup[512] = {
	'\x00','\x01','\x02','\x03','\x01','\x04','\x03','\x0c','\x02','\x03','\x05','\x09','\x07','\x0f','\x0d','\x13',
	'\x00','\x01','\x02','\x03','\x01','\x04','\x03','\x0c','\x02','\x03','\x05','\x09','\x07','\x0f','\x0d','\x13',
	'\x02','\x07','\x05','\x0d','\x03','\x0f','\x09','\x13','\x06','\x11','\x0b','\x1b','\x11','\x16','\x1b','\x23',
	'\x02','\x07','\x05','\x0d','\x03','\x0f','\x09','\x13','\x06','\x11','\x0b','\x1b','\x11','\x16','\x1b','\x23',
	'\x01','\x04','\x07','\x0f','\x08','\x0a','\x10','\x19','\x03','\x0c','\x0d','\x13','\x10','\x19','\x1d','\x20',
	'\x01','\x04','\x07','\x0f','\x08','\x0a','\x10','\x19','\x03','\x0c','\x0d','\x13','\x10','\x19','\x1d','\x20',
	'\x07','\x12','\x0e','\x18','\x10','\x1e','\x1a','\x24','\x11','\x1c','\x17','\x26','\x1f','\x28','\x27','\x2a',
	'\x07','\x12','\x0e','\x18','\x10','\x1e','\x1a','\x24','\x11','\x1c','\x17','\x26','\x1f','\x28','\x27','\x2a',
	'\x02','\x07','\x06','\x11','\x07','\x12','\x11','\x1c','\x05','\x0d','\x0b','\x1b','\x0e','\x18','\x17','\x26',
	'\x02','\x07','\x06','\x11','\x07','\x12','\x11','\x1c','\x05','\x0d','\x0b','\x1b','\x0e','\x18','\x17','\x26',
	'\x05','\x0e','\x0b','\x17','\x0d','\x18','\x1b','\x26','\x0b','\x17','\x15','\x21','\x17','\x29','\x21','\x2b',
	'\x05','\x0e','\x0b','\x17','\x0d','\x18','\x1b','\x26','\x0b','\x17','\x15','\x21','\x17','\x29','\x21','\x2b',
	'\x03','\x0f','\x11','\x16','\x10','\x1e','\x1f','\x28','\x09','\x13','\x1b','\x23','\x1a','\x24','\x27','\x2a',
	'\x03','\x0f','\x11','\x16','\x10','\x1e','\x1f','\x28','\x09','\x13','\x1b','\x23','\x1a','\x24','\x27','\x2a',
	'\x0d','\x18','\x17','\x29','\x1d','\x25','\x27','\x2e','\x1b','\x26','\x21','\x2b','\x27','\x2e','\x2f','\x30',
	'\x0d','\x18','\x17','\x29','\x1d','\x25','\x27','\x2e','\x1b','\x26','\x21','\x2b','\x27','\x2e','\x2f','\x30',
	'\x01','\x08','\x07','\x10','\x04','\x0a','\x0f','\x19','\x07','\x10','\x0e','\x1a','\x12','\x1e','\x18','\x24',
	'\x01','\x08','\x07','\x10','\x04','\x0a','\x0f','\x19','\x07','\x10','\x0e','\x1a','\x12','\x1e','\x18','\x24',
	'\x03','\x10','\x0d','\x1d','\x0c','\x19','\x13','\x20','\x11','\x1f','\x17','\x27','\x1c','\x28','\x26','\x2a',
	'\x03','\x10','\x0d','\x1d','\x0c','\x19','\x13','\x20','\x11','\x1f','\x17','\x27','\x1c','\x28','\x26','\x2a',
	'\x04','\x0a','\x12','\x1e','\x0a','\x14','\x1e','\x22','\x0f','\x19','\x18','\x24','\x1e','\x22','\x25','\x2c',
	'\x04','\x0a','\x12','\x1e','\x0a','\x14','\x1e','\x22','\x0f','\x19','\x18','\x24','\x1e','\x22','\x25','\x2c',
	'\x0f','\x1e','\x18','\x25','\x19','\x22','\x24','\x2c','\x16','\x28','\x29','\x2e','\x28','\x2d','\x2e','\x31',
	'\x0f','\x1e','\x18','\x25','\x19','\x22','\x24','\x2c','\x16','\x28','\x29','\x2e','\x28','\x2d','\x2e','\x31',
	'\x03','\x10','\x11','\x1f','\x0f','\x1e','\x16','\x28','\x0d','\x1d','\x17','\x27','\x18','\x25','\x29','\x2e',
	'\x03','\x10','\x11','\x1f','\x0f','\x1e','\x16','\x28','\x0d','\x1d','\x17','\x27','\x18','\x25','\x29','\x2e',
	'\x09','\x1a','\x1b','\x27','\x13','\x24','\x23','\x2a','\x1b','\x27','\x21','\x2f','\x26','\x2e','\x2b','\x30',
	'\x09','\x1a','\x1b','\x27','\x13','\x24','\x23','\x2a','\x1b','\x27','\x21','\x2f','\x26','\x2e','\x2b','\x30',
	'\x0c','\x19','\x1c','\x28','\x19','\x22','\x28','\x2d','\x13','\x20','\x26','\x2a','\x24','\x2c','\x2e','\x31',
	'\x0c','\x19','\x1c','\x28','\x19','\x22','\x28','\x2d','\x13','\x20','\x26','\x2a','\x24','\x2c','\x2e','\x31',
	'\x13','\x24','\x26','\x2e','\x20','\x2c','\x2a','\x31','\x23','\x2a','\x2b','\x30','\x2a','\x31','\x30','\x32',
	'\x13','\x24','\x26','\x2e','\x20','\x2c','\x2a','\x31','\x23','\x2a','\x2b','\x30','\x2a','\x31','\x30','\x32' };
int HenselToOrder(string st)
{
	for (int i = 0; i < 51; i++)
	{
		if (Hensel[i] == st) return i;
	}
	return -1;
}

mt19937 rng(random_device{}());
/*
int randfactor = 0xdeadbeef - 0x5f3759df;
int rng()
{
	randfactor = rand();
	return rand();
}*/

int CondToOrder(int st)
{
	return NLookup[st];
}

struct Rule
{
	bool b[51];
	bool s[51];
	Rule() { for (int i = 0; i < 51; i++) { b[i] = false; s[i] = false; } }
	Rule(string st)
	{
		for (int i = 0; i < 51; i++) { b[i] = false; s[i] = false; }
		char currentNumber = '0';
		bool inMinus = false;
		bool inBirth = true;
		st += "S";
		for (int i = 0; i < st.size(); i++)
		{
			if ('0' <= st[i] && st[i] <= '8')
			{
				currentNumber = st[i];
				inMinus = false;
				if (st[i + 1] == '/' || st[i + 1] == 'S' || st[i + 1] == 's' || ('0' <= st[i + 1] && st[i + 1] <= '8'))
				{
					st[i] = '-';
				}
				else continue;
			}
			if (st[i] == 'S' || st[i] == 's') { inBirth = false; continue; }
			if (st[i] == 'B' || st[i] == 'b' || st[i] == '/') continue;
			if (st[i] == '-')
			{
				inMinus = true;
				for (int j = 0; j < 51; j++)
				{
					if (Hensel[j][0] == currentNumber)
						if (inBirth) b[j] = true;
						else s[j] = true;
				}
				continue;
			}
			string currenth = ""; currenth += currentNumber; currenth += st[i];
			int index = HenselToOrder(currenth);
			if (inBirth) b[index] = !inMinus;
			else s[index] = !inMinus;
		}
	}
	bool evolve(int conds) const
	{
		if (conds & 16) return s[CondToOrder(conds)];
		else return b[CondToOrder(conds)];
	}
};
string toString(Rule a)
{
	string res = "B";
	char currentNumber = 'a';
	for (int i = 0; i < 51; i++)
	{
		if (a.b[i])
		{
			if (currentNumber != Hensel[i][0])
			{
				res += Hensel[i][0];
				currentNumber = Hensel[i][0];
			}
			if (Hensel[i] != "0" && Hensel[i] != "8") res += Hensel[i][1];
		}
	}
	currentNumber = 'a';
	res += "/S";
	for (int i = 0; i < 51; i++)
	{
		if (a.s[i])
		{
			if (currentNumber != Hensel[i][0])
			{
				res += Hensel[i][0];
				currentNumber = Hensel[i][0];
			}
			if (Hensel[i] != "0" && Hensel[i] != "8") res += Hensel[i][1];
		}
	}
	return res;
}
Rule operator|(Rule a, Rule b)
{
	Rule res;
	for (int i = 0; i < 51; i++)
	{
		res.b[i] = a.b[i] || b.b[i];
		res.s[i] = a.s[i] || b.s[i];
	}
	return res;
}
Rule operator&(Rule a, Rule b)
{
	Rule res;
	for (int i = 0; i < 51; i++)
	{
		res.b[i] = a.b[i] && b.b[i];
		res.s[i] = a.s[i] && b.s[i];
	}
	return res;
}
bool operator==(Rule a, Rule b)
{
	for (int i = 0; i < 51; i++)
	{
		if (a.b[i] != b.b[i]) return false;
		if (a.s[i] != b.s[i]) return false;
	}
	return true;
}
int diff(Rule a, Rule b)
{
	int cnt = 0;
	for (int i = 0; i < 51; i++)
	{
		if (a.b[i] != b.b[i]) cnt++;
		if (a.s[i] != b.s[i]) cnt++;
	}
	return cnt;
}

Rule randomRule(Rule minrule, Rule maxrule)
{
	long long randb = (long long)rng() << 32 | rng();
	long long rands = (long long)rng() << 32 | rng();
	Rule res;
	for (int i = 0; i < 51; i++)
	{
		if (minrule.b[i]) res.b[i] = true;
		else if (!maxrule.b[i]) res.b[i] = false;
		else res.b[i] = (randb >> i & 0x01);
		if (minrule.s[i]) res.s[i] = true;
		else if (!maxrule.s[i]) res.s[i] = false;
		else res.s[i] = (rands >> i & 0x01);
	}
	return res;
}

const int GRIDSIZE = 64;
typedef bitset<GRIDSIZE> Grid[GRIDSIZE], *GridPtr;
const int PATTPOS = GRIDSIZE / 2 - 2;
// return false if the RLE is empty or represents an empty pattern, true otherwise.
// by FWKnightship and modified by islptng
bool parseRLE(const string RLE, GridPtr grid)
{
	int num = 0, start_x = PATTPOS, start_y = PATTPOS;
	int x = 0, y = 0;

	bool empty = 1;

	for (unsigned i = 0; i < RLE.size(); ++i)
	{
		char c = RLE[i];
		if (c == 'r')
		{
			start_y -= num / 2;
			if (start_y < 0)
			{
				cerr << "ERROR: RLE size (" << num
					<< ") is larger than grid size (" << num
					<< ").\n";
				exit(1);
			}
			num = 0;
		}
		else if (isdigit(c))
		{
			num = num * 10 + c - '0';
		}
		else if (isalpha(c))
		{
			if (c > 'A' && c <= 'Z')
			{
				cerr << "ERROR: State out of range, only 2 states are supported.\n";
				exit(1);
			}
			else if (c == 'b')
			{
				x += num == 0 ? 1 : num;
			}
			else if (c == 'o' || c <= 'C')
			{
				int state = c == 'o' ? 1 : c - 'A' + 1;

				for (int j = 0; j < (num == 0 ? 1 : num); ++j)
				{
					if (start_x + x >= GRIDSIZE)
					{
						cerr << "ERROR: RLE contains too large pattern.(x)\n";
						exit(1);
					}
					grid[start_x + x][start_y + y] = state;
					++x;
				}

				empty = 0;
			}
			num = 0;
		}
		else if (c == '.')
		{
			x += num == 0 ? 1 : num;
			num = 0;
		}
		else if (c == '$')
		{
			y += num == 0 ? 1 : num;
			x = 0;
			if (start_y + y >= GRIDSIZE)
			{
				std::cerr << "ERROR: RLE contains too large pattern.(y)\n";
				exit(1);
			}
			num = 0;
		}
		else if (c == '!')
		{
			break;
		}
		else if (isgraph(c) && c != '=' && c != ',')
		{
			std::cerr << "ERROR: Invalid character \'" << c << "\'.\n";
			exit(1);
		}
	}

	return !empty;
}
// by FWKnightship and modified by islptng and EvinZL
struct cell
{
	int x, y;
} aa[GRIDSIZE * GRIDSIZE], bb[GRIDSIZE * GRIDSIZE];
int ComparePattern_dx, ComparePattern_dy;
bool ComparePattern(GridPtr a, GridPtr b)
{
	int aaa = 0, bbb = 0;
	for (int i = 0; i < GRIDSIZE; ++i)
	{
		if (a[i].any())
			for (int j = 0; j < GRIDSIZE; ++j)
			{
				if (a[i][j] != 0)
				{
					aa[aaa].x = i;
					aa[aaa].y = j;
					++aaa;
				}
			}
		if (b[i].any())
			for (int j = 0; j < GRIDSIZE; ++j)
			{
				if (b[i][j] != 0)
				{
					bb[bbb].x = i;
					bb[bbb].y = j;
					++bbb;
				}
			}
	}
	if (aaa != bbb) return 0;
	if (aaa == 0) return 1;
	ComparePattern_dx = bb[0].x - aa[0].x;
	ComparePattern_dy = bb[0].y - aa[0].y;
	for (int i = 0; i < aaa; ++i)
	{
		if (bb[i].x - aa[i].x != ComparePattern_dx) return 0;
		if (bb[i].y - aa[i].y != ComparePattern_dy) return 0;
	}
	return 1;
}

void gridcpy(GridPtr from, GridPtr to)
{
	for (int i = 0; i < GRIDSIZE; i++) to[i] = from[i];
}
int gridgcl(GridPtr grid, int x, int y)
{
	if (x < 0 || x >= GRIDSIZE) return false;
	if (y < 0 || y >= GRIDSIZE) return false;
	return grid[x][y];
}
const int deltax[] = { -1,-1,0,1,1,1,0,-1 };
const int deltay[] = { 0,1,1,1,0,-1,-1,-1 };
// return false if pattern touches the boundary or becomes empty.
uint64_t shr(uint64_t x, int s) {
	return (s > 0) ? (x >> s) : (x << -s);
}
bool evolve(GridPtr from, GridPtr to, Rule r)
{
	bool empty = true;
	for (int x = 0; x < GRIDSIZE; x++)
	{
		to[x].reset();
		if ((x == 0 ? false : from[x-1].any()) || from[x].any() || ((x == GRIDSIZE-1) ? false : from[x+1].any()))
			for (int y = 0; y < GRIDSIZE; y++)
			{
				int n0 = shr(x ==          0 ? 0ull : from[x - 1].to_ullong(), y-1) & 7;
				int n1 = shr(                         from[x    ].to_ullong(), y-1) & 7;
				int n2 = shr(x == GRIDSIZE-1 ? 0ull : from[x + 1].to_ullong(), y-1) & 7;
				int neighbors = n0 | (n1 << 3) | (n2 << 6);
				to[x][y] = r.evolve(neighbors);
				if (to[x][y])
				{
					empty = false;
					if (x == 0 || x == GRIDSIZE - 1 || y == 0 || y == GRIDSIZE - 1) return false;
				}
			}
	}
	return !empty;
}
Rule evolveRulespace_min, evolveRulespace_max;
void evolve_rulespace(GridPtr from, GridPtr to, Rule r)
{
	evolveRulespace_min = Rule("B/S");
	evolveRulespace_max = Rule("B012345678/S012345678");
	for (int x = 0; x < GRIDSIZE; x++)
		for (int y = 0; y < GRIDSIZE; y++)
		{
			int n0 = shr(x ==            0 ? 0ull : from[x - 1].to_ullong(), y - 1) & 7;
			int n1 = shr(                           from[x    ].to_ullong(), y - 1) & 7;
			int n2 = shr(x == GRIDSIZE - 1 ? 0ull : from[x + 1].to_ullong(), y - 1) & 7;
			int neighbors = n0 | (n1 << 3) | (n2 << 6);
			to[x][y] = r.evolve(neighbors);
			if (to[x][y])
				if (from[x][y]) evolveRulespace_min.s[CondToOrder(neighbors)] = true;
				else evolveRulespace_min.b[CondToOrder(neighbors)] = true;
			else
				if (from[x][y]) evolveRulespace_max.s[CondToOrder(neighbors)] = false;
				else evolveRulespace_max.b[CondToOrder(neighbors)] = false;
		}
}
Rule calcRulespace_min, calcRulespace_max;
void calc_rulespace(GridPtr grid, GridPtr temp, Rule r, int gens)
{
	calcRulespace_min = Rule("B/S");
	calcRulespace_max = Rule("B012345678/S012345678");
	for (int g = 0; g < gens; g++)
	{
		evolve_rulespace(grid, temp, r);
		calcRulespace_min = calcRulespace_min | evolveRulespace_min;
		calcRulespace_max = calcRulespace_max & evolveRulespace_max;
		gridcpy(temp, grid);
	}
}

Grid startpatt, endpatt, grid, grid2;

int minx, miny, maxx, maxy, minp, maxp;
string minrstr, maxrstr;
Rule minr, maxr;
string startrle, endrle;
bool readrequire()
{
	string strtemp;
	ifstream fin;
	fin.open("requirements.txt");
	fin >> strtemp >> minrstr >> maxrstr;
	if (strtemp != "r:") { cerr << "Missing R"; return false; }
	fin >> strtemp >> minp >> maxp;
	if (strtemp != "p:") { cerr << "Missing P"; return false; }
	if (maxp == -1) { cerr << ""; return false; }
	fin >> strtemp >> minx >> maxx;
	if (strtemp != "x:") { cerr << "Missing X"; return false; }
	fin >> strtemp >> miny >> maxy;
	if (strtemp != "y:") { cerr << "Missing Y"; return false; }
	fin >> strtemp; if (strtemp != "==start") { cerr << "Missing start pattern"; return false; }
	strtemp = "?"; startrle = "";
	while (strtemp[0] != '=')
	{
		if (strtemp != "?") startrle += strtemp;
		fin >> strtemp;
	}
	if (strtemp == "==end")
	{
		endrle = startrle;
		fin.close();
		return true;
	}
	if (strtemp != "==target") { cerr << "Missing end tag or target pattern"; return false; }
	strtemp = "?"; endrle = "";
	while (strtemp[0] != '=')
	{
		if (strtemp != "?") endrle += strtemp;
		fin >> strtemp;
	}
	if (strtemp != "==end") { cerr << "Missing end tag"; return false; }
	fin.close();
	return true;
}

Rule rresults[5000]; int cntres = 0;
bool inrange(int n, int from, int to)
{
	if (n < from && from != -1) return false;
	if (n > to && to != -1) return false;
	return true;
}
void swapdxy()
{
	if (ComparePattern_dx < 0) ComparePattern_dx *= -1;
	if (ComparePattern_dy < 0) ComparePattern_dy *= -1;
	if (ComparePattern_dx < ComparePattern_dy)
	{
		int t = ComparePattern_dx;
		ComparePattern_dx = ComparePattern_dy;
		ComparePattern_dy = t;
	}
}
void initres()
{
	ofstream fout;
	fout.open("TarRuleSrc_result.txt");
	fout << "TarRuleSrc Results:\n\n";
	fout.close();
}
void putres(int dx, int dy, int period, int optn, Rule r, Rule r2)
{
	ofstream fout;
	fout.open("TarRuleSrc_result.txt", ios::app);
	if (startrle == endrle)
	{
		if (dx == dy && dy == 0)
			fout << "           |  p";
		else if (dy == 0) fout << "      orth | " << dx << "c/";
		else if (dy == dx) fout << "   diag    | " << dx << "c/";
		else              fout << "obli       |(" << dx << "," << dy << ")c/";
	}
	else fout << "dx=" << dx << "\tdy=" << dy << "\tT=";
	fout << period << "\t | space 2^" << optn << "\t | " << toString(r) << " " << toString(r2) << endl;
	fout.close();
}
bool checkfound(Rule r)
{
	for (int i = 0; i < cntres; i++)
	{
		if (rresults[i] == r) return true;
	}
	return false;
}

void printGrid(GridPtr g) {
	for (int y = 0; y < GRIDSIZE; y++) {
		for (int x = 0; x < GRIDSIZE; x++)
			std::cout << (g[y][x] ? '.' : ' ');
		std::cout << "\n";
	}
}

int main()
{
	if (!readrequire()) return -1;
	minr = Rule(minrstr);
	maxr = Rule(maxrstr);
	if (!parseRLE(startrle, startpatt)) return -1;
	if (!parseRLE(endrle, endpatt)) return -1;

	initres();
	int cnt = 0;
	while (true)
	{
		Rule r = randomRule(minr, maxr);
		gridcpy(startpatt, grid);
		int gen = 0;
		while (gen <= maxp)
		{
			gen++;
			bool flag = evolve(grid, grid2, r);
			gridcpy(grid2, grid);
			if (!flag) break;
			if (gen < minp) continue;
			flag = ComparePattern(grid, endpatt);
			if (flag)
			{
				swapdxy();
				if (!inrange(gen, minp, maxp)) break;
				if (!inrange(ComparePattern_dx, minx, maxx)) break;
				if (!inrange(ComparePattern_dy, miny, maxy)) break;
				gridcpy(startpatt, grid);
				calc_rulespace(grid, grid2, r, gen);
				Rule tmir = minr | calcRulespace_min;
				if (checkfound(tmir)) break;
				Rule tmar = maxr & calcRulespace_max;
				putres(ComparePattern_dx, ComparePattern_dy, gen, diff(tmir, tmar), tmir, tmar);
				rresults[cntres] = tmir;
				cntres++;
				break;
			}
		}
		cnt++;
		if (cnt % 16384 == 0) cout << cnt << " rules tested, " << cntres << " results found\n";
		if(cntres == 5000)
		{
			cout << "5000 results found. Terminating..." << endl;
			break;
		}
	}
	return 0;
}

Write requirements.txt before you start this program. Format:

Code: Select all

r: <minrule> <maxrule>
p: <smallest period> <biggest period>
x: <smallest dx> <biggest dx, or -1 if unlimited>
y: <smallest dy> <biggest dy, or -1 if unlimited>
==start
<RLE of the start pattern>
==target
<RLE of the target pattern, can be omitted together with "==target" tag>
==end

For example, I want to search for the rules where T-tetromino is a spaceship with period lower than 30:

Code: Select all

r: B/S B2-a345678/S12345678
p: 1 30
x: 1 -1
y: 0 -1
==start
bo$3o!
==end

[EvinZL]

Certainly an important factor in the speed difference is the speed of evolution. Golly internally uses bit tricks and a big lookup table to evolve 4x4 squares at a time. I modified TarRuleSrc2 by using a big lookup table and no string to map neighborhood configurations into Hensel indices. Under -O3 this consistently reaches over 10k rules/sec and I have gotten a run of 30k rules/sec at one point. For some reason it's a lot slower on Windows.

Code: Select all

/*
 * TarRuleSrc2e.cpp -- Search for rules.
 * This is a modification of the 2nd version of TarRuleSrc.
 *
 * EvinZL, 2025
 * based on
 * islptng, 2025
 *
 * Thanks to FWKnightship for parseRLE(), ComparePattern(), and GridPtr.
 */

#include<iostream>
#include<fstream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<ctime>
using namespace std;

const string Hensel[51] = {"0","1c","1e","2a","2c","2e","2i","2k","2n","3a","3c","3e","3i","3j","3k","3n","3q","3r","3y",
"4a","4c","4e","4i","4j","4k","4n","4q","4r","4t","4w","4y","4z","5a","5c","5e","5i","5j","5k","5n","5q","5r","5y",
"6a","6c","6e","6i","6k","6n","7c","7e","8"};
char NLookup[256] = {
    '\x00','\x01','\x02','\x03','\x01','\x04','\x03','\x0c','\x02','\x07','\x05','\x0d','\x03','\x0f','\x09','\x13',
    '\x01','\x08','\x07','\x10','\x04','\x0a','\x0f','\x19','\x03','\x10','\x0d','\x1d','\x0c','\x19','\x13','\x20',
    '\x02','\x07','\x06','\x11','\x07','\x12','\x11','\x1c','\x05','\x0e','\x0b','\x17','\x0d','\x18','\x1b','\x26',
    '\x03','\x10','\x11','\x1f','\x0f','\x1e','\x16','\x28','\x09','\x1a','\x1b','\x27','\x13','\x24','\x23','\x2a',
    '\x01','\x04','\x07','\x0f','\x08','\x0a','\x10','\x19','\x07','\x12','\x0e','\x18','\x10','\x1e','\x1a','\x24',
    '\x04','\x0a','\x12','\x1e','\x0a','\x14','\x1e','\x22','\x0f','\x1e','\x18','\x25','\x19','\x22','\x24','\x2c',
    '\x03','\x0f','\x11','\x16','\x10','\x1e','\x1f','\x28','\x0d','\x18','\x17','\x29','\x1d','\x25','\x27','\x2e',
    '\x0c','\x19','\x1c','\x28','\x19','\x22','\x28','\x2d','\x13','\x24','\x26','\x2e','\x20','\x2c','\x2a','\x31',
    '\x02','\x03','\x05','\x09','\x07','\x0f','\x0d','\x13','\x06','\x11','\x0b','\x1b','\x11','\x16','\x1b','\x23',
    '\x07','\x10','\x0e','\x1a','\x12','\x1e','\x18','\x24','\x11','\x1f','\x17','\x27','\x1c','\x28','\x26','\x2a',
    '\x05','\x0d','\x0b','\x1b','\x0e','\x18','\x17','\x26','\x0b','\x17','\x15','\x21','\x17','\x29','\x21','\x2b',
    '\x0d','\x1d','\x17','\x27','\x18','\x25','\x29','\x2e','\x1b','\x27','\x21','\x2f','\x26','\x2e','\x2b','\x30',
    '\x03','\x0c','\x0d','\x13','\x10','\x19','\x1d','\x20','\x11','\x1c','\x17','\x26','\x1f','\x28','\x27','\x2a',
    '\x0f','\x19','\x18','\x24','\x1e','\x22','\x25','\x2c','\x16','\x28','\x29','\x2e','\x28','\x2d','\x2e','\x31',
    '\x09','\x13','\x1b','\x23','\x1a','\x24','\x27','\x2a','\x1b','\x26','\x21','\x2b','\x27','\x2e','\x2f','\x30',
    '\x13','\x20','\x26','\x2a','\x24','\x2c','\x2e','\x31','\x23','\x2a','\x2b','\x30','\x2a','\x31','\x30','\x32'};
int HenselToOrder(string st)
{
	for(int i = 0; i < 51; i++)
	{
		if(Hensel[i] == st) return i;
	}
	return -1;
}

int rng()
{
	static unsigned long long x = 1;
    x ^= x >> 12;
    x ^= x << 25;
    x ^= x >> 27;
    return (x * 0x2545f4914f6cdd1dull) >> 32;
}

int CondToOrder(int st)
{
	return NLookup[st];
}

struct Rule
{
	bool b[51];
	bool s[51];
	Rule(){for(int i = 0; i < 51; i++) { b[i] = false; s[i] = false; }}
	Rule(string st)
	{
		for(int i = 0; i < 51; i++) { b[i] = false; s[i] = false; }
		char currentNumber = '0';
		bool inMinus = false;
		bool inBirth = true;
		st += "S";
		for(int i = 0; i < st.size(); i++)
		{
			if('0' <= st[i] && st[i] <= '8')
			{
				currentNumber = st[i];
				inMinus = false;
				if(st[i+1] == '/' || st[i+1] == 'S' || st[i+1] == 's' || ('0' <= st[i+1] && st[i+1] <= '8'))
				{
					st[i] = '-';
				}
				else continue;
			}
			if(st[i] == 'S' || st[i] == 's'){ inBirth = false; continue;}
			if(st[i] == 'B' || st[i] == 'b' || st[i] == '/') continue;
			if(st[i] == '-')
			{
				inMinus = true;
				for(int j = 0; j < 51; j++)
				{
					if(Hensel[j][0] == currentNumber)
					if(inBirth) b[j] = true;
					else s[j] = true;
				}
				continue;
			}
			string currenth = ""; currenth += currentNumber; currenth += st[i];
			int index = HenselToOrder(currenth);
			if(inBirth) b[index] = !inMinus;
			else s[index] = !inMinus;
		}
	}
	bool evolve(int conds, bool self) const
	{
		if(self) return s[CondToOrder(conds)];
		else return b[CondToOrder(conds)];
	}
};
string toString(Rule a)
{
	string res = "B";
	char currentNumber = 'a';
	for(int i = 0; i < 51; i++)
	{
		if(a.b[i])
		{
			if(currentNumber != Hensel[i][0])
			{
				res += Hensel[i][0];
				currentNumber = Hensel[i][0];
			}
			if(Hensel[i] != "0" && Hensel[i] != "8") res += Hensel[i][1];
		}
	}
	res += "/S";
	for(int i = 0; i < 51; i++)
	{
		if(a.s[i])
		{
			if(currentNumber != Hensel[i][0])
			{
				res += Hensel[i][0];
				currentNumber = Hensel[i][0];
			}
			if(Hensel[i] != "0" && Hensel[i] != "8") res += Hensel[i][1];
		}
	}
	return res;
}
Rule operator|(Rule a,Rule b)
{
	Rule res;
	for(int i = 0; i < 51; i++)
	{
		res.b[i] = a.b[i] || b.b[i];
		res.s[i] = a.s[i] || b.s[i];
	}
	return res;
}
bool operator==(Rule a,Rule b)
{
	for(int i = 0; i < 51; i++)
	{
		if(a.b[i] != b.b[i]) return false;
		if(a.s[i] != b.s[i]) return false;
	}
	return true;
}

Rule randomRule(Rule minrule, Rule maxrule)
{
	Rule res;
	for(int i = 0; i < 51; i++)
	{
		if(minrule.b[i]) res.b[i] = true;
		else if(!maxrule.b[i]) res.b[i] = false;
		else res.b[i] = (rng() % 8 > 4);
		if(minrule.s[i]) res.b[i] = true;
		else if(!maxrule.s[i]) res.s[i] = false;
		else res.s[i] = (rng() % 8 > 4);
	}
	return res;
}

const int GRIDSIZE = 64;
typedef bool Grid[GRIDSIZE][GRIDSIZE], (*GridPtr)[GRIDSIZE];
const int PATTPOS = GRIDSIZE / 2 - 2;
// return false if the RLE is empty or represents an empty pattern, true otherwise.
// by FWKnightship and modified by islptng
bool parseRLE(const string RLE, GridPtr grid)
{
	int num = 0, start_x = PATTPOS, start_y = PATTPOS;
	int x = 0, y = 0;
	
	bool empty = 1;
	
	for (unsigned i = 0; i < RLE.size(); ++i)
	{
		char c = RLE[i];
		if (c == 'r')
		{
			start_y -= num/2;
			if (start_y < 0)
			{
				cerr << "ERROR: RLE size (" << num
				 << ") is larger than grid size (" << num
				  << ").\n";
				exit(1);
			}
			num = 0;
		}
		else if (isdigit(c))
		{
			num = num * 10 + c - '0';
		}
		else if (isalpha(c))
		{
			if (c > 'A' && c <= 'Z')
			{
				cerr << "ERROR: State out of range, only 2 states are supported.\n";
				exit(1);
			}
			else if (c == 'b')
			{
				x += num == 0 ? 1 : num;
			}
			else if (c == 'o' || c <= 'C')
			{
				int state = c == 'o' ? 1 : c - 'A' + 1;
				
				for (int j = 0; j < (num == 0 ? 1 : num); ++j)
				{
					if (start_x + x >= GRIDSIZE)
					{
						cerr << "ERROR: RLE contains too large pattern.(x)\n";
						exit(1);
					}
					grid[start_x + x][start_y + y] = state;
					++x;
				}
				
				empty = 0;
			}
			num = 0;
		}
		else if (c == '.')
		{
			x += num == 0 ? 1 : num;
			num = 0;
		}
		else if (c == '$')
		{
			y += num == 0 ? 1 : num;
			x = 0;
			if (start_y + y >= GRIDSIZE)
			{
				std::cerr << "ERROR: RLE contains too large pattern.(y)\n";
				exit(1);
			}
			num = 0;
		}
		else if (c == '!')
		{
			break;
		}
		else if (isgraph(c) && c != '=' && c != ',')
		{
			std::cerr << "ERROR: Invalid character \'" << c << "\'.\n";
			exit(1);
		}
	}
	
	return !empty;
}
// by FWKnightship and modified by islptng
struct cell
{
	int x, y;
} aa[GRIDSIZE * GRIDSIZE], bb[GRIDSIZE * GRIDSIZE];
int ComparePattern_dx, ComparePattern_dy;
bool ComparePattern(GridPtr a, GridPtr b)
{
	int aaa = 0, bbb = 0;
	for (int i = 0; i < GRIDSIZE; ++i)
	{
		for (int j = 0; j < GRIDSIZE; ++j)
		{
			if (a[i][j] != 0)
			{
				aa[aaa].x = i;
				aa[aaa].y = j;
				++aaa;
			}
			if (b[i][j] != 0)
			{
				bb[bbb].x = i;
				bb[bbb].y = j;
				++bbb;
			}
		}
	}
	if (aaa != bbb) return 0;
	if (aaa == 0) return 1;
	ComparePattern_dx = bb[0].x - aa[0].x;
	ComparePattern_dy = bb[0].y - aa[0].y;
	for (int i = 0; i < aaa; ++i)
	{
		if (bb[i].x - aa[i].x != ComparePattern_dx) return 0;
		if (bb[i].y - aa[i].y != ComparePattern_dy) return 0;
	}
	return 1;
}

void gridcpy(GridPtr from, GridPtr to)
{
	for(int x = 0; x < GRIDSIZE; x++)
	for(int y = 0; y < GRIDSIZE; y++)
		to[x][y] = from[x][y];
}
bool gridgcl(GridPtr grid, int x, int y)
{
	if(x < 0 || x >= GRIDSIZE) return false;
	if(y < 0 || y >= GRIDSIZE) return false;
	return grid[x][y];
}
const int deltax[] = {-1,-1,0,1,1,1,0,-1};
const int deltay[] = {0,1,1,1,0,-1,-1,-1};
// return false if pattern touches the boundary or becomes empty.
bool evolve(GridPtr from, GridPtr to, Rule r)
{
	bool empty = true;
	for(int x = 0; x < GRIDSIZE; x++)
	for(int y = 0; y < GRIDSIZE; y++)
	{
		int neighbors = 0;
		for(int i = 0; i < 8; i++)
			neighbors = (neighbors << 1) | gridgcl(from, x+deltax[i], y+deltay[i]);
		to[x][y] = r.evolve(neighbors,from[x][y]);
		if(to[x][y])
		{
			empty = false;
			if(x == 0 || x == GRIDSIZE-1 || y == 0 || y == GRIDSIZE-1) return false;
		}
	}
	return !empty;
}
Rule evolve_minrule(GridPtr from, GridPtr to, Rule r)
{
	Rule res;
	for(int x = 0; x < GRIDSIZE; x++)
	for(int y = 0; y < GRIDSIZE; y++)
	{
		int neighbors = 0;
		for(int i = 0; i < 8; i++)
			neighbors = (neighbors << 1) | gridgcl(from, x+deltax[i], y+deltay[i]);
		to[x][y] = r.evolve(neighbors,from[x][y]);
		if(to[x][y])
			if(from[x][y]) res.s[CondToOrder(neighbors)] = true;
			else res.b[CondToOrder(neighbors)] = true;
	}
	return res;
}
Rule calc_minrule(GridPtr grid, GridPtr temp, Rule r, int gens)
{
	Rule res;
	for(int g = 0; g < gens; g++)
	{
		res = res | evolve_minrule(grid, temp, r);
		gridcpy(temp, grid);
	}
	return res;
}

bool startpatt[GRIDSIZE][GRIDSIZE], endpatt[GRIDSIZE][GRIDSIZE], grid[GRIDSIZE][GRIDSIZE], grid2[GRIDSIZE][GRIDSIZE];

int minx, miny, maxx, maxy, minp, maxp;
string minrstr, maxrstr;
Rule minr, maxr;
string startrle, endrle;
bool readrequire()
{
	string strtemp;
	ifstream fin;
	fin.open("requirements.txt");
	fin >> strtemp >> minrstr >> maxrstr;
	if(strtemp != "r:") {cerr << "Missing R"; return false;}
	fin >> strtemp >> minp >> maxp;
	if(strtemp != "p:") {cerr << "Missing P"; return false;}
	if(maxp == -1) {cerr << ""; return false;}
	fin >> strtemp >> minx >> maxx;
	if(strtemp != "x:") {cerr << "Missing X"; return false;}
	fin >> strtemp >> miny >> maxy;
	if(strtemp != "y:") {cerr << "Missing Y"; return false;}
	fin >> strtemp; if(strtemp != "==start") {cerr << "Missing start pattern"; return false;}
	strtemp = "?"; startrle = "";
	while(strtemp[0] != '=')
	{
		if(strtemp != "?") startrle += strtemp;
		fin >> strtemp;
	}
	if(strtemp == "==end")
	{
		endrle = startrle;
		fin.close();
		return true;
	}
	if(strtemp != "==target") {cerr << "Missing end tag or target pattern"; return false;}
	strtemp = "?"; endrle = "";
	while(strtemp[0] != '=')
	{
		if(strtemp != "?") endrle += strtemp;
		fin >> strtemp;
	}
	if(strtemp != "==end") {cerr << "Missing end tag"; return false;}
	fin.close();
	return true;
}

Rule rresults[5000]; int cntres = 0;
bool inrange(int n, int from, int to)
{
	if(n < from && from != -1) return false;
	if(n > to && to != -1) return false;
	return true;
}
void swapdxy()
{
	if(ComparePattern_dx < ComparePattern_dy)
	{
		int t = ComparePattern_dx;
		ComparePattern_dx = ComparePattern_dy;
		ComparePattern_dy = t;
	}
}
void initres()
{
	ofstream fout;
	fout.open("TarRuleSrc_result.txt");
	fout << "TarRuleSrc Results:\n\n";
	fout.close();
}
void putres(int dx, int dy, int period, Rule r)
{
	ofstream fout;
	fout.open("TarRuleSrc_result.txt", ios::app);
	if(startrle == endrle)
	{
		     if(dx == dy && dy == 0)
		                  fout << "           |  p";
		else if(dy ==  0) fout << "      orth | " << dx << "c/";
		else if(dy == dx) fout << "   diag    | " << dx << "c/";
		else              fout << "obli       |(" << dx << "," << dy << ")c/";
	}
	else fout << "dx=" << dx << "\tdy=" << dy << "\tT=";
	fout << period << "\t | " << toString(r) << endl;
	fout.close();
}
bool checkfound(Rule r)
{
	for(int i = 0; i < cntres; i++)
	{
		if(rresults[i] == r) return true;
	}
	return false;
}

int main()
{
	if(!readrequire()) return -1;
	minr = Rule(minrstr);
	maxr = Rule(maxrstr);
	if(!parseRLE(startrle,startpatt)) return -1;
	if(!parseRLE(endrle,endpatt)) return -1;

	initres();
	int cnt = 0;
	while(true)
	{
		Rule r = randomRule(minr,maxr);
		gridcpy(startpatt,grid);
		int gen = 0;
		while(gen <= maxp)
		{
			gen++;
			bool flag = evolve(grid,grid2,r);
			gridcpy(grid2,grid);
			if(!flag) break;
			flag = ComparePattern(grid,endpatt);
			if(flag)
			{
				swapdxy();
				if(!inrange(gen,minp,maxp)) break;
				if(!inrange(ComparePattern_dx,minx,maxx)) break;
				if(!inrange(ComparePattern_dy,miny,maxy)) break;
				gridcpy(startpatt,grid);
				Rule mr = minr | calc_minrule(grid,grid2,r,gen);
				if(checkfound(mr)) break;
				putres(ComparePattern_dx,ComparePattern_dy,gen,mr);
				rresults[cntres] = mr;
				cntres++;
				break;
			}
		}
		cnt++;
		if(cnt % 512 == 0) cout << cnt << " rules tested, " << cntres << " results found\n";
	}
	return 0;
}

[islptng]

Certainly an important factor in the speed difference is the speed of evolution. Golly internally uses bit tricks and a big lookup table to evolve 4x4 squares at a time. I modified TarRuleSrc2 by using a big lookup table and no string to map neighborhood configurations into Hensel indices. Under -O3 this consistently reaches over 10k rules/sec and I have gotten a run of 30k rules/sec at one point. For some reason it's a lot slower on Windows.

Wow, Impressive! But I'm sure it can be more optimized.

Quoting my private messages to FWKnightship:

用一个列表或者vector存储细胞,节省算力,并且网格无限大,不然64x64的格子要算4096次还有限;
Use a list or vector to store cells, this speeds up the evolution, and the grid becomes infinite; In a 64x64 grid, however, it needs to calculate 4096 times and the grid is still finite

感谢你的建议，我已经在新脚本中使用vector存储每个非0细胞的位置和状态，每次只计算图形长宽+2那么大的地方，
Thank you for your advice. I have used vector to store the positions and states of all non-zero cells, and each time it only calculates in the pattern's bounding box +2 cells,

果然效率很高。最大步数150步时大概两秒就能随机10000个规则。
Of course, it's efficient. When the maxstep is set to 50, it runs 10k rules in 2 sec.

...

python+Golly在处理大图形时有优势（因为Golly的算法好），但是小图形还是C++脚本有优势。
Python+Golly has the advantage when calculating big patterns (for that Golly uses an efficient algorithm), but for small patterns, C++ scripts are better.

EDIT: Looks like your rng() function didn't work properly. I'm using my good, old thing:

Code: Select all

int randfactor = 0xdeadbeef - 0x5f3759df;
int rng()
{ 
	randfactor = rand();
	return rand();
}

int main()
{
	srand(time(0)^randfactor);

EDIT 2: I optimized my randomrule function:

Code: Select all

Rule randomRule(Rule minrule, Rule maxrule)
{
	long long randb = (long long)rand() << 32 | rand();
	long long rands = (long long)rand() << 32 | rand();
	Rule res;
	for(int i = 0; i < 51; i++)
	{
		if(minrule.b[i]) res.b[i] = true;
		else if(!maxrule.b[i]) res.b[i] = false;
		else res.b[i] = (randb >> i & 0x01);
		if(minrule.s[i]) res.b[i] = true;
		else if(!maxrule.s[i]) res.s[i] = false;
		else res.s[i] = (rands >> i & 0x01);
	}
	return res;
}

EDIT 3:

Did they give you a permission to post their messages?

Well, islptng, I don't want to ask you to delete these quote this time, but please don't do it next time.
(These are private messages between him and me, not anyone else.)

Please don't post direct/private messages without explicit permission from the person who sent the messages. The forum rule 1b says

Do not pry for others' personal information or post it without their permission.

Sorry. I didn't know that this counts as personal information (Now I know that and will never do it again.)
属于是教我做人了这

EDIT 4: Updated to v2.1, and merged with EvinZL's v2e! Congratulations!

[confocaloid]

Did they give you a permission to post their messages?

[...] Quoting my private messages [...]

[FWKnightship]

Did they give you a permission to post their messages?

Well, islptng, I don't want to ask you to delete these quote this time, but please don't do it next time.
(These are private messages between him and me, not anyone else.)

[confocaloid]

Please don't post direct/private messages without explicit permission from the person who sent the messages. The forum rule 1b says

Do not pry for others' personal information or post it without their permission.

[islptng]

I wonder why v1 returns 7 results for this requirement within 10240 rules, but v2 returns nothing in 40k rules:

Code: Select all

r: B2c3a5i/S2a3e B2ceikn3acejknqry45678/S12acikn3acejknqry4acejknqrtwyz5678
p: 1 30
x: 1 -1
y: 0 -1
==start
obo$4o!
==end

EDIT: There's no much difference on algorithms, but it seems that 1.5 runs 5x more efficiently (time not considered). I wonder why.
v1 returns 20 results in 4096 rules, but v2 returns only 40 in 40960.

EDIT: Sometimes v2 is more powerful than v1, when I used a require for SMOS. I ran a quick 3-min search and it returns 59 results:

Code: Select all

TarRuleSrc Results:

   diag    | 3c/22	 | space 2^31	 | B2e3aceijk5cnq6a/S1e2acen3ceij5c6ace
   diag    | 3c/26	 | space 2^17	 | B2ek3aceijk5aqr6ce/S1e2acei3ei5acenqy6c
   diag    | 3c/26	 | space 2^23	 | B2ek3aceijk5jkq6c/S1e2aceik3ei5aeqr6c
   diag    | 5c/32	 | space 2^22	 | B2en3aei5ikn6c/S1ce2aceik3eijk5aejr6acik
   diag    | 2c/19	 | space 2^30	 | B2ekn3aceijk5inq/S1e2acn3ceij5ajn6ac
   diag    | 2c/32	 | space 2^24	 | B2e3aei5aeijknr6c/S1ce2acekn3ei5ny6ceik
   diag    | 2c/15	 | space 2^34	 | B2en3aceij5acey/S1e2acein3eij5c6ac
   diag    | 2c/17	 | space 2^44	 | B2e3acijk5an/S1e2aeikn3ceik6c
   diag    | 1c/20	 | space 2^36	 | B2ek3aceij5cknq/S1ce2ai3ei5kn6c
   diag    | 1c/17	 | space 2^32	 | B2e3aeijk5acijnr6ak/S1ce2acikn3ei5kn6ac
   diag    | 1c/12	 | space 2^51	 | B2n3aceij6a/S1ce2acein3eik6c
   diag    | 3c/22	 | space 2^21	 | B2ekn3acijk5ay6e/S1e2acikn3ceijk5aq6c
   diag    | 1c/14	 | space 2^33	 | B2ekn3acijk5cq/S1e2akn3eik5ajr6c
   diag    | 1c/42	 | space 2^10	 | B2ekn3aceijk5ceqr6ac/S2aceik3ceij5acejqr6ac
   diag    | 1c/34	 | space 2^20	 | B2ekn3aeijk5kq6ae/S1e2ack3eij5ae6c
   diag    | 1c/15	 | space 2^45	 | B2ek3aijk5inq/S1ce2aeik3ceik5y6c
   diag    | 3c/24	 | space 2^30	 | B2k3aeijk5aqy6k/S1c2acekn3ceik5nqy6ck
   diag    | 1c/21	 | space 2^30	 | B2ek3aij5ceijn/S1e2acikn3eijk5en6c
   diag    | 1c/49	 | space 2^7	 | B2ekn3aceij5acijq6acik/S1ce2ai3eij5cry6cei
   diag    | 1c/15	 | space 2^38	 | B2en3aceijk5i6ce/S1ce2aeikn3ceij5j6ac
   diag    | 1c/24	 | space 2^33	 | B2ekn3aceik5aik/S1ce2acik3eijk5cejr6c
   diag    | 1c/18	 | space 2^42	 | B2ekn3aijk5k6ci/S1e2acik3ei5er6c
   diag    | 1c/15	 | space 2^48	 | B2e3acij5n/S1e2aeik3ei5n6c
   diag    | 2c/22	 | space 2^23	 | B2ek3aceij5ijkqry/S1e2aikn3ei5cery6ce
   diag    | 1c/27	 | space 2^25	 | B2ek3aeijk5jny6e/S1e2aikn3eik5cenr6c
   diag    | 3c/27	 | space 2^38	 | B2e3aijk5eknqy/S1ce2acen3ceijk5k6c
   diag    | 1c/15	 | space 2^44	 | B2ek3aij5ackny/S1c2ae3ei6c
   diag    | 1c/20	 | space 2^28	 | B2ek3aceij5acjn6e/S2aceik3ceik5acn6c
   diag    | 1c/31	 | space 2^32	 | B2ek3aceik5jn6a/S1e2acein3eij5ry6c
   diag    | 1c/17	 | space 2^33	 | B2e3aeij5ackn6ek/S1ce2aek3ceijk5ejkn6c
   diag    | 1c/15	 | space 2^50	 | B2en3acijk5c/S1e2aeik3ceij5j6c
   diag    | 2c/23	 | space 2^20	 | B2ek3aeij5aknqy6ac/S1ce2acikn3cei5c6ck
   diag    | 1c/16	 | space 2^52	 | B2ek3ai5n/S1ce2acei3eik6c
   diag    | 3c/15	 | space 2^39	 | B2kn3aceijk5c6a/S1e2aikn3ceik5ejkq6c
   diag    | 2c/34	 | space 2^35	 | B2e3aceijk5ckr/S1e2acei3ceik5jk6c
   diag    | 2c/18	 | space 2^37	 | B2en3aceij5jk6ae/S1ce2aikn3ei5a6c
   diag    | 2c/18	 | space 2^33	 | B2ekn3acijk6a/S1e2aeikn3cei5r6c
   diag    | 3c/22	 | space 2^29	 | B2ek3aceijk5jn6e/S1e2acn3ei5acjnq6ce
   diag    | 2c/16	 | space 2^45	 | B2e3acijk5knr/S1ce2aeik3ei6c
   diag    | 1c/12	 | space 2^51	 | B2n3aceij5y6a/S1ce2acein3eik6c
   diag    | 1c/17	 | space 2^39	 | B2en3acij5acikq6c/S1e2acin3ceik5cjk6c
   diag    | 1c/16	 | space 2^50	 | B2ekn3aeij/S1e2ac3ei5n6c
   diag    | 2c/23	 | space 2^36	 | B2e3acijk5acnq/S1e2aikn3cei5acj6c
   diag    | 1c/19	 | space 2^30	 | B2ek3aeijk5in6ae/S1ce2acikn3eik5jnqry6cei
   diag    | 1c/16	 | space 2^47	 | B2ek3aik5n/S1ce2acei3ei6ac
   diag    | 4c/18	 | space 2^36	 | B2e3aceij5kny6e/S1e2ace3ceijk5ckny6c
   diag    | 2c/32	 | space 2^23	 | B2ekn3acei5akr6c/S1ce2aikn3cei6ci
   diag    | 1c/22	 | space 2^43	 | B2kn3aijk/S1c2acek3ei5ajky6ac
   diag    | 1c/26	 | space 2^25	 | B2ek3aceijk5iq6e/S1e2aeikn3cei5cjnq6ck
   diag    | 1c/11	 | space 2^51	 | B2n3aceij5n/S1e2ackn3cei6ac
   diag    | 2c/18	 | space 2^43	 | B2e3aceik5an/S1e2acei3cei5k6c
   diag    | 1c/19	 | space 2^35	 | B2ekn3aceijk5cjy/S2acein3ei6ace
   diag    | 3c/24	 | space 2^23	 | B2ek3aceijk5ceknqr6e/S1ce2acik3ceik5acen6ac
   diag    | 1c/20	 | space 2^30	 | B2ek3acij5cein6c/S1ce2acein3ceijk5acj6c
   diag    | 1c/20	 | space 2^24	 | B2ek3acij5ckn6ac/S1ce2acn3ceij5nq6ce
   diag    | 3c/39	 | space 2^25	 | B2ek3aeij5aeky6a/S1ce2aek3eik5j6c
   diag    | 2c/15	 | space 2^39	 | B2ek3acij5i6a/S1c2ace3cei5jny6c
   diag    | 1c/30	 | space 2^16	 | B2ekn3aceijk5acnq6ck/S1e2akn3cei5cejkny6ci
   diag    | 1c/12	 | space 2^47	 | B2ek3aeij5cn/S1e2acein3cei5ceq6c

With v1, I need to wait for an hour for this.

[EvinZL]

What changed about the searching algorithm in v2.1? It runs through fewer rules/sec now but finds a lot more results.

According to profiling, over 80% of the time is spent in two lines in the evolution code. I started implementing some more bit tricks in the evolution rule. I did the least effort approach of swapping out bool arrays for std::bitset which means that basically no code has to change. The main difference now is that in a bitvector, the 3x3 neighborhood splits into three rows, each of which is three bits that are already adjacent. This means that fewer operations are needed to convert the grid into the neighborhood number. This also changes the lookup table because the bits are in a different order. (EDIT: I also changed ComparePattern to skip empty rows, which provides a further ~10% speedup)

Overall, this provides around a 30% speedup.

Code: Select all

/*
 * TarRuleSrc21e.cpp -- Search for rules.
 * Version 2.1e
 *
 * EvinZL, 2025
 * based on
 * islptng, 2025
 *
 * Thanks to FWKnightship for parseRLE(), ComparePattern(), and GridPtr.
 * Thanks to EvinZL for an improvement of Hensel lookup algorithms.
 */

#include<iostream>
#include<fstream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<ctime>
#include<bitset>
using namespace std;

const string Hensel[51] = { "0","1c","1e","2a","2c","2e","2i","2k","2n","3a","3c","3e","3i","3j","3k","3n","3q","3r","3y",
"4a","4c","4e","4i","4j","4k","4n","4q","4r","4t","4w","4y","4z","5a","5c","5e","5i","5j","5k","5n","5q","5r","5y",
"6a","6c","6e","6i","6k","6n","7c","7e","8" };
const int HenselCnt[9] = { 1,2,6,10,13,10,6,2,1 };
char NLookup[512] = {
	'\x00','\x01','\x02','\x03','\x01','\x04','\x03','\x0c','\x02','\x03','\x05','\x09','\x07','\x0f','\x0d','\x13',
	'\x00','\x01','\x02','\x03','\x01','\x04','\x03','\x0c','\x02','\x03','\x05','\x09','\x07','\x0f','\x0d','\x13',
	'\x02','\x07','\x05','\x0d','\x03','\x0f','\x09','\x13','\x06','\x11','\x0b','\x1b','\x11','\x16','\x1b','\x23',
	'\x02','\x07','\x05','\x0d','\x03','\x0f','\x09','\x13','\x06','\x11','\x0b','\x1b','\x11','\x16','\x1b','\x23',
	'\x01','\x04','\x07','\x0f','\x08','\x0a','\x10','\x19','\x03','\x0c','\x0d','\x13','\x10','\x19','\x1d','\x20',
	'\x01','\x04','\x07','\x0f','\x08','\x0a','\x10','\x19','\x03','\x0c','\x0d','\x13','\x10','\x19','\x1d','\x20',
	'\x07','\x12','\x0e','\x18','\x10','\x1e','\x1a','\x24','\x11','\x1c','\x17','\x26','\x1f','\x28','\x27','\x2a',
	'\x07','\x12','\x0e','\x18','\x10','\x1e','\x1a','\x24','\x11','\x1c','\x17','\x26','\x1f','\x28','\x27','\x2a',
	'\x02','\x07','\x06','\x11','\x07','\x12','\x11','\x1c','\x05','\x0d','\x0b','\x1b','\x0e','\x18','\x17','\x26',
	'\x02','\x07','\x06','\x11','\x07','\x12','\x11','\x1c','\x05','\x0d','\x0b','\x1b','\x0e','\x18','\x17','\x26',
	'\x05','\x0e','\x0b','\x17','\x0d','\x18','\x1b','\x26','\x0b','\x17','\x15','\x21','\x17','\x29','\x21','\x2b',
	'\x05','\x0e','\x0b','\x17','\x0d','\x18','\x1b','\x26','\x0b','\x17','\x15','\x21','\x17','\x29','\x21','\x2b',
	'\x03','\x0f','\x11','\x16','\x10','\x1e','\x1f','\x28','\x09','\x13','\x1b','\x23','\x1a','\x24','\x27','\x2a',
	'\x03','\x0f','\x11','\x16','\x10','\x1e','\x1f','\x28','\x09','\x13','\x1b','\x23','\x1a','\x24','\x27','\x2a',
	'\x0d','\x18','\x17','\x29','\x1d','\x25','\x27','\x2e','\x1b','\x26','\x21','\x2b','\x27','\x2e','\x2f','\x30',
	'\x0d','\x18','\x17','\x29','\x1d','\x25','\x27','\x2e','\x1b','\x26','\x21','\x2b','\x27','\x2e','\x2f','\x30',
	'\x01','\x08','\x07','\x10','\x04','\x0a','\x0f','\x19','\x07','\x10','\x0e','\x1a','\x12','\x1e','\x18','\x24',
	'\x01','\x08','\x07','\x10','\x04','\x0a','\x0f','\x19','\x07','\x10','\x0e','\x1a','\x12','\x1e','\x18','\x24',
	'\x03','\x10','\x0d','\x1d','\x0c','\x19','\x13','\x20','\x11','\x1f','\x17','\x27','\x1c','\x28','\x26','\x2a',
	'\x03','\x10','\x0d','\x1d','\x0c','\x19','\x13','\x20','\x11','\x1f','\x17','\x27','\x1c','\x28','\x26','\x2a',
	'\x04','\x0a','\x12','\x1e','\x0a','\x14','\x1e','\x22','\x0f','\x19','\x18','\x24','\x1e','\x22','\x25','\x2c',
	'\x04','\x0a','\x12','\x1e','\x0a','\x14','\x1e','\x22','\x0f','\x19','\x18','\x24','\x1e','\x22','\x25','\x2c',
	'\x0f','\x1e','\x18','\x25','\x19','\x22','\x24','\x2c','\x16','\x28','\x29','\x2e','\x28','\x2d','\x2e','\x31',
	'\x0f','\x1e','\x18','\x25','\x19','\x22','\x24','\x2c','\x16','\x28','\x29','\x2e','\x28','\x2d','\x2e','\x31',
	'\x03','\x10','\x11','\x1f','\x0f','\x1e','\x16','\x28','\x0d','\x1d','\x17','\x27','\x18','\x25','\x29','\x2e',
	'\x03','\x10','\x11','\x1f','\x0f','\x1e','\x16','\x28','\x0d','\x1d','\x17','\x27','\x18','\x25','\x29','\x2e',
	'\x09','\x1a','\x1b','\x27','\x13','\x24','\x23','\x2a','\x1b','\x27','\x21','\x2f','\x26','\x2e','\x2b','\x30',
	'\x09','\x1a','\x1b','\x27','\x13','\x24','\x23','\x2a','\x1b','\x27','\x21','\x2f','\x26','\x2e','\x2b','\x30',
	'\x0c','\x19','\x1c','\x28','\x19','\x22','\x28','\x2d','\x13','\x20','\x26','\x2a','\x24','\x2c','\x2e','\x31',
	'\x0c','\x19','\x1c','\x28','\x19','\x22','\x28','\x2d','\x13','\x20','\x26','\x2a','\x24','\x2c','\x2e','\x31',
	'\x13','\x24','\x26','\x2e','\x20','\x2c','\x2a','\x31','\x23','\x2a','\x2b','\x30','\x2a','\x31','\x30','\x32',
	'\x13','\x24','\x26','\x2e','\x20','\x2c','\x2a','\x31','\x23','\x2a','\x2b','\x30','\x2a','\x31','\x30','\x32' };
int HenselToOrder(string st)
{
	for (int i = 0; i < 51; i++)
	{
		if (Hensel[i] == st) return i;
	}
	return -1;
}

int randfactor = 0xdeadbeef - 0x5f3759df;
int rng()
{
	randfactor = rand();
	return rand();
}

int CondToOrder(int st)
{
	return NLookup[st];
}

struct Rule
{
	bool b[51];
	bool s[51];
	Rule() { for (int i = 0; i < 51; i++) { b[i] = false; s[i] = false; } }
	Rule(string st)
	{
		for (int i = 0; i < 51; i++) { b[i] = false; s[i] = false; }
		char currentNumber = '0';
		bool inMinus = false;
		bool inBirth = true;
		st += "S";
		for (int i = 0; i < st.size(); i++)
		{
			if ('0' <= st[i] && st[i] <= '8')
			{
				currentNumber = st[i];
				inMinus = false;
				if (st[i + 1] == '/' || st[i + 1] == 'S' || st[i + 1] == 's' || ('0' <= st[i + 1] && st[i + 1] <= '8'))
				{
					st[i] = '-';
				}
				else continue;
			}
			if (st[i] == 'S' || st[i] == 's') { inBirth = false; continue; }
			if (st[i] == 'B' || st[i] == 'b' || st[i] == '/') continue;
			if (st[i] == '-')
			{
				inMinus = true;
				for (int j = 0; j < 51; j++)
				{
					if (Hensel[j][0] == currentNumber)
						if (inBirth) b[j] = true;
						else s[j] = true;
				}
				continue;
			}
			string currenth = ""; currenth += currentNumber; currenth += st[i];
			int index = HenselToOrder(currenth);
			if (inBirth) b[index] = !inMinus;
			else s[index] = !inMinus;
		}
	}
	bool evolve(int conds) const
	{
		if (conds & 16) return s[CondToOrder(conds)];
		else return b[CondToOrder(conds)];
	}
};
string toString(Rule a)
{
	string res = "B";
	char currentNumber = 'a';
	for (int i = 0; i < 51; i++)
	{
		if (a.b[i])
		{
			if (currentNumber != Hensel[i][0])
			{
				res += Hensel[i][0];
				currentNumber = Hensel[i][0];
			}
			if (Hensel[i] != "0" && Hensel[i] != "8") res += Hensel[i][1];
		}
	}
	currentNumber = 'a';
	res += "/S";
	for (int i = 0; i < 51; i++)
	{
		if (a.s[i])
		{
			if (currentNumber != Hensel[i][0])
			{
				res += Hensel[i][0];
				currentNumber = Hensel[i][0];
			}
			if (Hensel[i] != "0" && Hensel[i] != "8") res += Hensel[i][1];
		}
	}
	return res;
}
Rule operator|(Rule a, Rule b)
{
	Rule res;
	for (int i = 0; i < 51; i++)
	{
		res.b[i] = a.b[i] || b.b[i];
		res.s[i] = a.s[i] || b.s[i];
	}
	return res;
}
Rule operator&(Rule a, Rule b)
{
	Rule res;
	for (int i = 0; i < 51; i++)
	{
		res.b[i] = a.b[i] && b.b[i];
		res.s[i] = a.s[i] && b.s[i];
	}
	return res;
}
bool operator==(Rule a, Rule b)
{
	for (int i = 0; i < 51; i++)
	{
		if (a.b[i] != b.b[i]) return false;
		if (a.s[i] != b.s[i]) return false;
	}
	return true;
}
int diff(Rule a, Rule b)
{
	int cnt = 0;
	for (int i = 0; i < 51; i++)
	{
		if (a.b[i] != b.b[i]) cnt++;
		if (a.s[i] != b.s[i]) cnt++;
	}
	return cnt;
}

Rule randomRule(Rule minrule, Rule maxrule)
{
	long long randb = (long long)rng() << 32 | rng();
	long long rands = (long long)rng() << 32 | rng();
	Rule res;
	for (int i = 0; i < 51; i++)
	{
		if (minrule.b[i]) res.b[i] = true;
		else if (!maxrule.b[i]) res.b[i] = false;
		else res.b[i] = (randb >> i & 0x01);
		if (minrule.s[i]) res.s[i] = true;
		else if (!maxrule.s[i]) res.s[i] = false;
		else res.s[i] = (rands >> i & 0x01);
	}
	return res;
}

const int GRIDSIZE = 64;
typedef bitset<GRIDSIZE> Grid[GRIDSIZE], *GridPtr;
const int PATTPOS = GRIDSIZE / 2 - 2;
// return false if the RLE is empty or represents an empty pattern, true otherwise.
// by FWKnightship and modified by islptng
bool parseRLE(const string RLE, GridPtr grid)
{
	int num = 0, start_x = PATTPOS, start_y = PATTPOS;
	int x = 0, y = 0;

	bool empty = 1;

	for (unsigned i = 0; i < RLE.size(); ++i)
	{
		char c = RLE[i];
		if (c == 'r')
		{
			start_y -= num / 2;
			if (start_y < 0)
			{
				cerr << "ERROR: RLE size (" << num
					<< ") is larger than grid size (" << num
					<< ").\n";
				exit(1);
			}
			num = 0;
		}
		else if (isdigit(c))
		{
			num = num * 10 + c - '0';
		}
		else if (isalpha(c))
		{
			if (c > 'A' && c <= 'Z')
			{
				cerr << "ERROR: State out of range, only 2 states are supported.\n";
				exit(1);
			}
			else if (c == 'b')
			{
				x += num == 0 ? 1 : num;
			}
			else if (c == 'o' || c <= 'C')
			{
				int state = c == 'o' ? 1 : c - 'A' + 1;

				for (int j = 0; j < (num == 0 ? 1 : num); ++j)
				{
					if (start_x + x >= GRIDSIZE)
					{
						cerr << "ERROR: RLE contains too large pattern.(x)\n";
						exit(1);
					}
					grid[start_x + x][start_y + y] = state;
					++x;
				}

				empty = 0;
			}
			num = 0;
		}
		else if (c == '.')
		{
			x += num == 0 ? 1 : num;
			num = 0;
		}
		else if (c == '$')
		{
			y += num == 0 ? 1 : num;
			x = 0;
			if (start_y + y >= GRIDSIZE)
			{
				std::cerr << "ERROR: RLE contains too large pattern.(y)\n";
				exit(1);
			}
			num = 0;
		}
		else if (c == '!')
		{
			break;
		}
		else if (isgraph(c) && c != '=' && c != ',')
		{
			std::cerr << "ERROR: Invalid character \'" << c << "\'.\n";
			exit(1);
		}
	}

	return !empty;
}
// by FWKnightship and modified by islptng and EvinZL
struct cell
{
	int x, y;
} aa[GRIDSIZE * GRIDSIZE], bb[GRIDSIZE * GRIDSIZE];
int ComparePattern_dx, ComparePattern_dy;
bool ComparePattern(GridPtr a, GridPtr b)
{
	int aaa = 0, bbb = 0;
	for (int i = 0; i < GRIDSIZE; ++i)
	{
		if (a[i].any())
			for (int j = 0; j < GRIDSIZE; ++j)
			{
				if (a[i][j] != 0)
				{
					aa[aaa].x = i;
					aa[aaa].y = j;
					++aaa;
				}
			}
		if (b[i].any())
			for (int j = 0; j < GRIDSIZE; ++j)
			{
				if (b[i][j] != 0)
				{
					bb[bbb].x = i;
					bb[bbb].y = j;
					++bbb;
				}
			}
	}
	if (aaa != bbb) return 0;
	if (aaa == 0) return 1;
	ComparePattern_dx = bb[0].x - aa[0].x;
	ComparePattern_dy = bb[0].y - aa[0].y;
	for (int i = 0; i < aaa; ++i)
	{
		if (bb[i].x - aa[i].x != ComparePattern_dx) return 0;
		if (bb[i].y - aa[i].y != ComparePattern_dy) return 0;
	}
	return 1;
}

void gridcpy(GridPtr from, GridPtr to)
{
	for (int i = 0; i < GRIDSIZE; i++) to[i] = from[i];
}
int gridgcl(GridPtr grid, int x, int y)
{
	if (x < 0 || x >= GRIDSIZE) return false;
	if (y < 0 || y >= GRIDSIZE) return false;
	return grid[x][y];
}
const int deltax[] = { -1,-1,0,1,1,1,0,-1 };
const int deltay[] = { 0,1,1,1,0,-1,-1,-1 };
// return false if pattern touches the boundary or becomes empty.
uint64_t shr(uint64_t x, int s) {
	return (s > 0) ? (x >> s) : (x << -s);
}
bool evolve(GridPtr from, GridPtr to, Rule r)
{
	bool empty = true;
	for (int x = 0; x < GRIDSIZE; x++)
		for (int y = 0; y < GRIDSIZE; y++)
		{
			int n0 = shr(x ==          0 ? 0ull : from[x - 1].to_ullong(), y-1) & 7;
			int n1 = shr(                         from[x    ].to_ullong(), y-1) & 7;
			int n2 = shr(x == GRIDSIZE-1 ? 0ull : from[x + 1].to_ullong(), y-1) & 7;
			int neighbors = n0 | (n1 << 3) | (n2 << 6);
			to[x][y] = r.evolve(neighbors);
			if (to[x][y])
			{
				empty = false;
				if (x == 0 || x == GRIDSIZE - 1 || y == 0 || y == GRIDSIZE - 1) return false;
			}
		}
	return !empty;
}
Rule evolveRulespace_min, evolveRulespace_max;
void evolve_rulespace(GridPtr from, GridPtr to, Rule r)
{
	evolveRulespace_min = Rule("B/S");
	evolveRulespace_max = Rule("B012345678/S012345678");
	for (int x = 0; x < GRIDSIZE; x++)
		for (int y = 0; y < GRIDSIZE; y++)
		{
			int n0 = shr(x ==            0 ? 0ull : from[x - 1].to_ullong(), y - 1) & 7;
			int n1 = shr(                           from[x    ].to_ullong(), y - 1) & 7;
			int n2 = shr(x == GRIDSIZE - 1 ? 0ull : from[x + 1].to_ullong(), y - 1) & 7;
			int neighbors = n0 | (n1 << 3) | (n2 << 6);
			to[x][y] = r.evolve(neighbors);
			if (to[x][y])
				if (from[x][y]) evolveRulespace_min.s[CondToOrder(neighbors)] = true;
				else evolveRulespace_min.b[CondToOrder(neighbors)] = true;
			else
				if (from[x][y]) evolveRulespace_max.s[CondToOrder(neighbors)] = false;
				else evolveRulespace_max.b[CondToOrder(neighbors)] = false;
		}
}
Rule calcRulespace_min, calcRulespace_max;
void calc_rulespace(GridPtr grid, GridPtr temp, Rule r, int gens)
{
	calcRulespace_min = Rule("B/S");
	calcRulespace_max = Rule("B012345678/S012345678");
	for (int g = 0; g < gens; g++)
	{
		evolve_rulespace(grid, temp, r);
		calcRulespace_min = calcRulespace_min | evolveRulespace_min;
		calcRulespace_max = calcRulespace_max & evolveRulespace_max;
		gridcpy(temp, grid);
	}
}

Grid startpatt, endpatt, grid, grid2;

int minx, miny, maxx, maxy, minp, maxp;
string minrstr, maxrstr;
Rule minr, maxr;
string startrle, endrle;
bool readrequire()
{
	string strtemp;
	ifstream fin;
	fin.open("requirements.txt");
	fin >> strtemp >> minrstr >> maxrstr;
	if (strtemp != "r:") { cerr << "Missing R"; return false; }
	fin >> strtemp >> minp >> maxp;
	if (strtemp != "p:") { cerr << "Missing P"; return false; }
	if (maxp == -1) { cerr << ""; return false; }
	fin >> strtemp >> minx >> maxx;
	if (strtemp != "x:") { cerr << "Missing X"; return false; }
	fin >> strtemp >> miny >> maxy;
	if (strtemp != "y:") { cerr << "Missing Y"; return false; }
	fin >> strtemp; if (strtemp != "==start") { cerr << "Missing start pattern"; return false; }
	strtemp = "?"; startrle = "";
	while (strtemp[0] != '=')
	{
		if (strtemp != "?") startrle += strtemp;
		fin >> strtemp;
	}
	if (strtemp == "==end")
	{
		endrle = startrle;
		fin.close();
		return true;
	}
	if (strtemp != "==target") { cerr << "Missing end tag or target pattern"; return false; }
	strtemp = "?"; endrle = "";
	while (strtemp[0] != '=')
	{
		if (strtemp != "?") endrle += strtemp;
		fin >> strtemp;
	}
	if (strtemp != "==end") { cerr << "Missing end tag"; return false; }
	fin.close();
	return true;
}

Rule rresults[5000]; int cntres = 0;
bool inrange(int n, int from, int to)
{
	if (n < from && from != -1) return false;
	if (n > to && to != -1) return false;
	return true;
}
void swapdxy()
{
	if (ComparePattern_dx < 0) ComparePattern_dx *= -1;
	if (ComparePattern_dy < 0) ComparePattern_dy *= -1;
	if (ComparePattern_dx < ComparePattern_dy)
	{
		int t = ComparePattern_dx;
		ComparePattern_dx = ComparePattern_dy;
		ComparePattern_dy = t;
	}
}
void initres()
{
	ofstream fout;
	fout.open("TarRuleSrc_result.txt");
	fout << "TarRuleSrc Results:\n\n";
	fout.close();
}
void putres(int dx, int dy, int period, int optn, Rule r)
{
	ofstream fout;
	fout.open("TarRuleSrc_result.txt", ios::app);
	if (startrle == endrle)
	{
		if (dx == dy && dy == 0)
			fout << "           |  p";
		else if (dy == 0) fout << "      orth | " << dx << "c/";
		else if (dy == dx) fout << "   diag    | " << dx << "c/";
		else              fout << "obli       |(" << dx << "," << dy << ")c/";
	}
	else fout << "dx=" << dx << "\tdy=" << dy << "\tT=";
	fout << period << "\t | space 2^" << optn << "\t | " << toString(r) << endl;
	fout.close();
}
bool checkfound(Rule r)
{
	for (int i = 0; i < cntres; i++)
	{
		if (rresults[i] == r) return true;
	}
	return false;
}

void printGrid(GridPtr g) {
	for (int y = 0; y < GRIDSIZE; y++) {
		for (int x = 0; x < GRIDSIZE; x++)
			std::cout << (g[y][x] ? '.' : ' ');
		std::cout << "\n";
	}
}

int main()
{
	srand(time(0) ^ randfactor);
	if (!readrequire()) return -1;
	minr = Rule(minrstr);
	maxr = Rule(maxrstr);
	if (!parseRLE(startrle, startpatt)) return -1;
	if (!parseRLE(endrle, endpatt)) return -1;

	initres();
	int cnt = 0;
	while (true)
	{
		Rule r = randomRule(minr, maxr);
		gridcpy(startpatt, grid);
		int gen = 0;
		while (gen <= maxp)
		{
			gen++;
			bool flag = evolve(grid, grid2, r);
			gridcpy(grid2, grid);
			if (!flag) break;
			flag = ComparePattern(grid, endpatt);
			if (flag)
			{
				swapdxy();
				if (!inrange(gen, minp, maxp)) break;
				if (!inrange(ComparePattern_dx, minx, maxx)) break;
				if (!inrange(ComparePattern_dy, miny, maxy)) break;
				gridcpy(startpatt, grid);
				calc_rulespace(grid, grid2, r, gen);
				Rule tmir = minr | calcRulespace_min;
				if (checkfound(tmir)) break;
				Rule tmar = maxr & calcRulespace_max;
				putres(ComparePattern_dx, ComparePattern_dy, gen, diff(tmir, tmar), tmir);
				rresults[cntres] = tmir;
				cntres++;
				break;
			}
		}
		cnt++;
		if (cnt % 2048 == 0) cout << cnt << " rules tested, " << cntres << " results found\n";
	}
	return 0;
}

(the code formatting changed because Visual Studio is extremely opinionated about code formatting)

MAJOR EDIT:
Since this task is embarrasingly parallel, I wrote a somewhat lazy multithreaded version.

Code: Select all

/*
 * pTarRuleSrc2e.cpp -- Search for rules.
 * Version 2.1e
 *
 * EvinZL, 2025
 * based on
 * islptng, 2025
 *
 * Thanks to FWKnightship for parseRLE(), ComparePattern(), and GridPtr.
 * Thanks to EvinZL for an improvement of Hensel lookup algorithms.
 */

#include<iostream>
#include<fstream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<ctime>
#include<bitset>
#include<thread>
#include<mutex>
#include <vector>
using namespace std;

const string Hensel[51] = { "0","1c","1e","2a","2c","2e","2i","2k","2n","3a","3c","3e","3i","3j","3k","3n","3q","3r","3y",
"4a","4c","4e","4i","4j","4k","4n","4q","4r","4t","4w","4y","4z","5a","5c","5e","5i","5j","5k","5n","5q","5r","5y",
"6a","6c","6e","6i","6k","6n","7c","7e","8" };
const int HenselCnt[9] = { 1,2,6,10,13,10,6,2,1 };
const char NLookup[512] = {
	'\x00','\x01','\x02','\x03','\x01','\x04','\x03','\x0c','\x02','\x03','\x05','\x09','\x07','\x0f','\x0d','\x13',
	'\x00','\x01','\x02','\x03','\x01','\x04','\x03','\x0c','\x02','\x03','\x05','\x09','\x07','\x0f','\x0d','\x13',
	'\x02','\x07','\x05','\x0d','\x03','\x0f','\x09','\x13','\x06','\x11','\x0b','\x1b','\x11','\x16','\x1b','\x23',
	'\x02','\x07','\x05','\x0d','\x03','\x0f','\x09','\x13','\x06','\x11','\x0b','\x1b','\x11','\x16','\x1b','\x23',
	'\x01','\x04','\x07','\x0f','\x08','\x0a','\x10','\x19','\x03','\x0c','\x0d','\x13','\x10','\x19','\x1d','\x20',
	'\x01','\x04','\x07','\x0f','\x08','\x0a','\x10','\x19','\x03','\x0c','\x0d','\x13','\x10','\x19','\x1d','\x20',
	'\x07','\x12','\x0e','\x18','\x10','\x1e','\x1a','\x24','\x11','\x1c','\x17','\x26','\x1f','\x28','\x27','\x2a',
	'\x07','\x12','\x0e','\x18','\x10','\x1e','\x1a','\x24','\x11','\x1c','\x17','\x26','\x1f','\x28','\x27','\x2a',
	'\x02','\x07','\x06','\x11','\x07','\x12','\x11','\x1c','\x05','\x0d','\x0b','\x1b','\x0e','\x18','\x17','\x26',
	'\x02','\x07','\x06','\x11','\x07','\x12','\x11','\x1c','\x05','\x0d','\x0b','\x1b','\x0e','\x18','\x17','\x26',
	'\x05','\x0e','\x0b','\x17','\x0d','\x18','\x1b','\x26','\x0b','\x17','\x15','\x21','\x17','\x29','\x21','\x2b',
	'\x05','\x0e','\x0b','\x17','\x0d','\x18','\x1b','\x26','\x0b','\x17','\x15','\x21','\x17','\x29','\x21','\x2b',
	'\x03','\x0f','\x11','\x16','\x10','\x1e','\x1f','\x28','\x09','\x13','\x1b','\x23','\x1a','\x24','\x27','\x2a',
	'\x03','\x0f','\x11','\x16','\x10','\x1e','\x1f','\x28','\x09','\x13','\x1b','\x23','\x1a','\x24','\x27','\x2a',
	'\x0d','\x18','\x17','\x29','\x1d','\x25','\x27','\x2e','\x1b','\x26','\x21','\x2b','\x27','\x2e','\x2f','\x30',
	'\x0d','\x18','\x17','\x29','\x1d','\x25','\x27','\x2e','\x1b','\x26','\x21','\x2b','\x27','\x2e','\x2f','\x30',
	'\x01','\x08','\x07','\x10','\x04','\x0a','\x0f','\x19','\x07','\x10','\x0e','\x1a','\x12','\x1e','\x18','\x24',
	'\x01','\x08','\x07','\x10','\x04','\x0a','\x0f','\x19','\x07','\x10','\x0e','\x1a','\x12','\x1e','\x18','\x24',
	'\x03','\x10','\x0d','\x1d','\x0c','\x19','\x13','\x20','\x11','\x1f','\x17','\x27','\x1c','\x28','\x26','\x2a',
	'\x03','\x10','\x0d','\x1d','\x0c','\x19','\x13','\x20','\x11','\x1f','\x17','\x27','\x1c','\x28','\x26','\x2a',
	'\x04','\x0a','\x12','\x1e','\x0a','\x14','\x1e','\x22','\x0f','\x19','\x18','\x24','\x1e','\x22','\x25','\x2c',
	'\x04','\x0a','\x12','\x1e','\x0a','\x14','\x1e','\x22','\x0f','\x19','\x18','\x24','\x1e','\x22','\x25','\x2c',
	'\x0f','\x1e','\x18','\x25','\x19','\x22','\x24','\x2c','\x16','\x28','\x29','\x2e','\x28','\x2d','\x2e','\x31',
	'\x0f','\x1e','\x18','\x25','\x19','\x22','\x24','\x2c','\x16','\x28','\x29','\x2e','\x28','\x2d','\x2e','\x31',
	'\x03','\x10','\x11','\x1f','\x0f','\x1e','\x16','\x28','\x0d','\x1d','\x17','\x27','\x18','\x25','\x29','\x2e',
	'\x03','\x10','\x11','\x1f','\x0f','\x1e','\x16','\x28','\x0d','\x1d','\x17','\x27','\x18','\x25','\x29','\x2e',
	'\x09','\x1a','\x1b','\x27','\x13','\x24','\x23','\x2a','\x1b','\x27','\x21','\x2f','\x26','\x2e','\x2b','\x30',
	'\x09','\x1a','\x1b','\x27','\x13','\x24','\x23','\x2a','\x1b','\x27','\x21','\x2f','\x26','\x2e','\x2b','\x30',
	'\x0c','\x19','\x1c','\x28','\x19','\x22','\x28','\x2d','\x13','\x20','\x26','\x2a','\x24','\x2c','\x2e','\x31',
	'\x0c','\x19','\x1c','\x28','\x19','\x22','\x28','\x2d','\x13','\x20','\x26','\x2a','\x24','\x2c','\x2e','\x31',
	'\x13','\x24','\x26','\x2e','\x20','\x2c','\x2a','\x31','\x23','\x2a','\x2b','\x30','\x2a','\x31','\x30','\x32',
	'\x13','\x24','\x26','\x2e','\x20','\x2c','\x2a','\x31','\x23','\x2a','\x2b','\x30','\x2a','\x31','\x30','\x32' };
int HenselToOrder(string st)
{
	for (int i = 0; i < 51; i++)
	{
		if (Hensel[i] == st) return i;
	}
	return -1;
}

uint64_t x = 1;
int rng()
{
	x ^= x >> 12;
	x ^= x << 25;
	x ^= x >> 27;
	return (x * 0x2545F4914F6CDD1DULL) >> 32;
}

int CondToOrder(int st)
{
	return NLookup[st];
}

struct Rule
{
	bool b[51];
	bool s[51];
	Rule() { for (int i = 0; i < 51; i++) { b[i] = false; s[i] = false; } }
	Rule(string st)
	{
		for (int i = 0; i < 51; i++) { b[i] = false; s[i] = false; }
		char currentNumber = '0';
		bool inMinus = false;
		bool inBirth = true;
		st += "S";
		for (int i = 0; i < st.size(); i++)
		{
			if ('0' <= st[i] && st[i] <= '8')
			{
				currentNumber = st[i];
				inMinus = false;
				if (st[i + 1] == '/' || st[i + 1] == 'S' || st[i + 1] == 's' || ('0' <= st[i + 1] && st[i + 1] <= '8'))
				{
					st[i] = '-';
				}
				else continue;
			}
			if (st[i] == 'S' || st[i] == 's') { inBirth = false; continue; }
			if (st[i] == 'B' || st[i] == 'b' || st[i] == '/') continue;
			if (st[i] == '-')
			{
				inMinus = true;
				for (int j = 0; j < 51; j++)
				{
					if (Hensel[j][0] == currentNumber)
						if (inBirth) b[j] = true;
						else s[j] = true;
				}
				continue;
			}
			string currenth = ""; currenth += currentNumber; currenth += st[i];
			int index = HenselToOrder(currenth);
			if (inBirth) b[index] = !inMinus;
			else s[index] = !inMinus;
		}
	}
	bool evolve(int conds) const
	{
		return (conds & 16) ? s[CondToOrder(conds)] : b[CondToOrder(conds)];
	}
};
string toString(Rule a)
{
	string res = "B";
	char currentNumber = 'a';
	for (int i = 0; i < 51; i++)
	{
		if (a.b[i])
		{
			if (currentNumber != Hensel[i][0])
			{
				res += Hensel[i][0];
				currentNumber = Hensel[i][0];
			}
			if (Hensel[i] != "0" && Hensel[i] != "8") res += Hensel[i][1];
		}
	}
	currentNumber = 'a';
	res += "/S";
	for (int i = 0; i < 51; i++)
	{
		if (a.s[i])
		{
			if (currentNumber != Hensel[i][0])
			{
				res += Hensel[i][0];
				currentNumber = Hensel[i][0];
			}
			if (Hensel[i] != "0" && Hensel[i] != "8") res += Hensel[i][1];
		}
	}
	return res;
}
Rule operator|(Rule a, Rule b)
{
	Rule res;
	for (int i = 0; i < 51; i++)
	{
		res.b[i] = a.b[i] || b.b[i];
		res.s[i] = a.s[i] || b.s[i];
	}
	return res;
}
Rule operator&(Rule a, Rule b)
{
	Rule res;
	for (int i = 0; i < 51; i++)
	{
		res.b[i] = a.b[i] && b.b[i];
		res.s[i] = a.s[i] && b.s[i];
	}
	return res;
}
bool operator==(Rule a, Rule b)
{
	for (int i = 0; i < 51; i++)
	{
		if (a.b[i] != b.b[i]) return false;
		if (a.s[i] != b.s[i]) return false;
	}
	return true;
}
int diff(Rule a, Rule b)
{
	int cnt = 0;
	for (int i = 0; i < 51; i++)
	{
		if (a.b[i] != b.b[i]) cnt++;
		if (a.s[i] != b.s[i]) cnt++;
	}
	return cnt;
}

Rule randomRule(Rule minrule, Rule maxrule)
{
	long long randb = (long long)rng() << 32 | rng();
	long long rands = (long long)rng() << 32 | rng();
	Rule res;
	for (int i = 0; i < 51; i++)
	{
		if (minrule.b[i]) res.b[i] = true;
		else if (!maxrule.b[i]) res.b[i] = false;
		else res.b[i] = (randb >> i & 0x01);
		if (minrule.s[i]) res.s[i] = true;
		else if (!maxrule.s[i]) res.s[i] = false;
		else res.s[i] = (rands >> i & 0x01);
	}
	return res;
}

const int GRIDSIZE = 64;
typedef bitset<GRIDSIZE> Grid[GRIDSIZE], *GridPtr;
const int PATTPOS = GRIDSIZE / 2 - 2;
// return false if the RLE is empty or represents an empty pattern, true otherwise.
// by FWKnightship and modified by islptng
bool parseRLE(const string RLE, GridPtr grid)
{
	int num = 0, start_x = PATTPOS, start_y = PATTPOS;
	int x = 0, y = 0;

	bool empty = 1;

	for (unsigned i = 0; i < RLE.size(); ++i)
	{
		char c = RLE[i];
		if (c == 'r')
		{
			start_y -= num / 2;
			if (start_y < 0)
			{
				cerr << "ERROR: RLE size (" << num
					<< ") is larger than grid size (" << num
					<< ").\n";
				exit(1);
			}
			num = 0;
		}
		else if (isdigit(c))
		{
			num = num * 10 + c - '0';
		}
		else if (isalpha(c))
		{
			if (c > 'A' && c <= 'Z')
			{
				cerr << "ERROR: State out of range, only 2 states are supported.\n";
				exit(1);
			}
			else if (c == 'b')
			{
				x += num == 0 ? 1 : num;
			}
			else if (c == 'o' || c <= 'C')
			{
				int state = c == 'o' ? 1 : c - 'A' + 1;

				for (int j = 0; j < (num == 0 ? 1 : num); ++j)
				{
					if (start_x + x >= GRIDSIZE)
					{
						cerr << "ERROR: RLE contains too large pattern.(x)\n";
						exit(1);
					}
					grid[start_x + x][start_y + y] = state;
					++x;
				}

				empty = 0;
			}
			num = 0;
		}
		else if (c == '.')
		{
			x += num == 0 ? 1 : num;
			num = 0;
		}
		else if (c == '$')
		{
			y += num == 0 ? 1 : num;
			x = 0;
			if (start_y + y >= GRIDSIZE)
			{
				std::cerr << "ERROR: RLE contains too large pattern.(y)\n";
				exit(1);
			}
			num = 0;
		}
		else if (c == '!')
		{
			break;
		}
		else if (isgraph(c) && c != '=' && c != ',')
		{
			std::cerr << "ERROR: Invalid character \'" << c << "\'.\n";
			exit(1);
		}
	}

	return !empty;
}

struct cell
{
	int x, y;
};

uint64_t shr(uint64_t x, int s) {
	return (s > 0) ? (x >> s) : (x << -s);
}

bool inrange(int n, int from, int to)
{
	if (n < from && from != -1) return false;
	if (n > to && to != -1) return false;
	return true;
}

Rule rresults[5000]; int cntres = 0;
mutex g_mutex;
// by FWKnightship and modified by islptng and EvinZL
struct ThreadData {
	Grid startpatt, endpatt, grid, grid2;

	int minx, miny, maxx, maxy, minp, maxp;
	string minrstr, maxrstr;
	Rule minr, maxr;
	string startrle, endrle;
	cell aa[GRIDSIZE * GRIDSIZE], bb[GRIDSIZE * GRIDSIZE];
	int ComparePattern_dx, ComparePattern_dy;
	bool failbit = false;
	bool ComparePattern(GridPtr a, GridPtr b)
	{
		int aaa = 0, bbb = 0;
		for (int i = 0; i < GRIDSIZE; ++i)
		{
			if (a[i].any())
				for (int j = 0; j < GRIDSIZE; ++j)
				{
					if (a[i][j] != 0)
					{
						aa[aaa].x = i;
						aa[aaa].y = j;
						++aaa;
					}
				}
			if (b[i].any())
				for (int j = 0; j < GRIDSIZE; ++j)
				{
					if (b[i][j] != 0)
					{
						bb[bbb].x = i;
						bb[bbb].y = j;
						++bbb;
					}
				}
		}
		if (aaa != bbb) return 0;
		if (aaa == 0) return 1;
		ComparePattern_dx = bb[0].x - aa[0].x;
		ComparePattern_dy = bb[0].y - aa[0].y;
		for (int i = 0; i < aaa; ++i)
		{
			if (bb[i].x - aa[i].x != ComparePattern_dx) return 0;
			if (bb[i].y - aa[i].y != ComparePattern_dy) return 0;
		}
		return 1;
	}

	void gridcpy(GridPtr from, GridPtr to)
	{
		for (int i = 0; i < GRIDSIZE; i++) to[i] = from[i];
	}
	int gridgcl(GridPtr grid, int x, int y)
	{
		if (x < 0 || x >= GRIDSIZE) return false;
		if (y < 0 || y >= GRIDSIZE) return false;
		return grid[x][y];
	}
	// return false if pattern touches the boundary or becomes empty.
	bool evolve(GridPtr from, GridPtr to, Rule r)
	{
		bool empty = true;
		for (int x = 0; x < GRIDSIZE; x++)
			for (int y = 0; y < GRIDSIZE; y++)
			{
				int n0 = shr(x == 0 ? 0ull : from[x - 1].to_ullong(), y - 1) & 7;
				int n1 = shr(from[x].to_ullong(), y - 1) & 7;
				int n2 = shr(x == GRIDSIZE - 1 ? 0ull : from[x + 1].to_ullong(), y - 1) & 7;
				int neighbors = n0 | (n1 << 3) | (n2 << 6);
				to[x][y] = r.evolve(neighbors);
				if (to[x][y])
				{
					empty = false;
					if (x == 0 || x == GRIDSIZE - 1 || y == 0 || y == GRIDSIZE - 1) return false;
				}
			}
		return !empty;
	}
	Rule evolveRulespace_min, evolveRulespace_max;
	void evolve_rulespace(GridPtr from, GridPtr to, Rule r)
	{
		evolveRulespace_min = Rule("B/S");
		evolveRulespace_max = Rule("B012345678/S012345678");
		for (int x = 0; x < GRIDSIZE; x++)
			for (int y = 0; y < GRIDSIZE; y++)
			{
				int n0 = shr(x == 0 ? 0ull : from[x - 1].to_ullong(), y - 1) & 7;
				int n1 = shr(from[x].to_ullong(), y - 1) & 7;
				int n2 = shr(x == GRIDSIZE - 1 ? 0ull : from[x + 1].to_ullong(), y - 1) & 7;
				int neighbors = n0 | (n1 << 3) | (n2 << 6);
				to[x][y] = r.evolve(neighbors);
				if (to[x][y])
					if (from[x][y]) evolveRulespace_min.s[CondToOrder(neighbors)] = true;
					else evolveRulespace_min.b[CondToOrder(neighbors)] = true;
				else
					if (from[x][y]) evolveRulespace_max.s[CondToOrder(neighbors)] = false;
					else evolveRulespace_max.b[CondToOrder(neighbors)] = false;
			}
	}
	Rule calcRulespace_min, calcRulespace_max;
	void calc_rulespace(GridPtr grid, GridPtr temp, Rule r, int gens)
	{
		calcRulespace_min = Rule("B/S");
		calcRulespace_max = Rule("B012345678/S012345678");
		for (int g = 0; g < gens; g++)
		{
			evolve_rulespace(grid, temp, r);
			calcRulespace_min = calcRulespace_min | evolveRulespace_min;
			calcRulespace_max = calcRulespace_max & evolveRulespace_max;
			gridcpy(temp, grid);
		}
	}

	bool readrequire()
	{
		string strtemp;
		ifstream fin;
		fin.open("requirements.txt");
		fin >> strtemp >> minrstr >> maxrstr;
		if (strtemp != "r:") { cerr << "Missing R"; return false; }
		fin >> strtemp >> minp >> maxp;
		if (strtemp != "p:") { cerr << "Missing P"; return false; }
		if (maxp == -1) { cerr << ""; return false; }
		fin >> strtemp >> minx >> maxx;
		if (strtemp != "x:") { cerr << "Missing X"; return false; }
		fin >> strtemp >> miny >> maxy;
		if (strtemp != "y:") { cerr << "Missing Y"; return false; }
		fin >> strtemp; if (strtemp != "==start") { cerr << "Missing start pattern"; return false; }
		strtemp = "?"; startrle = "";
		while (strtemp[0] != '=')
		{
			if (strtemp != "?") startrle += strtemp;
			fin >> strtemp;
		}
		if (strtemp == "==end")
		{
			endrle = startrle;
			fin.close();
			return true;
		}
		if (strtemp != "==target") { cerr << "Missing end tag or target pattern"; return false; }
		strtemp = "?"; endrle = "";
		while (strtemp[0] != '=')
		{
			if (strtemp != "?") endrle += strtemp;
			fin >> strtemp;
		}
		if (strtemp != "==end") { cerr << "Missing end tag"; return false; }
		fin.close();
		return true;
	}

	void swapdxy()
	{
		if (ComparePattern_dx < 0) ComparePattern_dx *= -1;
		if (ComparePattern_dy < 0) ComparePattern_dy *= -1;
		if (ComparePattern_dx < ComparePattern_dy)
		{
			int t = ComparePattern_dx;
			ComparePattern_dx = ComparePattern_dy;
			ComparePattern_dy = t;
		}
	}
	void putres(int dx, int dy, int period, int optn, Rule r)
	{
		ofstream fout;
		fout.open("TarRuleSrc_result.txt", ios::app);
		if (startrle == endrle)
		{
			if (dx == dy && dy == 0)
				fout << "           |  p";
			else if (dy == 0) fout << "      orth | " << dx << "c/";
			else if (dy == dx) fout << "   diag    | " << dx << "c/";
			else              fout << "obli       |(" << dx << "," << dy << ")c/";
		}
		else fout << "dx=" << dx << "\tdy=" << dy << "\tT=";
		fout << period << "\t | space 2^" << optn << "\t | " << toString(r) << endl;
		fout.close();
	}
	bool checkfound(Rule r)
	{
		for (int i = 0; i < cntres; i++)
		{
			if (rresults[i] == r) return true;
		}
		return false;
	}

	ThreadData() {
		if (!readrequire()) { failbit = true; return; }
		minr = Rule(minrstr);
		maxr = Rule(maxrstr);
		parseRLE(startrle, startpatt);
		parseRLE(endrle, endpatt);
	}
};

int cnt = 0;

void function(ThreadData* tp)
{
	ThreadData& td = *tp;
	while (true)
	{
		g_mutex.lock();
		Rule r = randomRule(td.minr, td.maxr);
		g_mutex.unlock();
		td.gridcpy(td.startpatt, td.grid);
		int gen = 0;
		while (gen <= td.maxp)
		{
			gen++;
			bool flag = td.evolve(td.grid, td.grid2, r);
			td.gridcpy(td.grid2, td.grid);
			if (!flag) break;
			flag = td.ComparePattern(td.grid, td.endpatt);
			if (flag)
			{
				td.swapdxy();
				if (!inrange(gen, td.minp, td.maxp)) break;
				if (!inrange(td.ComparePattern_dx, td.minx, td.maxx)) break;
				if (!inrange(td.ComparePattern_dy, td.miny, td.maxy)) break;
				td.gridcpy(td.startpatt, td.grid);
				td.calc_rulespace(td.grid, td.grid2, r, gen);
				Rule tmir = td.minr | td.calcRulespace_min;
				g_mutex.lock();
				if (td.checkfound(tmir)) {
					g_mutex.unlock();
					break;
				}
				Rule tmar = td.maxr & td.calcRulespace_max;
				td.putres(td.ComparePattern_dx, td.ComparePattern_dy, gen, diff(tmir, tmar), tmir);
				rresults[cntres] = tmir;
				cntres++;
				g_mutex.unlock();
				break;
			}
		}
		g_mutex.lock();
		cnt++;
		if (cnt % 32768 == 0) { 
			cout << cnt << " rules tested, " << cntres << " results found\n";
		}
		g_mutex.unlock();
	}
}

int main(int argc, char* argv[])
{
	int THREADS = 1;
	for (int i = 1; i < argc; i++) {
		if (strcmp(argv[i], "-p") == 0) {
			i++;
			THREADS = atoi(argv[i]);
		}
	}
	vector<ThreadData> x(THREADS);
	for (ThreadData& i : x)
		if (i.failbit) return -1;

	ofstream fout;
	fout.open("TarRuleSrc_result.txt");
	fout << "pTarRuleSrc Results:\n\n";
	fout.close();

	vector<thread> workers;
	for (int i = 0; i < THREADS; i++)
		workers.emplace_back(function, x.data() + i);

	for (thread& t : workers)
		t.join();

	return 0;
}

(NOTE: don't use rand() for the parallel version becasue apparently its thread-local, so all the threads will duplicate each others' work)

[islptng]

What changed about the searching algorithm in v2.1? It runs through fewer rules/sec now but finds a lot more results.

Code: Select all

if dx < 0: dx *= -1
if dy < 0: dy *= -1

Code: Select all

void swapdxy()
{
	if(ComparePattern_dx < ComparePattern_dy)
	{
		int t = ComparePattern_dx;
		ComparePattern_dx = ComparePattern_dy;
		ComparePattern_dy = t;
	}
}

Code: Select all

void swapdxy()
{
	if(ComparePattern_dx < 0) ComparePattern_dx *= -1;
	if(ComparePattern_dy < 0) ComparePattern_dy *= -1;
	if(ComparePattern_dx < ComparePattern_dy)
	{
		int t = ComparePattern_dx;
		ComparePattern_dx = ComparePattern_dy;
		ComparePattern_dy = t;
	}
}

Missing those two lines meaning that it treats every pattern that goes left/up as invalid.


Also, I'm planning change the rng() to Mersenne Twister 19937. (EDIT: Done! Updated to 2.2!)

[EvinZL]

Well, it's quite fortunate that you changed the rng to Mersenne Twister, because the old version has several issues. Firstly, apparently the behavior of rand() is completely implementation defined, which is quite concerning. In the random rule code, four consecutive calls to rng() are used to generate the rule, so for this to behave as intended, the random number generator needs to have 4-dimensional equidistribution. Very few generators have this property. Fortunately, mt19937 does.

If the evolve function is changed to skip empty space, as in

Code: Select all

bool evolve(GridPtr from, GridPtr to, Rule r)
{
	bool empty = true;
	for (int x = 0; x < GRIDSIZE; x++)
	        if ((x == 0 ? false : from[x-1].any()) || from[x].any() || (x == GRIDSIZE-1) ? false : from[x+1].any())
		for (int y = 0; y < GRIDSIZE; y++)
		{
			int n0 = shr(x ==          0 ? 0ull : from[x - 1].to_ullong(), y-1) & 7;
			int n1 = shr(                         from[x    ].to_ullong(), y-1) & 7;
			int n2 = shr(x == GRIDSIZE-1 ? 0ull : from[x + 1].to_ullong(), y-1) & 7;
			int neighbors = n0 | (n1 << 3) | (n2 << 6);
			to[x][y] = r.evolve(neighbors);
			if (to[x][y])
			{
				empty = false;
				if (x == 0 || x == GRIDSIZE - 1 || y == 0 || y == GRIDSIZE - 1) return false;
			}
		}
	return !empty;
}

then this appears to make it around 10x faster.

[Redstoneboi]

I can't seem to get the "empty space" patch to work. It just tells me 0 results found every time for whatever reason.

What if the rule evolver stored the bounding box of the pattern every tick instead? that way it would be able to skip both axes of empty space and compare equality of patterns faster per tick.
The problem would be the overhead of checking the min/max x and y positions.

[islptng]

Bump

v2.2.3 Precompiled for Windows and Ubuntu is available!

TarRuleSrc-2.2.3-win-ubuntu.tar

(1.96 MiB) Downloaded 77 times

For those who don't want to get a C++ environment on their computer. A readme is also inside.