Currently known bugs:
Symmetries are completely broken.
Negation in rules (such as B2-ac3/S23) is broken. This can be dealt with by using all the transitions (B2eikn3/S23).
I know everything looks messy, I am just a horrible programmer.
Code: Select all
// SuperStringSearch v0.1 by Sylvani
// Type -h for help.
// Compile with the following command (requires g++):
// g++ -O3 -flto -pthread -march=native -openmp -o supstrsrc supstrsrc.cpp
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <sstream>
#include <thread>
#include <random>
#include <climits>
static int GENERATIONS = 2;
static bool RULE_TABLE[102];
const int PERMUTATIONS[8][8] = { // rotate4reflect symmetry
{0, 1, 2, 3, 4, 5, 6, 7},
{2, 3, 4, 5, 6, 7, 0, 1},
{4, 5, 6, 7, 0, 1, 2, 3},
{6, 7, 0, 1, 2, 3, 4, 5},
{0, 7, 6, 5, 4, 3, 2, 1},
{2, 1, 0, 7, 6, 5, 4, 3},
{4, 3, 2, 1, 0, 7, 6, 5},
{6, 5, 4, 3, 2, 1, 0, 7},
};
static int offsets[9] = { 0, 1, 3, 9, 19, 32, 42, 48, 50 };
static int sizes[9] = { 1, 2, 6, 10, 13, 10, 6, 2, 1 };
static int HENSEL[51][8] = {
{0, 0, 0, 0, 0, 0, 0, 0}, // 0
{0, 1, 0, 0, 0, 0, 0, 0}, // 1c
{1, 0, 0, 0, 0, 0, 0, 0}, // 1e
{1, 1, 0, 0, 0, 0, 0, 0}, // 2a
{0, 1, 0, 1, 0, 0, 0, 0}, // 2c
{1, 0, 1, 0, 0, 0, 0, 0}, // 2e
{1, 0, 0, 0, 1, 0, 0, 0}, // 2i
{1, 0, 0, 1, 0, 0, 0, 0}, // 2k
{0, 1, 0, 0, 0, 1, 0, 0}, // 2n
{1, 1, 1, 0, 0, 0, 0, 0}, // 3a
{0, 1, 0, 1, 0, 1, 0, 0}, // 3c
{1, 0, 1, 0, 1, 0, 0, 0}, // 3e
{0, 1, 1, 1, 0, 0, 0, 0}, // 3i
{0, 1, 1, 0, 1, 0, 0, 0}, // 3j
{1, 0, 1, 0, 0, 1, 0, 0}, // 3k
{0, 1, 0, 1, 1, 0, 0, 0}, // 3n
{0, 1, 1, 0, 0, 1, 0, 0}, // 3q
{0, 1, 1, 0, 0, 0, 1, 0}, // 3r
{0, 1, 0, 1, 0, 0, 1, 0}, // 3y
{1, 1, 1, 1, 0, 0, 0, 0}, // 4a
{0, 1, 0, 1, 0, 1, 0, 1}, // 4c
{1, 0, 1, 0, 1, 0, 1, 0}, // 4e
{1, 1, 0, 1, 1, 0, 0, 0}, // 4i
{0, 1, 1, 0, 1, 0, 1, 0}, // 4j
{1, 1, 0, 1, 0, 0, 1, 0}, // 4k
{0, 1, 1, 1, 0, 0, 0, 1}, // 4n
{1, 1, 1, 0, 0, 1, 0, 0}, // 4q
{1, 1, 1, 0, 1, 0, 0, 0}, // 4r
{0, 1, 1, 1, 0, 0, 1, 0}, // 4t
{0, 1, 1, 0, 1, 1, 0, 0}, // 4w
{0, 1, 0, 1, 1, 0, 0, 1}, // 4y
{0, 1, 1, 0, 0, 1, 1, 0}, // 4z
{0, 0, 0, 1, 1, 1, 1, 1}, // 5a
{1, 0, 1, 0, 1, 0, 1, 1}, // 5c
{0, 1, 0, 1, 0, 1, 1, 1}, // 5e
{1, 0, 0, 0, 1, 1, 1, 1}, // 5i
{1, 0, 0, 1, 0, 1, 1, 1}, // 5j
{1, 0, 1, 0, 1, 1, 1, 0}, // 5k
{1, 0, 1, 0, 0, 1, 1, 1}, // 5n
{1, 0, 0, 1, 1, 0, 1, 1}, // 5q
{1, 0, 0, 1, 1, 1, 0, 1}, // 5r
{1, 0, 1, 0, 1, 1, 0, 1}, // 5y
{0, 0, 1, 1, 1, 1, 1, 1}, // 6a
{1, 0, 1, 0, 1, 1, 1, 1}, // 6c
{0, 1, 0, 1, 1, 1, 1, 1}, // 6e
{0, 1, 1, 1, 0, 1, 1, 1}, // 6i
{0, 1, 1, 0, 1, 1, 1, 1}, // 6k
{1, 0, 1, 1, 1, 0, 1, 1}, // 6n
{1, 0, 1, 1, 1, 1, 1, 1}, // 7c
{0, 1, 1, 1, 1, 1, 1, 1}, // 7e
{1, 1, 1, 1, 1, 1, 1, 1}, // 8
};
static char HENSELC[51] = "xceaceiknaceijknqryaceijknqrtwyzaceijknqryaceiknce";
inline int rule(int center, const std::vector<int>& neighbor_states) {
int sum = 0;
for (int i = 0; i < 8; ++i) {
sum += neighbor_states[i] == 1;
}
int offset = offsets[sum];
int count = sizes[sum];
for (int i = 0; i < count; ++i) {
const int* pattern = HENSEL[offset + i];
for (int j = 0; j < 8; ++j) {
bool match = true;
for (int k = 0; k < 8; ++k) {
if (pattern[k] != neighbor_states[PERMUTATIONS[j][k]]) {
match = false;
break;
}
}
if (match) {
if (center == 1) {
return RULE_TABLE[center * 51 + offset + i];
}
else if (center == 0) {
return RULE_TABLE[center * 51 + offset + i];
}
}
}
}
return 0;
}
std::string rule_name() {
int b_offset = 0;
int s_offset = 51;
std::string s = "B";
for (int j = 0; j < 9; ++j) {
bool n = false;
int hs = 0;
for (int i = 0; i < sizes[j]; ++i) {
if (RULE_TABLE[offsets[j] + i + b_offset] == 1) {
hs++;
}
}
if (hs == sizes[j]) {
s += std::to_string(j);
continue;
}
if (hs > 0 && hs <= (sizes[j] / 2)) {
s += std::to_string(j);
}
else if (hs > (sizes[j] / 2)) {
s += std::to_string(j);
s += '-';
n = true;
}
if (!n) {
for (int i = 0; i < sizes[j]; ++i) {
if (RULE_TABLE[offsets[j] + i + b_offset] == 1) {
if (HENSELC[offsets[j] + i] != 'x') {
s += HENSELC[offsets[j] + i];
}
}
}
}
else {
for (int i = 0; i < sizes[j]; ++i) {
if (RULE_TABLE[offsets[j] + i + b_offset] != 1) {
if (HENSELC[offsets[j] + i] != 'x') {
s += HENSELC[offsets[j] + i];
}
}
}
}
}
s += "/";
s += "S";
for (int j = 0; j < 9; ++j) {
bool n = false;
int hs = 0;
for (int i = 0; i < sizes[j]; ++i) {
if (RULE_TABLE[offsets[j] + i + s_offset] == 1) {
hs++;
}
}
if (hs == sizes[j]) {
s += std::to_string(j);
continue;
}
if (hs > 0 && hs <= (sizes[j] / 2)) {
s += std::to_string(j);
}
else if (hs > (sizes[j] / 2)) {
s += std::to_string(j);
s += '-';
n = true;
}
if (!n) {
for (int i = 0; i < sizes[j]; ++i) {
if (RULE_TABLE[offsets[j] + i + s_offset] == 1) {
if (HENSELC[offsets[j] + i] != 'x') {
s += HENSELC[offsets[j] + i];
}
}
}
}
else {
for (int i = 0; i < sizes[j]; ++i) {
if (RULE_TABLE[offsets[j] + i + s_offset] != 1) {
if (HENSELC[offsets[j] + i] != 'x') {
s += HENSELC[offsets[j] + i];
}
}
}
}
}
return s;
}
void parse_rule(const std::string& r) {
bool birth = false;
int cur = 0;
bool neg = false;
for (int i = 0; i < r.length(); ++i) {
if (r[i] == 'B' || r[i] == 'b') { birth = true; continue; }
if (r[i] == 'S' || r[i] == 's') { birth = false; continue; }
if (r[i] == '0' && !birth) { RULE_TABLE[51] = 1; continue; }
if (isdigit(r[i])) {
cur = r[i] - '0';
neg = false;
if (r[i + 1] == '-') {
neg = true;
}
else if (isdigit(r[i + 1]) || r[i + 1] == '/' || i == (r.length() - 1)) {
for (int j = 0; j < sizes[cur]; ++j) {
if (HENSELC[offsets[cur] + j] != 'x') {
RULE_TABLE[!birth * 51 + offsets[cur] + j] = 1;
}
}
}
}
else if (r[i] != '/' && r[i] != '-') {
for (int j = 0; j < sizes[cur]; ++j) {
if ((neg ? r[i] != HENSELC[offsets[cur] + j] : r[i] == HENSELC[offsets[cur] + j]) && (HENSELC[offsets[cur] + j] != 'x')) {
RULE_TABLE[!birth * 51 + offsets[cur] + j] = 1;
}
}
}
}
}
typedef uint64_t Row;
enum Symmetry {
ASYM,
EVEN,
ODD,
GUTTER
};
static uint8_t g_vely = 1;
static uint8_t g_width = 7;
static uint64_t g_height = 100;
static Symmetry g_symmetry = ASYM;
static uint64_t g_maxp = 1000;
static bool g_wraph = true;
inline uint8_t getsafe(const int& idx, const Row& row, const Symmetry& symm = g_symmetry) {
if (g_wraph)
switch (symm) {
case ASYM:
return idx < 0 ? row >> (idx + g_width) & 1 : idx >= g_width ? row >> (idx - g_width) & 1 : row >> idx & 1;
case EVEN:
return idx < 0 ? row << (-idx - 1) & 1 : idx >= g_width ? row >> (idx - g_width) & 1 : row >> idx & 1;
case ODD:
return idx < 0 ? row << (-idx) & 1 : idx >= g_width ? row >> (idx - g_width) & 1 : row >> idx & 1;
case GUTTER:
return idx < 1 ? row << (-idx) & 1 : idx < 0 ? 0 : idx >= g_width ? row >> (idx - g_width) & 1 : row >> idx & 1;
}
else
switch (symm) {
case ASYM:
return idx < 0 ? 0 : idx > g_width ? 0 : row >> idx & 1;
case EVEN:
return idx < 0 ? row << (idx - 1) & 1 : idx > g_width ? 0 : row >> idx & 1;
case ODD:
return idx < 0 ? row << idx & 1 : idx > g_width ? 0 : row >> idx & 1;
case GUTTER:
return idx < 1 ? row << (idx + 1) & 1 : idx < 0 ? 0 : idx > g_width ? 0 : row >> idx & 1;
}
return 0;
}
struct Grid {
std::unordered_set<size_t> hashes;
std::vector<Row> rows;
uint8_t width;
uint8_t height;
Grid(uint8_t width, uint8_t height) : width(width), height(height) { rows = std::vector<Row>(height, 0); }
void rotate(int d) {
int n = rows.size();
d = d % n;
if (d < 0) {
d += n;
}
if (d != 0) std::rotate(rows.begin(), rows.begin() + d, rows.end());
rows.back() = 0;
}
Row evorow(Row a, Row b, Row c) {
Row d = 0;
int neighbor_states[8] = { 0 };
for (int i = 0; i < width; ++i) {
d |= rule(b >> i & 1, std::vector<int>({ getsafe(i - 1, a), getsafe(i, a), getsafe(i + 1, a), getsafe(i - 1, b), getsafe(i + 1, b), getsafe(i - 1, c), getsafe(i, c), getsafe(i + 1, c) })) << i;
}
return d;
}
void evo() {
std::vector<Row> next;
for (int i = 0; i < height; ++i) {
Row a = i == 0 ? 0 : rows[i - 1];
Row b = rows[i];
Row c = (i + 1) == height ? 0 : rows[i + 1];
next.push_back(evorow(a, b, c));
}
rows = next;
next.clear();
}
void make_soup(std::mt19937& engine, std::uniform_int_distribution<int>& dist) {
srand(time(0));
for (int i = 0; i < height - 2; ++i) {
rows[rows.size() - i - 2] = dist(engine) & ((1 << width + 1) - 1);
}
rows[rows.size() - 2] = (1 << width + 1) - 1;
}
void print_row(size_t idx, std::stringstream& ss) {
if (rows[idx] != 0)
for (int i = 0; i < width; ++i) {
ss << "bo"[rows[idx] >> i & 1];
}
ss << "$!"[idx==0];
}
size_t hash() {
size_t s = 0;
for (Row r : rows) {
s ^= std::hash<Row>{}(r) + 0x9e3779b9 + (s<<6) + (s>>2);
}
return s;
}
};
bool cmdOptionExists(char** begin, char** end, const std::string& option) {
return std::find(begin, end, option) != end;
}
char* getCmdOption(char** begin, char** end, const std::string& option) {
char** itr = std::find(begin, end, option);
if (itr != end && ++itr != end) {
return *itr;
}
return nullptr;
}
void search(int id) {
Grid g(g_width, g_height);
std::stringstream ss;
thread_local std::mt19937 engine(std::random_device{}());
std::uniform_int_distribution<int> dist(0, INT_MAX);
while (1) {
g.make_soup(engine, dist);
while (1) {
g.evo();
g.rotate(1);
size_t h = g.hash();
if (g.hashes.count(h)) {
break;
}
g.hashes.insert(h);
}
g.hashes.clear();
size_t h2 = g.hash();
int p = 1;
while (p < g_maxp) {
g.rotate(1);
g.evo();
size_t h = g.hash();
if (h2 == h) {
break;
}
p++;
}
if (p == g_maxp || p == 1) continue;
ss << "#C Period: " << p << std::endl;
ss << "x = " << (int)g_width << ", y = " << g_height << ", rule = " << rule_name() << std::endl;
for (int i = g_height - 1; i >= 0; --i) {
g.print_row(i, ss);
}
ss << std::endl;
std::cout << ss.str();
ss.str("");
ss.clear();
}
}
int main(int argc, char* argv[]) {
if (cmdOptionExists(argv, argv + argc, "-h") || cmdOptionExists(argv, argv + argc, "--help") || argc <= 1) {
std::cout << "Usage: " << argv[0] << " [-h|--help] [-r <rule>] [-w <width>] [-s <symmetry>] [-m <max_period>] [-d <max_height>] [-p|--b012a]" << std::endl;
return 0;
}
if (cmdOptionExists(argv, argv + argc, "-p") || cmdOptionExists(argv, argv + argc, "--b012a")) {
g_wraph = false;
}
char* rule = getCmdOption(argv, argv + argc, "-r");
char* width = getCmdOption(argv, argv + argc, "-w");
char* height = getCmdOption(argv, argv + argc, "-d");
char* symm = getCmdOption(argv, argv + argc, "-s");
if (rule) parse_rule(std::string(rule)); else parse_rule("B3/S23");
if (width) g_width = atoi(width);
if (height) g_height = atoi(height);
if (symm)
switch (symm[0]) {
case 'a':
g_symmetry = ASYM;
break;
case 'o':
g_symmetry = ODD;
break;
case 'e':
g_symmetry = EVEN;
break;
}
std::vector<std::thread> threads;
for (int i = 0; i < std::thread::hardware_concurrency(); ++i)
threads.emplace_back(search, i);
while (1) {
for (int i = 0; i < std::thread::hardware_concurrency(); ++i)
if (threads[i].joinable()) threads[i].join();
}
return 0;
}