sldiff -- Find closest still-lifes in Catagolue
Posted: August 8th, 2016, 8:28 pm
When a still-life X is difficult to synthesise, the first port of call is to look it up on Catagolue. However, if X hasn't occurred naturally, the next best option is to find a natural still-life Y which resembles X as closely as possible.
Enter sldiff, a tool for rapidly comparing still-lifes.
Firstly, you need to download the list of all natural still-lifes. In Unix, this can be accomplished by:
Now, suppose you want to find a still-life which resembles the Snark core (xs31_0g89fgkcz8llljgzx641) as closely as possible. With sldiff, this is as simple as running:
which will print the 10 closest matches, where distance is measured by:
d = 5 * (missing cells) + 2 * (unwanted extra cells)
The parameters 5 and 2 are located very close to the end of the source code.
Example output:
The top line means that the best match to xs31_0g89fgkcz8llljgzx641 is xs28_oggs2uge1egozw643, which has 26 matching cells, 2 extra cells, and 5 missing cells (for an overall distance of 29). The second-best match is the recently-observed xs33_mmge1egu2sggoz1y3346.
Anyway, here's the source code:
Enter sldiff, a tool for rapidly comparing still-lifes.
Firstly, you need to download the list of all natural still-lifes. In Unix, this can be accomplished by:
Code: Select all
curl https://catagolue.appspot.com/textcensus/b3s23/C1 | grep -o 'xs[0-9]*_[0-9a-z]*' > stills.txtCode: Select all
cat stills.txt | ./sldiff.cpp "xs31_0g89fgkcz8llljgzx641" | sort -n | headd = 5 * (missing cells) + 2 * (unwanted extra cells)
The parameters 5 and 2 are located very close to the end of the source code.
Example output:
Code: Select all
29 26 2 5 xs28_oggs2uge1egozw643 xs31_0g89fgkcz8llljgzx641
39 26 7 5 xs33_mmge1egu2sggoz1y3346 xs31_0g89fgkcz8llljgzx641
42 23 1 8 xs24_0g89fgkczol553 xs31_0g89fgkcz8llljgzx641
52 21 1 10 xs22_g89fgkczd553 xs31_0g89fgkcz8llljgzx641
56 21 3 10 xs24_0okkm996z4aaq1 xs31_0g89fgkcz8llljgzx641
56 21 3 10 xs24_2egu1u0u156zy21 xs31_0g89fgkcz8llljgzx641
56 23 8 8 xs31_0caab8brz255ll2zx11 xs31_0g89fgkcz8llljgzx641
57 20 1 11 xs21_0g09fg4cz8ll91 xs31_0g89fgkcz8llljgzx641
57 20 1 11 xs21_g09fgkczd553 xs31_0g89fgkcz8llljgzx641
57 22 6 9 xs28_g88bbgz8llll8zx66 xs31_0g89fgkcz8llljgzx641Anyway, here's the source code:
Code: Select all
//bin/cat /dev/null; outfile="$0.exe"
//bin/cat /dev/null; g++ -O3 -Wall -Wextra "$0" -o "$outfile"
//bin/cat /dev/null; "$outfile" "$@"
//bin/cat /dev/null; status=$?
//bin/cat /dev/null; rm "$outfile"
//bin/cat /dev/null; exit $status
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <stdint.h>
struct grid64 {
uint64_t a[64];
int height;
int width;
};
uint64_t reverse64(uint64_t x) {
uint64_t y = (x >> 32) | (x << 32);
y = ((y & 0xffff0000ffff0000ull) >> 16) | ((y & 0x0000ffff0000ffffull) << 16);
y = ((y & 0xff00ff00ff00ff00ull) >> 8) | ((y & 0x00ff00ff00ff00ffull) << 8);
y = ((y & 0xf0f0f0f0f0f0f0f0ull) >> 4) | ((y & 0x0f0f0f0f0f0f0f0full) << 4);
y = ((y & 0xccccccccccccccccull) >> 2) | ((y & 0x3333333333333333ull) << 2);
y = ((y & 0xaaaaaaaaaaaaaaaaull) >> 1) | ((y & 0x5555555555555555ull) << 1);
return y;
}
grid64 horizontal_flip(grid64 h) {
grid64 g;
g.width = h.width;
g.height = h.height;
std::memset(g.a, 0, 64 * sizeof(uint64_t));
for (int i = 0; i < g.height; i++) {
g.a[i] = reverse64(h.a[i]) >> (64 - g.width);
}
return g;
}
grid64 vertical_flip(grid64 h) {
grid64 g;
g.width = h.width;
g.height = h.height;
std::memset(g.a, 0, 64 * sizeof(uint64_t));
for (int i = 0; i < g.height; i++) {
g.a[i] = h.a[(g.height - 1) - i];
}
return g;
}
grid64 apgcode_to_grid(std::string apgcode, bool transpose) {
grid64 g;
std::memset(g.a, 0, 64 * sizeof(uint64_t));
int l = apgcode.length();
bool underscore = false;
g.width = 0;
g.height = 0;
int x = 0;
int y = 0;
bool iny = false;
for (int i = 0; i < l; i++) {
char c = apgcode[i];
if (underscore) {
int d = -1;
if ((c >= 97) && (c < 123)) {
d = c - 87;
} else if ((c >= 48) && (c < 58)) {
d = c - 48;
} else if ((c >= 65) && (c < 91)) {
d = c - 55;
}
if (d >= 0) {
if (iny) {
iny = false;
x += d;
} else {
if (d < 32) {
for (int j = 0; j < 5; j++) {
if (d & (1 << j)) {
if (transpose) {
g.a[x] |= (1ull << (y + j));
g.width = ((y + j) > g.width) ? (y + j) : g.width;
g.height = (x > g.height) ? x : g.height;
} else {
g.a[y + j] |= (1ull << x);
g.width = (x > g.width) ? x : g.width;
g.height = ((y + j) > g.height) ? (y + j) : g.height;
}
}
}
x += 1;
} else {
if (d == 35) {
x = 0;
y += 5;
} else {
x += 2;
if (d >= 33) {
x += 1;
if (d >= 34) {
x += 1;
iny = true;
}
}
}
}
}
}
} else {
underscore = (c == '_');
}
}
g.width += 1;
g.height += 1;
return g;
}
int popcount2d(uint64_t* a, int ah) {
int c = 0;
for (int i = 0; i < ah; i++) {
c += __builtin_popcountll(a[i]);
}
return c;
}
int popcount2d(grid64 g) {
return popcount2d(g.a, g.height);
}
int vconvolve(uint64_t* a, int ah, uint64_t* b, int bh, int shift) {
int counts[ah + bh - 1];
std::memset(counts, 0, (ah + bh - 1) * sizeof(int));
for (int i = 0; i < ah; i++) {
for (int j = 0; j < bh; j++) {
counts[i + j] += __builtin_popcountll(a[i] & (b[j] << shift));
}
}
int c = 0;
for (int i = 0; i < ah + bh - 1; i++) {
c = (c < counts[i]) ? counts[i] : c;
}
return c;
}
int convolve2d(uint64_t* a, int ah, int aw, uint64_t* b, int bh, int bw) {
int d = 0;
for (int i = 0; i < aw - 1; i++) {
int c = vconvolve(a, ah, b, bh, i);
d = (d < c) ? c : d;
}
for (int i = 0; i < bw - 1; i++) {
int c = vconvolve(b, bh, a, ah, i);
d = (d < c) ? c : d;
}
return d;
}
int convolve2d(grid64 g, grid64 h) {
return convolve2d(g.a, g.height, g.width, h.a, h.height, h.width);
}
void display_grid(grid64 g) {
for (int y = 0; y < g.height; y++) {
for (int x = 0; x < g.width; x++) {
if (g.a[y] & (1ull << x)) {
std::cout << '*';
} else {
std::cout << '.';
}
}
std::cout << std::endl;
}
std::cout << std::endl;
}
int main(int argc, char *argv[]) {
std::vector<grid64> grids;
std::vector<std::string> names;
/*
grid64 ma = apgcode_to_grid("xs15_354cgc453", false);
std::cout << ma.width << " by " << ma.height << " (pop : ";
std::cout << popcount2d(ma.a, ma.height) << ")" << std::endl;
*/
for (int i = 1; i < argc; i++) {
std::string argument(argv[i]);
// std::cout << argument << std::endl;
grids.push_back(apgcode_to_grid(argument, false));
grids.push_back(apgcode_to_grid(argument, true));
names.push_back(argument);
names.push_back(argument);
}
int l = grids.size();
for (int i = 0; i < l; i++) {
grids.push_back(vertical_flip(grids[i]));
names.push_back(names[i]);
}
l += l;
for (int i = 0; i < l; i++) {
grids.push_back(horizontal_flip(grids[i]));
names.push_back(names[i]);
}
l += l;
/*
for (int i = 0; i < l; i++) {
std::cout << names[i] << std::endl;
display_grid(grids[i]);
}
*/
std::string line;
while (std::getline(std::cin, line)) {
int ersection = -1;
std::string name = "";
grid64 g = apgcode_to_grid(line, false);
int p = popcount2d(g);
int q = -1;
for (int i = 0; i < l; i++) {
int e = convolve2d(g, grids[i]);
if (e > ersection) {
ersection = e;
name = names[i];
q = popcount2d(grids[i]);
}
}
std::cout << 2 * (p - ersection) + 5 * (q - ersection) << " ";
std::cout << ersection << " ";
std::cout << p - ersection << " ";
std::cout << q - ersection << " ";
std::cout << line << " " << name << std::endl;
}
return 0;
}