Abelian sandpile model/Identity: Difference between revisions
Content added Content deleted
(Added Go) |
(Added C++ solution) |
||
Line 58: | Line 58: | ||
* https://en.wikipedia.org/wiki/Abelian_sandpile_model |
* 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}}== |
=={{header|Go}}== |