Langton's ant

Langton's ant is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Langton's ant models an ant sitting on a plane of cells, which initially are all white, facing in one of four directions. Each cell can either be black or white. The ant moves according to the color of the cell it is current sitting in based on the following rules. If the cell is black it turns left, if it is white it turns right. It then moves forward to the next cell and the color of the cell it was in is switched black/white. This rather simple ruleset leads some movement appearing like random (or maybe like some kind of edge detecion being run on random images) and after about 10000 a cyle appears that makes the ant move in a diagonal movements with a corridor about 10 pixels wide, which essentially means that the ant will move out of the screen. The program terminates when the ant moves off screen.

For this task, start the ant near the center of a 100 by 100 field of cells (coordinates 50,50 if you use zero origin indexing).

The problem has recieved some analysis, for more details, please take a look at the Wikipedia article.

C

Requires ANSI terminal. <lang c>#include <stdio.h>

1. include <stdlib.h>
2. include <string.h>
3. include <unistd.h>

int w = 0, h = 0; unsigned char *pix;

void refresh(int x, int y) { int i, j, k; printf("\033[H"); for (i = k = 0; i < h; putchar('\n'), i++) for (j = 0; j < w; j++, k++) putchar(pix[k] ? '#' : ' '); }

void walk() { int dx = 0, dy = 1, i, k; int x = w / 2, y = h / 2;

pix = calloc(1, w * h); printf("\033[H\033[J");

while (1) { i = (y * w + x); if (pix[i]) k = dx, dx = -dy, dy = k; else k = dy, dy = -dx, dx = k;

pix[i] = !pix[i]; printf("\033[%d;%dH%c", y + 1, x + 1, pix[i] ? '#' : ' ');

x += dx, y += dy; printf("\033[%d;%dH\033[31m@\033[m", y + 1, x + 1);

k = 0; if (x < 0) { memmove(pix + 1, pix, w * h - 1); for (i = 0; i < w * h; i += w) pix[i] = 0; x++, k = 1; } else if (x >= w) { memmove(pix, pix + 1, w * h - 1); for (i = w-1; i < w * h; i += w) pix[i] = 0; x--, k = 1; }

if (y >= h) { memmove(pix, pix + w, w * (h - 1)); memset(pix + w * (h - 1), 0, w); y--, k = 1; } else if (y < 0) { memmove(pix + w, pix, w * (h - 1)); memset(pix, 0, w); y++, k = 1; } if (k) refresh(x, y);

fflush(stdout); usleep(10000); } }

int main(int c, char **v) { if (c > 1) w = atoi(v[1]); if (c > 2) h = atoi(v[2]); if (w < 40) w = 40; if (h < 25) h = 25;

walk(); return 0; }</lang>

D

A basic version.

Translation of: Processing

<lang D>import std.stdio, std.algorithm;

enum Direction { up, right, down, left } enum Turn : bool { left = false, right = true } enum Color : char { white = '.', black = '#' }

void main() {

   enum width = 75, height = 52;
   enum nsteps = 12_000;

   auto M = new Color[][](height, width);
   int x = width / 2;
   int y = height / 2;
   Direction dir = Direction.up;

   for (int i = 0; i < nsteps &&
        x >= 0 && y >= 0 && x < width && y < height; i++) {
       Turn turn = M[y][x] == Color.black ? Turn.left : Turn.right;
       M[y][x] = M[y][x] == Color.black ? Color.white : Color.black;

       dir = cast(Direction)((4 + dir + (turn ? +1 : -1)) % 4);
       final switch(dir) {
           case Direction.up:    y--; break;
           case Direction.right: x--; break;
           case Direction.down:  y++; break;
           case Direction.left:  x++; break;
       }
   }

   foreach (row; M)
       writeln(cast(char[])row);

}</lang> Output:

