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, all of which are white initially, 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 currently sitting in, with the following rules:

1. If the cell is black, it changes to white and the ant turns left;
2. If the cell is white, it changes to black and the ant turns right;
3. The Ant then moves forward to the next cell, and repeat from step 1.

This rather simple ruleset leads to an initially chaotic movement pattern, and after about 10000 steps, a cycle appears where the ant moves steadily away from the starting location in a diagonal corridor about 10 pixels wide. Conceptually the ant can then travel to infinitely far away.

For this task, start the ant near the center of a 100 by 100 field of cells, which is about big enough to contain the initial chaotic part of the movement. Follow the movement rules for the ant, terminate when it moves out of the region, and show the cell colors it leaves behind.

The problem has received 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;

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); printf("\033[%d;%dH\033[31m@\033[m", y + 1, x + 1);

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 textual version. <lang D>import std.stdio, std.algorithm, std.traits;

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;
 auto dir = Direction.up;

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

   immutable d = (4 + dir + (turn == Turn.right ? 1 : -1)) % 4;
   dir = [EnumMembers!Direction][d];
   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:

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

Icon and Unicon

<lang Icon>link graphics,printf

procedure main(A)

  e := ( 0 < integer(\A[1])) | 100   # 100 or whole number from command line
  LangtonsAnt(e)

end

record antrec(x,y,nesw)

procedure LangtonsAnt(e)

  size  := sprintf("size=%d,%d",e,e)
  label := sprintf("Langton's Ant %dx%d [%d]",e,e,0)
  &window := open(label,"g","bg=white",size) | 
              stop("Unable to open window") 

  ant := antrec(e/2,e/2,?4%4)
  board := list(e)
  every !board := list(e,"w")
  
  k := 0
  repeat {
     k +:= 1
     WAttrib("fg=red")
     DrawPoint(ant.x,ant.y)
     
     cell := board[ant.x,ant.y]
     if cell == "w" then {                        # white cell
        WAttrib("fg=black")
        ant.nesw := (ant.nesw + 1) % 4            # . turn right
        }
     else {                                       # black cell
        WAttrib( "fg=white")   
        ant.nesw := (ant.nesw + 3) % 4            # . turn left = 3 x right
        }
     board[ant.x,ant.y] := map(cell,"wb","bw")    # flip colour         
     DrawPoint(ant.x,ant.y)
     
     case ant.nesw of {                           # go
        0: ant.y -:= 1                            # . north
        1: ant.x +:= 1                            # . east
        2: ant.y +:= 1                            # . south
        3: ant.x -:= 1                            # . west
        }
        
     if 0 < ant.x <= e & 0 < ant.y <= e then next
     else break      
     }
  printf("Langton's Ant exited the field after %d rounds.\n",k)
  label := sprintf("label=Langton's Ant %dx%d [%d]",e,e,k)
  WAttrib(label)
  WDone()

end</lang>

Library: Icon Programming Library

printf.icn provides formatting graphics.icn provides graphics support (WDone)

J

