5
\$\begingroup\$

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 and 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';
  }
}
\$\endgroup\$
2
  • 3
    \$\begingroup\$ When a contiguous array suffices, a hash table is never better. Think of it this way: your 2D array has simple index arithmetic as a perfect, no collisions hash function. You have no guarantee of sparsity, so your storage is optimally compact. With a hashtable you sacrifice speed both on lookups but also memory fragmentation. \$\endgroup\$ Dec 11, 2018 at 7:07
  • \$\begingroup\$ @AlexReinking this does not allow for an infinite grid. I think an unordered_set is the efficient way to get an infinite grid. \$\endgroup\$
    – Brady Dean
    Dec 11, 2018 at 18:54

1 Answer 1

4
\$\begingroup\$

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';
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.