...........................................................................
...........................................................................
...........................................................................
...........................................................................
..........................##..############..##.............................
.........................##..#..........####..#............................
........................#.##............##...###...........................
........................#....#..#.........#..#.#...........................
......................#.......###.........#.#.##..##.......................
......................###..##.##.....#.....#...#..#.###....................
..................##..##.#..#.#...##.####.##..###..#.#.....................
.................###...###.....#.#.###..##.#..##.###.#.....................
................#.#.#.###...#..####..#.#.#####...#.....#...................
................#...#.###.#.######.##.##..####.#...##.###..................
.................##.###.#####...#.##.##.##.#.#.##.#.###.#..................
...............##.#....####..#.#...#...###.##.#...#.#......................
..............##.....#.##.....##..#...##.##.........#..#...................
.............#.##..##.###...#.....##..#..###.##.#.#...###..................
.............#...####.##..#....#..###...##.##...##..###..#.................
..............#.....#..###.##.#..##.####.#.#..#.#...#...###................
............##..#..#.##.###......#..###.#..#....##.#..###..#...............
...........#...##.####..####.#####..##..##.#.##.#.....#...###..............
..........#...#....#.#.#...##......##.#.#.###.#..#.#.#..###..#.............
..........#......#...####.####.......##...#.##..###.##..#...###............
...........#....#....#..####..#.###########..##...#..#.#..###..#...........
...........##..#....##..#..#########..##..####.#......##..#...###..........
..........#.####..##.#..#...###.###.##.##...##.#..##...#.#..###..#.........
..........#...##...###.###....#.#.##.#.##.######.#..#...##..#...###........
...........#...##....#.##..#.#.....#####.#.#####.....#...#.#..###..#.......
...........#..#..#.##..#..#...#.#..##.#####.##.#.....#....##..#...###......
...........##...##########...##.#####..#.####...#....#.....#.#..###..#.....
...............##.####.##...#..####...#..#...##...##.#......##..#...###....
.............#.#..#..#..#.#....#...#.##...##..#.#####........#.#..###..#...
.............##..##..#..##.#.#.##.##....#.#.#.##..##..........##..#...###..
.............#.####..##.#.#.########.#....#..#.................#.#..###..#.
.............#.##..#..#...##.##.......#...#..#..................##..#...###
.............####.##...##..##..#......#..#..#....................#.#..##...
............###.#...#....##..##.......#...##......................##..#..##
............####.###.####....####..##.#............................#.#.#.#.
...........#..#.#.##.#..##....####..##..............................##.####
..........#####.##.###.##....##....##................................#.##.#
..........####..#.##.#................................................####.
..........##.##.##.....................................................##..
................##.........................................................
........#.####..##.#.......................................................
........###..###.#..#......................................................
.........#..#..#.##.#......................................................
..........##......##.......................................................
.................##........................................................
...........................................................................
...........................................................................
...........................................................................

Processing

Processing implementation, this uses two notable features of Processing, first of all, the animation is calculated with the draw() loop, second the drawing on the screen is also used to represent the actual state.

Sample output

<lang processing>/*

* we use the following conventions:
* directions 0: up, 1: right, 2: down: 3: left
*
* pixel white: true, black: false
*
* turn right: true, left: false
*
*/

// number of iteration steps per frame // set this to 1 to see a slow animation of each // step or to 10 or 100 for a faster animation

final int STEP=100;

int x; int y; int direction;

void setup() {

 // 100x100 is large enough to show the
 // corridor after about 10000 cycles
 size(100, 100, P2D);

 background(#ffffff);

 x=width/2;
 y=height/2;

 direction=0;

}

int count=0;

void draw() {

 for(int i=0;i<STEP;i++) {
   count++;
   boolean pix=get(x,y)!=-1;
   setBool(x,y,pix);
 
   turn(pix);
   move();
 
   if(x<0||y<0||x>=width||y>=height) {
     println("finished");
     noLoop();
     break;
   }
 }
 if(count%1000==0) {
   println("iteration "+count);
 }

}

void move() {

 switch(direction) {
   case 0:
     y--;
     break;
   case 1:
     x++;
     break;
   case 2:
     y++;
     break;
   case 3:
     x--;
     break;
 }

}

void turn(boolean rightleft) {

 direction+=rightleft?1:-1;
 if(direction==-1) direction=3;
 if(direction==4) direction=0;

}

void setBool(int x, int y, boolean white) {

 set(x,y,white?#ffffff:#000000);

}</lang>