<lang j>dirs=: 0 _1,_1 0,0 1,:1 0 langton=:3 :0

 loc=. <.-:$cells=. (2{.y,y)$dir=. 0
 while. *./(0<:loc), loc<$cells do.
   color=. (<loc) { cells
   cells=. (-.color) (<loc)} cells
   dir=. 4 | dir +  _1 ^ color
   loc=. loc + dir { dirs
 end.
 '.#' {~ cells

)</lang>

   langton 100 100
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................##..............................
.....................................................................##.............................
..............................................##..##............###.##.#............................
.............................................#..##..###........####.#..#............................
............................................#....##...#......##.##..#.#.............................
.........................................##.#.....#.....#######.###.##..............................
........................................#..#..#...##.#...#..#####.#..#..............................
.......................................###...#...####..##.###.#......##.............................
....................................##.#.#..##..#...#.##..####.######...............................
...................................#..#...#....#.....##..##...#.#.#####.#...........................
..................................###.##..#..#....#...#####.#.##.#....###...........................
..................................##.....##.###...##.###...##.####..#..#............................
....................................###..###.#...#.#.###.....#..#....##.............................
......................................#.#...#########.#####...####..................................
................................###.###..##.#..#......#...##..#.....................................
.................................#####.#####..##...#####....#.#.#...................................
..............................##.#.#######.###.######.#####.#.###...................................
.............................#....##..##...###..#..#..#..#...#.#....................................
............................###......###..#.##.##....#..#.##.#......................................
............................#.#..#....#....#.#####..#....#.##.......................................
.................................##.###..#.#..##.##....#..#.#.......................................
.............................#.#.....#.#.....#.#.##.#.#..###.##.#...................................
............................#...###..#..#..#.#..####.##...##.####...................................
............................#...##.###.##.#..#...#.....####.#.##....................................
............................#..##...###......#..####.###.##...##....................................
............................#......###.....###..###...##..#....#....................................
............................#.....#.#.#.####....####..##.##.........................................
............................#.....##.###.##...#.##.####.###...#.#...................................
............................#......#.#....#####.#.#.###.......###...................................
............................#....####.#....###.##.###...#.#....#....................................
............................#.....#..##.##.##.####..##.##..####.....................................
............................#.....#.##.##..#....#######.............................................
............................###...##..##..#.###.#.##.#...#..........................................
............................###....##.######.#..#...####....#.......................................
.............................#.##.#.##..##....####.#.##.####.#......................................
.............................#...#######.######..#.##.#.#....#......................................
............................#...#...##.#..#...##.######..#..#.......................................
............................#.##....###..#...#.#######.#..##........................................
.............................##.#.##...#.#.#.##.#..##..###..........................................
..............................######.##..........#####...#..........................................
..................................#...#..#####.#......#.#...........................................
...................................##.....#.#.##...#....#...........................................
................................##.#..##.#.....##.#....###..........................................
................................#.##.#......#.#...#....###..........................................
.................................#...####.##...#...#....#...........................................
.................................###..#...#...###...####............................................
.................................#...##..##.##...#..................................................
....................................##..##..#...###.................................................
.....................................##..#.##.##...#................................................
..........................................##..#...###...............................................
...........................................#.##.##...#..............................................
............................................##..#...###.............................................
.............................................#.##.##...#............................................
..............................................##..#...###...........................................
...............................................#.##.##...#..........................................
................................................##..#...###.........................................
.................................................#.##.##...#........................................
..................................................##..#...###.......................................
...................................................#.##.##...#......................................
....................................................##..#...###.....................................
.....................................................#.##.##...#....................................
......................................................##..#...###...................................
.......................................................#.##.##...#..................................
........................................................##..#...###.................................
.........................................................#.##.##...#................................
..........................................................##..#...###...............................
...........................................................#.##.##...#..............................
............................................................##..#...###.............................
.............................................................#.##.##...#............................
..............................................................##..#...###...........................
...............................................................#.##.##...#..........................
................................................................##..#...###.........................
.................................................................#.##.##...#........................
..................................................................##..#...###.......................
...................................................................#.##.##...#......................
....................................................................##..#.#####.....................
.....................................................................#.#...####.....................
......................................................................##.###.#......................
.......................................................................#.#.##.......................

PicoLisp

This code pipes a PBM into ImageMagick's "display" to show the result: <lang PicoLisp>(de ant (Width Height X Y)

  (let (Field (make (do Height (link (need Width)))) Dir 0)
     (until (or (le0 X) (le0 Y) (> X Width) (> Y Height))
        (let Cell (nth Field X Y)
           (setq Dir (% (+ (if (car Cell) 1 3) Dir) 4))
           (set Cell (not (car Cell))) 
           (case Dir
              (0 (inc 'X))
              (1 (inc 'Y))
              (2 (dec 'X))
              (3 (dec 'Y)) ) ) )
     (prinl "P1")
     (prinl Width " " Height)
     (for Row Field
        (prinl (mapcar '[(X) (if X 1 0)] Row)) ) ) )

(out '(display -) (ant 100 100 50 50)) (bye) </lang>

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>

Python

Translation of: D

<lang python>width = 75 height = 52 nsteps = 12000

class Dir: up, right, down, left = range(4) class Turn: left, right = False, True class Color: white, black = '.', '#' M = [[Color.white] * width for _ in xrange(height)]

x = width // 2 y = height // 2 dir = Dir.up

i = 0 while i < nsteps and 0 <= x < width and 0 <= y < height:

   turn = Turn.left if M[y][x] == Color.black else Turn.right
   M[y][x] = Color.white if M[y][x] == Color.black else Color.black

   dir = (4 + dir + (1 if turn else -1)) % 4
   dir = [Dir.up, Dir.right, Dir.down, Dir.left][dir]
   if   dir == Dir.up:    y -= 1
   elif dir == Dir.right: x -= 1
   elif dir == Dir.down:  y += 1
   elif dir == Dir.left:  x += 1
   else: assert False
   i += 1

print "\n".join("".join(row) for row in M)</lang> The output is the same as the basic D version.

Ruby

<lang ruby>class Ant

 Directions = [:north, :east, :south, :west]

 def initialize(plane, pos_x, pos_y)
   @plane = plane
   @position = Position.new(plane, pos_x, pos_y)
   @direction = :south
 end
 attr_reader :plane, :direction, :position

 def run
   moves = 0
   loop do
     begin
       if $DEBUG and moves % 100 == 0
         system "clear"
         puts "%5d %s" % [moves, position]
         puts plane
       end
       moves += 1
       move
     rescue OutOfBoundsException
       break
     end
   end
   moves
 end

 def move
   plane.at(position).toggle_colour
   position.advance(direction)
   if plane.at(position).white?
     turn(:right)
   else
     turn(:left)
   end
 end

 def turn(left_or_right)
   idx = Directions.index(direction)
   case left_or_right
   when :left  then @direction = Directions[(idx - 1) % Directions.length]
   when :right then @direction = Directions[(idx + 1) % Directions.length]
   end
 end

end

class Plane

 def initialize(x, y)
   @x = x
   @y = y
   @cells = Array.new(y) {Array.new(x) {Cell.new}}
 end
 attr_reader :x, :y

 def at(position)
   @cells[position.y][position.x]
 end

 def to_s
   @cells.inject("") do |output, row|
     column = row.inject("") {|col, cell| col + (cell.white? ? "." : "#")}
     output += column + "\n"
   end
 end

end

class Cell

 def initialize
   @colour = :white
 end
 attr_reader :colour

 def white?
   colour == :white
 end

 def toggle_colour
   @colour = (white? ? :black : :white)
 end

end

class Position

 def initialize(plane, x, y)
   @plane = plane
   @x = x
   @y = y
   check_bounds
 end
 attr_accessor :x, :y

 def advance(direction)
   case direction
   when :north then @y -= 1
   when :east  then @x += 1
   when :south then @y += 1
   when :west  then @x -= 1
   end
   check_bounds
 end

 def check_bounds
   unless (0 <= @x and @x < @plane.x) and (0 <= @y and @y < @plane.y)
     raise OutOfBoundsException, to_s 
   end
 end

 def to_s
   "(%d, %d)" % [x, y]
 end

end

class OutOfBoundsException < StandardError; end

2. the simulation

ant = Ant.new(Plane.new(100, 100), 50, 50) moves = ant.run puts "out of bounds after #{moves} moves: #{ant.position}" puts ant.plane</lang>

output

out of bounds after 11669 moves: (26, -1)
..........................#.#.......................................................................
........................##.#.#......................................................................
.......................#.###.##.....................................................................
......................####.###.#....................................................................
......................#####.#..##...................................................................
.......................#...##.##.#..................................................................
........................###...#..##.................................................................
.........................#...##.##.#................................................................
..........................###...#..##...............................................................
...........................#...##.##.#..............................................................
............................###...#..##.............................................................
.............................#...##.##.#............................................................
..............................###...#..##...........................................................
...............................#...##.##.#..........................................................
................................###...#..##.........................................................
.................................#...##.##.#........................................................
..................................###...#..##.......................................................
...................................#...##.##.#......................................................
....................................###...#..##.....................................................
.....................................#...##.##.#....................................................
......................................###...#..##...................................................
.......................................#...##.##.#..................................................
........................................###...#..##.................................................
.........................................#...##.##.#................................................
..........................................###...#..##...............................................
...........................................#...##.##.#..............................................
............................................###...#..##.............................................
.............................................#...##.##.#............................................
..............................................###...#..##...........................................
...............................................#...##.##.#..........................................
................................................###...#..##.........................................
.................................................#...##.##.#..##....................................
..................................................###...#..##..##...................................
...................................................#...##.##..##...#................................
.............................................####...###...#...#..###................................
............................................#....#...#...##.####...#................................
...........................................###....#...#.#......#.##.#...............................
...........................................###....#.##.....#.##..#.##...............................
............................................#....#...##.#.#.....##..................................
............................................#.#......#.#####..#...#.................................
...........................................#...#####..........##.######.............................
...........................................###..##..#.##.#.#.#...##.#.##............................
.........................................##..#.#######.#...#..###....##.#...........................
........................................#..#..######.##...#..#.##...#...#...........................
.......................................#....#.#.##.#..######.#######...#............................
.......................................#.####.##.#.####....##..##.#.##.#............................
........................................#....####...#..#.######.##....###...........................
...........................................#...#.##.#.###.#..##..##...###...........................
..............................................#######....#..##.##.#.....#...........................
......................................####..##.##..####.##.##.##..#.....#...........................
.....................................#....#.#...###.##.###....#.####....#...........................
....................................###.......###.#.#.#####....#.#......#...........................
....................................#.#...###.####.##.#...##.###.##.....#...........................
..........................................##.##..####....####.#.#.#.....#...........................
.....................................#....#..##...###..###.....###......#...........................
.....................................##...##.###.####..#......###...##..#...........................
.....................................##.#.####.....#...#..#.##.###.##...#...........................
....................................####.##...##.####..#.#..#..#..###...#...........................
....................................#.##.###..#.#.##.#.#.....#.#.....#.#............................
........................................#.#..#....##.##..#.#..###.##................................
........................................##.#....#..#####.#....#....#..#.#...........................
.......................................#.##.#..#....##.##.#..###......###...........................
.....................................#.#...#..#..#..#..###...##..##....#............................
....................................###.#.#####.######.###.#######.#.##.............................
....................................#.#.#....#####...##..#####.#####................................
......................................#..##...#......#..#.##..###.###...............................
...................................####...#####.#########...#.#.....................................
..............................##....#..#.....###.#.#...#.###..###...................................
.............................#..#..####.##...###.##...###.##.....##.................................
............................###....#.##.#.#####...#....#..#..##.###.................................
............................#.#####.#.#...##..##.....#....#...#..#..................................
................................######.####..##.#...#..##..#.#.##...................................
..............................##......#.###.##..####...#...###......................................
...............................#..#.#####..#...#.##...#..#..#.......................................
...............................##.###.#######.....#.....#.##........................................
..............................#.#..##.##......#...##....#...........................................
.............................#..#.####........###..##..#............................................
.............................#.##.###............##..##.............................................
..............................##....................................................................
...............................##...................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................