Written in C++.
This is a very crude search program for still lives, oscillators, and spaceships.
This program will, at first, search patterns in a small grid, and when searching is completed within that grid, expand that grid by one row, or one column if that grid is a square. ((3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4),(5,1), and so on.)
This program does this because it will only search for patterns that fits in that grid.
Also, this program won't search mirrored or rotated copy of already searched pattern.
... But, when searching in a square grid, The program will search for 2 copies of them. (This is considered a bug, but it is very hard to fix it)
This program won't search for any subperiod.
This program will only find one result.
This program will be automatically parallelized for multi-core processor.
The codes of the program:
Code: Select all
#ifndef LIFE_H_INCLUDED
#define LIFE_H_INCLUDED
#include <array>
#include <bitset>
#include <string>
#include <vector>
#include <utility>
#include <cstdint>
#include <iostream>
#include <unordered_map>
#include <initializer_list>
namespace NDos {
struct liferule {
std::bitset<9> B; // No access to B0!
std::bitset<9> S;
};
constexpr liferule GOL = {0b000001000, 0b000001100};
struct lifecell { // A cell
std::int8_t x; // x coordinate
std::int8_t y; // y coordinate
};
bool operator == (const lifecell &a, const lifecell &b) { // Compare object that compares cells by coordinate
return reinterpret_cast<const std::uint16_t&>(a) == reinterpret_cast<const std::uint16_t&>(b);
};
}
namespace std {
template <> struct hash<NDos::lifecell> {
public:
size_t operator () (const NDos::lifecell &cell) const noexcept {
return reinterpret_cast<const std::uint16_t&>(cell);
}
};
}
namespace NDos {
class pattern {
private:
typedef std::unordered_map<lifecell, int> cellmap;
cellmap on; // "ON" cells
cellmap off; // "OFF" cells that is neighbor to "ON" cells
public:
typedef cellmap::key_type key_type; // A cell
typedef cellmap::mapped_type mapped_type; // its neighbor count
typedef cellmap::value_type value_type;
typedef cellmap::hasher hasher;
typedef cellmap::key_equal key_equal;
typedef cellmap::allocator_type allocator_type;
typedef cellmap::size_type size_type;
typedef cellmap::difference_type difference_type;
typedef cellmap::reference reference;
typedef cellmap::const_reference const_reference;
typedef cellmap::pointer pointer;
typedef cellmap::const_pointer const_pointer;
typedef cellmap::const_iterator iterator;
typedef cellmap::const_iterator const_iterator;
typedef cellmap::const_local_iterator local_iterator;
typedef cellmap::const_local_iterator const_local_iterator;
pattern() = default;
pattern(std::initializer_list<std::array<std::int8_t, 2u>> coords) : pattern() {
for (const auto &i : coords)
insert(lifecell{i[0], i[1]});
}
// copy constructor : default
// move constructor : default
// copy assignment operator : default
// move assignment operator : default
// destructor : default
bool empty() const noexcept {
return on.empty();
}
size_type size() const noexcept { // population
return on.size();
}
size_type max_size() const noexcept {
return on.max_size();
}
void clear() noexcept {
on.clear();
for (auto &cell : off)
cell.second = 0;
}
bool insert(lifecell cell) {
if (on.find(cell) == on.end()) {
{
const auto i = off.find(cell);
if (i == off.end())
on[cell] = 0;
else {
on[cell] = i->second;
off.erase(i);
}
}
constexpr std::int8_t disp[][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
for (const auto &d : disp) {
lifecell neigh{static_cast<std::int8_t>(cell.x+d[0]), static_cast<std::int8_t>(cell.y+d[1])};
if (on.count(neigh) != 0)
++on[neigh];
else if (off.count(neigh) != 0)
++off[neigh];
else
off[neigh] = 1;
}
return true;
} else
return false;
}
void erase(lifecell cell) {
const auto i = on.find(cell);
if (i == on.end())
return;
constexpr std::int8_t disp[][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
for (const auto &d : disp) {
lifecell neigh{static_cast<std::int8_t>(cell.x+d[0]), static_cast<std::int8_t>(cell.y+d[1])};
--off[neigh];
--on[neigh];
}
on.erase(i);
}
pattern generate(const liferule &rule) {
pattern temp;
for (const auto &cell : off) {
if (rule.B[cell.second])
temp.insert(cell.first);
}
for (const auto &cell : on) {
if (rule.S[cell.second])
temp.insert(cell.first);
}
return temp;
}
pattern translate(std::int8_t x, std::int8_t y) const {
pattern temp;
for (const auto &cell : on)
temp.insert(lifecell{static_cast<std::int8_t>(cell.first.x + x), static_cast<std::int8_t>(cell.first.y + y)});
return temp;
}
/*
pattern flip_x() const {
pattern temp;
for (const auto &cell : on)
temp.insert(lifecell{-cell.first.x, cell.first.y});
return temp;
}
pattern flip_y() const {
pattern temp;
for (const auto &cell : on)
temp.insert(lifecell{cell.first.x, -cell.first.y});
return temp;
}
pattern rotate_CCW() const {
pattern temp;
for (const auto &cell : on)
temp.insert(lifecell{-cell.first.y, cell.first.x});
return temp;
}
pattern rotate_CW() const {
pattern temp;
for (const auto &cell : on)
temp.insert(lifecell{cell.first.y, -cell.first.x});
return temp;
}
*/
friend std::ostream &operator << (std::ostream &s, const pattern &p) {
if (p.empty())
return s;
std::int8_t ybegin = p.on.begin()->first.y, yend = p.on.begin()->first.y;
std::int8_t xbegin = p.on.begin()->first.x, xend = p.on.begin()->first.x;
for (const auto &cell : p.on) {
if (cell.first.x < xbegin)
xbegin = cell.first.x;
if (cell.first.x > xend)
xend = cell.first.x;
if (cell.first.y < ybegin)
ybegin = cell.first.y;
if (cell.first.y > yend)
yend = cell.first.y;
}
++yend;
++xend;
std::vector<std::string> out(yend - ybegin, std::string(xend - xbegin, '.'));
for (const auto &cell : p.on)
out[cell.first.y - ybegin][cell.first.x - xbegin] = '0';
for (const auto &row : out)
s << row << std::endl;
return s;
}
friend bool operator == (const pattern &a, const pattern &b) {
return a.on == b.on;
}
};
}
#endif // LIFE_H_INCLUDED
Code: Select all
/*
NDosearch 1.1
Written by Bag Sinhwan(aka Dannyu NDos).
Configure period, x_trans, y_trans, min_column, and OUTPUT_FILE below.
Order of x_trans and y_trans doesn't matter.
*/
#include "Life.h"
constexpr std::int8_t period = 3, x_trans = 0, y_trans = 0;
constexpr std::int8_t min_column = 3;
#define OUTPUT_FILE 0
class grid {
private:
std::vector<std::pair<NDos::lifecell, std::int8_t>> cells;
// orientation: for 0b0000DCBA:
// DB
// CA
enum sym : std::int8_t {OMNI = 0b1111, ROT2 = 0b0110, REFY = 0b0101, REFX = 0b0011, ASY = 0b0001};
std::vector<std::pair<NDos::lifecell, sym>> symstack;
NDos::lifecell right, left, down, up;
static const NDos::lifecell invalid_cell;
const std::int8_t X, Y;
void undo_edge() noexcept {
if (cells.back().first == right)
right = invalid_cell;
if (cells.back().first == left)
left = invalid_cell;
if (cells.back().first == down)
down = invalid_cell;
if (cells.back().first == up)
up = invalid_cell;
}
void update_edge() noexcept {
if (right == invalid_cell && (X - 1) >> 1 == cells.back().first.x && (cells.back().second & 0b0011) != 0)
right = cells.back().first;
if (left == invalid_cell && (X - 1) >> 1 == cells.back().first.x && (cells.back().second & 0b1100) != 0)
left = cells.back().first;
if (down == invalid_cell && (Y - 1) >> 1 == cells.back().first.y && (cells.back().second & 0b0101) != 0)
down = cells.back().first;
if (up == invalid_cell && (Y - 1) >> 1 == cells.back().first.y && (cells.back().second & 0b1010) != 0)
up = cells.back().first;
}
void undo_sym() noexcept {
if (cells.back().first == symstack.back().first)
symstack.pop_back();
}
void update_sym() noexcept {
switch (cells.back().second) {
case 0b1111: break;
case 0b0110: case 0b1001:
if (OMNI == symstack.back().second)
symstack.emplace_back(cells.back().first, ROT2);
if (REFY == symstack.back().second || REFX == symstack.back().second)
symstack.emplace_back(cells.back().first, ASY);
break;
case 0b0101: case 0b1010:
if (OMNI == symstack.back().second)
symstack.emplace_back(cells.back().first, REFY);
if (ROT2 == symstack.back().second || REFX == symstack.back().second)
symstack.emplace_back(cells.back().first, ASY);
break;
case 0b0011: case 0b1100:
if (OMNI == symstack.back().second)
symstack.emplace_back(cells.back().first, REFX);
if (ROT2 == symstack.back().second || REFY == symstack.back().second)
symstack.emplace_back(cells.back().first, ASY);
break;
default:
if (ASY != symstack.back().second)
symstack.emplace_back(cells.back().first, ASY);
}
}
void enumerate_sym() noexcept {
undo_edge();
undo_sym();
do {
if (X % 2 == 1 && 0 == cells.back().first.x)
cells.back().second = 0b0101 == cells.back().second ? 0b1010 : 0b1111;
else if (Y % 2 == 1 && 0 == cells.back().first.y)
cells.back().second = 0b0011 == cells.back().second ? 0b1100 : 0b1111;
else
++cells.back().second;
} while (symstack.back().second != ASY && 0b1111 != cells.back().second && (
symstack.back().second == ROT2 ? (cells.back().second & 0b1100) != 0b0100 && (cells.back().second & 0b0101) != 0b0001 :
(cells.back().second & 0b1001) != 0b0001 && (
symstack.back().second == REFY ? (cells.back().second & 0b0011) != 0b0010 :
symstack.back().second == REFX ? (cells.back().second & 0b0101) != 0b0100 : 0b0110 != cells.back().second
)));
update_sym();
update_edge();
}
void enumerate_coor() {
if ((X - 1) >> 1 == cells.back().first.x) {
++cells.back().first.y;
cells.back().first.x = 0;
} else
++cells.back().first.x;
cells.back().second = 0 != cells.back().first.x || X % 2 == 0 ?
0 != cells.back().first.y || Y % 2 == 0 ? 0b0001 : 0b0011 :
0 != cells.back().first.y || Y % 2 == 0 ? 0b0101 : 0b1111;
update_sym();
update_edge();
}
public:
grid(std::int8_t _x, std::int8_t _y)
: symstack{std::make_pair(NDos::lifecell{0, 0}, OMNI)},
right{invalid_cell}, left{invalid_cell}, down{invalid_cell}, up{invalid_cell},
X(_x), Y(_y) {
std::int8_t orientation = X % 2 == 0 ? (Y % 2 == 0 ? 0b0001 : 0b0011) : Y % 2 == 0 ? 0b0101 : 0b1111;
cells.emplace_back(NDos::lifecell{0, 0}, orientation);
if (OMNI != static_cast<sym>(orientation))
symstack.emplace_back(cells.back().first, static_cast<sym>(orientation));
update_edge();
enumerate();
}
bool enumerate() {
do {
if ((X - 1) >> 1 == cells.back().first.x && (Y - 1) >> 1 == cells.back().first.y) {
if (0b1111 == cells.back().second) {
undo_edge();
cells.pop_back();
if (cells.empty())
return false;
if (0b1111 == cells.back().second) {
undo_edge();
enumerate_coor();
continue;
}
}
enumerate_sym();
} else {
cells.push_back(cells.back());
enumerate_coor();
}
} while (right == invalid_cell || left == invalid_cell || down == invalid_cell || up == invalid_cell);
return true;
}
operator NDos::pattern() const {
NDos::pattern result;
for (const auto &cell : cells) {
if ((cell.second & 0b0001) != 0)
result.insert(cell.first);
if ((cell.second & 0b0010) != 0)
result.insert(NDos::lifecell{cell.first.x, static_cast<std::int8_t>(Y % 2 == 0 ? ~cell.first.y : -cell.first.y)});
if ((cell.second & 0b0100) != 0)
result.insert(NDos::lifecell{static_cast<std::int8_t>(X % 2 == 0 ? ~cell.first.x : -cell.first.x), cell.first.y});
if ((cell.second & 0b1000) != 0)
result.insert(NDos::lifecell{
static_cast<std::int8_t>(X % 2 == 0 ? ~cell.first.x : -cell.first.x),
static_cast<std::int8_t>(Y % 2 == 0 ? ~cell.first.y : -cell.first.y)
});
}
return result;
}
friend std::ostream &operator << (std::ostream &s, const grid &p) {
std::vector<std::string> out(p.Y, std::string(p.X, '.'));
for (const auto &cell : p.cells) {
if ((cell.second & 0b0001) != 0)
out[cell.first.y + (p.Y >> 1)][cell.first.x + (p.X >> 1)] = '0';
if ((cell.second & 0b0010) != 0)
out[(p.Y % 2 == 0 ? ~cell.first.y : -cell.first.y) + (p.Y >> 1)][cell.first.x + (p.X >> 1)] = '0';
if ((cell.second & 0b0100) != 0)
out[cell.first.y + (p.Y >> 1)][(p.X % 2 == 0 ? ~cell.first.x : -cell.first.x) + (p.X >> 1)] = '0';
if ((cell.second & 0b1000) != 0)
out[(p.Y % 2 == 0 ? ~cell.first.y : -cell.first.y) + (p.Y >> 1)]
[(p.X % 2 == 0 ? ~cell.first.x : -cell.first.x) + (p.X >> 1)] = '0';
}
for (auto &row : out)
s << row << std::endl;
return s;
}
};
const NDos::lifecell grid::invalid_cell{-1, -1};
#include <list>
#include <future>
#include <thread>
#if OUTPUT_FILE
#include <fstream>
#endif
const unsigned max_threads = 0 == std::thread::hardware_concurrency() ? 0 : std::thread::hardware_concurrency() - 1;
std::list<std::int8_t> factors_orig;
int main() {
#if OUTPUT_FILE
std::ofstream output_file("Result.txt");
if (!output_file) {
std::cout << "File not found." << std::endl << "Press enter key." << std::endl;
std::cin.get();
return 1;
}
#endif
for (std::int8_t factor = 1; factor <= period; ++factor) {
if (period % factor == 0)
factors_orig.push_back(factor);
}
if (0 == max_threads) { // single core
for (std::int8_t x_search = min_column; true; ++x_search) {
for (std::int8_t y_search = 1; y_search <= x_search; ++y_search) {
std::cout << "Searching on (" << static_cast<int>(x_search) << ',' << static_cast<int>(y_search) << ") grid..." << std::endl;
unsigned long long pattern_so_far(0ull);
grid search_grid(x_search, y_search);
do {
if (++pattern_so_far % 100000ull == 0ull)
std::cout << pattern_so_far << " patterns processed..." << std::endl;
NDos::pattern patt_orig(search_grid), patt(patt_orig);
std::list<std::int8_t> factors(factors_orig);
for (std::int8_t gen = 1; gen < period; ++gen) {
patt = patt.generate(NDos::GOL);
if (patt.size() < patt_orig.size())
goto next_enumeration;
if (factors.front() == gen) {
factors.pop_front();
if (patt_orig == patt.translate(x_trans, y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(y_trans, x_trans))
|| (0 != x_trans && (patt_orig == patt.translate(-x_trans, y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(y_trans, -x_trans))))
|| (0 != y_trans && (patt_orig == patt.translate(x_trans, -y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(-y_trans, x_trans))
|| (0 != x_trans && (patt_orig == patt.translate(-x_trans, -y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(-y_trans, -x_trans)))))))
goto next_enumeration;
}
}
patt = patt.generate(NDos::GOL);
if (patt.size() >= patt_orig.size() && (patt_orig == patt.translate(x_trans, y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(y_trans, x_trans))
|| (0 != x_trans && (patt_orig == patt.translate(-x_trans, y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(y_trans, -x_trans))))
|| (0 != y_trans && (patt_orig == patt.translate(x_trans, -y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(-y_trans, x_trans))
|| (0 != x_trans && (patt_orig == patt.translate(-x_trans, -y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(-y_trans, -x_trans)))))))) {
#if OUTPUT_FILE
output_file << patt_orig << "Period: " << period << " X Translation: " << x_trans << " Y Translation: " << y_trans << std::endl << std::endl;
#endif
std::cout << "Pattern found:" << std::endl << patt_orig;
#if OUTPUT_FILE
output_file.close();
#endif
std::cout << "Press enter key." << std::endl;
std::cin.get();
return 0;
}
next_enumeration:;
} while (search_grid.enumerate());
}
}
} else { // multi core
for (std::int8_t x_search = min_column; true; ++x_search) {
for (std::int8_t y_search = 1; y_search <= x_search; ++y_search) {
std::cout << "Searching on (" << static_cast<int>(x_search) << ',' << static_cast<int>(y_search) << ") grid..." << std::endl;
unsigned long long pattern_so_far(0ull);
grid search_grid(x_search, y_search);
std::list<std::future<bool>> results_future;
std::vector<NDos::pattern> results;
std::mutex results_mutex;
do {
if (++pattern_so_far % 100000ull == 0ull)
std::cout << pattern_so_far << " patterns processed..." << std::endl;
if (0 != max_threads && results_future.size() == max_threads) {
if (results_future.front().get()) {
for (const auto &res : results) {
#if OUTPUT_FILE
output_file << res << "Period: " << static_cast<int>(period)
<< " X Translation: " << static_cast<int>(x_trans)
<< " Y Translation: " << static_cast<int>(y_trans) << std::endl << std::endl;
#endif
std::cout << "Pattern found:" << std::endl << res;
}
#if OUTPUT_FILE
output_file.close();
#endif
std::cout << "Press enter key." << std::endl;
std::cin.get();
return 0;
}
results_future.pop_front();
}
results_future.push_back(std::async([&, patt_orig = (NDos::pattern)search_grid]{
std::list<std::int8_t> factors(factors_orig);
NDos::pattern patt(patt_orig);
for (std::int8_t gen = 1; gen < period; ++gen) {
patt = patt.generate(NDos::GOL);
if (patt.size() < patt_orig.size())
return false;
if (factors.front() == gen) {
factors.pop_front();
if (patt_orig == patt.translate(x_trans, y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(y_trans, x_trans))
|| (0 != x_trans && (patt_orig == patt.translate(-x_trans, y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(y_trans, -x_trans))))
|| (0 != y_trans && (patt_orig == patt.translate(x_trans, -y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(-y_trans, x_trans))
|| (0 != x_trans && (patt_orig == patt.translate(-x_trans, -y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(-y_trans, -x_trans)))))))
return false;
}
}
patt = patt.generate(NDos::GOL);
if (patt.size() >= patt_orig.size() && (patt_orig == patt.translate(x_trans, y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(y_trans, x_trans))
|| (0 != x_trans && (patt_orig == patt.translate(-x_trans, y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(y_trans, -x_trans))))
|| (0 != y_trans && (patt_orig == patt.translate(x_trans, -y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(-y_trans, x_trans))
|| (0 != x_trans && (patt_orig == patt.translate(-x_trans, -y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(-y_trans, -x_trans)))))))) {
std::lock_guard<std::mutex> results_guard(results_mutex);
results.push_back(std::move(patt_orig));
return true;
}
return false;
}));
} while (search_grid.enumerate());
while (!results_future.empty()) {
results_future.front().wait();
results_future.pop_front();
}
if (!results.empty()) {
for (const auto &res : results) {
#if OUTPUT_FILE
output_file << res << "Period: " << static_cast<int>(period)
<< " X Translation: " << static_cast<int>(x_trans)
<< " Y Translation: " << static_cast<int>(y_trans) << std::endl << std::endl;
#endif
std::cout << "Pattern found:" << std::endl << res;
}
#if OUTPUT_FILE
output_file.close();
#endif
std::cout << "Press enter key." << std::endl;
std::cin.get();
return 0;
}
}
}
}
}
/*
int main() {
grid test(4, 2);
do
std::cout << test << std::endl;
while (test.enumerate());
return 0;
}
*/
As you see in the code, there is configurable options:
period: Pattern's period to search for.
x_trans: Translation to x direction.
y_trans: Translation to y diraction. Order of x_trans and y_trans doesn't matter.
min_column: Minimum number of columns of pattern to search for. Must be 3 or greater.
OUTPUT_FILE: when set to 1, the program will save its result to "Result.txt"(it must be pre-created).
Also, there is an alternate version of this program. This alternative will search for only patterns that population is not greater than specific value. This program will find all such pattern.
Code: Select all
/*
NDosearch 1.1, alternate version
Written by Bag Sinhwan(aka Dannyu NDos).
Configure period, x_trans, y_trans, min_column, and OUTPUT_FILE below.
Order of x_trans and y_trans doesn't matter.
*/
#include "Life.h"
constexpr std::int8_t period = 4, x_trans = 1, y_trans = 1;
constexpr std::uint8_t min_column = 3u;
constexpr std::uint64_t Maxcell = 5u;
#define OUTPUT_FILE 0
class grid {
private:
std::vector<std::pair<NDos::lifecell, std::int8_t>> cells;
enum sym : std::int8_t {OMNI = 0b1111, ROT2 = 0b0110, REFY = 0b0101, REFX = 0b0011, ASY = 0b0001};
std::vector<std::pair<NDos::lifecell, sym>> symstack;
NDos::lifecell right, left, down, up;
std::uint64_t sz;
const std::int8_t X, Y;
static const NDos::lifecell invalidcell;
// orientation: DCBA
// DB
// CA
void undo_edge() noexcept {
if (cells.back().first == right)
right = invalidcell;
if (cells.back().first == left)
left = invalidcell;
if (cells.back().first == down)
down = invalidcell;
if (cells.back().first == up)
up = invalidcell;
}
void update_edge() noexcept {
if (right == invalidcell && (X - 1) >> 1 == cells.back().first.x && (cells.back().second & 0b0011) != 0)
right = cells.back().first;
if (left == invalidcell && (X - 1) >> 1 == cells.back().first.x && (cells.back().second & 0b1100) != 0)
left = cells.back().first;
if (down == invalidcell && (Y - 1) >> 1 == cells.back().first.y && (cells.back().second & 0b0101) != 0)
down = cells.back().first;
if (up == invalidcell && (Y - 1) >> 1 == cells.back().first.y && (cells.back().second & 0b1010) != 0)
up = cells.back().first;
}
std::uint64_t front_cells() const noexcept {
return (((cells.back().second & 0b0001) != 0)
+ ((cells.back().second & 0b0010) != 0)
+ ((cells.back().second & 0b0100) != 0)
+ ((cells.back().second & 0b1000) != 0))
>> ((X % 2 == 1 && 0 == cells.back().first.x)
+ (Y % 2 == 1 && 0 == cells.back().first.y));
}
void undo_sym() noexcept {
if (cells.back().first == symstack.back().first)
symstack.pop_back();
sz -= front_cells();
}
void update_sym() noexcept {
switch (cells.back().second) {
case 0b1111: break;
case 0b0110: case 0b1001:
if (OMNI == symstack.back().second)
symstack.emplace_back(cells.back().first, ROT2);
if (REFY == symstack.back().second || REFX == symstack.back().second)
symstack.emplace_back(cells.back().first, ASY);
break;
case 0b0101: case 0b1010:
if (OMNI == symstack.back().second)
symstack.emplace_back(cells.back().first, REFY);
if (ROT2 == symstack.back().second || REFX == symstack.back().second)
symstack.emplace_back(cells.back().first, ASY);
break;
case 0b0011: case 0b1100:
if (OMNI == symstack.back().second)
symstack.emplace_back(cells.back().first, REFX);
if (ROT2 == symstack.back().second || REFY == symstack.back().second)
symstack.emplace_back(cells.back().first, ASY);
break;
default:
if (ASY != symstack.back().second)
symstack.emplace_back(cells.back().first, ASY);
}
sz += front_cells();
}
void enumerate_sym() noexcept {
undo_edge();
undo_sym();
do {
if (X % 2 == 1 && 0 == cells.back().first.x)
cells.back().second = 0b0101 == cells.back().second ? 0b1010 : 0b1111;
else if (Y % 2 == 1 && 0 == cells.back().first.y)
cells.back().second = 0b0011 == cells.back().second ? 0b1100 : 0b1111;
else
++cells.back().second;
} while (symstack.back().second != ASY && 0b1111 != cells.back().second && (
symstack.back().second == ROT2 ? (cells.back().second & 0b1100) != 0b0100 && (cells.back().second & 0b0101) != 0b0001 :
(cells.back().second & 0b1001) != 0b0001 && (
symstack.back().second == REFY ? (cells.back().second & 0b0011) != 0b0010 :
symstack.back().second == REFX ? (cells.back().second & 0b0101) != 0b0100 : 0b0110 != cells.back().second
)));
update_sym();
update_edge();
}
void enumerate_coor() {
if ((X - 1) >> 1 == cells.back().first.x) {
++cells.back().first.y;
cells.back().first.x = 0;
} else
++cells.back().first.x;
cells.back().second = 0 != cells.back().first.x || X % 2 == 0 ?
0 != cells.back().first.y || Y % 2 == 0 ? 0b0001 : 0b0011 :
0 != cells.back().first.y || Y % 2 == 0 ? 0b0101 : 0b1111;
update_sym();
update_edge();
}
public:
grid(std::int8_t _x, std::int8_t _y)
: symstack{std::make_pair(invalidcell, OMNI)},
right{invalidcell}, left{invalidcell}, down{invalidcell}, up{invalidcell},
sz(1u), X(_x), Y(_y) {
std::int8_t orientation = X % 2 == 0 ? (Y % 2 == 0 ? 0b0001 : 0b0011) : Y % 2 == 0 ? 0b0101 : 0b1111;
cells.emplace_back(NDos::lifecell{0, 0}, orientation);
if (OMNI != static_cast<sym>(orientation))
symstack.emplace_back(cells.back().first, static_cast<sym>(orientation));
update_edge();
enumerate();
}
std::uint64_t size() const noexcept {
return sz;
}
bool enumerate() {
do {
if ((X - 1) >> 1 == cells.back().first.x && (Y - 1) >> 1 == cells.back().first.y) {
if (0b1111 == cells.back().second) {
undo_edge();
sz -= 4 >> ((X % 2 == 1 && 0 == cells.back().first.x) + (Y % 2 == 1 && 0 == cells.back().first.y));
cells.pop_back();
if (cells.empty())
return false;
if (0b1111 == cells.back().second) {
undo_edge();
sz -= 4 >> ((X % 2 == 1 && 0 == cells.back().first.x) + (Y % 2 == 1 && 0 == cells.back().first.y));
enumerate_coor();
continue;
}
}
enumerate_sym();
} else if (sz >= Maxcell) {
if (0b1111 == cells.back().second) {
undo_edge();
sz -= 4 >> ((X % 2 == 1 && 0 == cells.back().first.x) + (Y % 2 == 1 && 0 == cells.back().first.y));
enumerate_coor();
continue;
}
enumerate_sym();
} else {
cells.push_back(cells.back());
enumerate_coor();
}
} while (sz > Maxcell || right == invalidcell || left == invalidcell || down == invalidcell || up == invalidcell);
return true;
}
operator NDos::pattern() const {
NDos::pattern result;
for (const auto &cell : cells) {
if ((cell.second & 0b0001) != 0)
result.insert(cell.first);
if ((cell.second & 0b0010) != 0)
result.insert(NDos::lifecell{cell.first.x, static_cast<std::int8_t>(Y % 2 == 0 ? ~cell.first.y : -cell.first.y)});
if ((cell.second & 0b0100) != 0)
result.insert(NDos::lifecell{static_cast<std::int8_t>(X % 2 == 0 ? ~cell.first.x : -cell.first.x), cell.first.y});
if ((cell.second & 0b1000) != 0)
result.insert(NDos::lifecell{
static_cast<std::int8_t>(X % 2 == 0 ? ~cell.first.x : -cell.first.x),
static_cast<std::int8_t>(Y % 2 == 0 ? ~cell.first.y : -cell.first.y)
});
}
return result;
}
friend std::ostream &operator << (std::ostream &s, const grid &p) {
std::vector<std::string> out(p.Y, std::string(p.X, '.'));
for (const auto &cell : p.cells) {
if ((cell.second & 0b0001) != 0)
out[cell.first.y + (p.Y >> 1)][cell.first.x + (p.X >> 1)] = '0';
if ((cell.second & 0b0010) != 0)
out[(p.Y % 2 == 0 ? ~cell.first.y : -cell.first.y) + (p.Y >> 1)][cell.first.x + (p.X >> 1)] = '0';
if ((cell.second & 0b0100) != 0)
out[cell.first.y + (p.Y >> 1)][(p.X % 2 == 0 ? ~cell.first.x : -cell.first.x) + (p.X >> 1)] = '0';
if ((cell.second & 0b1000) != 0)
out[(p.Y % 2 == 0 ? ~cell.first.y : -cell.first.y) + (p.Y >> 1)]
[(p.X % 2 == 0 ? ~cell.first.x : -cell.first.x) + (p.X >> 1)] = '0';
}
for (auto &row : out)
s << row << std::endl;
return s;
}
};
const NDos::lifecell grid::invalidcell{-1, -1};
#include <list>
#include <future>
#include <thread>
#if OUTPUT_FILE
#include <fstream>
#endif
const unsigned max_threads = 0 == std::thread::hardware_concurrency() ? 0 : std::thread::hardware_concurrency() - 1;
std::list<std::int8_t> factors_orig;
int main() {
#if OUTPUT_FILE
std::ofstream output_file("Result.txt");
if (!output_file) {
std::cout << "File not found." << std::endl << "Press enter key." << std::endl;
std::cin.get();
return 1;
}
#endif
for (std::int8_t factor = 1; factor <= period; ++factor) {
if (period % factor == 0)
factors_orig.push_back(factor);
}
if (0 == max_threads) { // single core
for (std::uint8_t x_search = min_column; x_search < Maxcell << 1u; ++x_search) {
for (std::uint8_t y_search = 1u; y_search <= x_search; ++y_search) {
std::cout << "Searching on (" << static_cast<int>(x_search) << ',' << static_cast<int>(y_search) << ") grid..." << std::endl;
unsigned long long pattern_so_far(0ull);
grid search_grid(x_search, y_search);
do {
if (++pattern_so_far % 100000ull == 0ull)
std::cout << pattern_so_far << " patterns processed..." << std::endl;
NDos::pattern patt_orig(search_grid), patt(patt_orig);
std::list<std::int8_t> factors(factors_orig);
for (std::int8_t gen = 1; gen < period; ++gen) {
patt = patt.generate(NDos::GOL);
if (patt.size() < patt_orig.size())
goto next_enumeration;
if (factors.front() == gen) {
factors.pop_front();
if (patt_orig == patt.translate(x_trans, y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(y_trans, x_trans))
|| (0 != x_trans && (patt_orig == patt.translate(-x_trans, y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(y_trans, -x_trans))))
|| (0 != y_trans && (patt_orig == patt.translate(x_trans, -y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(-y_trans, x_trans))
|| (0 != x_trans && (patt_orig == patt.translate(-x_trans, -y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(-y_trans, -x_trans)))))))
goto next_enumeration;
}
}
patt = patt.generate(NDos::GOL);
if (patt.size() >= patt_orig.size() && (patt_orig == patt.translate(x_trans, y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(y_trans, x_trans))
|| (0 != x_trans && (patt_orig == patt.translate(-x_trans, y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(y_trans, -x_trans))))
|| (0 != y_trans && (patt_orig == patt.translate(x_trans, -y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(-y_trans, x_trans))
|| (0 != x_trans && (patt_orig == patt.translate(-x_trans, -y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(-y_trans, -x_trans)))))))) {
#if OUTPUT_FILE
output_file << patt_orig << "Period: " << period << " X Translation: " << x_trans << " Y Translation: " << y_trans << std::endl << std::endl;
#endif
std::cout << "Pattern found:" << std::endl << patt_orig;
}
next_enumeration:;
} while (search_grid.enumerate());
}
}
} else { // multi core
for (std::uint8_t x_search = min_column; x_search < Maxcell << 1u; ++x_search) {
for (std::uint8_t y_search = 1u; y_search <= x_search; ++y_search) {
std::cout << "Searching on (" << static_cast<int>(x_search) << ',' << static_cast<int>(y_search) << ") grid..." << std::endl;
unsigned long long pattern_so_far(0ull);
grid search_grid(x_search, y_search);
std::list<std::future<bool>> results_future;
std::vector<NDos::pattern> results;
std::mutex results_mutex;
do {
if (++pattern_so_far % 100000ull == 0ull)
std::cout << pattern_so_far << " patterns processed..." << std::endl;
if (0 != max_threads && results_future.size() == max_threads) {
if (results_future.front().get()) {
for (const auto &res : results) {
#if OUTPUT_FILE
output_file << res << "Period: " << period << " X Translation: " << x_trans << " Y Translation: " << y_trans << std::endl << std::endl;
#endif
std::cout << "Pattern found:" << std::endl << res;
}
}
results_future.pop_front();
}
results_future.push_back(std::async([&, patt_orig = (NDos::pattern)search_grid]{
std::list<std::int8_t> factors(factors_orig);
NDos::pattern patt(patt_orig);
for (std::int8_t gen = 1; gen < period; ++gen) {
patt = patt.generate(NDos::GOL);
if (patt.size() < patt_orig.size())
return false;
if (factors.front() == gen) {
factors.pop_front();
if (patt_orig == patt.translate(x_trans, y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(y_trans, x_trans))
|| (0 != x_trans && (patt_orig == patt.translate(-x_trans, y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(y_trans, -x_trans))))
|| (0 != y_trans && (patt_orig == patt.translate(x_trans, -y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(-y_trans, x_trans))
|| (0 != x_trans && (patt_orig == patt.translate(-x_trans, -y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(-y_trans, -x_trans)))))))
return false;
}
}
patt = patt.generate(NDos::GOL);
if (patt.size() >= patt_orig.size() && (patt_orig == patt.translate(x_trans, y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(y_trans, x_trans))
|| (0 != x_trans && (patt_orig == patt.translate(-x_trans, y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(y_trans, -x_trans))))
|| (0 != y_trans && (patt_orig == patt.translate(x_trans, -y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(-y_trans, x_trans))
|| (0 != x_trans && (patt_orig == patt.translate(-x_trans, -y_trans)
|| (x_trans != y_trans && patt_orig == patt.translate(-y_trans, -x_trans)))))))) {
std::lock_guard<std::mutex> results_guard(results_mutex);
results.push_back(std::move(patt_orig));
return true;
}
return false;
}));
} while (search_grid.enumerate());
while (!results_future.empty()) {
results_future.front().wait();
results_future.pop_front();
}
if (!results.empty()) {
for (const auto &res : results) {
#if OUTPUT_FILE
output_file << res << "Period: " << period << " X Translation: " << x_trans << " Y Translation: " << y_trans << std::endl << std::endl;
#endif
std::cout << "Pattern found:" << std::endl << res;
}
}
}
}
}
#if OUTPUT_FILE
output_file.close();
#endif
std::cout << "Press enter key." << std::endl;
std::cin.get();
return 0;
}