/*

Linus Åkesson wrote the following excellent program:

            Linus Akesson presents:
                   The Game Of Life implemented in Brainfuck

       +>>++++[<++++>-]<[<++++++>-]+[<[>>>>+<<<<-]>>>>[<<<<+>>>>>>+<<-]<+
   +++[>++++++++<-]>.[-]<+++[>+++<-]>+[>>.+<<-]>>[-]<<<++[<+++++>-]<.<<[>>>>+
 <<<<-]>>>>[<<<<+>>>>>>+<<-]<<[>>>>.+<<<++++++++++[<[>>+<<-]>>[<<+>>>>>++++++++
 +++<<<-]<[>+<-]>[<+>>>>+<<<-]>>>[>>>>>>>>>>>>+>+<<     <<<<<<<<<<<-]>>>>>>>>>>
>>[-[>>>>+<<<<-]>[>>>>+<<<<-]>>>]>      >>[<<<+>>  >-    ]<<<[>>+>+<<<-]>[->[<<<
<+>>>>-]<[<<<  <+>      >>>-]<<<< ]<     ++++++  ++       +[>+++++<-]>>[<<+>>-]<
<[>---<-]>.[- ]         <<<<<<<<< <      <<<<<< <         -]++++++++++.[-]<-]>>>
>[-]<[-]+++++           +++[>++++        ++++<     -     ]>--.[-]<,----------[<+
>-]>>>>>>+<<<<< <     <[>+>>>>>+>[      -]<<<      <<   <<-]>++++++++++>>>>>[[-]
<<,<<<<<<<->>>> >    >>[<<<<+>>>>-]<<<<[>>>>+      >+<<<<<-]>>>>>----------[<<<<
<<<<+<[>>>>+<<<      <-]>>>>[<<<<+>>>>>>+<<-      ]>[>-<-]>++++++++++[>+++++++++
++<-]<<<<<<[>>>      >+<<<<-]>>>>[<<<<+>>>>>      >+<<-]>>>>[<<->>-]<<++++++++++
[>+<-]>[>>>>>>>      >>>>>+>+<<<<      <<<<<      <<<<-]>>> >>     >>>>>>>[-[>>>
>+<<<<-]>[>>>>       +<<<<-]>> >       ]>> >           [<< <        +>>>-]+<<<[>
>>-<<<-]>[->[<      <<<+>>>>-]         <[ <            < <           <+>>>>-]<<<
<]<<<<<<<<<<<, [    -]]>]>[-+++        ++               +    +++     ++[>+++++++
++++>+++++++++ +    +<<-]>[-[>>>      +<<<-      ]>>>[ <    <<+      >>>>>>>+>+<
<<<<-]>>>>[-[> >    >>+<<<<-]>[>      >>>+< <    <<-]> >    >]>      >>[<<<+>>>-
]<<<[>>+>+<<< -     ]>[->[<<<<+>      >>>-] <    [<<< <    +>>       >>-]<<<<]<<
<<<<<<[>>>+<< <     -]>>>[<<<+>>      >>>>> +    >+<< <             <<-]<<[>>+<<
-]>>[<<+>>>>>      >+>+<<<<<-]>>      >>[-[ >    >>>+ <            <<<-]>[>>>>+<
<<<-]>[>>>>+<      <<<-]>>]>>>[ -    ]<[>+< -    ]<[ -           [<<<<+>>>>-]<<<
<]<<<<<<<<]<<      <<<<<<<<++++ +    +++++  [   >+++ +    ++++++[<[>>+<<-]>>[<<+
>>>>>++++++++ +    ++<<<     -] <    [>+<- ]    >[<+ >    >>>+<<<-]>>>[<<<+>>>-]
<<<[>>>+>>>>  >    +<<<<     <<      <<-]> >    >>>>       >>>[>>+<<-]>>[<<+<+>>
>-]<<<------ -    -----[     >>      >+<<< -    ]>>>       [<<<+> > >>>>>+>+<<<<
<-]>>>>[-[>> >    >+<<<<    -] >     [>>>> +    <<<<-       ]>>> ]  >>>[<<<+>>>-
]<<<[>>+>+<< <    -]>>>     >>           > >    [<<<+               >>>-]<<<[>>>
+<<<<<+>>-                  ]>           >     >>>>>[<             <<+>>>-]<<<[>
>>+<<<<<<<                  <<+         >      >>>>>-]<          <<<<<<[->[<<<<+
>>>>-]<[<<<<+>>>>-]<<<<]>[<<<<<<    <+>>>      >>>>-]<<<<     <<<<<+++++++++++[>
>>+<<<-]>>>[<<<+>>>>>>>+>+<<<<<-]>>>>[-[>     >>>+<<<<-]>[>>>>+<<<<-]>>>]>>>[<<<
+>>>-]<<<[>>+>+<<<-]>>>>>>>[<<<+>>>-]<<<[     >>>+<<<<<+>>-]>>>>>>>[<<<+>>>-]<<<
[>>>+<<<<<<<<<+>>>>>>-]<<<<<<<[->[< <  <     <+>>>>-]<[<<<<+>>>>-]<<<<]>[<<<<<<<
+>>>>>>>-]<<<<<<<<<+++++++++++[>>> >        >>>+>+<<<<<<<<-]>>>>>>>[-[>>>>+<<<<-
]>[>>>>+<<<<-]>>>]>>>[<<<+>>>-]<<< [       >>+>+<<<-]>>>>>>>[<<<+>>>-]<<<[>>>+<<
<<<+>>-]>>>>>>>[<<<+>>>-]<<<[>>>+<        <<<<<<<<+>>>>>>-]<<<<<<<[->[<<<<+>>>>-
 ]<[<<<<+>>>>-]<<<<]>[<<<<<<<+>>>>>      >>-]<<<<<<<----[>>>>>>>+<<<<<<<+[>>>>>
 >>-<<<<<<<[-]]<<<<<<<[>>>>>>>>>>>>+>+<<<<<<<<<<<<<-][   lft@df.lth.se   ]>>>>>
   >>>>>>>[-[>>>>+<<<<-]>[>>>>+<<<<-]>[>>>>+<<<<-]>>]>>>[-]<[>+<-]<[-[<<<<+>>
       >>-]<<<<]<<<<<<[-]]<<<<<<<[-]<<<<-]<-]>>>>>>>>>>>[-]<<]<<<<<<<<<<]

        Type for instance "fg" to toggle the cell at row f and column g
                   Hit enter to calculate the next generation
                                 Type q to quit

It runs slowly in my Brainfuck implementation, 12 CPU seconds per
10×10 generation, without wraparound.  But how slowly is that?  Can we
compare it to a reasonable implementation?

So I took a couple of hours to write this C version. It can compute
about 56000 generations per CPU second on this netbook, about 700k
times faster than the Brainfuck version.

*/

