/*
Simple Wireworld iteration program
Copyright Mark Owen, September 2004
E-mail: mail -at- quinapalus.com

Takes pattern on stdin, emits pattern n generations later on stdout,
n specified as single command-line argument. Sets borders to blank.

Code reformatted, splitted into functions and speed up by leonardo maffi, Jul 29 2008
Based on wirun.c by Mark Owen:
www.quinapalus.com/wi-index.html

Compile:
  gcc -O3 -s -fprofile-generate wirun2.c -o wirun2
    followed by a run several seconds long, followed by:
  gcc -O3 -s -fprofile-use wirun2.c -o wirun2

Wireworld rules:
- Empty -> Empty
- Electron head -> Electron tail
- Electron tail -> Conductor
- Conductor -> Electron head if exactly one or two of the neighbouring cells are
               electron heads and remains Conductor otherwise.

Encoding of I/O format:
  Empty=' '  Conductor='#'    Electron head='@'   Electron tail='~'

*/

#include "stdio.h"


// max board sizes
#define SIZEX 1024
#define SIZEY 1024
#define LINE_MAX SIZEX+10


int head, tail, wire, empty;

// Each list will contain the (linear) positions of all the heads, tails, wires
// empty isn't stored here, the empty array is used as auxiliary to store
// the soon-to-be heads
// Using fixed-size power-of-two 2D arrays allows a faster computation of the positions
int lists[4][SIZEX * SIZEY];

// number of heads, tails, wires
int llen[4];

// this will contain the circuit schema, the line length will be fixed to SIZE
// the circuit is placed on the top left, with free space on the right
char board[SIZEX * SIZEY];


#define ADD_LIST(material, i) lists[material][llen[material]++] = i

// character encoding of the four states
// this encoding allows to count the number of head quickly
#define EMPTY_C   0
#define HEAD_C    1
#define TAIL_C   16
#define WIRE_C   32


void set_list(int material, char c) {
    int i, n;
    int *p;

    p = lists[material];
    n = llen[material];
    for (i = 0; i < n; i++)
        board[*p++] = c;
}


int read_stdin_data(int *nx, int *ny) {
    int i, x, y;
    char *p;
    char line[LINE_MAX];

    for (i = 0; i < SIZEX * SIZEY; i++)
        board[i] = EMPTY_C;

    llen[0] = llen[1] = llen[2] = llen[3] = 0;
    head = 0;
    tail = 1;
    wire = 2;
    empty = 3;

    p = fgets(line, LINE_MAX, stdin);
    if (p == NULL) {
        fprintf(stderr, "File error\n");
        return 1;
    }

    int n_read = sscanf(line, "%d %d", nx, ny);
    if (n_read != 2) {
        fprintf(stderr, "File format error: the first line must contain nx ny\n");
        return 1;
    }
    if (*nx > SIZEX || *ny > SIZEY) {
        fprintf(stderr, "Board too big\n");
        return 1;
    }
    if (*nx < 3 || *ny < 3) {
        fprintf(stderr, "Board too small\n");
        return 1;
    }

    fprintf(stderr, "Board size: %d %d\n", *nx, *ny);

    p = fgets(line, LINE_MAX, stdin);
    if (p == NULL) {
        fprintf(stderr, "File error\n");
        return 1;
    }

    for (y = 1; y < (*ny - 1); y++) {
        p = fgets(line, LINE_MAX, stdin);
        if (p == NULL) {
            fprintf(stderr,"File error\n");
            return 1;
        }

        for (x = 1; x < (*nx - 1); x++) {
            int t = x + y * SIZEX;
            switch (line[x]) {
                case ' ':
                    board[t] = EMPTY_C;
                    break;
                case '@':
                    board[t] = HEAD_C;
                    ADD_LIST(wire, t);
                    ADD_LIST(head, t);
                    break;
                case '~':
                    board[t] = TAIL_C;
                    ADD_LIST(wire, t);
                    ADD_LIST(tail, t);
                    break;
                case '#':
                    board[t] = WIRE_C;
                    ADD_LIST(wire, t);
                    break;
                default:
                    fprintf(stderr, "Bad character %c\n", line[x]);
                    return 1;
                    break;
            }
        }
    }

    fprintf(stderr, "Board read.\n");
    return 0; // all okay
}


void compute_generations(int ngenerations) {
    int i, generation, nheads, aux;

    for (generation = 0; generation < ngenerations; generation++) {
        llen[empty] = 0;

        for (i = 0; i < llen[wire]; i++) {
            int u = lists[wire][i];
            char *ptr = board + u;
            if (*ptr == WIRE_C) {
                nheads = (ptr[-SIZEX-1] + ptr[-SIZEX  ] + ptr[-SIZEX+1] +
                          ptr[      -1]                 + ptr[      +1] +
                          ptr[ SIZEX-1] + ptr[ SIZEX  ] + ptr[ SIZEX+1]) & 15;
                if (nheads == 1 || nheads == 2)
                    ADD_LIST(empty, u);
            }
        }

        set_list(tail, WIRE_C);
        set_list(head, TAIL_C);
        set_list(empty, HEAD_C);
        aux = tail; tail = head; head = empty; empty = aux;
    }
}


void save_board(char* board, int nx, int ny) {
    int x, y;

    printf("%d %d\n", nx, ny);
    for (y = 0; y < ny; y++) {
        for (x = 0; x < nx; x++) {
            char state = board[y * SIZEX + x];
            switch (state) {
                case (char)HEAD_C:
                    putchar('@'); break;
                case EMPTY_C:
                    putchar(' '); break;
                case TAIL_C:
                    putchar('~'); break;
                case WIRE_C:
                    putchar('#'); break;
            }
        }
        putchar('\n');
    }
}


int main(int argc, char** argv) {
    int nx, ny, ngenerations;

    if (argc != 2) {
        fprintf(stderr, "Usage: %s <count>\n", argv[0]);
        return 1;
    }

    int n_read = sscanf(argv[1], "%d", &ngenerations);
    if (n_read != 1 || ngenerations < 0) {
        fprintf(stderr, "Usage: %s <count>\n", argv[0]);
        fprintf(stderr, "count must be >= 0\n");
        return 1;
    }

    if (read_stdin_data(&nx, &ny))
        return 1;

    compute_generations(ngenerations);
    save_board(board, nx, ny);

    return 0;
}