Langton ant simulator

/* Simulation of Langton's ant on a toroidally wrapped grid. Takes two
 * command-line arguments: number of rows and number of columns. Grid is initially
 * all-white, and the ant starts facing up (i.e. looking up a column).
 */

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef enum {WHITE=0, BLACK=1} color_t;
typedef enum {UP=0, RIGHT=1, DOWN=2, LEFT=3} dir_t;

int ROWS;
int COLS;
int ant_row;
int ant_col;
dir_t ant_dir;

char* color_to_str(color_t color) {
  if (color == WHITE) {
    return("white");
  } else if (color == BLACK){
    return("black");
  } else {
    assert(0);
  }
}

char* dir_to_str(dir_t dir) {
  if (dir == UP) {
    return("up");
  } else if (dir == RIGHT) {
    return("right");
  } else if (dir == DOWN) {
    return("down");
  } else if (dir == LEFT) {
    return("left");
  } else {
    assert(0);
  }
}

inline static int mod(int a, int b)
{
  int r = a % b;
  return r < 0 ? r + b : r;
}

inline static void turn_counterclockwise(void) {
  ant_dir += (ant_dir == UP)?3:-1;
}

inline static void turn_clockwise(void) {
 ant_dir += (ant_dir == LEFT)?-3:1;
}

inline static void advance(void) {
  switch (ant_dir) {
  case UP:
    ant_row = (ant_row == ROWS-1)?0:(ant_row + 1);
    break;
  case RIGHT:
    ant_col = (ant_col == COLS-1)?0:(ant_col+1);
    break;
  case DOWN:
    ant_row = (ant_row == 0)?(ROWS-1):(ant_row-1);
    break;
  case LEFT:
    ant_col = (ant_col == 0)?(COLS-1):(ant_col-1);
    break;
  default:
    break;
  }
}

inline static void translate(int forward, int right) {
  switch (ant_dir) {
  case UP:
    ant_row += forward;
    ant_col += right;
    break;
  case RIGHT:
    ant_col += forward;
    ant_row -= right;
    break;
  case DOWN:
    ant_row -= forward;
    ant_col -= right;
    break;
  case LEFT:
    ant_col -= forward;
    ant_row += right;
    break;
  default:
    assert(0);
  }
  ant_col = mod(ant_col, COLS);
  ant_row = mod(ant_row, ROWS);
}

int main(int argc, char* argv[]) {
  assert(argc == 3);
  ROWS = atoi(argv[1]);
  COLS = atoi(argv[2]);

  // initialize grid
  color_t grid[ROWS][COLS];
  for (int r = 0; r < ROWS; r++) {
    for (int c = 0; c < COLS; c++) {
      grid[r][c] = WHITE;
    }
  }
  int black_cells = 0;
  int tot_cells = ROWS * COLS;

  ant_row = 0;
  ant_col = 0;
  ant_dir = UP;

  // Initialize with invalid values
  color_t qr_color = -1;
  dir_t qr_dir = -1;
  int qr_row = -1;
  int qr_col = -1;

  // main loop; runs until quasi-recurrence
  unsigned long turns = 0;
  while (1) {
    color_t color = grid[ant_row][ant_col];
    if (color == WHITE) {
      turn_clockwise();
    } else {
      turn_counterclockwise();
    }
    // flip grid color
    grid[ant_row][ant_col] ^= 1;
    black_cells += (color == WHITE)?1:-1;
    // move ant
    advance();

    turns += 1;
    // print
    if (turns % 100000000 == 0) {
      fprintf(stderr, "(%luM) ", turns/1000000);
    }
    // test for quasi-recurrence
    if ((black_cells == 0 || black_cells == tot_cells) &&
        (ant_dir == UP || ant_dir == DOWN || ROWS == COLS)) {
      // Save color of board, as well as ant direction and displacement forward and right
      qr_color = (black_cells == 0)?WHITE:BLACK;
      qr_dir = ant_dir;
      qr_row = ant_row;
      qr_col = ant_col;
      printf("col: %d row: %d color: %s dir: %s\n",
             qr_row, qr_col, color_to_str(qr_color), dir_to_str(qr_dir));
      break;
    }
  }
// Now simulate "megaturns" between one quasi-recurrence and next until true recurrence
// Note: if board is black (odd-numbered megaturns and qr_dir == BLACK), then
// left and right are flipped relative to ant's initial direction.

  unsigned long megaturns = 0;
  ant_row = 0;
  ant_col = 0;
  ant_dir = UP;
  bool white_board = true;
  while (1) {
    // Translate ant to next quasirecurrence
    translate(qr_row, white_board?qr_col:-qr_col);
    // Rotate ant
    if (qr_dir == DOWN) {
      turn_clockwise();
      turn_clockwise();
    } else if ((qr_dir == RIGHT && white_board) || (qr_dir == LEFT && !white_board)) {
      turn_clockwise();
    } else if ((qr_dir == LEFT && white_board) || (qr_dir == RIGHT && !white_board)) {
      turn_counterclockwise();
    }
    megaturns++;
    white_board = (qr_color == WHITE) || (megaturns % 2 == 0);
    if (ant_row == 0 && ant_col == 0 && ant_dir == UP && white_board) {
      printf("%lu quasirecurrence(s) x %lu turns each = %lu\n",
               megaturns, turns, turns*megaturns);
      break;
    }
  }
  return 0;
}