#include <stdio.h>

enum { ww = 10, hh = 10 };

int board[3][hh][ww];

/* From the cells in `from`, compute a parallel array with the sum of
   cells above and to the left of that cell, including that cell
   itself.  For example:

    >>> x
    array([[1, 0, 1],
           [0, 2, 1],
           [1, 1, 1]])
    >>> x.cumsum(axis=0).cumsum(axis=1)
    array([[1, 1, 2],
           [1, 3, 5],
           [2, 5, 8]])
 */
void sum(int from[hh][ww], int to[hh][ww])
{
    for (int x = 0; x < ww; x++) {
        to[0][x] = from[0][x];
        for (int y = 1; y < hh; y++) to[y][x] = to[y-1][x] + from[y][x];
    }
    for (int y = 0; y < hh; y++) {
        int total = to[y][0];
        for (int x = 1; x < ww; x++) to[y][x] = total += to[y][x];
    }
}

/* Return total neighbors in the neighborhood that includes (xmin+1,
   ymin+1), (xmin+2, ymin+1), ... (xmax, ymin+1), (xmin+1, ymin+2),
   ... (xmax, ymax).  xmin and/or ymin will be negative if the
   neighborhood is intended to encompass the leftmost and/or topmost
   cells; xmax may be >=ww-1 and/or ymax may be >=hh-1 if it is intended
   to encompass the rightmost and/or bottommost cells.
 */
static inline int rect(int sums[hh][ww], int xmin, int xmax, int ymin, int ymax)
{
    if (xmax > ww-1) xmax = ww-1;
    if (ymax > ww-1) ymax = hh-1;
    int ul = xmin < 0 ? 0 : ymin < 0 ? 0 : sums[ymin][xmin];
    int ur = ymin < 0 ? 0 : sums[ymin][xmax];
    int ll = xmin < 0 ? 0 : sums[ymax][xmin];
    int lr = sums[ymax][xmax];
    return lr - ur - ll + ul;
}

/* Return total cells in the 3×3 neighborhood centered on (x, y). */
static inline int neighborhood(int sums[hh][ww], int x, int y)
{
    return rect(sums, x-2, x+1, y-2, y+1);
}

static inline int should_live(int cells[hh][ww], int sums[hh][ww], int x, int y)
{
    int n = neighborhood(sums, x, y);
    return cells[y][x] ? 3 <= n && n <= 4 : n == 3;
}

void generation(int from[hh][ww], int to[hh][ww], int scratch[hh][ww])
{
    sum(from, scratch);
    for (int y = 0; y < hh; y++) {
        for (int x = 0; x < ww; x++) {
            to[y][x] = should_live(from, scratch, x, y);
        }
    }
}

void print_board(int cells[hh][ww])
{
    putchar(' ');
    for (int x = 0; x < ww; x++) putchar('a' + x);
    putchar('\n');

    for (int y = 0; y < hh; y++) {
        putchar('a' + y);
        for (int x = 0; x < ww; x++) putchar(cells[y][x] ? '*' : '-');
        putchar('\n');
    }
}

/* Returns 1 if we should do another generation, 0 to quit */
int prompt(int cells[hh][ww])
{
    for (;;) {
        print_board(cells);

        putchar('>');
        fflush(stdout);

        int c1 = getchar();
        if (c1 == 'q' || c1 == EOF) return 0;
        if (c1 == '\n') return 1;

        int c2 = getchar();
        int newline = getchar();
        if (c2 == EOF || newline == EOF) return 0;

        int *cell = &cells[c1-'a'][c2-'a'];
        *cell = !*cell;
    }
}

int main()
{
    int which = 0;
    for (;;) {
        if (!prompt(board[which])) return 0;
        generation(board[which], board[!which], board[2]);
        which = !which;
    }
}