Guest User

Langton ant simulator

a guest
Jul 18th, 2019
331
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* Simulation of Langton's ant on a toroidally wrapped grid. Takes two
  2.  * command-line arguments: number of rows and number of columns. Grid is initially
  3.  * all-white, and the ant starts facing up (i.e. looking up a column).
  4.  */
  5.  
  6. #include <assert.h>
  7. #include <stdbool.h>
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10.  
  11. typedef enum {WHITE=0, BLACK=1} color_t;
  12. typedef enum {UP=0, RIGHT=1, DOWN=2, LEFT=3} dir_t;
  13.  
  14. int ROWS;
  15. int COLS;
  16. int ant_row;
  17. int ant_col;
  18. dir_t ant_dir;
  19.  
  20. char* color_to_str(color_t color) {
  21.   if (color == WHITE) {
  22.     return("white");
  23.   } else if (color == BLACK){
  24.     return("black");
  25.   } else {
  26.     assert(0);
  27.   }
  28. }
  29.  
  30. char* dir_to_str(dir_t dir) {
  31.   if (dir == UP) {
  32.     return("up");
  33.   } else if (dir == RIGHT) {
  34.     return("right");
  35.   } else if (dir == DOWN) {
  36.     return("down");
  37.   } else if (dir == LEFT) {
  38.     return("left");
  39.   } else {
  40.     assert(0);
  41.   }
  42. }
  43.  
  44. inline static int mod(int a, int b)
  45. {
  46.   int r = a % b;
  47.   return r < 0 ? r + b : r;
  48. }
  49.  
  50. inline static void turn_counterclockwise(void) {
  51.   ant_dir += (ant_dir == UP)?3:-1;
  52. }
  53.  
  54. inline static void turn_clockwise(void) {
  55.  ant_dir += (ant_dir == LEFT)?-3:1;
  56. }
  57.  
  58. inline static void advance(void) {
  59.   switch (ant_dir) {
  60.   case UP:
  61.     ant_row = (ant_row == ROWS-1)?0:(ant_row + 1);
  62.     break;
  63.   case RIGHT:
  64.     ant_col = (ant_col == COLS-1)?0:(ant_col+1);
  65.     break;
  66.   case DOWN:
  67.     ant_row = (ant_row == 0)?(ROWS-1):(ant_row-1);
  68.     break;
  69.   case LEFT:
  70.     ant_col = (ant_col == 0)?(COLS-1):(ant_col-1);
  71.     break;
  72.   default:
  73.     break;
  74.   }
  75. }
  76.  
  77. inline static void translate(int forward, int right) {
  78.   switch (ant_dir) {
  79.   case UP:
  80.     ant_row += forward;
  81.     ant_col += right;
  82.     break;
  83.   case RIGHT:
  84.     ant_col += forward;
  85.     ant_row -= right;
  86.     break;
  87.   case DOWN:
  88.     ant_row -= forward;
  89.     ant_col -= right;
  90.     break;
  91.   case LEFT:
  92.     ant_col -= forward;
  93.     ant_row += right;
  94.     break;
  95.   default:
  96.     assert(0);
  97.   }
  98.   ant_col = mod(ant_col, COLS);
  99.   ant_row = mod(ant_row, ROWS);
  100. }
  101.  
  102. int main(int argc, char* argv[]) {
  103.   assert(argc == 3);
  104.   ROWS = atoi(argv[1]);
  105.   COLS = atoi(argv[2]);
  106.  
  107.   // initialize grid
  108.   color_t grid[ROWS][COLS];
  109.   for (int r = 0; r < ROWS; r++) {
  110.     for (int c = 0; c < COLS; c++) {
  111.       grid[r][c] = WHITE;
  112.     }
  113.   }
  114.   int black_cells = 0;
  115.   int tot_cells = ROWS * COLS;
  116.  
  117.   ant_row = 0;
  118.   ant_col = 0;
  119.   ant_dir = UP;
  120.  
  121.   // Initialize with invalid values
  122.   color_t qr_color = -1;
  123.   dir_t qr_dir = -1;
  124.   int qr_row = -1;
  125.   int qr_col = -1;
  126.  
  127.   // main loop; runs until quasi-recurrence
  128.   unsigned long turns = 0;
  129.   while (1) {
  130.     color_t color = grid[ant_row][ant_col];
  131.     if (color == WHITE) {
  132.       turn_clockwise();
  133.     } else {
  134.       turn_counterclockwise();
  135.     }
  136.     // flip grid color
  137.     grid[ant_row][ant_col] ^= 1;
  138.     black_cells += (color == WHITE)?1:-1;
  139.     // move ant
  140.     advance();
  141.    
  142.     turns += 1;
  143.     // print
  144.     if (turns % 100000000 == 0) {
  145.       fprintf(stderr, "(%luM) ", turns/1000000);
  146.     }
  147.     // test for quasi-recurrence
  148.     if ((black_cells == 0 || black_cells == tot_cells) &&
  149.         (ant_dir == UP || ant_dir == DOWN || ROWS == COLS)) {
  150.       // Save color of board, as well as ant direction and displacement forward and right
  151.       qr_color = (black_cells == 0)?WHITE:BLACK;
  152.       qr_dir = ant_dir;
  153.       qr_row = ant_row;
  154.       qr_col = ant_col;
  155.       printf("col: %d row: %d color: %s dir: %s\n",
  156.              qr_row, qr_col, color_to_str(qr_color), dir_to_str(qr_dir));
  157.       break;
  158.     }
  159.   }
  160. // Now simulate "megaturns" between one quasi-recurrence and next until true recurrence
  161. // Note: if board is black (odd-numbered megaturns and qr_dir == BLACK), then
  162. // left and right are flipped relative to ant's initial direction.
  163.  
  164.   unsigned long megaturns = 0;
  165.   ant_row = 0;
  166.   ant_col = 0;
  167.   ant_dir = UP;
  168.   bool white_board = true;
  169.   while (1) {
  170.     // Translate ant to next quasirecurrence
  171.     translate(qr_row, white_board?qr_col:-qr_col);
  172.     // Rotate ant
  173.     if (qr_dir == DOWN) {
  174.       turn_clockwise();
  175.       turn_clockwise();
  176.     } else if ((qr_dir == RIGHT && white_board) || (qr_dir == LEFT && !white_board)) {
  177.       turn_clockwise();
  178.     } else if ((qr_dir == LEFT && white_board) || (qr_dir == RIGHT && !white_board)) {
  179.       turn_counterclockwise();
  180.     }
  181.     megaturns++;
  182.     white_board = (qr_color == WHITE) || (megaturns % 2 == 0);
  183.     if (ant_row == 0 && ant_col == 0 && ant_dir == UP && white_board) {
  184.       printf("%lu quasirecurrence(s) x %lu turns each = %lu\n",
  185.                megaturns, turns, turns*megaturns);
  186.       break;
  187.     }
  188.   }
  189.   return 0;
  190. }
RAW Paste Data