I began implementing Game of Life for fun, then I challenged myself to implement the game with no loops. I only used STL Algorithms. I don't know how to make pretty GUI's yet but this will print the coordinates of each alive cell. I also do not know if I made a good hashing function. I think it's sufficient for the game but I don't know any theory behind good hashing functions. I glanced through the top questions with c++ and game-of-life and noticed everyone used a 2d array. I figured a hashing container would be more efficient.
#include <unordered_set>
#include <iostream>
#include <vector>
#include <functional>
#include <array>
#include <iterator>
#include <cstddef>
#include <algorithm>
#include <utility>
using Cell = std::pair<int, int>;
namespace std {
template<>
struct hash<Cell> {
std::size_t operator()(const Cell& cell) const {
const std::hash<int> hasher;
return hasher(cell.first) & hasher(cell.second);
}
};
}
std::ostream& operator<<(std::ostream& out, const Cell& cell) {
out << '(' << cell.first << ',' << cell.second << ')';
return out;
}
class Life {
public:
template<typename InputIt>
Life(InputIt begin, InputIt end);
void tick();
friend std::ostream& operator<<(std::ostream& out, const Life& life);
private:
std::unordered_set<Cell> grid;
std::array<Cell, 8> neighbors_of(const Cell& cell) const;
int n_alive_neighbors(const std::array<Cell, 8>& neighbors) const;
};
template<typename InputIt>
Life::Life(InputIt begin, InputIt end)
: grid(begin, end) {}
void Life::tick() {
std::vector<Cell> to_die;
std::vector<Cell> to_create;
std::vector<Cell> all_neighbors;
// find cells that will die
std::copy_if(grid.begin(), grid.end(), std::back_inserter(to_die),
[&](const auto& cell){
const auto neighbors = neighbors_of(cell);
const auto alive_neighbors = n_alive_neighbors(neighbors);
return alive_neighbors < 2 || alive_neighbors > 3;
});
// collect neighbors of all cells
std::for_each(grid.begin(), grid.end(),
[&](const auto& cell){
const auto neighbors = neighbors_of(cell);
std::copy(neighbors.begin(), neighbors.end(), std::back_inserter(all_neighbors));
});
// find cells that will be created
std::copy_if(all_neighbors.begin(), all_neighbors.end(), std::back_inserter(to_create),
[&](const auto& cell) {
if (grid.find(cell) != grid.end()) return false;
const auto neighbors = neighbors_of(cell);
const auto alive_neighbors = n_alive_neighbors(neighbors);
return alive_neighbors == 3;
});
// kill cells
std::for_each(to_die.begin(), to_die.end(), [&](const auto& cell){ grid.erase(cell); });
// reproduce cells
grid.insert(to_create.begin(), to_create.end());
}
std::array<Cell, 8> Life::neighbors_of(const Cell& cell) const {
return { Cell(cell.first - 1, cell.second + 1),
Cell(cell.first, cell.second + 1),
Cell(cell.first + 1, cell.second + 1),
Cell(cell.first + 1, cell.second),
Cell(cell.first + 1, cell.second - 1),
Cell(cell.first, cell.second - 1),
Cell(cell.first - 1, cell.second - 1),
Cell(cell.first - 1, cell.second) };
}
int Life::n_alive_neighbors(const std::array<Cell, 8>& neighbors) const {
return std::count_if(neighbors.begin(), neighbors.end(),
[&](const auto& cell){ return grid.find(cell) != grid.end(); });
}
std::ostream& operator<<(std::ostream& out, const Life& life) {
if (life.grid.empty()) return out;
out << *life.grid.begin();
std::for_each(std::next(life.grid.begin()), life.grid.end(),
[&](const auto& cell){
out << '\n' << cell;
});
return out;
}
int main() {
std::array<Cell, 3> blinker {Cell(-1, 0), Cell(0, 0), Cell(1, 0)};
std::array<Cell, 6> toad {Cell(0, 0), Cell(1, 0), Cell(2, 0),
Cell(1, 1), Cell(2, 1), Cell(3, 1)};
Life life(toad.begin(), toad.end());
std::cout << life << '\n';
for (int i = 0; i < 6; ++i) {
life.tick();
std::cout << '\n' << life << '\n';
}
}