Game of Life implementation with no loops

Question

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';
  }
}

Answer 1

I challenged myself to implement the game with no loops

However I like your set of mind, I wouldn't advise to renounce raw loops in this kind of program. There is no equivalent to for (int i = 0; i < n; ++i) in the algorithm standard library if you only want the i (as opposed to as an offset in a container, or as a value to fill a container with, or anything related to a container), and you'll need it to efficiently compute the cell's neighbors for instance. What you could do though is to rely on Eric Niebler's range library, which will be partially standardized in C++20; that would give something like for (auto i : view::iota(0) | view::take(n)) // do something with i)

The thing I don't like about your program is that it is too complex. The whole program could fit into two core functions and a display function: one function would compute the number of alive neighbors for each cell of the grid (so the return value would be a grid of the same size as the input), and one function would compute the grid's next state from the grid of alive neighbors by cell. You don't even have to create a Grid class, as a std::vector or yet better a std::array has every functionality you need and more (such as compile-time size and bounds for a std::array).

#include <unordered_set>
#include <iostream>
#include <vector>
#include <functional>
#include <array>
#include <iterator>
#include <cstddef>
#include <algorithm>
#include <utility>

There is I think a bit too many headers here: for instance, is <functional> really used?

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);
    }
  };
}

As @AlexReinking said, a hash map isn't more efficient here, or rather: a simple 2d array is the most efficient hash map you could devise.

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;

That looks like a lot of intermediary vectors.

  // find cells that will die
  std::copy_if(grid.begin(), grid.end(), std::back_inserter(to_die),
               [&](const auto& cell){

It is a bad idea to capture the whole context, and even worse when you do it by reference, because it's a source of silent bugs: one or two wrong keystrokes and you can refer to a variable outside of the lambda while thinking you refer to a variable inside

                 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(),

No raw loops is a nice goal, but for_each shouldn't be used instead of for (const auto& elem : container): it's more convoluted, less readable, etc.

                [&](const auto& cell){
                  const auto neighbors = neighbors_of(cell);
                  std::copy(neighbors.begin(), neighbors.end(), std::back_inserter(all_neighbors));

I don't understand why you have the neighbors intermediary array, if the only thing you do with it is copy it into all_neighbors. It's just a waste.

                });

  // 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) };
}

This doesn't take into account the fact that some cells are at the border of the grid: those don't have 8 neighbors, but between 3 (angles) and 7.

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;
}

You don't have to master GUIs in order to do better than that: just output your grid as a grid, not as a list of cells (for instance for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid.find(cell(i, j)) != grid.end()) std::cout << 'O' else std::cout ' '; } std::cout << std::endl; }).

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';
  }
}