v1.0
Update:
Object counting
Code: Select all
/*
** Theoretical Life Ash Counter (TLAC) v1.0
** By g0t0 (Modify this and the version number if someone update the program)
**
** This project aims to count ash objects strictly according to the definition.
**
** Bug list:
** Sparks now are standalone objects.
*/
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
int cells[128][128], field[2][128][128];
namespace dsu {
/* The Disjoint Set Union algorithm */
int parent[16384], weight[16384];
void init(int num) {
for (int i = 1; i <= num; ++i) {
parent[i] = i;
weight[i] = 1;
}
}
int find_root(int x) {
return parent[x] == x ? x : (parent[x] = find_root(parent[x]) /* Path compression */);
}
void merge(int x, int y) { /* Oops, I can't use 'union' as the name of the function */
x = find_root(x);
y = find_root(y);
if (weight[x] > weight[y]) std::swap(x, y);
parent[x] = y;
weight[y] += weight[x];
}
}
std::vector<std::vector<int>> rotate(std::vector<std::vector<int>> origin) {
/* Clockwise 90 degrees */
int height = origin.size(), width = origin[0].size();
std::vector<std::vector<int>> obj(width, std::vector<int>(height));
for (int i = 0; i < height; ++i) {
for (int j = 0; j < width; ++j) {
obj[j][height - i - 1] = origin[i][j];
}
}
return obj;
}
std::vector<std::vector<int>> flip(std::vector<std::vector<int>> origin) {
/* Flip vertically */
int height = origin.size(), width = origin[0].size();
std::vector<std::vector<int>> obj(width, std::vector<int>(height));
for (int i = 0; i < height; ++i) {
for (int j = 0; j < width; ++j) {
obj[i][height - j - 1] = origin[i][j];
}
}
return obj;
}
std::vector<std::vector<int>> standard_form(std::vector<std::vector<int>> o0) {
auto o1 = rotate(o0);
auto o2 = rotate(o1);
auto o3 = rotate(o2);
auto o4 = flip(o0);
auto o5 = rotate(o4);
auto o6 = rotate(o5);
auto o7 = rotate(o6);
return std::max({o0, o1, o2, o3, o4, o5, o6, o7});
}
int main() {
/*
** The code now run in bounded grid and the pattern must be ash.
** It now can count all the pseudo still lifes / oscillators.
*/
using std::cin;
using std::cout;
cout << "Please input height and width of the grid (<= 100): ";
int height, width;
cin >> height >> width;
cout << "Please input the pattern:\n";
int total = 0, (*front)[128] = ::field[0], (*back)[128] = ::field[1];
for (int i = 1; i <= height; ++i) {
for (int j = 1; j <= width; ++j) {
char c;
cin >> c;
if (!(c == ' ' || c == '.')) {
front[i][j] = cells[i][j] = ++total;
}
}
}
cout << "Please input the maximum step (-1 for no limit): ";
int step;
cin >> step;
dsu::init(total);
const int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
/* Merge interacting cells */
int run;
do {
run = false;
for (int i = 1; i <= height; ++i) {
for (int j = 1; j <= width; ++j) {
int cnt = 0, flag = 0;
for (int d = 0; d < 8; ++d) cnt += front[i + dir[d][0]][j + dir[d][1]] > 0;
if (front[i][j]) {
/* Case 1: Live, underpopulation, NOT MERGE(Is it right?) */
if (cnt < 2) back[i][j] = 0;
/* Case 2: Live, remains, merge */
else if (cnt <= 3) flag = 1;
/* Case 3: Live, overpopulation, merge */
else flag = 2;
} else {
/* Case 4: Dead, underpopulation, not merge(quasi) */
if (cnt < 3) back[i][j] = 0;
/* Case 5: Dead, borns, merge */
else if (cnt == 3) flag = 1;
/* Case 6: Dead, overpopulation, merge(pseudo) */
else flag = 2;
}
if (flag) {
int first = 0;
for (int x = -1; x <= 1; ++x) {
for (int y = -1; y <= 1; ++y) {
int cur = front[i + x][j + y];
if (cur) {
if (first) dsu::merge(cur, first);
else first = cur;
}
}
}
if (flag == 1) back[i][j] = first;
else back[i][j] = 0;
}
if (!back[i][j] != !cells[i][j]) run = true;
}
}
std::swap(front, back);
-- step;
} while (run && step); // Repeat until the pattern turn to the origin state (may can be optimize)
/* Count all things */
std::map<std::vector<std::vector<int>>, int> objects;
for (int i = 1; i <= total; ++i) {
if (dsu::parent[i] == i) {
int minj = 1000, maxj = 0, mink = 1000, maxk = 0;
for (int j = 1; j <= height; ++j) {
for (int k = 1; k <= width; ++k) {
if (cells[j][k] && dsu::find_root(cells[j][k]) == i) {
minj = std::min(minj, j);
maxj = std::max(maxj, j);
mink = std::min(mink, k);
maxk = std::max(maxk, k);
}
}
}
std::vector<std::vector<int>> obj(maxj - minj + 1, std::vector<int>(maxk - mink + 1));
for (int j = minj; j <= maxj; ++j) {
for (int k = mink; k <= maxk; ++k) {
if (cells[j][k] && dsu::find_root(cells[j][k]) == i) obj[j - minj][k - mink] = 1;
}
}
++objects[standard_form(obj)];
}
}
cout << "Objects:\n";
for (auto p : objects) {
auto obj = p.first;
int cnt = p.second;
cout << "Count: " << cnt << '\n';
for (auto row : obj) {
for (int cell : row) {
if (cell) cout << 'o';
else cout << '.';
}
cout << '\n';
}
}
}
v1.1
Modified the definition of
one object.
Code: Select all
/*
** Theoretical Life Ash Counter (TLAC) v1.1
** By g0t0 (Modify this and the version number if someone update the program)
**
** This project aims to count ash objects strictly according to the definition.
**
** Bug list:
** Sparks now are standalone objects.
*/
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
int cells[128][128], field[2][128][128];
namespace dsu {
/* The Disjoint Set Union algorithm */
int parent[16384], weight[16384];
void init(int num) {
for (int i = 1; i <= num; ++i) {
parent[i] = i;
weight[i] = 1;
}
}
int find_root(int x) {
return parent[x] == x ? x : (parent[x] = find_root(parent[x]) /* Path compression */);
}
void merge(int x, int y) { /* Oops, I can't use 'union' as the name of the function */
x = find_root(x);
y = find_root(y);
if (weight[x] > weight[y]) std::swap(x, y);
parent[x] = y;
weight[y] += weight[x];
}
}
std::vector<std::vector<int>> rotate(std::vector<std::vector<int>> origin) {
/* Clockwise 90 degrees */
int height = origin.size(), width = origin[0].size();
std::vector<std::vector<int>> obj(width, std::vector<int>(height));
for (int i = 0; i < height; ++i) {
for (int j = 0; j < width; ++j) {
obj[j][height - i - 1] = origin[i][j];
}
}
return obj;
}
std::vector<std::vector<int>> flip(std::vector<std::vector<int>> origin) {
/* Flip vertically */
int height = origin.size(), width = origin[0].size();
std::vector<std::vector<int>> obj(width, std::vector<int>(height));
for (int i = 0; i < height; ++i) {
for (int j = 0; j < width; ++j) {
obj[i][height - j - 1] = origin[i][j];
}
}
return obj;
}
std::vector<std::vector<int>> standard_form(std::vector<std::vector<int>> o0) {
auto o1 = rotate(o0);
auto o2 = rotate(o1);
auto o3 = rotate(o2);
auto o4 = flip(o0);
auto o5 = rotate(o4);
auto o6 = rotate(o5);
auto o7 = rotate(o6);
return std::max({o0, o1, o2, o3, o4, o5, o6, o7});
}
int main() {
/*
** The code now run in bounded grid and the pattern must be ash.
** It now can count all the pseudo still lifes / oscillators.
*/
using std::cin;
using std::cout;
cout << "Please input height and width of the grid (<= 100): ";
int height, width;
cin >> height >> width;
cout << "Please input the pattern:\n";
int total = 0, (*front)[128] = ::field[0], (*back)[128] = ::field[1];
for (int i = 1; i <= height; ++i) {
for (int j = 1; j <= width; ++j) {
char c;
cin >> c;
if (!(c == ' ' || c == '.')) {
front[i][j] = cells[i][j] = ++total;
}
}
}
cout << "Please input the maximum step (-1 for no limit): ";
int step;
cin >> step;
dsu::init(total);
const int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
/* Merge interacting cells */
int run;
do {
run = false;
for (int i = 1; i <= height; ++i) {
for (int j = 1; j <= width; ++j) {
int cnt = 0, flag = 0;
for (int d = 0; d < 8; ++d) cnt += front[i + dir[d][0]][j + dir[d][1]] > 0;
if (front[i][j]) {
/* Case 1: Live, underpopulation, MERGE */
if (cnt < 2) flag = 2;
/* Case 2: Live, remains, merge */
else if (cnt <= 3) flag = 1;
/* Case 3: Live, overpopulation, merge */
else flag = 2;
} else {
/* Case 4: Dead, underpopulation, not merge(quasi) */
if (cnt < 3) back[i][j] = 0;
/* Case 5: Dead, borns, merge */
else if (cnt == 3) flag = 1;
/* Case 6: Dead, overpopulation, merge(pseudo) */
else flag = 2;
}
if (flag) {
int first = 0;
for (int x = -1; x <= 1; ++x) {
for (int y = -1; y <= 1; ++y) {
int cur = front[i + x][j + y];
if (cur) {
if (first) dsu::merge(cur, first);
else first = cur;
}
}
}
if (flag == 1) back[i][j] = first;
else back[i][j] = 0;
}
if (!back[i][j] != !cells[i][j]) run = true;
}
}
std::swap(front, back);
-- step;
} while (run && step); // Repeat until the pattern turn to the origin state (may can be optimize)
/* Count all things */
std::map<std::vector<std::vector<int>>, int> objects;
for (int i = 1; i <= total; ++i) {
if (dsu::parent[i] == i) {
int minj = 1000, maxj = 0, mink = 1000, maxk = 0;
for (int j = 1; j <= height; ++j) {
for (int k = 1; k <= width; ++k) {
if (cells[j][k] && dsu::find_root(cells[j][k]) == i) {
minj = std::min(minj, j);
maxj = std::max(maxj, j);
mink = std::min(mink, k);
maxk = std::max(maxk, k);
}
}
}
std::vector<std::vector<int>> obj(maxj - minj + 1, std::vector<int>(maxk - mink + 1));
for (int j = minj; j <= maxj; ++j) {
for (int k = mink; k <= maxk; ++k) {
if (cells[j][k] && dsu::find_root(cells[j][k]) == i) obj[j - minj][k - mink] = 1;
}
}
++objects[standard_form(obj)];
}
}
cout << "Objects:\n";
for (auto p : objects) {
auto obj = p.first;
int cnt = p.second;
cout << "Count: " << cnt << '\n';
for (auto row : obj) {
for (int cell : row) {
if (cell) cout << 'o';
else cout << '.';
}
cout << '\n';
}
}
}
v1.2
Fix a bug about flip.
Modify the -1 mode.
Code: Select all
/*
** Theoretical Life Ash Counter (TLAC) v1.2
** By g0t0 (Modify this and the version number if someone update the program)
**
** This project aims to count ash objects strictly according to the definition.
**
** Sparks now are standalone objects in the maximum step mode.
**
** Bug list:
** The oscillators in different phases will be different object.
**
** v0.1 2026/8/20
** v1.0 2026/8/20
** v1.1 2026/9/15
** v1.2 2026/9/15
*/
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
int cells[128][128], field[2][128][128];
namespace dsu {
/* The Disjoint Set Union algorithm */
int parent[16384], weight[16384];
void init(int num) {
for (int i = 1; i <= num; ++i) {
parent[i] = i;
weight[i] = 1;
}
}
int find_root(int x) {
return parent[x] == x ? x : (parent[x] = find_root(parent[x]) /* Path compression */);
}
void merge(int x, int y) { /* Oops, I can't use 'union' as the name of the function */
x = find_root(x);
y = find_root(y);
if (weight[x] > weight[y]) std::swap(x, y);
parent[x] = y;
weight[y] += weight[x];
}
}
std::vector<std::vector<int>> rotate(std::vector<std::vector<int>> origin) {
/* Clockwise 90 degrees */
int height = origin.size(), width = origin[0].size();
std::vector<std::vector<int>> obj(width, std::vector<int>(height));
for (int i = 0; i < height; ++i) {
for (int j = 0; j < width; ++j) {
obj[j][height - i - 1] = origin[i][j];
}
}
return obj;
}
std::vector<std::vector<int>> flip(std::vector<std::vector<int>> origin) {
/* Flip vertically */
int height = origin.size(), width = origin[0].size();
std::vector<std::vector<int>> obj(height, std::vector<int>(width));
for (int i = 0; i < height; ++i) {
for (int j = 0; j < width; ++j) {
obj[i][width - j - 1] = origin[i][j];
}
}
return obj;
}
std::vector<std::vector<int>> standard_form(std::vector<std::vector<int>> o0) {
auto o1 = rotate(o0);
auto o2 = rotate(o1);
auto o3 = rotate(o2);
auto o4 = flip(o0);
auto o5 = rotate(o4);
auto o6 = rotate(o5);
auto o7 = rotate(o6);
return std::max({o0, o1, o2, o3, o4, o5, o6, o7});
}
int main() {
/*
** The code now run in bounded grid.
** It now can count all the pseudo still lifes / oscillators.
*/
using std::cin;
using std::cout;
cout << "Please input height and width of the grid (<= 100): ";
int height, width;
cin >> height >> width;
cout << "Please input the pattern:\n";
int total = 0, (*front)[128] = ::field[0], (*back)[128] = ::field[1];
for (int i = 1; i <= height; ++i) {
for (int j = 1; j <= width; ++j) {
char c;
cin >> c;
if (!(c == ' ' || c == '.')) {
front[i][j] = cells[i][j] = ++total;
}
}
}
cout << "Please input the maximum step (-1 for no limit): ";
int step;
cin >> step;
dsu::init(total);
const int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
/* Merge interacting cells */
int run;
do {
run = false;
for (int i = 1; i <= height; ++i) {
for (int j = 1; j <= width; ++j) {
int cnt = 0, flag = 0;
for (int d = 0; d < 8; ++d) cnt += front[i + dir[d][0]][j + dir[d][1]] > 0;
if (front[i][j]) {
/* Case 1: Live, underpopulation, MERGE */
if (cnt < 2) flag = 2;
/* Case 2: Live, remains, merge */
else if (cnt <= 3) flag = 1;
/* Case 3: Live, overpopulation, merge */
else flag = 2;
} else {
/* Case 4: Dead, underpopulation, not merge(quasi) */
if (cnt < 3) back[i][j] = 0;
/* Case 5: Dead, borns, merge */
else if (cnt == 3) flag = 1;
/* Case 6: Dead, overpopulation, merge(pseudo) */
else flag = 2;
}
if (flag) {
int first = 0;
for (int x = -1; x <= 1; ++x) {
for (int y = -1; y <= 1; ++y) {
int cur = front[i + x][j + y];
if (cur) {
if (first) dsu::merge(cur, first);
else first = cur;
}
}
}
if (flag == 1) back[i][j] = first;
else back[i][j] = 0;
}
if (!back[i][j] != !cells[i][j]) run = true;
}
}
std::swap(front, back);
-- step;
} while (run && step); // Repeat until the pattern turn to the origin state (may can be optimize)
if (step < 0) {
memcpy(cells, front, sizeof(cells));
}
/* Count all things */
std::map<std::vector<std::vector<int>>, int> objects;
for (int i = 1; i <= total; ++i) {
if (dsu::parent[i] == i) {
int minj = 1000, maxj = 0, mink = 1000, maxk = 0;
for (int j = 1; j <= height; ++j) {
for (int k = 1; k <= width; ++k) {
if (cells[j][k] && dsu::find_root(cells[j][k]) == i) {
minj = std::min(minj, j);
maxj = std::max(maxj, j);
mink = std::min(mink, k);
maxk = std::max(maxk, k);
}
}
}
if (minj == 1000) continue;
std::vector<std::vector<int>> obj(maxj - minj + 1, std::vector<int>(maxk - mink + 1));
for (int j = minj; j <= maxj; ++j) {
for (int k = mink; k <= maxk; ++k) {
if (cells[j][k] && dsu::find_root(cells[j][k]) == i) obj[j - minj][k - mink] = 1;
}
}
++objects[standard_form(obj)];
}
}
cout << "Objects:\n";
for (auto p : objects) {
auto obj = p.first;
int cnt = p.second;
cout << "Count: " << cnt << '\n';
for (auto row : obj) {
for (int cell : row) {
if (cell) cout << 'o';
else cout << '.';
}
cout << '\n';
}
}
}
Replicating or dying, that is a question.
