/* Simple one-dimensional cellular automata
 *
 * The cells have two states (black and white), represented by '*' and ' '.
 * At each step, the new state of a cell is a function of its current
 * state and that of its two immediate neighbiours. This means a total
 * of eight possible conditions selecting its new state.
 * For each condition, there are two possible outcomes, meaning that there
 * are exactly 2^8 possible sets of rules; some are uninteresting (e.g.
 * always go black or always go white); some lead to simple repetitive
 * or expanding patterns, some to regular but non-repretitive patterns,
 * and some to 'random' patterns.
 *
 * Given that the row of cells is finite, there is another decision to be
 * made: what happens at the edges. There are six possible cases:
 *    Both off-edge cells are white
 *    Both off-edge cells are black;
 *    One of each (two cases)
 *    The array wraps around
 *    The array wraps around but with a sense change
 *      (i.e. black becomes white and white becomes black).
 *
 * Another variable is the starting pattern.
 * We start with all cells white and a single black cell in the centre.
 * We could also start with a random vector of black/white cells.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <stdbool.h>



/* The cells are represented as a character array.
 * We have 128 of them, with number 64 initially set.
 *
 * Numbers 0 and 129 are used to represent the off-edge cells.
 *
 * We need two arrays, one for the current state and one for
 * the new state.
 */
#define BLACK '*'
#define WHITE ' '

#define CELLS 128
#define MID  CELLS / 2

char curtCells[CELLS + 2];
char newCells[CELLS + 2];

/* The rules can be represented by a single 8-bit value
 * The bit represents the new state (0 = white, 1 = black)
 * with the input combinations represented in order:
 *   LEFT    MID   RIGHT  Bit No
 *   white  white  white    0
 *   while  white  black    1
 *   white  black  white    2
 *   white  black  black    3
 *   black  white  white    4
 *   black  white  black    5
 *   black  black  white    6
 *   black  black  black    7
 */

showRule(int ruleNo)
{
#define COLOUR(x) ((x) ? "black" : "white")
  fprintf(stderr, "Rule No: %d\n", ruleNo);
  fprintf(stderr, " LEFT    MID   RIGHT   RESULT\n");
  fprintf(stderr, " white  white  white   => %s\n", COLOUR(ruleNo & 1));
  fprintf(stderr, " while  white  black   => %s\n", COLOUR(ruleNo & 2));
  fprintf(stderr, " white  black  white   => %s\n", COLOUR(ruleNo & 4));
  fprintf(stderr, " white  black  black   => %s\n", COLOUR(ruleNo & 8));
  fprintf(stderr, " black  white  white   => %s\n", COLOUR(ruleNo & 16));
  fprintf(stderr, " black  white  black   => %s\n", COLOUR(ruleNo & 32));
  fprintf(stderr, " black  black  white   => %s\n", COLOUR(ruleNo & 64));
  fprintf(stderr, " black  black  black   => %s\n", COLOUR(ruleNo & 128));
  fprintf(stderr, "\n");
}


/* A simple procedure to print the current generation. */
void printCells(int generation, char *cells)
{
  int  j;

  printf("%4d ", generation);
  for (j = 1; j <= CELLS; ++j)
    putchar(cells[j]);
  putchar('\n');
}



/* Calculate maxGen generations, given the rule number */
void process(int rule, int maxGen)
{
  int   j;
  int   generation;
  int   index;

  /* Initial conditions */
  memset(curtCells, ' ', sizeof curtCells);
  curtCells[MID] = '*';

  /* Show the starting config */
  printCells(0, curtCells);

  for (generation = 1; generation <= maxGen; ++generation) {
    /* Wrap around */
    curtCells[0]     = curtCells[CELLS];
    curtCells[CELLS] = curtCells[1];

    /* Apply the rule */
    for (j = 1; j <= CELLS; ++j) {
      index = 0;
      if (curtCells[j - 1] == BLACK) index  = 4;
      if (curtCells[j] == BLACK)     index += 2;
      if (curtCells[j + 1] == BLACK) index += 1;

      if (rule & (1 << index)) newCells[j] = BLACK;
      else                     newCells[j] = WHITE;
    }

    /* Print the current state */
    printCells(generation, newCells);

    /* Copy the cells back */
    memcpy(curtCells, newCells, sizeof curtCells);
  }

  putchar('\n');
}


/* Show some help for the program */
void showUsage(char *name)
{
  fprintf(stderr, "Usage:\n");
  fprintf(stderr, "  %s [-g <gens>] [-r <rule>] [-h]\n", name);
  fprintf(stderr, "   -g <gens>  Set no of generations (default 40)\n");
  fprintf(stderr, "   -r <rule>  Set rule (0 to 255, default 110)\n");
  fprintf(stderr, "   -s         Show what the rule is\n");
  fprintf(stderr, "   -h         Show this help and exit\n");
  fprintf(stderr, "  Setting '-r -1' will cycle through all rules.\n\n");
}

/* A simple wrapper around the 'process' procedure.
 * Command-line parameters:
 *    -g <number of generations> (default 40)
 *    -r <rule no>               (default 110)
 *    -h                         Show help
 */
int main(int argc, char **argv)
{
  int  ruleNo;
  int  maxGen;
  bool show;
  int  j;

  ruleNo = 110;
  maxGen = 40;
  show   = false;

  for (j = 1; j < argc; ++j) {
    if (strcmp(argv[j], "-g") == 0) {
      if (j == argc - 1) break;
      maxGen = atoi(argv[++j]);
    } else if (strcmp(argv[j], "-r") == 0) {
      if (j == argc - 1) break;
      ruleNo = atoi(argv[++j]);
    } else if (strcmp(argv[j], "-s") == 0) {
      show = true;
    } else if (strcmp(argv[j], "-h") == 0) {
      showUsage(argv[0]);
      return 1;
    } else {
      fprintf(stderr, "Bad parameter: %s\n", argv[j]);
      showUsage(argv[0]);
      return 1;
    }
  }
  if (j == argc - 1) {
    fprintf(stderr, "Bad additional parameter: %s\n", argv[j]);
    showUsage(argv[0]);
    return 1;
  }

  if (ruleNo >= 0) {
    if (show) showRule(ruleNo);
    else      printf("\nRule number: %d\n", ruleNo);
    process(ruleNo, maxGen);
  } else {
    for (ruleNo = 0; ruleNo < 256; ++ruleNo) {
      if (show) showRule(ruleNo);
      else      printf("\nRule number: %d\n", ruleNo);
      process(ruleNo, maxGen);
      sleep(2);
    }
  }

  return 0;
}