ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

NDosearch 1.0

For scripts to aid with computation or simulation in cellular automata.

NDosearch 1.0

Postby David » February 5th, 2017, 8:10 am

Version 1.1 as Feb 13th, 2017. Significant speed improval. --Dannyu NDos

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:
#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

This is a general Life API. Save it as "Life.h". You can configure NDos::GOL to find patterns in other Life-like rules, but remember not to set B0!
/*
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;
}
*/

This is the search program. Save it as "NDosearch.cpp".
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.
/*
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;
}

Maxcell: The program will only search for pattern with population that is not greater than this value.
Last edited by David on February 5th, 2017, 11:59 pm, edited 1 time in total.
David
 
Posts: 211
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

Re: NDosearch 1.0

Postby GUYTU6J » February 5th, 2017, 9:45 am

There are so many problems...
--------开始编译--------
In file included from NDosearch.cpp:7:
Life.h:3:17: array: No such file or directory
Life.h:8:19: cstdint: No such file or directory
Life.h:10:25: unordered_map: No such file or directory
Life.h:11:28: initializer_list: No such file or directory
In file included from NDosearch.cpp:7:
Life.h:17: error: `constexpr' does not name a type
Life.h:17:31: invalid suffix "b000001000" on integer constant
Life.h:17:44: invalid suffix "b000001100" on integer constant
Life.h:19: error: using-declaration for non-member at class scope
Life.h:19: error: expected `;' before "x"
Life.h:20: error: using-declaration for non-member at class scope
Life.h:20: error: expected `;' before "y"
Life.h: In function `bool NDos::operator==(const NDos::lifecell&, const NDos::lifecell&)':
Life.h:23: error: ISO C++ forbids declaration of `type name' with no type
Life.h:23: error: expected `>'
Life.h:23: error: expected `('
Life.h:23: error: `uint16_t' is not a member of `std'
Life.h:23: error: expected primary-expression before '>' token
Life.h:23: error: ISO C++ forbids declaration of `type name' with no type
Life.h:23: error: expected `>'
Life.h:23: error: expected `('
Life.h:23: error: `uint16_t' is not a member of `std'
Life.h:23: error: expected primary-expression before '>' token
Life.h:23: error: expected `)' before ';' token
Life.h:23: error: expected `)' before ';' token
Life.h: At global scope:
Life.h:27: error: `hash' is not a template
Life.h:27: error: explicit specialization of non-template `std::hash'
Life.h:29: error: expected `;' before "noexcept"
Life.h:32: error: expected `;' before '}' token
Life.h:37: error: ISO C++ forbids declaration of `unordered_map' with no type
Life.h:37: error: expected `;' before '<' token
Life.h:38: error: `cellmap' does not name a type
Life.h:39: error: `cellmap' does not name a type
Life.h:41: error: `cellmap' has not been declared
Life.h:41: error: ISO C++ forbids declaration of `key_type' with no type
Life.h:41: error: expected `;' before "key_type"
Life.h:42: error: `cellmap' has not been declared
Life.h:42: error: ISO C++ forbids declaration of `mapped_type' with no type
Life.h:42: error: expected `;' before "mapped_type"
Life.h:43: error: `cellmap' has not been declared
Life.h:43: error: ISO C++ forbids declaration of `value_type' with no type
Life.h:43: error: expected `;' before "value_type"
Life.h:44: error: `cellmap' has not been declared
Life.h:44: error: ISO C++ forbids declaration of `hasher' with no type
Life.h:44: error: expected `;' before "hasher"
Life.h:45: error: `cellmap' has not been declared
Life.h:45: error: ISO C++ forbids declaration of `key_equal' with no type
Life.h:45: error: expected `;' before "key_equal"
Life.h:46: error: `cellmap' has not been declared
Life.h:46: error: ISO C++ forbids declaration of `allocator_type' with no type
Life.h:46: error: expected `;' before "allocator_type"
Life.h:47: error: `cellmap' has not been declared
Life.h:47: error: ISO C++ forbids declaration of `size_type' with no type
Life.h:47: error: expected `;' before "size_type"
Life.h:48: error: `cellmap' has not been declared
Life.h:48: error: ISO C++ forbids declaration of `difference_type' with no type
Life.h:48: error: expected `;' before "difference_type"
Life.h:49: error: `cellmap' has not been declared
Life.h:49: error: ISO C++ forbids declaration of `reference' with no type
Life.h:49: error: expected `;' before "reference"
Life.h:50: error: `cellmap' has not been declared
Life.h:50: error: ISO C++ forbids declaration of `const_reference' with no type
Life.h:50: error: expected `;' before "const_reference"
Life.h:51: error: `cellmap' has not been declared
Life.h:51: error: ISO C++ forbids declaration of `pointer' with no type
Life.h:51: error: expected `;' before "pointer"
Life.h:52: error: `cellmap' has not been declared
Life.h:52: error: ISO C++ forbids declaration of `const_pointer' with no type
Life.h:52: error: expected `;' before "const_pointer"
Life.h:53: error: `cellmap' has not been declared
Life.h:53: error: ISO C++ forbids declaration of `const_iterator' with no type
Life.h:53: error: expected `;' before "iterator"
Life.h:54: error: `cellmap' has not been declared
Life.h:54: error: ISO C++ forbids declaration of `const_iterator' with no type
Life.h:54: error: expected `;' before "const_iterator"
Life.h:55: error: `cellmap' has not been declared
Life.h:55: error: ISO C++ forbids declaration of `const_local_iterator' with no type
Life.h:55: error: expected `;' before "local_iterator"
Life.h:56: error: `cellmap' has not been declared
Life.h:56: error: ISO C++ forbids declaration of `const_local_iterator' with no type
Life.h:56: error: expected `;' before "const_local_iterator"
Life.h:57: error: expected `0' before "default"
Life.h:57: error: invalid initializer for virtual method `NDos::pattern::pattern()'
Life.h:57: error: expected `;' before "default"
Life.h:58: error: expected `)' before '<' token
Life.h:67: error: expected `;' before "noexcept"
Life.h:70: error: expected `;' before "size_type"
Life.h:70: error: `size_type' does not name a type
Life.h:73: error: `size_type' does not name a type
Life.h:76: error: expected `;' before "noexcept"
Life.h:81: error: expected `;' before "bool"
Life.h:130: error: `std::int8_t' has not been declared
Life.h:130: error: `std::int8_t' has not been declared
Life.h:130: error: ISO C++ forbids declaration of `x' with no type
Life.h:130: error: ISO C++ forbids declaration of `y' with no type
Life.h: In member function `bool NDos::pattern::insert(NDos::lifecell)':
Life.h:82: error: `on' was not declared in this scope
Life.h:84: error: ISO C++ forbids declaration of `i' with no type
Life.h:84: error: `off' was not declared in this scope
Life.h:88: error: base operand of `->' is not a pointer
Life.h:92: error: `constexpr' was not declared in this scope
Life.h:92: error: expected `;' before "std"
Life.h:93: error: a function-definition is not allowed here before ':' token
Life.h:102: error: expected primary-expression before "return"
Life.h:102: error: expected `;' before "return"
Life.h:102: error: expected primary-expression before "return"
Life.h:102: error: expected `)' before "return"
Life.h:92: warning: unused variable 'constexpr'
Life.h: In member function `void NDos::pattern::erase(NDos::lifecell)':
Life.h:107: error: ISO C++ forbids declaration of `i' with no type
Life.h:107: error: `on' was not declared in this scope
Life.h:110: error: `constexpr' was not declared in this scope
Life.h:110: error: expected `;' before "std"
Life.h:111: error: a function-definition is not allowed here before ':' token
Life.h:117: error: expected primary-expression before '}' token
Life.h:117: error: expected `)' before '}' token
Life.h:117: error: expected primary-expression before '}' token
Life.h:117: error: expected `;' before '}' token
Life.h:110: warning: unused variable 'constexpr'
Life.h: In member function `NDos::pattern NDos::pattern::generate(const NDos::liferule&)':
Life.h:119: error: no matching function for call to `NDos::pattern::pattern()'
Life.h:35: note: candidates are: NDos::pattern::pattern(const NDos::pattern&)
Life.h:120: error: a function-definition is not allowed here before ':' token
Life.h:124: error: expected primary-expression before "for"
Life.h:124: error: expected `;' before "for"
Life.h:124: error: expected primary-expression before "for"
Life.h:124: error: expected `)' before "for"
Life.h:124: error: a function-definition is not allowed here before ':' token
Life.h:128: error: expected primary-expression before "return"
Life.h:128: error: expected `;' before "return"
Life.h:128: error: expected primary-expression before "return"
Life.h:128: error: expected `)' before "return"
Life.h: In member function `NDos::pattern NDos::pattern::translate(int, int) const':
Life.h:131: error: no matching function for call to `NDos::pattern::pattern()'
Life.h:35: note: candidates are: NDos::pattern::pattern(const NDos::pattern&)
Life.h:132: error: a function-definition is not allowed here before ':' token
Life.h:133: error: expected primary-expression before ')' token
Life.h:133: error: expected `;' before ')' token
Life.h: In function `std::ostream& NDos::operator<<(std::ostream&, const NDos::pattern&)':
Life.h:163: error: 'const class NDos::pattern' has no member named 'empty'
Life.h:165: error: `int8_t' is not a member of `std'
Life.h:165: error: expected `;' before "ybegin"
Life.h:166: error: `int8_t' is not a member of `std'
Life.h:166: error: expected `;' before "xbegin"
Life.h:167: error: a function-definition is not allowed here before ':' token
Life.h:177: error: `yend' was not declared in this scope
Life.h:178: error: `xend' was not declared in this scope
Life.h:178: error: expected `)' before ';' token
Life.h:177: warning: unused variable 'yend'
Life.h:178: warning: unused variable 'xend'
Life.h:179: error: `yend' was not declared in this scope
Life.h:179: error: `ybegin' was not declared in this scope
Life.h:179: error: `xend' was not declared in this scope
Life.h:179: error: `xbegin' was not declared in this scope
Life.h:180: error: a function-definition is not allowed here before ':' token
Life.h:182: error: expected primary-expression before "for"
Life.h:182: error: expected `;' before "for"
Life.h:182: error: expected primary-expression before "for"
Life.h:182: error: expected `)' before "for"
Life.h:182: error: a function-definition is not allowed here before ':' token
Life.h:184: error: expected primary-expression before "return"
Life.h:184: error: expected `;' before "return"
Life.h:184: error: expected primary-expression before "return"
Life.h:184: error: expected `)' before "return"
Life.h:179: warning: unused variable 'yend'
Life.h:179: warning: unused variable 'ybegin'
Life.h:179: warning: unused variable 'xend'
Life.h:179: warning: unused variable 'xbegin'
Life.h: In function `bool NDos::operator==(const NDos::pattern&, const NDos::pattern&)':
Life.h:187: error: 'const class NDos::pattern' has no member named 'on'
Life.h:187: error: 'const class NDos::pattern' has no member named 'on'
Life.h:191:26: warning: no newline at end of file
NDosearch.cpp: At global scope:
NDosearch.cpp:8: error: `constexpr' does not name a type
NDosearch.cpp:9: error: `constexpr' does not name a type
NDosearch.cpp:11:24: forward_list: No such file or directory
NDosearch.cpp:14: error: using-declaration for non-member at class scope
NDosearch.cpp:14: error: expected `;' before '<' token
NDosearch.cpp:18: error: use of enum `sym' without previous declaration
NDosearch.cpp:18: error: `int8_t' is not a member of `std'
NDosearch.cpp:18: error: ISO C++ forbids declaration of `type name' with no type
NDosearch.cpp:18: error: expected `;' before '{' token
NDosearch.cpp:18:36: invalid suffix "b1111" on integer constant
NDosearch.cpp:18:51: invalid suffix "b0110" on integer constant
NDosearch.cpp:18:66: invalid suffix "b0101" on integer constant
NDosearch.cpp:18:81: invalid suffix "b0011" on integer constant
NDosearch.cpp:18:95: invalid suffix "b0001" on integer constant
NDosearch.cpp:19: error: using `typename' outside of template
NDosearch.cpp:19: error: expected nested-name-specifier before "decltype"
NDosearch.cpp:19: error: `cells' has not been declared
NDosearch.cpp:19: error: ISO C++ forbids declaration of `decltype' with no type
NDosearch.cpp:19: error: ISO C++ forbids declaration of `parameter' with no type
NDosearch.cpp:19: error: expected `;' before '::' token
NDosearch.cpp:20: error: `cellit' was not declared in this scope
NDosearch.cpp:20: error: `sym' was not declared in this scope
NDosearch.cpp:20: error: `symstack' was not declared in this scope
NDosearch.cpp:34:111: invalid suffix "b0011" on integer constant
NDosearch.cpp:36:110: invalid suffix "b1100" on integer constant
NDosearch.cpp:38:110: invalid suffix "b0101" on integer constant
NDosearch.cpp:40:108: invalid suffix "b1010" on integer constant
NDosearch.cpp:49:14: invalid suffix "b1111" on integer constant
NDosearch.cpp:50:14: invalid suffix "b0110" on integer constant
NDosearch.cpp:50:27: invalid suffix "b1001" on integer constant
NDosearch.cpp:56:14: invalid suffix "b0101" on integer constant
NDosearch.cpp:56:27: invalid suffix "b1010" on integer constant
NDosearch.cpp:62:14: invalid suffix "b0011" on integer constant
NDosearch.cpp:62:27: invalid suffix "b1100" on integer constant
NDosearch.cpp:78:40: invalid suffix "b0101" on integer constant
NDosearch.cpp:78:73: invalid suffix "b1010" on integer constant
NDosearch.cpp:78:82: invalid suffix "b1111" on integer constant
NDosearch.cpp:80:40: invalid suffix "b0011" on integer constant
NDosearch.cpp:80:73: invalid suffix "b1100" on integer constant
NDosearch.cpp:80:82: invalid suffix "b1111" on integer constant
NDosearch.cpp:83:51: invalid suffix "b1111" on integer constant
NDosearch.cpp:84:70: invalid suffix "b1100" on integer constant
NDosearch.cpp:84:81: invalid suffix "b0100" on integer constant
NDosearch.cpp:84:115: invalid suffix "b0101" on integer constant
NDosearch.cpp:84:126: invalid suffix "b0001" on integer constant
NDosearch.cpp:85:37: invalid suffix "b1001" on integer constant
NDosearch.cpp:85:48: invalid suffix "b0001" on integer constant
NDosearch.cpp:86:70: invalid suffix "b0011" on integer constant
NDosearch.cpp:86:81: invalid suffix "b0010" on integer constant
NDosearch.cpp:87:70: invalid suffix "b0101" on integer constant
NDosearch.cpp:87:81: invalid suffix "b0100" on integer constant
NDosearch.cpp:87:90: invalid suffix "b0110" on integer constant
NDosearch.cpp:98:44: invalid suffix "b0001" on integer constant
NDosearch.cpp:98:53: invalid suffix "b0011" on integer constant
NDosearch.cpp:99:44: invalid suffix "b0101" on integer constant
NDosearch.cpp:99:53: invalid suffix "b1111" on integer constant
NDosearch.cpp:109:62: invalid suffix "b0001" on integer constant
NDosearch.cpp:109:71: invalid suffix "b0011" on integer constant
NDosearch.cpp:109:94: invalid suffix "b0101" on integer constant
NDosearch.cpp:109:103: invalid suffix "b1111" on integer constant
NDosearch.cpp:118:21: invalid suffix "b1111" on integer constant
NDosearch.cpp:123:25: invalid suffix "b1111" on integer constant
NDosearch.cpp:142:32: invalid suffix "b0001" on integer constant
NDosearch.cpp:144:32: invalid suffix "b0010" on integer constant
NDosearch.cpp:146:32: invalid suffix "b0100" on integer constant
NDosearch.cpp:148:32: invalid suffix "b1000" on integer constant
NDosearch.cpp:159:32: invalid suffix "b0001" on integer constant
NDosearch.cpp:161:32: invalid suffix "b0010" on integer constant
NDosearch.cpp:163:32: invalid suffix "b0100" on integer constant
NDosearch.cpp:165:32: invalid suffix "b1000" on integer constant
NDosearch.cpp:173: error: template argument 1 is invalid
NDosearch.cpp:173: error: template argument 2 is invalid
NDosearch.cpp:173: error: template argument 1 is invalid
NDosearch.cpp:173: error: template argument 2 is invalid
NDosearch.cpp:173: error: expected unqualified-id before '}' token
NDosearch.cpp:175:18: future: No such file or directory
NDosearch.cpp:176:18: thread: No such file or directory
NDosearch.cpp:180: error: `std::thread' has not been declared
NDosearch.cpp:180: error: `hardware_concurrency' was not declared in this scope
NDosearch.cpp:180: error: `std::thread' has not been declared
NDosearch.cpp:180: error: `hardware_concurrency' was not declared in this scope
NDosearch.cpp:181: error: `int8_t' is not a member of `std'
NDosearch.cpp:181: error: `int8_t' is not a member of `std'
NDosearch.cpp:181: error: template argument 1 is invalid
NDosearch.cpp:181: error: template argument 2 is invalid
NDosearch.cpp:181: error: invalid type in declaration before ';' token
NDosearch.cpp: In function `int main()':
NDosearch.cpp:191: error: `int8_t' is not a member of `std'
NDosearch.cpp:191: error: expected `;' before "factor"
NDosearch.cpp:191: error: `factor' was not declared in this scope
NDosearch.cpp:191: error: `period' was not declared in this scope
NDosearch.cpp:193: error: request for member `push_back' in `factors_orig', which is of non-class type `int'
NDosearch.cpp:196: error: `int8_t' is not a member of `std'
NDosearch.cpp:196: error: expected `;' before "x_search"
NDosearch.cpp:196: error: `x_search' was not declared in this scope
NDosearch.cpp:197: error: `int8_t' is not a member of `std'
NDosearch.cpp:197: error: expected `;' before "y_search"
NDosearch.cpp:197: error: `y_search' was not declared in this scope
NDosearch.cpp:204: error: no matching function for call to `NDos::pattern::pattern(grid&)'
Life.h:35: note: candidates are: NDos::pattern::pattern(const NDos::pattern&)
NDosearch.cpp:205: error: `int8_t' is not a member of `std'
NDosearch.cpp:205: error: `int8_t' is not a member of `std'
NDosearch.cpp:205: error: template argument 1 is invalid
NDosearch.cpp:205: error: template argument 2 is invalid
NDosearch.cpp:205: error: invalid type in declaration before '(' token
NDosearch.cpp:206: error: `int8_t' is not a member of `std'
NDosearch.cpp:206: error: expected `;' before "gen"
NDosearch.cpp:206: error: `gen' was not declared in this scope
NDosearch.cpp:206: error: `period' was not declared in this scope
NDosearch.cpp:207: error: `GOL' is not a member of `NDos'
NDosearch.cpp:208: error: 'class NDos::pattern' has no member named 'size'
NDosearch.cpp:208: error: 'class NDos::pattern' has no member named 'size'
NDosearch.cpp:210: error: request for member `front' in `factors', which is of non-class type `int'
NDosearch.cpp:211: error: request for member `pop_front' in `factors', which is of non-class type `int'
NDosearch.cpp:212: error: `x_trans' was not declared in this scope
NDosearch.cpp:212: error: `y_trans' was not declared in this scope
NDosearch.cpp:206: warning: unused variable 'period'
NDosearch.cpp:223: error: `GOL' is not a member of `NDos'
NDosearch.cpp:224: error: 'class NDos::pattern' has no member named 'size'
NDosearch.cpp:224: error: 'class NDos::pattern' has no member named 'size'
NDosearch.cpp:224: error: `x_trans' was not declared in this scope
NDosearch.cpp:224: error: `y_trans' was not declared in this scope
NDosearch.cpp:233: error: `period' was not declared in this scope
NDosearch.cpp:233: warning: unused variable 'period'
NDosearch.cpp:244: error: 'class grid' has no member named 'enumerate'
NDosearch.cpp:248: error: `int8_t' is not a member of `std'
NDosearch.cpp:248: error: expected `;' before "x_search"
NDosearch.cpp:248: error: `x_search' was not declared in this scope
NDosearch.cpp:249: error: `int8_t' is not a member of `std'
NDosearch.cpp:249: error: expected `;' before "y_search"
NDosearch.cpp:249: error: `y_search' was not declared in this scope
NDosearch.cpp:253: error: `future' is not a member of `std'
NDosearch.cpp:253: error: `future' is not a member of `std'
NDosearch.cpp:254: error: template argument 1 is invalid
NDosearch.cpp:254: error: template argument 2 is invalid
NDosearch.cpp:254: error: invalid type in declaration before ';' token
NDosearch.cpp:255: error: `mutex' is not a member of `std'
NDosearch.cpp:255: error: expected `;' before "results_mutex"
NDosearch.cpp:259: error: `results_future' was not declared in this scope
NDosearch.cpp:261: error: a function-definition is not allowed here before ':' token
NDosearch.cpp:270: error: could not convert `(&output_file)->std::basic_ofstream<_CharT, _Traits>::close [with _CharT = char, _Traits = std::char_traits<char>]()' to `bool'
NDosearch.cpp:272: error: expected `)' before ';' token
NDosearch.cpp:278: error: `results_future' was not declared in this scope
NDosearch.cpp:278: error: `async' is not a member of `std'
NDosearch.cpp:278: error: expected primary-expression before '[' token
NDosearch.cpp:278: error: expected primary-expression before ',' token
NDosearch.cpp:278: error: `patt_orig' was not declared in this scope
NDosearch.cpp:278: error: no matching function for call to `NDos::pattern::pattern(grid&)'
Life.h:35: note: candidates are: NDos::pattern::pattern(const NDos::pattern&)
NDosearch.cpp:278: warning: unused variable 'results_future'
NDosearch.cpp:278: warning: unused variable 'patt_orig'
NDosearch.cpp:313: error: 'class grid' has no member named 'enumerate'
NDosearch.cpp:314: error: `results_future' was not declared in this scope
NDosearch.cpp:318: error: request for member `empty' in `results', which is of non-class type `int'
NDosearch.cpp:319: error: a function-definition is not allowed here before ':' token
NDosearch.cpp:328: error: could not convert `(&output_file)->std::basic_ofstream<_CharT, _Traits>::close [with _CharT = char, _Traits = std::char_traits<char>]()' to `bool'
NDosearch.cpp:330: error: expected `)' before ';' token
编译结束但存在 242 错误 和 24 警告

Also,how to configure NDos::GOL?
Welcome to share your ideas about
etymology of names!
User avatar
GUYTU6J
 
Posts: 343
Joined: August 5th, 2016, 10:27 am
Location: outside Plain of Life

Re: NDosearch 1.0

Postby David » February 5th, 2017, 11:36 am

GUYTU6J wrote:There are so many problems...
Also,how to configure NDos::GOL?

Your compiler must support at least C++14.
NDos::GOL, for both B(Birth) and S(Survival), ith (start from 0th) least significant bit represents i neighbors.
By default, NDos::GOL.B is 0b000001000, so it represents B3, and NDos::GOL.S is 0b000001100, so it represents S23.
Call me "Dannyu NDos" in Forum. Call me "Bag Sinhwan"(박신환) in Wiki.
David
 
Posts: 211
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

Re: NDosearch 1.0

Postby GUYTU6J » February 5th, 2017, 12:04 pm

David wrote:Your compiler must support at least C++14.

I'm using mingw 5.1.4.Where can I check the version number?
Welcome to share your ideas about
etymology of names!
User avatar
GUYTU6J
 
Posts: 343
Joined: August 5th, 2016, 10:27 am
Location: outside Plain of Life

Re: NDosearch 1.0

Postby David » February 5th, 2017, 7:53 pm

GUYTU6J wrote:I'm using mingw 5.1.4.Where can I check the version number?


It appears MinGW doesn't support C++14 yet.
Suggested replacements:
Clang, MSVC, EDG eccp, Intel C++, IBM XLC++, Sun/Opera C++.

(I'm using GCC 6 on Linux Ubuntu 16.10.)
Call me "Dannyu NDos" in Forum. Call me "Bag Sinhwan"(박신환) in Wiki.
David
 
Posts: 211
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea


Return to Scripts

Who is online

Users browsing this forum: No registered users and 1 guest

cron