// C++ code to compute sequence A164936 in the OEIS, by Eric M. Schmidt.
// I hereby waive all rights to this code, in accordance with the CC0
// waiver:
// http://creativecommons.org/publicdomain/zero/1.0/

#include <array>
#include <map>
#include <vector>

typedef std::pair<int, int> Pnt;
typedef std::vector<Pnt> CellList;

Pnt operator+(Pnt pnt1, Pnt pnt2)
{
    return {pnt1.first + pnt2.first, pnt1.second + pnt2.second};
}

std::array<Pnt, 8> const neighOffsets
{{
    {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}
}};

CellList appliedConwayLife(CellList const & cells)
{
    CellList newcells;
    newcells.reserve(cells.size());

    std::map<Pnt, std::pair<int, bool>> neighInfo;
    for (Pnt const & pnt : cells)
    {
        neighInfo[pnt].second = true;
        for (Pnt const & offset : neighOffsets)
        {
            ++neighInfo[pnt + offset].first;
        }
    }

    for (auto const & cell : neighInfo)
    {
        Pnt const & pnt(cell.first);
        int const & numNeighbors(cell.second.first);
        bool const & wasAlive(cell.second.second);

        if ((numNeighbors == 3) || (wasAlive && numNeighbors == 2))
        {
            newcells.push_back(pnt);
        }
    }

    return newcells;
}

// Main to compute b-file to n=1500
#include <iostream>
int main()
{
    CellList pattern
        {{1,7}, {2,5}, {2,7}, {2,8}, {3,5}, {3,7}, {4,5}, {5,3}, {6,1}, {6,3}};
    for (int ii(0); ii <= 1500; ++ii)
    {
        std::cout << ii << ' ' << pattern.size() << std::endl;
        pattern = appliedConwayLife(pattern);
    }
}