Abelian sandpile model/Identity: Difference between revisions
Content added Content deleted
(Added Go) |
(Added C++ solution) |
||
Line 58:
* https://en.wikipedia.org/wiki/Abelian_sandpile_model
=={{header|C++}}==
<lang cpp>#include <algorithm>
#include <array>
#include <cassert>
#include <initializer_list>
#include <iostream>
constexpr size_t sp_rows = 3;
constexpr size_t sp_columns = 3;
constexpr size_t sp_cells = sp_rows * sp_columns;
constexpr size_t sp_limit = 4;
class abelian_sandpile {
public:
abelian_sandpile();
explicit abelian_sandpile(std::initializer_list<int> init);
void stabilize();
bool is_stable() const;
void topple();
abelian_sandpile& operator+=(const abelian_sandpile& other);
void print(std::ostream&) const;
private:
int& cell_value(size_t row, size_t column) {
return cells_[cell_index(row, column)];
}
static size_t cell_index(size_t row, size_t column) {
return row * sp_columns + column;
}
static size_t row_index(size_t cell_index) {
return cell_index/sp_columns;
}
static size_t column_index(size_t cell_index) {
return cell_index % sp_columns;
}
friend bool operator==(const abelian_sandpile&, const abelian_sandpile&);
std::array<int, sp_cells> cells_;
};
abelian_sandpile::abelian_sandpile() {
cells_.fill(0);
}
abelian_sandpile::abelian_sandpile(std::initializer_list<int> init) {
assert(init.size() == sp_cells);
std::copy(init.begin(), init.end(), cells_.begin());
}
abelian_sandpile& abelian_sandpile::operator+=(const abelian_sandpile& other) {
for (size_t i = 0; i < sp_cells; ++i)
cells_[i] += other.cells_[i];
stabilize();
return *this;
}
bool abelian_sandpile::is_stable() const {
return std::none_of(cells_.begin(), cells_.end(),
[](int a) { return a >= sp_limit; });
}
void abelian_sandpile::topple() {
for (size_t i = 0; i < sp_cells; ++i) {
if (cells_[i] >= sp_limit) {
cells_[i] -= sp_limit;
size_t row = row_index(i);
size_t column = column_index(i);
if (row > 0)
++cell_value(row - 1, column);
if (row + 1 < sp_rows)
++cell_value(row + 1, column);
if (column > 0)
++cell_value(row, column - 1);
if (column + 1 < sp_columns)
++cell_value(row, column + 1);
break;
}
}
}
void abelian_sandpile::stabilize() {
while (!is_stable())
topple();
}
bool operator==(const abelian_sandpile& a, const abelian_sandpile& b) {
return std::equal(a.cells_.begin(), a.cells_.end(), b.cells_.begin());
}
abelian_sandpile operator+(const abelian_sandpile& a, const abelian_sandpile& b) {
abelian_sandpile c(a);
c += b;
return c;
}
void abelian_sandpile::print(std::ostream& out) const {
for (size_t i = 0; i < sp_cells; ++i) {
if (i > 0)
out << (column_index(i) == 0 ? '\n' : ' ');
out << cells_[i];
}
out << '\n';
}
int main() {
std::cout << std::boolalpha;
std::cout << "Avalanche:\n";
abelian_sandpile sp({4,3,3, 3,1,2, 0,2,3});
while (!sp.is_stable()) {
sp.print(std::cout);
std::cout << "stable? " << sp.is_stable() << "\n\n";
sp.topple();
}
sp.print(std::cout);
std::cout << "stable? " << sp.is_stable() << "\n\n";
std::cout << "Commutativity:\n";
abelian_sandpile s1({1,2,0, 2,1,1, 0,1,3});
abelian_sandpile s2({2,1,3, 1,0,1, 0,1,0});
abelian_sandpile sum1(s1 + s2);
abelian_sandpile sum2(s2 + s1);
std::cout << "s1 + s2 equals s2 + s1? " << (sum1 == sum2) << "\n\n";
std::cout << "s1 + s2 = \n";
sum1.print(std::cout);
std::cout << "\ns2 + s1 = \n";
sum1.print(std::cout);
std::cout << '\n';
std::cout << "Identity:\n";
abelian_sandpile s3({3,3,3, 3,3,3, 3,3,3});
abelian_sandpile s3_id({2,1,2, 1,0,1, 2,1,2});
abelian_sandpile sum3(s3 + s3_id);
abelian_sandpile sum4(s3_id + s3_id);
std::cout << "s3 + s3_id equals s3? " << (sum3 == s3) << '\n';
std::cout << "s3_id + s3_id equals s3_id? " << (sum4 == s3_id) << "\n\n";
std::cout << "s3 + s3_id = \n";
sum3.print(std::cout);
std::cout << "\ns3_id + s3_id = \n";
sum4.print(std::cout);
return 0;
}</lang>
{{out}}
<pre>
Avalanche:
4 3 3
3 1 2
0 2 3
stable? false
0 4 3
4 1 2
0 2 3
stable? false
1 0 4
4 2 2
0 2 3
stable? false
1 1 0
4 2 3
0 2 3
stable? false
2 1 0
0 3 3
1 2 3
stable? true
Commutativity:
s1 + s2 equals s2 + s1? true
s1 + s2 =
3 3 3
3 1 2
0 2 3
s2 + s1 =
3 3 3
3 1 2
0 2 3
Identity:
s3 + s3_id equals s3? true
s3_id + s3_id equals s3_id? true
s3 + s3_id =
3 3 3
3 3 3
3 3 3
s3_id + s3_id =
2 1 2
1 0 1
2 1 2
</pre>
=={{header|Go}}==
| |||