I do not think 3 neighbours is the problem. We want to order "in backwards view" the targets prefering those closest to "source of salvo".
I think I have actually increased the constraint for which block move is acceptable not to do only block migration.
When a block is close to line segment connecting its closest neighbours, its removal almost does not change spanning tree length. Moving anywhere could hardly shrink the spanning length. So two neighbours are the problem. (Three neighbours in the spanning tree usually means, there is another neighbour to be processed with higher priority.)
Hmm, still thinking about it, but V would not help (in general) ... for a pattern ... big horseshoe (almost circle ... opened on the distant end) consisting of only blocks. The soluion could be "deep move" sidesteping a nearby block than hitting the furthermost block to sufficiently shorten the spanning tree. A lot of deep moves could be required to get rid of one of carrots. The strategy to concentrate on just one carrot would work better for this case.
Following idea does not match well to this case, but there is also an option to skip building several blocks ... that would lead to salvos requiring several starting blocks ... and we could be forced to do deep moves... (But for example for DBCA, I needed to move the starting block 10 times (if I remember well) by 36 steps in manhatan metrics. It would be cheaper to left several blocks behind me, and if required starting blocks will be nearby, it would be cheaper to start from these remnants than building them from one block. But let's not complicate the matters now...
May be we should create an incentive to move the nearest blocks forward for the donkey carrot case. That would work with flat frontier and after a while the leaves would become active starting shrinking the spanning tree.
(Stopping work with chunk when an eccenter's x+y becomes the biggest).
That would force next time the chunk would contain the eccenter.
I hope I will make some experiments already tonight ....
Than I should again mostly work on the ECCA.
I am currently experimenting with an antidonkey strategy, but I need some Donkey problem causing infiles for testing. (I got 7887 on your DBCA version with trash start SW on first attempt, just starting experiments with parametrisation ... but the hack have not applied).
The evaluation is not still debugged, but I am experimenting with prefering donkey preventing moves to increasing bailout, what applies even to the tested pattern ... will it really increase the glider count? ... yep 7964. ... let me fix the evaluation ... now when the evaluation is not completely wrong, I got 7887. I prioritized it before "yellow and purple", but not before "cyan"
Actually it always used 3 gliders salvo and the local problem was always solved by just one such salvo ... just the 3 gliders salvo was deeper than the deep strategy had time to find. So further experiments could show it is better to use this "heuristics" than trying deep at all. Now I am going to skip evaluating donkey when there are not exactly two carrots. I hope it would work well giving reasobably small salvos while maintaining high speed.
Seems there was 2 carrots problem just twice during solving the pattern, and both times it was solved naturally without using the heuristic.
(resulting in 7887 gliders big salvo ... probably different...(golly estimated the xor of these two paterns to took 50 minutes). So I definitely need infile with donkey - carrot problem to be able to test changes.
Oh the salvos are the same ... surprisingly, when in one case deep strategy was used and in another "donkey prevention". (On several places in the salvo). I am somehow confused. Oh all three 7887 result have the same salvo (when L1 optimization is turned off).
I have tried to ignore the 2 carrots condition and initbail condition as well ... and with the tuned evauation it produced 7864 salvo.
Code: Select all
#pragma once
#include "../lifelib/pattern2.h"
#include "../lifelib/spantree.h"
#include "../lifelib/classifier.h"
#include "../lifelib/ssplit.h"
#include <set>
#include <cstdlib>
#include <sstream>
#include <algorithm>
#define MIN_EXCLUSION_SIZE 32
/*
* Functionality for constructing constellations of still-lifes.
*/
namespace apg {
/**
* Computes the period-8 envelope of a pattern
*/
pattern to_env(pattern x) {
pattern y = x;
pattern z = x;
for (int i = 0; i < 7; i++) {
z = z[1];
y += z;
}
return y;
}
std::vector<coords64> getccenters(std::vector<bitworld> clusters) {
std::vector<coords64> ccenters;
for (uint64_t i = 0; i < clusters.size(); i++) {
// Get bounding box:
int64_t bbox[4] = {0};
clusters[i].getbbox(bbox);
int64_t mx2 = bbox[0] * 2 + bbox[2] - 1;
int64_t my2 = bbox[1] * 2 + bbox[3] - 1;
coords64 m2(mx2, my2);
ccenters.push_back(m2);
}
return ccenters;
}
double stlength(pattern stell, std::vector<coords64> eccenters, classifier &cfier) {
bitworld env = to_env(stell).flatlayer(0);
bitworld live = stell.flatlayer(0);
std::vector<bitworld> clusters = cfier.getclusters(live, env, false);
std::vector<coords64> ccenters = getccenters(clusters);
const uint64_t ccenters_size = ccenters.size();
for(std::vector<coords64>::iterator it = eccenters.begin(); it != eccenters.end(); ++it) {
ccenters.push_back(*it);
}
dsds colours(ccenters_size+1);
std::vector<edge64> sgraph = spanning_graph(ccenters);
// Compute squared length of edges with an endpoint in stell:
std::vector<std::pair<int64_t, edge64> > sedges;
for (std::vector<edge64>::iterator it = sgraph.begin(); it != sgraph.end(); ++it) {
if ((it->first < ccenters_size)||(it->second < ccenters_size)) {
coords64 a = ccenters[it->first];
coords64 b = ccenters[it->second];
int64_t xdiff = a.first - b.first;
int64_t ydiff = a.second - b.second;
int64_t sqlength = (xdiff * xdiff) + (ydiff * ydiff);
sedges.push_back(std::make_pair(sqlength, *it));
}
}
// Sort edges into ascending order:
std::sort(sedges.begin(), sedges.end());
double length=0;
// Apply Kruskal's algorithm:
for (std::vector<std::pair<int64_t, edge64> >::iterator it = sedges.begin(); it != sedges.end(); ++it) {
uint64_t a = it->second.first;
uint64_t b = it->second.second;
bool internal=true;
if (a >= ccenters_size) { a = ccenters_size; internal=false;}
if (b >= ccenters_size) { b = ccenters_size; internal=false;} // vertices of extra has the same color
if (!colours.connected(a, b)) {
colours.merge(a, b);
if (internal) { length+= std::sqrt(it->first); }
}
}
return 0.5 * length;
}
pattern diagonalise(pattern inp) {
/*
* Create a diagonal line longer than the diameter of a pattern.
*/
int64_t bbox[4] = {0};
inp.getrect(bbox);
pattern diagonal(inp.getlab(), "o$bo$2bo$3bo$4bo$5bo$6bo$7bo$8bo$9bo$10bo$11bo$12bo$13bo$14bo$15bo!", inp.getrule());
for (uint64_t i = 4; i < 64; i++) {
if (((1 << i) >= bbox[2]) && ((1 << i) >= bbox[3])) { break; }
diagonal += diagonal(1 << i, 1 << i);
}
return diagonal;
}
pattern get_exclusions(pattern inpat, classifier &cfier) {
auto lab = inpat.getlab();
pattern excl(lab, "", "b3s23");
bitworld live = inpat.flatlayer(0);
std::vector<bitworld> clusters = cfier.getclusters(live, live, true);
for (uint64_t i = 0; i < clusters.size(); i++) {
if (clusters[i].population() >= MIN_EXCLUSION_SIZE) {
excl += pattern(lab, lab->demorton(clusters[i], 1), "b3s23");
}
}
return excl;
}
uint64_t excluded_popcount(pattern inpat, classifier &cfier) {
pattern excl = get_exclusions(inpat, cfier);
return (inpat - excl).popcount((1 << 30) + 3);
}
pattern cell_lowerright(pattern inpat) {
// Get a reasonably lower-right cell of an input pattern.
bitworld bw = inpat.flatlayer(0);
bw = bw.br1cell();
auto lab = inpat.getlab();
pattern brcell(lab, lab->demorton(bw, 1), inpat.getrule());
return brcell;
}
pattern bounding_hull(pattern x) {
int64_t bbox[4] = {0};
x.getrect(bbox);
pattern y(x.getlab(), "bbo$bo$o!", "b3s23");
y = y.shift(-1, -1);
uint64_t p = bbox[2] + bbox[3];
while (p > 0) {
p = p >> 1;
y = y.convolve(y);
}
return x.convolve(y).subrect(bbox);
}
pattern get_isolated_block(pattern inpat) {
auto lab = inpat.getlab();
pattern convrect(lab, lab->rectangle(-20, -20, 41, 41), "b3s23");
return inpat & cell_lowerright(inpat).convolve(convrect);
}
bool has_isolated_block(pattern inpat) {
pattern x = get_isolated_block(inpat);
int64_t bbox[4] = {0};
x.getrect(bbox);
return (bbox[2] == 2) && (bbox[3] == 2);
}
pattern get_lowerright(pattern inpat, pattern inpat2, uint64_t minpop, int radius, classifier &cfier, pattern extra) {
// Get a lower-right chunk of an input pattern.
auto lab = inpat.getlab();
pattern convrect(lab, lab->rectangle(-radius, -radius, 2 * radius + 1, 2 * radius + 1), "b3s23");
pattern icell = cell_lowerright(inpat2);
pattern diag = diagonalise(inpat);
pattern sword(lab, "o$bo$2bo$3b2o$3b2o!", "b3s23");
for (int i = 0; i < 6; i++) {
sword = sword.convolve(sword);
}
sword = sword.convolve(diag).convolve(convrect);
pattern chunk(lab, "", "b3s23");
for (;;) {
pattern newchunk = chunk + icell;
while (chunk != newchunk) {
chunk = newchunk & inpat;
newchunk = bounding_hull(chunk).convolve(sword) & inpat;
}
pattern rempat = inpat - chunk;
if (rempat.empty()) { break; }
uint64_t epc = excluded_popcount(chunk, cfier);
if (epc < minpop) {
icell = icell.convolve(convrect);
} else {
std::cout << "\033[36;1mFound " << epc;
std::cout << "-cell chunk; " << excluded_popcount(rempat, cfier);
std::cout << " + " << extra.popcount((1 << 30) + 3);
std::cout << " cells remain.\033[0m" << std::endl;
break;
}
}
return chunk;
}
std::vector<std::pair<int64_t,pattern>> dimerise(pattern stell, classifier &cfier, int64_t maxDepth) {
/*
* Find promising still-life pairs and individual still-lifes
* which the compiler has a good chance of being able to build.
*/
/*
dimers have monomer center distances at most 25\sqrt{2} so Manhattan distance at most 50
for a monomer A center of the most distance dimmer containing A is from center of A in Manhattan distance at most 25
We want A to be processed after last dimmer containing A so we should penalise A by Manhattan distance > 25
We use 2 points coordinates so the penalty should be > 50
(After that we try to reduce a tub or beehive to block, and other monomer than tub, beehive or block to tub, beehive or block)
Monomer blocks are processed differently, we transform them to blocks, but we should try to improve a
chance it will create dimmer to be processed.
The heuristic trying to shorten (global) minimum spanning forest looks well as the most distant blocks tend to move
towards the rest.
moving block to Manhattan distance 36 is rather cheap, it seems to me they should be
"invited to follow monomers" from around such a distance.
*/
const int64_t diPenalty = 0;
// bespokePenalty=-80 < -50 to prefere be broken to clusters before the clusters could become part of active dimers
const int64_t monoPenalty = 51;
const int64_t blockPenalty = 120;
std::vector<std::pair<int64_t,pattern>> sorted_dimers;
//std::vector<std::vector<pattern> > sdimers;
bitworld env = to_env(stell).flatlayer(0);
bitworld live = stell.flatlayer(0);
std::vector<bitworld> clusters = cfier.getclusters(live, env, true);
std::vector<coords64> ccenters;
std::set<std::pair<int64_t, edge64>> edgelist_sorted;
for (uint64_t i = 0; i < clusters.size(); i++) {
// Get bounding box:
int64_t bbox[4] = {0};
clusters[i].getbbox(bbox);
int64_t mx2 = bbox[0] * 2 + bbox[2] - 1;
int64_t my2 = bbox[1] * 2 + bbox[3] - 1;
coords64 m2(mx2, my2);
ccenters.push_back(m2);
// penalty to ensure that singleton blocks appear after everything else:
int64_t pen = ((bbox[2] == 2) && (bbox[3] == 2)) ? blockPenalty : monoPenalty;
edgelist_sorted.emplace(pen - 2*(mx2 + my2), edge64(i, i));
}
std::vector<edge64> edgelist_unsorted = spanning_graph(ccenters);
for (uint64_t i = 0; i < edgelist_unsorted.size(); i++) {
edge64 edge = edgelist_unsorted[i];
int64_t x1 = ccenters[edge.first].first;
int64_t y1 = ccenters[edge.first].second;
int64_t x2 = ccenters[edge.second].first;
int64_t y2 = ccenters[edge.second].second;
if ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) > 5000) { continue; }
edgelist_sorted.emplace(diPenalty - (x1 + y1 + x2 + y2), edge);
}
lifetree_abstract<uint32_t>* lab = stell.getlab();
std::set<edge64> edgedump;
int64_t priorityLimit = edgelist_sorted.begin()->first + maxDepth;
uint64_t ActiveMonomers=0;
for (auto it = edgelist_sorted.begin(); it != edgelist_sorted.end(); ++it) {
if (it->first >= priorityLimit) {break;}
edge64 edge = it->second;
if (edge.first == edge.second) {
// Include monomers:
ActiveMonomers++;
uint64_t i = edge.first;
pattern monomer(lab, lab->demorton(clusters[i], 1), stell.getrule());
sorted_dimers.push_back(std::make_pair(it->first,monomer));
} else {
// Include dimers:
uint64_t idLo = (edge.first < edge.second) ? edge.first : edge.second;
uint64_t idHi = (edge.first > edge.second) ? edge.first : edge.second;
bitworld bw = clusters[edge.first];
bw += clusters[edge.second];
pattern dimer(lab, lab->demorton(bw, 1), stell.getrule());
edge64 newedge(idLo, idHi);
if (edgedump.count(newedge) == 0) {
sorted_dimers.push_back(std::make_pair(it->first,dimer));
edgedump.insert(newedge);
}
}
}
std::cout << "considered clusters/dimers/monomers/bespokes/active bespokes/early targets/later targets/early maxDepth/later maxdepth: " <<
clusters.size() << "/"<< sorted_dimers.size()-ActiveMonomers << "/" << ActiveMonomers << "/";
return sorted_dimers;
}
template <typename T> struct cgsalvo {
std::vector<std::pair<T, char> > gliders;
T dx;
T dy;
bool age;
bool transpose;
void glidermatch(pattern pat) {
std::map<std::pair<int64_t, int64_t>, uint8_t> gmap;
std::vector<pattern> matches;
pattern a_glider(pat.getlab(), "3o$o$bo!", pat.getrule());
int64_t bbox[4] = {0};
for (uint64_t i = 0; i < 4; i++) {
bitworld bw = pat.match(a_glider).flatlayer(0);
a_glider = a_glider[1];
while (bw.population()) {
bitworld onecell = bw.get1cell();
bw -= onecell;
onecell.getbbox(bbox);
int64_t lane = (bbox[0] - bbox[1]);
uint8_t phase = (uint8_t) (((bbox[1] & 1) << 2) + i);
gmap[std::pair<int64_t, int64_t>(bbox[0] + bbox[1], lane)] = phase;
}
}
for (auto it = gmap.begin(); it != gmap.end(); ++it) {
T lane = it->first.second;
uint8_t phase = it->second;
gliders.emplace_back(lane, phase);
}
}
std::pair<pattern, pattern> frompattern(pattern pat) {
int64_t bbox[4] = {0};
pattern fin = pat[1 << 20];
to_env(fin).getrect(bbox);
pattern centred = pat(-bbox[0], -bbox[1]);
fin = fin(-bbox[0], -bbox[1]);
pattern target = centred & centred[8];
pattern gliders = centred - target;
glidermatch(gliders);
dx = 0;
dy = 0;
age = 0;
transpose = 0;
return std::pair<pattern, pattern>(target, fin);
}
void fromline(std::string line) {
std::vector<std::string> colons = string_split(line, ':');
if (colons.size() >= 3) {
std::string t = colons[colons.size() - 2];
std::vector<std::string> gstrings = string_split(t, ' ');
for (uint64_t i = 0; i < gstrings.size(); i++) {
std::string g = gstrings[i];
if (g != "") {
char lastchar = g[g.length() - 1];
if ((lastchar == 'E') || (lastchar == 'O')) {
T j = (std::stoll(g.substr(0, g.length() - 1)) - 1) / 2;
gliders.emplace_back(j, ((lastchar == 'E') ? 0 : 1));
}
}
}
std::string s = colons[colons.size() - 3];
std::replace(s.begin(), s.end(), '(', ' ');
std::replace(s.begin(), s.end(), ')', ' ');
std::replace(s.begin(), s.end(), ',', ' ');
std::vector<std::string> hstrings = string_split(s, ' ');
std::vector<std::string> hstrings2;
for (uint64_t i = 0; i < hstrings.size(); i++) {
std::string h = hstrings[i];
if (h != "") { hstrings2.push_back(h); }
}
if (hstrings2.size() == 3) {
dx = std::stoll(hstrings2[0]);
dy = std::stoll(hstrings2[1]);
transpose = (hstrings2[2] == "T");
}
std::string r = colons[colons.size() - 1];
if (r.find("o") != std::string::npos) { age = 1; }
if (r.find("e") != std::string::npos) { age = 0; }
}
}
};
struct cgfile {
std::map<std::string, std::vector<std::vector<std::pair<std::string, cgsalvo<int16_t>>>>> sdata;
std::set<std::string> btargets;
void digestmc(std::string filename, lifetree_abstract<uint32_t> *lab) {
pattern x(lab, filename);
uint64_t period = x[1 << 20].ascertain_period();
std::cout << " -- " << filename << " has period " << period << "." << std::endl;
for (uint64_t i = 0; i < period; i++) {
for (uint64_t j = 0; j < 2; j++) {
cgsalvo<int16_t> cg;
std::pair<pattern, pattern> respair = cg.frompattern(x);
std::string source = respair.first._string32();
std::string target = respair.second._string32();
btargets.insert(target);
if (sdata[target].size() <= cg.gliders.size()) {
sdata[target].resize(cg.gliders.size() + 1);
}
sdata[target][cg.gliders.size()].emplace_back(source, cg);
x = x.transpose();
}
x = x[1];
}
}
void readfile(std::string filename, lifetree_abstract<uint32_t> *lab, std::string rule) {
std::ifstream f(filename);
std::string line;
std::string rlesofar;
std::string target;
std::string source;
bool readingsrc = false;
if (!f.good()) { return; }
std::cout << "Reading file " << filename << "..." << std::endl;
while (std::getline(f, line)) {
if (line.empty()) { continue; }
char c = line[0];
if ((c == ' ') || (c == '*')) {
if (rlesofar != "") { rlesofar += "$"; }
rlesofar += line;
} else if (rlesofar != "") {
std::replace( rlesofar.begin(), rlesofar.end(), ' ', 'b');
std::replace( rlesofar.begin(), rlesofar.end(), '*', 'o');
rlesofar += "!";
// std::cout << rlesofar << std::endl;
pattern p(lab, rlesofar, rule);
if (readingsrc) { source = p._string32(); } else { target = p._string32(); }
rlesofar = "";
}
if (c == '-') {
if (line.find("Source") != std::string::npos) {
readingsrc = true;
} else if (line.find("Target") != std::string::npos) {
readingsrc = false;
}
} else if (rlesofar == "") {
cgsalvo<int16_t> cg;
cg.fromline(line);
if (cg.gliders.size() != 0) {
if (sdata[target].size() <= cg.gliders.size()) {
sdata[target].resize(cg.gliders.size() + 1);
}
sdata[target][cg.gliders.size()].emplace_back(source, cg);
}
}
}
std::cout << "..." << filename << " successfully read." << std::endl;
}
};
struct cghq {
/*
* Collection of slow-salvo recipes
*/
std::map<std::string, cgfile> cgfiles;
std::string rule;
std::string datadir;
lifetree_abstract<uint32_t> *lab;
uint64_t stat_bespoke=0, stat_deep=0, stat_tree=0, stat_split=0, stat_reduce=0;
uint64_t assertfile(std::string filename) {
if (cgfiles.count(filename) == 0) {
cgfiles[filename].readfile(filename, lab, rule);
}
return cgfiles[filename].sdata.size();
}
void assertbespoke(std::string dirname) {
if (cgfiles.count(dirname) == 0) {
std::ifstream f(dirname + "/filelist.txt");
std::string line;
while (std::getline(f, line)) {
std::string filename = dirname + "/" + line;
cgfiles[dirname].digestmc(filename, lab);
}
}
}
std::vector<pattern> depthExtras;
std::vector<std::vector<coords64>> depthECCBoundary;
std::vector<std::vector<std::pair<int64_t,pattern>>> depthSDimers;
std::vector<pattern> depthavoid;
std::vector<std::uint64_t> depthnbespoke;
std::vector<std::uint64_t> depthnblocks;
std::vector<std::int64_t> depthEarlyPriorityLimit;
std::vector<std::double_t> depthStLen;
std::vector<std::double_t> depthNextSaveTime;
std::vector<pattern> depthBestDonkey;
std::vector<std::int64_t> depthBestDonkeyEval;
void preparedepth(uint64_t depth, pattern extra, pattern work, classifier &cfier) {
if (depthSDimers.size()==depth) {
std::vector<std::pair<int64_t,pattern>> empty;
depthSDimers.push_back(empty);
pattern dummy(lab,"",rule);
depthExtras.push_back(dummy);
std::vector<coords64> noccoords;
depthECCBoundary.push_back(noccoords);
depthavoid.push_back(dummy);
depthnbespoke.push_back(0);
depthnblocks.push_back(0);
depthEarlyPriorityLimit.push_back(0);
depthStLen.push_back(1.1);
depthNextSaveTime.push_back(0.0);
depthBestDonkey.push_back(dummy);
depthBestDonkeyEval.push_back(-1);
}
depthExtras[depth]=extra;
depthStLen[depth]=1.1;
depthBestDonkeyEval[depth]=-1;
std::vector<coords64> noccoords;
depthECCBoundary[depth] = noccoords;
pattern stell = work & work[8];
bitworld env = to_env(stell).flatlayer(0), live = stell.flatlayer(0);
std::vector<bitworld> sclusters = cfier.getclusters(live, env, false);
env = to_env(extra).flatlayer(0); live = extra.flatlayer(0);
std::vector<bitworld> eclusters = cfier.getclusters(live, env, false);
std::vector<coords64> sccenters,eccenters,accenters;
sccenters=getccenters(sclusters);
eccenters=getccenters(eclusters);
for (uint64_t i = 0; i < sccenters.size(); i++) {
accenters.push_back(sccenters[i]);
}
for (uint64_t i = 0; i < eccenters.size(); i++) {
accenters.push_back(eccenters[i]);
}
dsds colours(sccenters.size()+1);
std::vector<edge64> sgraph = spanning_graph(accenters);
// Compute squared length of edges with an endpoint in stell:
std::vector<std::pair<int64_t, edge64> > sedges;
for (std::vector<edge64>::iterator it = sgraph.begin(); it != sgraph.end(); ++it) {
if ((it->first < sccenters.size())||(it->second < sccenters.size())) {
coords64 a = accenters[it->first];
coords64 b = accenters[it->second];
int64_t xdiff = a.first - b.first;
int64_t ydiff = a.second - b.second;
int64_t sqlength = (xdiff * xdiff) + (ydiff * ydiff);
sedges.push_back(std::make_pair(sqlength, *it));
}
}
// Sort edges into ascending order:
std::sort(sedges.begin(), sedges.end());
// Apply Kruskal's algorithm:
std::set<uint64_t> eboundary;
for (std::vector<std::pair<int64_t, edge64> >::iterator it = sedges.begin(); it != sedges.end(); ++it) {
uint64_t a = it->second.first;
uint64_t b = it->second.second;
uint64_t e = 0;
if (a >= sccenters.size()) { e = a - sccenters.size(); a = sccenters.size(); }
if (b >= sccenters.size()) { e = b - sccenters.size(); b = sccenters.size(); } // vertices of extra has the same color
if (!colours.connected(a, b)) {
colours.merge(a, b);
if (e != 0) { eboundary.emplace(e); }
}
}
for(std::set<uint64_t> :: iterator it = eboundary.begin(); it != eboundary.end(); ++it) {
depthECCBoundary[depth].push_back(eccenters[*it]);
}
}
pattern precurse(pattern orig, classifier &cfier, int state, int initbail, int maxbail, uint32_t lastbail, int64_t *ideal, uint64_t depth, uint64_t shallowFlags = 0) {
std::cout << "precurse " << state << " " << initbail << " " << maxbail << " " << lastbail << " " << ((ideal==0)?"0":"i") << " " << depthExtras[depth].popcount((1 << 30) + 3) << " " << depth << std::endl;
assertbespoke(datadir+"bespoke");
pattern stell = orig & orig[8];
pattern exsalvo = orig - stell;
pattern diagonal = diagonalise(stell);
pattern smallblock(lab, "2o$2o!", rule);
pattern bigblock(lab, "4o$4o$4o$4o!", rule);
pattern utilhash(lab,"o5bo5bo5bo5$o5bo5bo5bo5$o5bo5bo5bo5$o5bo5bo5bo5!",rule);
pattern sword = diagonal.convolve(bigblock);
/*pattern swordExtender(lab,"o12o12$o!",rule);
pattern extSword = sword.convolve(swordExtender);*/
uint64_t deep_bailout = initbail - 1, last_deep_bailout = lastbail - 1;
uint64_t tree_bailout = initbail * 100, last_tree_bailout = lastbail * 100;
const int64_t earlyMaxDepth = 150;
int64_t laterMaxDepth = 220; if (shallowFlags>0) {laterMaxDepth = earlyMaxDepth;}
std::vector<std::pair<int64_t,pattern>> sorted_dimers;
uint64_t nbespoke, nblocks=0;
pattern avoid(lab, "", rule);
int64_t earlyPriorityLimit;
if ((state==0)) {
const int64_t bespokePenalty = -80;
std::vector<std::pair<int64_t,pattern>> sorted_xdimers = dimerise(stell, cfier, laterMaxDepth);
earlyPriorityLimit = sorted_xdimers .begin()->first + earlyMaxDepth;
uint64_t nAllBespokes=0;
depthBestDonkeyEval[depth]=-1;
for (auto it = cgfiles[datadir+"bespoke"].btargets.begin(); it != cgfiles[datadir+"bespoke"].btargets.end(); ++it) {
pattern sterm(lab, lab->_string32(*it), rule);
bitworld bw = stell.match(sterm).flatlayer(0);
while (bw.population()) {
int64_t bbox[4] = {0};
bitworld onecell = bw.get1cell();
bw -= onecell;
onecell.getbbox(bbox);
pattern subset = sterm(bbox[0], bbox[1]);
avoid += subset;
bitworld fsubset = subset.flatlayer(0);
fsubset.getbbox(bbox);
int64_t priority = bespokePenalty - 2*(bbox[0] * 2 + bbox[2] + bbox[1] * 2 + bbox[3] - 2);
nAllBespokes++;
if (priority<earlyPriorityLimit) {
sorted_dimers.push_back(std::make_pair(priority,subset));
}
}
}
nbespoke = sorted_dimers.size(); //bespokes are filtered by priority, but unsorted at front of others
std::cout << nAllBespokes << "/" << nbespoke << "/";
if (nbespoke==0) { laterMaxDepth = earlyMaxDepth;}
int64_t laterPriorityLimit = earlyPriorityLimit - earlyMaxDepth + laterMaxDepth;
uint64_t nEarlyTargets=nbespoke;
for (uint64_t i = 0; i < sorted_xdimers.size(); i++) {
if (sorted_xdimers[i].first>=laterPriorityLimit) {break;}
if ((sorted_xdimers[i].second & avoid).empty()) {
if (sorted_xdimers[i].first<earlyPriorityLimit) {nEarlyTargets++;}
sorted_dimers.push_back(sorted_xdimers[i]);
}
}
std::cout << nEarlyTargets << "/" << sorted_dimers.size() << "/" << earlyMaxDepth << "/" << laterMaxDepth << std::endl;
depthStLen[depth] = 1.1; //dummy ... not 0.0 yet
} else {
sorted_dimers=depthSDimers[depth];
avoid=depthavoid[depth];
nbespoke=depthnbespoke[depth];
nblocks=depthnblocks[depth];
earlyPriorityLimit=depthEarlyPriorityLimit[depth];
}
double stelllength = depthStLen[depth];
if ((depth>0)&&(stelllength<0.5)) {
std::cout << "\033[36;1mAlgorithm terminated with an opimal ST.\033[0m" << std::endl;
return orig;
}
pattern eglider(lab, "3o$o$bo!", rule);
int budget = (nbespoke>20) ? nbespoke + 10 : 30; // budget rarely stops the state==0 phase
bool promissingBlockExists = false;
/*if (state != 0) {
std::cout << "Obtained " << (freshDimers?"fresh ":"") << depthDimers[depth].size() << " dimers/monomers";
if (nbespoke) { std::cout << " (including " << nbespoke << " bespoke objects)"; }
std::cout << "." << std::endl;
bitworld env = to_env(stell).flatlayer(0);
bitworld live = stell.flatlayer(0);
std::vector<bitworld> clusters = cfier.getclusters(live, env, true);
for (uint64_t i = 0; i < clusters.size(); i++) {
if (clusters[i].population() < MIN_EXCLUSION_SIZE) { smallobj += 1; }
}
std::cout << smallobj << " objects of < " << MIN_EXCLUSION_SIZE << " cells." << std::endl;
}
if (state == 0) {
std::cout << "Obtained " << (freshDimers?"fresh ":"") << depthDimers[depth].size() << " dimers/monomers";
if (nbespoke) { std::cout << " (including " << nbespoke << " bespoke objects)"; }
std::cout << " budget " << budget << "." << std::endl;
}*/
// Display dimers:
for (uint64_t i = 0; i < sorted_dimers.size(); i++) {
int64_t priority = sorted_dimers[i].first; pattern dimer = sorted_dimers[i].second;
bitworld live = dimer.flatlayer(0);
bitworld env = to_env(dimer).flatlayer(0);
int64_t envbbox[4] = {0};
env.getbbox(envbbox);
pattern remainder = stell - dimer;
pattern dcs = dimer.convolve(sword);
if ((dcs & remainder).nonempty() && (dcs(12, 0) & remainder).nonempty() && (dcs(0, 12) & remainder).nonempty()) { continue; }
// ^ one of the 3 must be empty ?! I would expect pattern dcs = dimer.convolve(extSword) ... (dcs & remainder).nonempty()
std::map<std::string, int64_t> counts = cfier.census(live, env);
std::ostringstream ss;
uint64_t totobj = 0;
for (auto it = counts.begin(); it != counts.end(); ++it) {
if (totobj != 0) { ss << "__"; }
if (it->second != 0) {
ss << it->first;
if (it->second != 1) { ss << "(" << it->second << ")"; }
}
totobj += it->second;
}
std::string lexrepr = ss.str();
std::vector<std::string> prefices;
if (i < nbespoke) {prefices.push_back("bespoke");}
bool oneblock = false;
if (lexrepr == "xs4_33") {
if (state == 0) { nblocks++;continue; }
if ((sorted_dimers.size() == 1) && (stell.popcount((1 << 30) + 3)==4)) { oneblock = true; }
prefices.push_back("longmove");
} else if (initbail>5) {continue; // initbail 1->1->3->9->27...}
} else if ((lexrepr == "xs6_696") || (lexrepr == "xs4_252")) {
if ((initbail==1) == (priority >= earlyPriorityLimit)) { continue; }
if (initbail==1) {
budget--;
if ((state == 0) && (budget == 0)) { break; }
if ((state != 0) && (budget>0)) {continue; } //processed in budget last time
}
prefices.push_back("edgy/xs4_33");
} else {
if ((initbail==1) == (priority >= earlyPriorityLimit)) { continue; }
if (initbail==1) {
budget--;
if ((state == 0) && (budget == 0)) { break; }
if ((state != 0) && (budget>0)) {continue; } //processed in budget last time
}
prefices.push_back("edgy/xs4_33");
if (totobj == 1) { //monomer
prefices.push_back("edgy/xs6_696");
prefices.push_back("edgy/xs4_252");
}
}
if (lexrepr == "xs4_33") { // test the block is promissing
if (initbail>2) {promissingBlockExists = true;}
if (promissingBlockExists) {
if (initbail>5) {//there is big enough chance we will try several deep attempts with no chance
if ((nbespoke == 0) && (nblocks>1)) {
double altstelllength = stlength(remainder - avoid, depthECCBoundary[depth], cfier);
if (altstelllength > stelllength - 15.0) {
pattern empty(lab,"",rule);
preparedepth(depth+1,empty,remainder,cfier); // no need to prepare spanning tree for shallow search
std::cout << "\033[33;1m";
pattern newpatt = precurse(remainder, cfier, 0, 1, 1, 0, ideal, depth+1, 2);
std::cout << "\033[0m";
if (newpatt == remainder) {
continue;
}
}
}
}
} else {
if ((nbespoke > 0)||oneblock) { promissingBlockExists = true;}
else {
double altstelllength = stlength(remainder - avoid, depthECCBoundary[depth], cfier);
if (altstelllength <= stelllength - 15.0) {
promissingBlockExists = true;
} else {
pattern empty(lab,"",rule);
preparedepth(depth+1,empty,remainder,cfier); // no need to prepare spanning tree for shallow search
std::cout << "\033[35;1m";
pattern newpatt = precurse(remainder, cfier, 0, 1, 1, 0, ideal, depth+1, 2);
std::cout << "\033[0m";
if (newpatt != remainder) {
promissingBlockExists = true;
} else {
continue;
}
}
}
}
}
uint64_t bdiff = 0;
if (oneblock) {
if (ideal != 0) {
int64_t bbox2[4] = {0};
dimer.getrect(bbox2);
bbox2[0] -= ideal[0];
bbox2[1] -= ideal[1];
bdiff = (bbox2[0] * bbox2[0]) + (bbox2[1] * bbox2[1]);
}
if (bdiff == 0) {
std::cout << "\033[36;1mAlgorithm terminated with single block.\033[0m" << std::endl;
return orig;
}
}
for (uint64_t z = 0; z < prefices.size(); z++) {
bool is_bespoke = (prefices[z] == "bespoke");
std::string filename = datadir + prefices[z];
if (!is_bespoke) {
filename += ("/" + lexrepr);
}
assertfile(filename);
for (uint64_t j = 0; j < (is_bespoke ? 1 : 4); j++) {
pattern tlt = dimer.shift(-envbbox[0], -envbbox[1]);
if (j & 1) {
if (tlt == tlt[1]) { continue; }
tlt = tlt[1];
}
if (j & 2) {
if (lexrepr == "xs4_33") { continue; }
//if (lexrepr == "xs4_252") { continue; } ??
tlt = tlt.transpose();
}
//std::cout << i << lexrepr << " z " << z << " j " << j << std::endl;
auto it = cgfiles[filename].sdata.find(tlt._string32());
if (it != cgfiles[filename].sdata.end()) {
uint64_t trycount = 0;
for (uint64_t k = 1; k < it->second.size(); k++) {
uint64_t n_recipes = it->second[k].size();
double tree_req_progress = 4*k-initbail/10;
if (tree_req_progress<15.0) {
tree_req_progress=15.0;
}
if (lexrepr == "xs4_33") {
if (trycount > tree_bailout) { break; }
//std::cout << "Attempting to construct xs4_33 with " << k << " gliders (" << n_recipes << " recipes)" << std::endl;
}
//std::cout << i << lexrepr << " z " << z << " j " << j << " k " << k<< std::endl;
for (uint64_t l = 0; l < n_recipes; l++) {
cgsalvo<int16_t> cs = it->second[k][l].second;
std::string srcstr = it->second[k][l].first;
pattern source(lab, lab->_string32(srcstr), rule);
// Determine whether it is worth proceeding:
bool trythis = false;
pattern xlt = source.shift(-cs.dx, -cs.dy);
pattern altstell = remainder + xlt.shift(envbbox[0], envbbox[1]);
double altstelllength = stelllength;
uint64_t altbdiff = 0;
bool oneblock_improvement = false;
//std::cout << i << lexrepr << " z " << z << " j " << j << " k " << k << " l " << l << std::endl;
if (oneblock) {
int64_t bbox2[4] = {0};
xlt.shift(envbbox[0], envbbox[1]).getrect(bbox2);
bbox2[0] -= ideal[0];
bbox2[1] -= ideal[1];
altbdiff = (bbox2[0] * bbox2[0]) + (bbox2[1] * bbox2[1]);
oneblock_improvement = (std::sqrt((double) altbdiff) <= std::sqrt((double) bdiff) - 25.0 + 0.1 * initbail);
trythis = (altbdiff == 0) || oneblock_improvement;
} else if (lexrepr == "xs4_33") {
/*if (trycount == deep_bailout) {
//std::cout << "Reached bailout " << deep_bailout << " for strategy 'deep'" << std::endl;
} else if (trycount == tree_bailout) {
//std::cout << "Reached bailout " << tree_bailout << " for strategy 'tree'" << std::endl;
} else*/
if (trycount > tree_bailout) { break; }
altstelllength = stlength(altstell - avoid, depthECCBoundary[depth], cfier);
trythis = (altstelllength <= stelllength - tree_req_progress) || (trycount < deep_bailout) || (nbespoke >= 1);
} else {
trythis = true;
}
if (trythis) {
pattern slt = source;
for (uint64_t m = 0; m < cs.gliders.size(); m++) {
std::pair<int16_t, uint8_t> ng = cs.gliders[m];
int64_t posback = (m + 1) * 128;
slt += eglider(posback + ng.first, posback)[ng.second];
}
uint64_t j2 = (cs.transpose ? 2 : 0) + cs.age;
j2 ^= j;
slt = slt.shift(-cs.dx, -cs.dy);
pattern xlt = source.shift(-cs.dx, -cs.dy);
if (j2 & 1) { slt = slt[1]; xlt = xlt[1]; }
if (j2 & 2) { slt = slt.transpose(); xlt = xlt.transpose(); }
pattern sltshift = slt.shift(envbbox[0], envbbox[1]);
pattern newpat = sltshift + remainder;
//std::cout << i << lexrepr << " z " << z << " j " << j << " k " << k << " l " << l << " trying" << std::endl;
if (newpat[512 * (cs.gliders.size() + 1)] == stell) {
if ((sltshift.convolve(sword) & remainder).empty()) {
// std::cout << "Good match!" << std::endl;
} else {
// std::cout << "Inaccessible from infinity" << std::endl;
continue;
}
int64_t posback = (cs.gliders.size() + 2) * 128;
newpat += exsalvo(posback, posback);
pattern altstell = remainder + xlt.shift(envbbox[0], envbbox[1]);
if (oneblock) {
if (altbdiff == 0) {
std::cout << "\033[32;1mInitial block correctly emplaced\033[0m" << std::endl;
return newpat;
} else if (oneblock_improvement) {
std::cout << "\033[32;1mInitial block moved towards target\033[0m" << std::endl;
return newpat;
}
} else if (lexrepr == "xs4_33") {
pattern newpat2 = newpat;
if ((trycount >= last_deep_bailout) && (trycount < deep_bailout)) {
// We now create a really large sword to ensure only the BR-most
// block is moved by the 'deep' strategy:
pattern qlt = sltshift.convolve(bigblock).convolve(bigblock);
qlt += qlt(8, 8).convolve(bigblock).convolve(bigblock);
if ((qlt.convolve(sword) & remainder).empty()) {
pattern empty(lab,"",rule);
preparedepth(depth+1,empty,newpat2,cfier); // no need to prepare spanning tree for shallow search
std::cout << "\033[36;1m";
newpat2 = precurse(newpat, cfier, 0, 1, 1, 0, ideal, depth+1, 1);
std::cout << "\033[0m";
std::cout << "back to precurse A" << std::endl;
}
}
if (newpat != newpat2) {
stat_deep++;
std::cout << (double) clock() << " \033[32;1mdeep \033[0m" ;
std::cout << i << " " << z << " " << j << " " << k << " " << l << " + " << cs.gliders.size() ;
std::cout << " " << stat_bespoke << " " << stat_deep << " " << stat_tree << " " << stat_split << " " << stat_reduce;
std::cout << " " << sorted_dimers.size() << "(" << nbespoke << ")";
std::cout << " predeep population " << stell.popcount((1 << 30) + 3) << " --> ";
std::cout << altstell.popcount((1 << 30) + 3) << " + " << depthExtras[depth].popcount((1 << 30) + 3) << " " << lexrepr << std::endl;
return newpat2;
}
if (trycount >= last_tree_bailout) {
double nutil_old = stelllength;
double nutil_new = altstelllength;
if (nbespoke > 0) {
pattern barrier = avoid.convolve(sword);
pattern altrem = altstell - avoid, rem = stell - avoid;
altrem = altrem.convolve(utilhash), rem = rem.convolve(utilhash);
/*altrem += altrem(0, 6); altrem += altrem(6, 0);
altrem += altrem(0, 12); altrem += altrem(12, 0);
rem += rem(0, 6); rem += rem(6, 0); // ?? why not convolve?
rem += rem(0, 12); rem += rem(12, 0); */
uint64_t pop1 = 0;
uint64_t pop2 = 0;
for (uint64_t zz = 0; zz < 4; zz++) {
pop2 += (barrier & altrem).popcount((1 << 30) + 3);
pop1 += (barrier & rem).popcount((1 << 30) + 3);
barrier = barrier.convolve(sword).convolve(sword);
}
nutil_old += 0.1 * pop1;
nutil_new += 0.1 * pop2;
}
if (nutil_new <= nutil_old - tree_req_progress) {
stat_tree++;
std::cout << (double) clock() << " \033[32;1mtree \033[0m: ";
std::cout << i << " " << z << " " << j << " " << k << " " << l << " + " << cs.gliders.size() ;
std::cout << " " << stat_bespoke << " " << stat_deep << " " << stat_tree << " " << stat_split << " " << stat_reduce;
std::cout << " " << sorted_dimers.size() << "(" << nbespoke << ")";
std::cout << " population " << stell.popcount((1 << 30) + 3) << " + " << depthExtras[depth].popcount((1 << 30) + 3) << " " << lexrepr;
std::cout << " loss " << nutil_old << " --> " << nutil_new << std::endl;
depthStLen[depth] = altstelllength;
return newpat;
}
if (depthECCBoundary[depth].size()==2) {
int64_t bbox2[4] = {0};
xlt.shift(envbbox[0], envbbox[1]).getrect(bbox2);
int64_t donkeyEval = (120-4*(bbox2[0]+bbox2[1])-priority);
if (donkeyEval>0) {
donkeyEval *= (laterMaxDepth-earlyMaxDepth+earlyPriorityLimit-priority)/cs.gliders.size();
}
if (donkeyEval>depthBestDonkeyEval[depth]) {
std::cout << "\033[37;1mDonkeyEvalCalc "<< donkeyEval << " ("<< bbox2[0] << "," << bbox2[1] << ") "
<< earlyPriorityLimit << "-" << priority << "/" << cs.gliders.size() << "\033[0m" << std::endl;
depthBestDonkeyEval[depth]=donkeyEval;
depthBestDonkey[depth]=newpat;
std::cout << "\033[37;1mDonkeyEvalImprovement "<< donkeyEval << "\033[0m" << std::endl;
}
}
}
} else {
if (shallowFlags<2) {
if (is_bespoke) {
stat_bespoke++;
std::cout << (double) clock() << " \033[32;1mbespoke\033[0m: ";
} else if (totobj == 1) {
stat_reduce++;
std::cout << (double) clock() << " \033[32;1mreduce \033[0m: ";
} else {
stat_split++;
std::cout << (double) clock() << " \033[32;1msplit \033[0m: ";
}
} else {
std::cout << (double) clock() << " promise ";
}
std::cout << i << " " << z << " " << j << " " << k << " " << l << " + " << cs.gliders.size() ;
std::cout << " " << stat_bespoke << " " << stat_deep << " " << stat_tree << " " << stat_split << " " << stat_reduce;
std::cout << " " << sorted_dimers.size() << "(" << nbespoke << ")";
std::cout << " population " << stell.popcount((1 << 30) + 3) << " --> ";
std::cout << altstell.popcount((1 << 30) + 3) << " + " << depthExtras[depth].popcount((1 << 30) + 3) << " " << lexrepr << std::endl;
return newpat;
}
}
}
trycount += 1;
}
}
}
}
}
}
// std::cout << "--------------------------------" << std::endl;
depthSDimers[depth]=sorted_dimers;
depthavoid[depth]=avoid;
depthnbespoke[depth]=nbespoke;
depthnblocks[depth]=nblocks;
depthEarlyPriorityLimit[depth]=earlyPriorityLimit;
if ((state == 0) && (shallowFlags==0)) {
depthStLen[depth] = stlength(stell - avoid, depthECCBoundary[depth], cfier);
std::cout << "stelllength " << depthStLen[depth] << std::endl;
}
if ((initbail>5) && (depthBestDonkeyEval[depth]>0)) {//testing
std::cout << "\033[37;1mno improvement found, early using best donkey move\033[0m" << std::endl;
return depthBestDonkey[depth];
}
if ((maxbail != 0) && (initbail < maxbail)) {
if (promissingBlockExists) {
std::cout << "Increasing bailout to " << (initbail * 3) << std::endl;
pattern ret=precurse(orig, cfier, state, initbail * 3, maxbail, initbail, ideal, depth);
std::cout << "back to precurse B" << std::endl;
return ret;
} else {
std::cout << "no promissing block ... ";
}
}
if (depthBestDonkeyEval[depth]>0) {
std::cout << "\033[37;1mno improvement found, using best donkey move\033[0m" << std::endl;
return depthBestDonkey[depth];
}
if (shallowFlags) {
std::cout << "no shallow improvement found" << std::endl;
return orig;
}
std::cout << "no improvement found" << std::endl;
return orig;
}
pattern preiterate(pattern initial, classifier &cfier, int64_t *ideal, uint64_t depth, pattern extra) {
std::cout << "preiterate " << ((ideal==0)?"0":"i") << " " << depth << " " << extra.popcount((1 << 30) + 3) << std::endl;
pattern pcend = initial;
pattern pcstart(lab, "", rule);
pattern gliders(lab, "", rule);
preparedepth(depth,extra,initial,cfier);
//uint64_t chunk1minpop = 8, chunk2minpop = 8;
while (pcstart != pcend) {
pcstart = pcend & pcend[8];
pattern salvo = pcend - pcstart;
if (salvo.nonempty() && gliders.nonempty()) {
int64_t diag = 0;
int64_t gliders_bbox[4] = {0};
int64_t pcend_bbox[4] = {0};
gliders.getrect(gliders_bbox);
pcend.getrect(pcend_bbox);
int64_t horizontal = (pcend_bbox[0] + pcend_bbox[2] - gliders_bbox[0]);
int64_t vertical = (pcend_bbox[1] + pcend_bbox[3] - gliders_bbox[1]);
if (diag < horizontal) { diag = horizontal; }
if (diag < vertical) { diag = vertical; }
diag += 512;
diag -= (diag & 255);
gliders = gliders(diag, diag);
}
gliders += salvo;
if (clock()>=depthNextSaveTime[depth]) {
depthNextSaveTime[depth] = clock()+30*CLOCKS_PER_SEC;
// save progress
std::ostringstream ss;
ss << "current" << depth << ".mc";
std::ofstream out(ss.str());
(pcstart + gliders).write_macrocell(out);
}
if (depth>0) {
if (depthStLen[depth]<0.5) {
std::cout << "\033[36;1m Reached optimal ST -> break.\033[0m" << std::endl;
break;
}
}
pattern inpat2 = pcstart;
if (has_isolated_block(pcstart)) {
pattern chunk = get_lowerright(pcstart, inpat2, 8, 32, cfier, extra); //
if (chunk != pcstart) {
pattern remainder = pcstart - chunk;
pcend = remainder + preiterate(chunk, cfier, 0, depth+1, extra + remainder);
std::cout << "back to preiterate A " << depth << " " << depthStLen[depth+1];
if (pcend == pcstart) {
std::cout << " with no progress" << std::endl;
} else {
std::cout << " with a progress" << std::endl;
continue;
}
}
inpat2 -= get_isolated_block(inpat2);
}
pcend = precurse(pcstart, cfier, 0, 1, 1, 0, ideal, depth);
std::cout << "back to preiterate B " << depth << " " << depthStLen[depth];
if (pcend != pcstart) {
std::cout << " with a progress" << std::endl;
continue;
}
if (depth>0) {
if (depthStLen[depth]<0.5) {
std::cout << "\033[36;1m with optimal ST -> break.\033[0m" << std::endl;
break;
}
}
std::cout << " with no progress" << std::endl;
if (inpat2.nonempty()) {
pattern chunk = get_lowerright(pcstart, inpat2, 8, 25, cfier, extra);
if (chunk != pcstart) {
pattern remainder = pcstart - chunk;
pcend = remainder + preiterate(chunk, cfier, 0, depth+1, extra + remainder);
std::cout << "back to preiterate C " << depth << " " << depthStLen[depth+1];
if (pcend == pcstart) {
std::cout << " with no progress" << std::endl;
} else {
std::cout << " with a progress" << std::endl;
continue;
}
}
}
// attempt deeper constructions:
pcend = precurse(pcstart, cfier, 1, 1, 4096, 0, ideal, depth);
std::cout << "back to preiterate D " << depth << " " << depthStLen[depth];
if (pcend != pcstart) {
std::cout << " with a progress" << std::endl;
continue;
}
if (depth>0) {
if (depthStLen[depth]<0.5) {
std::cout << "\033[36;1m with optimal ST -> break.\033[0m" << std::endl;
break;
}
}
std::cout << " ending with no progress" << std::endl;
}
return (pcstart + gliders);
}
pattern preiterate(pattern initial, classifier &cfier, int64_t *ideal, uint64_t depth = 0) {
std::cout << "preiterate0 " << ((ideal==0)?"0":"i") << " " << depth << std::endl;
lab = initial.getlab();
rule = initial.getrule();
pattern extra(lab, "", rule);
return preiterate(initial, cfier, ideal, depth, extra);
}
pattern preiterate(pattern initial, classifier &cfier) {
pattern findme(initial.getlab(), "3b2o$2bo2bo$bob2obo$obo2bobo$obo2bobo$bob2obo$2bo2bo$3b2o!", initial.getrule());
pattern m = initial.match(findme);
pattern im = initial - m.convolve(findme);
if (m.empty()) {
return preiterate(im, cfier, 0, 0);
} else {
int64_t ideal[4] = {0};
m(3, 3).getrect(ideal);
return preiterate(im, cfier, ideal, 0);
}
}
};
}
Watch the 7864 salvo generations 592000-620000. I would be much more happy if we use split move rather to move (destroying one of the blocks) and later creating block in nearby location due to another move ... . This is what "more source blocks" would be able to do if we would find a way to work with it. Hmm, I wander why it happened ... has isolated block chunk strategy caused the problem separating SW block, to solve middle one?
Whould the preiterate stop working without this chunking? ... No with isolated block chunking commented out, the recipe (finished in 16 minutes) consists of 7917 gliders.
If the "anti donkey" strategy is so efficient (and usually it resullts in easy followup), it could be helpfull to have donkeylong moves ordered by maximizing ratio of x+y/salvo size. Using this order for deep moves (may be alternating with the original order for safety) could improve both time and salvo size.