Langton's ant
You are encouraged to solve this task according to the task description, using any language you may know.
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:
- If the cell is black, it changes to white and the ant turns left;
- If the cell is white, it changes to black and the ant turns right;
- 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.
Ada
<lang Ada>with Ada.Text_IO;
procedure Langtons_Ant is
Size: constant Positive := 100; -- change this to extend the playground
subtype Step is Integer range -1 .. +1;
procedure Right(N, W: in out Step) is
Tmp: Step := W;
begin
W := - N;
N := Tmp;
end Right;
procedure Left(N, W: in out Step) is
begin
for I in 1 .. 3 loop
Right(N, W);
end loop;
end Left;
Color_Character: array(Boolean) of Character :=
(False => ' ', True => '#');
Is_Black: array (1 .. Size, 1 .. Size) of Boolean :=
(others => (others => False)); -- initially, the world is white;
Ant_X, Ant_Y: Natural := Size/2; -- Position of Ant; Ant_North: Step := 1; Ant_West: Step := 0; -- initially, Ant looks northward
Iteration: Positive := 1;
begin
loop -- iterate the loop until an exception is raised
Is_Black(Ant_X, Ant_Y) := not Is_Black(Ant_X, Ant_Y);
if Is_Black(Ant_X, Ant_Y) then
Left(Ant_North, Ant_West);
else
Right(Ant_North, Ant_West);
end if;
Ant_X := Ant_X - Ant_North; -- this may raise an exception
Ant_Y := Ant_Y - Ant_West; -- this may raise an exception
Iteration := Iteration + 1;
end loop;
exception
when Constraint_Error => -- Ant has left its playground ... now output
for X in 1 .. Size loop
for Y in 1 .. Size loop
Ada.Text_IO.Put(Color_Character(Is_Black(X, Y)));
end loop;
Ada.Text_IO.New_Line;
end loop;
Ada.Text_IO.Put_Line("# Iteration:" & Integer'Image(Iteration));
end Langtons_Ant; </lang>
Ouptut (to save space, I have removed the all-blank lines):
## ############ ##
## # #### #
# ## ## ###
# # # # # #
# ### # # ## ##
### ## ## # # # # ###
## ## # # # ## #### ## ### # #
### ### # # ### ## # ## ### #
# # # ### # #### # # ##### # #
# # ### # ###### ## ## #### # ## ###
## ### ##### # ## ## ## # # ## # ### #
## # #### # # # ### ## # # #
## # ## ## # ## ## # #
# ## ## ### # ## # ### ## # # ###
# #### ## # # ### ## ## ## ### #
# # ### ## # ## #### # # # # # ###
## # # ## ### # ### # # ## # ### #
# ## #### #### ##### ## ## # ## # # ###
# # # # # ## ## # # ### # # # # ### #
# # #### #### ## # ## ### ## # ###
# # # #### # ########### ## # # # ### #
## # ## # ######### ## #### # ## # ###
# #### ## # # ### ### ## ## ## # ## # # ### #
# ## ### ### # # ## # ## ###### # # ## # ###
# ## # ## # # ##### # ##### # # # ### #
# # # ## # # # # ## ##### ## # # ## # ###
## ########## ## ##### # #### # # # # ### #
## #### ## # #### # # ## ## # ## # ###
# # # # # # # # ## ## # ##### # # ### #
## ## # ## # # ## ## # # # ## ## ## # ###
# #### ## # # ######## # # # # # ### #
# ## # # ## ## # # # ## # ###
#### ## ## ## # # # # # # ### #
### # # ## ## # ## ## # ###
#### ### #### #### ## # # # ### #
# # # ## # ## #### ## ## # ###
##### ## ### ## ## ## # # ### #
#### # ## # ## # ###
## ## ## # # ### #
## ## # ###
# #### ## # # # ### #
### ### # # ## # ###
# # # ## # # # ### #
## ## ## # ###
## # # ### #
## # ###
# # # # #
## ####
# ## #
####
##
# Iteration: 11670
AutoHotkey
To support all AHK flavors, a pseudo-array is used. <lang AHK>SetBatchLines -1 n := 0, x := 50, y := 50, d := 1 ; starting positions and orientation
While x > 0 and x < 100 and y > 0 and y < 100 ; In this loop the ant moves d := d + !!(a%x%_%y%) - !(a%x%_%y%) ,d := d=5 ? 1 : d=0 ? 4 : d ,a%x%_%y% := !a%x%_%y% ,x := x + (d=3) - (d=1) ,y := y + (d=4) - (d=2)
Loop 99 ; in this loop the ant's movements are compiled into a string { y := A_Index Loop 99 x := A_Index ,o .= a%x%_%y% ? "#" : "."
o .= "`r`n" } clipboard := o ; set the string to the clipboard</lang>
- Output
......................................................................#.#.##....................... .....................................................................##.###.#...................... ....................................................................#.#...####..................... ...................................................................##..#.#####..................... ..................................................................#.##.##...#...................... .................................................................##..#...###....................... ................................................................#.##.##...#........................ ...............................................................##..#...###......................... ..............................................................#.##.##...#.......................... .............................................................##..#...###........................... ............................................................#.##.##...#............................ ...........................................................##..#...###............................. ..........................................................#.##.##...#.............................. .........................................................##..#...###............................... ........................................................#.##.##...#................................ .......................................................##..#...###................................. ......................................................#.##.##...#.................................. .....................................................##..#...###................................... ....................................................#.##.##...#.................................... ...................................................##..#...###..................................... ..................................................#.##.##...#...................................... .................................................##..#...###....................................... ................................................#.##.##...#........................................ ...............................................##..#...###......................................... ..............................................#.##.##...#.......................................... .............................................##..#...###........................................... ............................................#.##.##...#............................................ ...........................................##..#...###............................................. ..........................................#.##.##...#.............................................. .........................................##..#...###............................................... ....................................##..#.##.##...#................................................ ...................................##..##..#...###................................................. ................................#...##..##.##...#.................................................. ................................###..#...#...###...####............................................ ................................#...####.##...#...#....#........................................... ...............................#.##.#......#.#...#....###.......................................... ...............................##.#..##.#.....##.#....###.......................................... ..................................##.....#.#.##...#....#........................................... .................................#...#..#####.#......#.#........................................... .............................######.##..........#####...#.......................................... ............................##.#.##...#.#.#.##.#..##..###.......................................... ...........................#.##....###..#...#.#######.#..##........................................ ...........................#...#...##.#..#...##.######..#..#....................................... ............................#...#######.######..#.##.#.#....#...................................... ............................#.##.#.##..##....####.#.##.####.#...................................... ...........................###....##.######.#..#...####....#....................................... ...........................###...##..##..#.###.#.##.#...#.......................................... ...........................#.....#.##.##..#....#######............................................. ...........................#.....#..##.##.##.####..##.##..####..................................... ...........................#....####.#....###.##.###...#.#....#.................................... ...........................#......#.#....#####.#.#.###.......###................................... ...........................#.....##.###.##...#.##.####.###...#.#................................... ...........................#.....#.#.#.####....####..##.##......................................... ...........................#......###.....###..###...##..#....#.................................... ...........................#..##...###......#..####.###.##...##.................................... ...........................#...##.###.##.#..#...#.....####.#.##.................................... ...........................#...###..#..#..#.#..####.##...##.####................................... ............................#.#.....#.#.....#.#.##.#.#..###.##.#................................... ................................##.###..#.#..##.##....#..#.#....................................... ...........................#.#..#....#....#.#####..#....#.##....................................... ...........................###......###..#.##.##....#..#.##.#...................................... ............................#....##..##...###..#..#..#..#...#.#.................................... .............................##.#.#######.###.######.#####.#.###................................... ................................#####.#####..##...#####....#.#.#................................... ...............................###.###..##.#..#......#...##..#..................................... .....................................#.#...#########.#####...####.................................. ...................................###..###.#...#.#.###.....#..#....##............................. .................................##.....##.###...##.###...##.####..#..#............................ .................................###.##..#..#....#...#####.#.##.#....###........................... ..................................#..#...#....#.....##..##...#.#.#####.#........................... ...................................##.#.#..##..#...#.##..####.######............................... ......................................###...#...####..##.###.#......##............................. .......................................#..#..#...##.#...#..#####.#..#.............................. ........................................##.#.....#.....#######.###.##.............................. ...........................................#....##...#......##.##..#.#............................. ............................................#..##..###........####.#..#............................ .............................................##..##............###.##.#............................ ....................................................................##............................. ...................................................................##.............................. ................................................................................................... ................................................................................................... ................................................................................................... ................................................................................................... ................................................................................................... ................................................................................................... ................................................................................................... ................................................................................................... ................................................................................................... ................................................................................................... ................................................................................................... ................................................................................................... ................................................................................................... ................................................................................................... ................................................................................................... ................................................................................................... ................................................................................................... ................................................................................................... ................................................................................................... ...................................................................................................
BBC BASIC
<lang BBC BASIC>
REM Implementation of Langton's ant for Rosetta Code
fieldsize%=100
REM Being pedantic, this will actually result in a field of 101 square,
REM since arrays start at 0, and my implementation allows them to use it
DIM field&(fieldsize%,fieldsize%) : REM variables with an & suffix are byte variables
x%=fieldsize%/2
y%=fieldsize%/2
d%=0
REPEAT
IF field&(x%,y%)=0 THEN field&(x%,y%)=1:d%-=1 ELSE field&(x%,y%)=0:d%+=1
GCOL 15*field&(x%,y%)
PLOT 69,x%*2,y%*2 :REM for historical reasons there are two "plot points" per pixel
d%=(d%+4) MOD 4 :REM ensure direction is always between 0 and 3
CASE d% OF
WHEN 0:y%+=1
WHEN 1:x%+=1
WHEN 2:y%-=1
WHEN 3:x%-=1
ENDCASE
UNTIL x%>fieldsize% OR x%<0 OR y%>fieldsize% OR y%<0
END
</lang>
C
Requires ANSI terminal. <lang c>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
- 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>
C#
<lang csharp>using System;
namespace LangtonAnt {
public struct Point
{
public int X;
public int Y;
public Point(int x, int y)
{
X = x;
Y = y;
}
}
enum Direction
{
North, East, West, South
}
public class Langton
{
public readonly bool [,] IsBlack;
private Point _origin;
private Point _antPosition = new Point(0, 0);
public bool OutOfBounds { get; set;}
// I don't see any mention of what direction the ant is supposed to start out in
private Direction _antDirection = Direction.East;
private readonly Direction[] _leftTurn = new[] { Direction.West, Direction.North, Direction.South, Direction.East };
private readonly Direction[] _rightTurn = new[] { Direction.East, Direction.South, Direction.North, Direction.West };
private readonly int[] _xInc = new[] {0, 1, -1, 0};
private readonly int[] _yInc = new[] {1, 0, 0, -1};
public Langton(int width, int height, Point origin)
{
_origin = origin;
IsBlack = new bool[width, height];
OutOfBounds = false;
}
public Langton(int width, int height) : this(width, height, new Point(width / 2, height / 2)) {}
private void MoveAnt()
{
_antPosition.X += _xInc[(int)_antDirection];
_antPosition.Y += _yInc[(int)_antDirection];
}
public Point Step()
{
if (OutOfBounds)
{
throw new InvalidOperationException("Trying to step after ant is out of bounds");
}
Point ptCur = new Point(_antPosition.X + _origin.X, _antPosition.Y + _origin.Y);
bool leftTurn = IsBlack[ptCur.X, ptCur.Y];
int iDirection = (int) _antDirection;
_antDirection = leftTurn ? _leftTurn[iDirection] : _rightTurn[iDirection];
IsBlack[ptCur.X, ptCur.Y] = !IsBlack[ptCur.X, ptCur.Y];
MoveAnt();
ptCur = new Point(_antPosition.X + _origin.X, _antPosition.Y + _origin.Y);
OutOfBounds =
ptCur.X < 0 ||
ptCur.X >= IsBlack.GetUpperBound(0) ||
ptCur.Y < 0 ||
ptCur.Y >= IsBlack.GetUpperBound(1);
return _antPosition;
}
}
class Program
{
static void Main()
{
Langton ant = new Langton(100, 100);
while (!ant.OutOfBounds) ant.Step();
for (int iRow = 0; iRow < 100; iRow++)
{
for (int iCol = 0; iCol < 100; iCol++)
{
Console.Write(ant.IsBlack[iCol, iRow] ? "#" : " ");
}
Console.WriteLine();
}
Console.ReadKey();
}
}
} </lang> Output:
<Blank lines eliminated for efficiency>
##
##
# ## ### ## ##
# # #### ### ## #
# # ## ## # ## #
## ### ####### # # ##
# # ##### # # ## # # #
## # ### ## #### # ###
###### #### ## # # ## # # ##
# ##### # # ## ## # # # #
### # ## # ##### # # # ## ###
# # #### ## ### ## ### ## ##
## # # ### # # # ### ###
#### ##### ######### # #
# ## # # # ## ### ###
# # # ##### ## ##### #####
### # ##### ###### ### ####### # ##
# # # # # # ### ## ## #
# ## # # ## ## # ### ###
## # # ##### # # # # #
# # # ## ## # # ### ##
# ## ### # # ## # # # # # #
#### ## ## #### # # # # ### #
## # #### # # # ## ### ## #
## ## ### #### # ### ## #
# # ## ### ### ### #
## ## #### #### # # # #
# # ### #### ## # ## ### ## #
### ### # # ##### # # #
# # # ### ## ### # #### #
#### ## ## #### ## ## ## # #
####### # ## ## # #
# # ## # ### # ## ## ###
# #### # # ###### ## ###
# #### ## # #### ## ## # ## #
# # # ## # ###### ####### #
# # ###### ## # # ## # #
## # ####### # # ### ## #
### ## # ## # # # ## # ##
# ##### ## ######
# # # ##### # #
# # ## # # ##
### # ## # ## # ##
### # # # # ## #
# # # ## #### #
#### ### # # ###
# ## ## ## #
### # ## ##
# ## ## # ##
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
##### # ##
#### ### #
# ### ##
## # #
# #
CoffeeScript
<lang coffeescript> class Ant
constructor: (@world) ->
@location = [0, 0]
@direction = 'E'
move: =>
[x, y] = @location
if @world.is_set x, y
@world.unset x, y
@direction = Directions.left @direction
else
@world.set x, y
@direction = Directions.right @direction
@location = Directions.forward(x, y, @direction)
- Model a theoretically infinite 2D world with a hash, allowing squares
- to be black or white (independent of any ants.)
class BlackWhiteWorld
constructor: ->
@bits = {}
set: (x, y) ->
@bits["#{x},#{y}"] = true
unset: (x, y) ->
delete @bits["#{x},#{y}"]
is_set: (x, y) ->
@bits["#{x},#{y}"]
draw: ->
# Most of this code just involves finding the extent of the world.
# Always include the origin, even if it's not set.
@min_x = @max_x = @min_y = @max_y = 0
for key of @bits
[xx, yy] = (coord for coord in key.split ',')
x = parseInt xx
y = parseInt yy
@min_x = x if x < @min_x
@max_x = x if x > @max_x
@min_y = y if y < @min_y
@max_y = y if y > @max_y
console.log "top left: #{@min_x}, #{@max_y}, bottom right: #{@max_x}, #{@min_y}"
for y in [@max_y..@min_y] by -1
s =
for x in [@min_x..@max_x]
if @bits["#{x},#{y}"]
s += '#'
else
s += '_'
console.log s
- Simple code for directions, independent of ants.
Directions =
left: (dir) -> return 'W' if dir == 'N' return 'S' if dir == 'W' return 'E' if dir == 'S' 'N' right: (dir) -> return 'E' if dir == 'N' return 'S' if dir == 'E' return 'W' if dir == 'S' 'N' forward: (x, y, dir) -> return [x, y+1] if dir == 'N' return [x, y-1] if dir == 'S' return [x+1, y] if dir == 'E' return [x-1, y] if dir == 'W'
world = new BlackWhiteWorld()
ant = new Ant(world)
for i in [1..11500]
ant.move()
console.log "Ant is at #{ant.location}, direction #{ant.direction}" world.draw() </lang>
output
<lang> > coffee langstons_ant.coffee Ant is at -24,46, direction W top left: -25, 47, bottom right: 22, -29 _##__##_________________________________________
- _#####________________________________________
- ____##_#_______________________________________
____#_#_##______________________________________ _####_###_#_____________________________________ _#####_#__##____________________________________ __#___##_##_#___________________________________ ___###___#__##__________________________________ ____#___##_##_#_________________________________ _____###___#__##________________________________ ______#___##_##_#_______________________________ _______###___#__##______________________________ ________#___##_##_#_____________________________ _________###___#__##____________________________ __________#___##_##_#___________________________ ___________###___#__##__________________________ ____________#___##_##_#_________________________ _____________###___#__##________________________ ______________#___##_##_#_______________________ _______________###___#__##______________________ ________________#___##_##_#_____________________ _________________###___#__##____________________ __________________#___##_##_#___________________ ___________________###___#__##__________________ ____________________#___##_##_#_________________ _____________________###___#__##________________ ______________________#___##_##_#_______________ _______________________###___#__##______________ ________________________#___##_##_#__##_________ _________________________###___#__##__##________ __________________________#___##_##__##___#_____ ____________________####___###___#___#__###_____ ___________________#____#___#___##_####___#_____ __________________###____#___#_#______#_##_#____ __________________###____#_##_____#_##__#_##____ ___________________#____#___##_#_#_____##_______ ___________________#_#______#_#####__#___#______ __________________#___#####__________##_######__ __________________###__##__#_##_#_#_#___##_#_##_ ________________##__#_#######_#___#__###____##_# _______________#__#__######_##___#__#_##___#___# ______________#____#_#_##_#__######_#######___#_ ______________#_####_##_#_####____##__##_#_##_#_ _______________#____####___#__#_######_##____### __________________#___#_##_#_###_#__##__##___### _____________________#######____#__##_##_#_____# _____________####__##_##__####_##_##_##__#_____# ____________#____#_#___###_##_###____#_####____# ___________###_______###_#_#_#####____#_#______# ___________#_#___###_####_##_#___##_###_##_____# _________________##_##__####____####_#_#_#_____# ____________#____#__##___###__###_____###______# ____________##___##_###_####__#______###___##__# ____________##_#_####_____#___#__#_##_###_##___# ___________####_##___##_####__#_#__#__#__###___# ___________#_##_###__#_#_##_#_#_____#_#_____#_#_ _______________#_#__#____##_##__#_#__###_##_____ _______________##_#____#__#####_#____#____#__#_# ______________#_##_#__#____##_##_#__###______### ____________#_#___#__#__#__#__###___##__##____#_ ___________###_#_#####_######_###_#######_#_##__ ___________#_#_#____#####___##__#####_#####_____ _____________#__##___#______#__#_##__###_###____ __________####___#####_#########___#_#__________ _____##____#__#_____###_#_#___#_###__###________ ____#__#__####_##___###_##___###_##_____##______ ___###____#_##_#_#####___#____#__#__##_###______ ___#_#####_#_#___##__##_____#____#___#__#_______ _______######_####__##_#___#__##__#_#_##________ _____##______#_###_##__####___#___###___________ ______#__#_#####__#___#_##___#__#__#____________ ______##_###_#######_____#_____#_##_____________ _____#_#__##_##______#___##____#________________ ____#__#_####________###__##__#_________________ ____#_##_###____________##__##__________________ _____##_________________________________________ ______##________________________________________ </lang>
D
A basic textual version. <lang d>import std.stdio, std.algorithm, std.traits, std.string;
enum Direction { up, right, down, left } enum Color : char { white = '.', black = '#' }
void main() {
enum width = 75, height = 52; enum nsteps = 12_000; uint x = width / 2, y = height / 2; auto M = new Color[][](height, width); auto dir = Direction.up;
for (int i = 0; i < nsteps && x < width && y < height; i++) {
immutable turn = M[y][x] == Color.black;
dir = [EnumMembers!Direction][(dir + (turn ? 1 : -1)) & 3];
M[y][x] = (M[y][x] == Color.black) ? Color.white : Color.black;
final switch(dir) {
case Direction.up: y--; break;
case Direction.right: x++; break;
case Direction.down: y++; break;
case Direction.left: x--; break;
}
}
writeln(join(cast(char[][])M, "\n"));
}</lang> Output:
........................................................................... ........................................................................... ........................................................................... ........................................................................... ..........................##..############..##............................. .........................##..#..........####..#............................ ........................#.##............##...###........................... ........................#....#..#.........#..#.#........................... ......................#.......###.........#.#.##..##....................... ......................###..##.##.....#.....#...#..#.###.................... ..................##..##.#..#.#...##.####.##..###..#.#..................... .................###...###.....#.#.###..##.#..##.###.#..................... ................#.#.#.###...#..####..#.#.#####...#.....#................... ................#...#.###.#.######.##.##..####.#...##.###.................. .................##.###.#####...#.##.##.##.#.#.##.#.###.#.................. ...............##.#....####..#.#...#...###.##.#...#.#...................... ..............##.....#.##.....##..#...##.##.........#..#................... .............#.##..##.###...#.....##..#..###.##.#.#...###.................. .............#...####.##..#....#..###...##.##...##..###..#................. ..............#.....#..###.##.#..##.####.#.#..#.#...#...###................ ............##..#..#.##.###......#..###.#..#....##.#..###..#............... ...........#...##.####..####.#####..##..##.#.##.#.....#...###.............. ..........#...#....#.#.#...##......##.#.#.###.#..#.#.#..###..#............. ..........#......#...####.####.......##...#.##..###.##..#...###............ ...........#....#....#..####..#.###########..##...#..#.#..###..#........... ...........##..#....##..#..#########..##..####.#......##..#...###.......... ..........#.####..##.#..#...###.###.##.##...##.#..##...#.#..###..#......... ..........#...##...###.###....#.#.##.#.##.######.#..#...##..#...###........ ...........#...##....#.##..#.#.....#####.#.#####.....#...#.#..###..#....... ...........#..#..#.##..#..#...#.#..##.#####.##.#.....#....##..#...###...... ...........##...##########...##.#####..#.####...#....#.....#.#..###..#..... ...............##.####.##...#..####...#..#...##...##.#......##..#...###.... .............#.#..#..#..#.#....#...#.##...##..#.#####........#.#..###..#... .............##..##..#..##.#.#.##.##....#.#.#.##..##..........##..#...###.. .............#.####..##.#.#.########.#....#..#.................#.#..###..#. .............#.##..#..#...##.##.......#...#..#..................##..#...### .............####.##...##..##..#......#..#..#....................#.#..##... ............###.#...#....##..##.......#...##......................##..#..## ............####.###.####....####..##.#............................#.#.#.#. ...........#..#.#.##.#..##....####..##..............................##.#### ..........#####.##.###.##....##....##................................#.##.# ..........####..#.##.#................................................####. ..........##.##.##.....................................................##.. ................##......................................................... ........#.####..##.#....................................................... ........###..###.#..#...................................................... .........#..#..#.##.#...................................................... ..........##......##....................................................... .................##........................................................ ........................................................................... ........................................................................... ...........................................................................
Fantom
<lang fantom> class World {
Int height Int width Bool[] state
new make (Int height, Int width)
{
this.height = height
this.width = width
state = List(Bool#, height * width)
(height*width).times { state.add (false) }
}
Bool inWorld (Int x, Int y)
{
x >= 0 && x < width && y >= 0 && y < height
}
Void show ()
{
height.times |h|
{
width.times |w|
{
Env.cur.out.writeChar (state[w*width+h] ? '#' : '.')
}
Env.cur.out.writeChar ('\n')
}
}
Void flip (Int x, Int y)
{
state[x*width + y] = !state[x*width + y]
}
Bool stateOf (Int x, Int y)
{
state[x*width + y]
}
}
enum class Direction {
up (0, -1), down (0, 1), left (-1, 0), right (1, 0)
private new make (Int deltaX, Int deltaY)
{
this.deltaX = deltaX
this.deltaY = deltaY
}
Direction rotateLeft ()
{
if (this == up) return left
if (this == down) return right
if (this == left) return down
// if (this == right)
return up
}
Direction rotateRight ()
{
if (this == up) return right
if (this == down) return left
if (this == left) return up
// if (this == right)
return down
}
const Int deltaX const Int deltaY
}
class Ant {
World world Int currX Int currY Direction direction
new make (World world, Int x, Int y)
{
this.world = world
currX = x
currY = y
direction = Direction.up
}
Bool inWorld ()
{
world.inWorld (currX, currY)
}
// the ant movement rules
Void move ()
{
if (world.stateOf (currX, currY))
{
direction = direction.rotateLeft
}
else
{
direction = direction.rotateRight
}
world.flip (currX, currY)
currX += direction.deltaX
currY += direction.deltaY
}
}
class Main {
Void main ()
{
world := World (100, 100)
ant := Ant (world, 50, 50)
numIterations := 0
while (ant.inWorld)
{
ant.move
numIterations += 1
}
world.show
echo ("Finished in $numIterations iterations")
}
} </lang>
Output (snipping the blank lines):
..........................................##..############..##...................................... .........................................#..####..........#..##..................................... ........................................###...##............##.#.................................... ........................................#.#..#.........#..#....#.................................... ....................................##..##.#.#.........###.......#.................................. .................................###.#..#...#.....#.....##.##..###.................................. ..................................#.#..###..##.####.##...#.#..#.##..##.............................. ..................................#.###.##..#.##..###.#.#.....###...###............................. ................................#.....#...#####.#.#..####..#...###.#.#.#............................ ...............................###.##...#.####..##.##.######.#.###.#...#............................ ...............................#.###.#.##.#.#.##.##.##.#...#####.###.##............................. ...................................#.#...#.##.###...#...#.#..####....#.##........................... ................................#..#.........##.##...#..##.....##.#.....##.......................... ...............................###...#.#.##.###..#..##.....#...###.##..##.#......................... ..............................#..###..##...##.##...###..#....#..##.####...#......................... .............................###...#...#.#..#.#.####.##..#.##.###..#.....#.......................... ............................#..###..#.##....#..#.###..#......###.##.#..#..##........................ ...........................###...#.....#.##.#.##..##..#####.####..####.##...#....................... ..........................#..###..#.#.#..#.###.#.#.##......##...#.#.#....#...#...................... .........................###...#..##.###..##.#...##.......####.####...#......#...................... ........................#..###..#.#..#...##..###########.#..####..#....#....#....................... .......................###...#..##......#.####..##..#########..#..##....#..##....................... ......................#..###..#.#...##..#.##...##.##.###.###...#..#.##..####.#...................... .....................###...#..##...#..#.######.##.#.##.#.#....###.###...##...#...................... ....................#..###..#.#...#.....#####.#.#####.....#.#..##.#....##...#....................... ...................###...#..##....#.....#.##.#####.##..#.#...#..#..##.#..#..#....................... ..................#..###..#.#.....#....#...####.#..#####.##...##########...##....................... .................###...#..##......#.##...##...#..#...####..#...##.####.##........................... ................#..###..#.#........#####.#..##...##.#...#....#.#..#..#..#.#......................... ...............###...#..##..........##..##.#.#.#....##.##.#.#.##..#..##..##......................... ..............#..###..#.#.................#..#....#.########.#.#.##..####.#......................... .............###...#..##..................#..#...#.......##.##...#..#..##.#......................... ............#..###..#.#....................#..#..#......#..##..##...##.####......................... ...........###...#..##......................##...#.......##..##....#...#.###........................ ..........#..###..#.#............................#.##..####....####.###.####........................ .........###...#..##..............................##..####....##..#.##.#.#..#....................... ........#..###..#.#................................##....##....##.###.##.#####...................... .......###...#..##................................................#.##.#..####...................... ......#..###..#.#.....................................................##.##.##...................... .....###...#..##......................................................##............................ ....#..###..#.#.....................................................#.##..####.#.................... ...###...#..##.....................................................#..#.###..###.................... ..#..###..#.#......................................................#.##.#..#..#..................... .###...#..##........................................................##......##...................... #..###..#.#..........................................................##............................. .###.#..##.......................................................................................... #.#.#.#.#........................................................................................... .####.##............................................................................................ .#.##.#............................................................................................. ..####.............................................................................................. ...##............................................................................................... Finished in 11669 iterations
Go
<lang go>package main
import (
"fmt" "image" "image/color" "image/draw" "image/png" "os"
)
const (
up = iota rt dn lt
)
func main() {
bounds := image.Rect(0, 0, 100, 100)
im := image.NewGray(bounds)
gBlack := color.Gray{0}
gWhite := color.Gray{255}
draw.Draw(im, bounds, image.NewUniform(gWhite), image.ZP, draw.Src)
pos := image.Point{50, 50}
dir := up
for pos.In(bounds) {
switch im.At(pos.X, pos.Y).(color.Gray).Y {
case gBlack.Y:
im.SetGray(pos.X, pos.Y, gWhite)
dir--
case gWhite.Y:
im.SetGray(pos.X, pos.Y, gBlack)
dir++
}
if dir&1 == 1 {
pos.X += 1 - dir&2
} else {
pos.Y -= 1 - dir&2
}
}
f, err := os.Create("ant.png")
if err != nil {
fmt.Println(err)
return
}
if err = png.Encode(f, im); err != nil {
fmt.Println(err)
}
if err = f.Close(); err != nil {
fmt.Println(err)
}
}</lang>
Haskell
<lang Haskell>data Color = Black | White
deriving (Read, Show, Enum, Eq, Ord)
putCell c = putStr (case c of Black -> "#"
White -> ".")
toggle :: Color -> Color toggle color = toEnum $ 1 - fromEnum color
data Dir = East | North | West | South
deriving (Read, Show, Enum, Eq, Ord)
turnLeft South = East turnLeft dir = succ dir
turnRight East = South turnRight dir = pred dir
data Pos = Pos { x :: Int, y :: Int }
deriving (Read)
instance Show Pos where
show p@(Pos x y) = "(" ++ (show x) ++ "," ++ (show y) ++ ")"
-- Return the new position after moving one unit in the given direction moveOne pos@(Pos x y) dir =
case dir of East -> Pos (x+1) y South -> Pos x (y+1) West -> Pos (x-1) y North -> Pos x (y-1)
-- Grid is just a list of lists type Grid = Color
colorAt g p@(Pos x y) = (g !! y) !! x
replaceNth n newVal (x:xs)
| n == 0 = newVal:xs
| otherwise = x:replaceNth (n-1) newVal xs
toggleCell g p@(Pos x y) =
let newVal = toggle $ colorAt g p in replaceNth y (replaceNth x newVal (g !! y)) g
printRow r = do { mapM_ putCell r ; putStrLn "" }
printGrid g = mapM_ printRow g
data State = State { move :: Int, pos :: Pos, dir :: Dir, grid :: Grid }
printState s = do {
putStrLn $ show s; printGrid $ grid s
}
instance Show State where
show s@(State m p@(Pos x y) d g) =
"Move: " ++ (show m) ++ " Pos: " ++ (show p) ++ " Dir: " ++ (show d)
nextState s@(State m p@(Pos x y) d g) =
let color = colorAt g p
new_d = case color of White -> (turnRight d)
Black -> (turnLeft d)
new_m = m + 1
new_p = moveOne p new_d
new_g = toggleCell g p
in State new_m new_p new_d new_g
inRange size s@(State m p@(Pos x y) d g) =
x >= 0 && x < size && y >= 0 && y < size
initialState size = (State 0 (Pos (size`div`2) (size`div`2)) East [ [ White | x <- [1..size] ] | y <- [1..size] ])
--- main size = 100 allStates = initialState size : [nextState s | s <- allStates]
main = printState $ last $ takeWhile (inRange size) allStates</lang>
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>
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
# #
## # #
# ### ##
#### ### #
##### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## #
### # ##
# ## ## # ##
### # ## ##
# ## ## ## #
#### ### # # ###
# # # ## #### #
### # # # # ## #
### # ## # ## # ##
# # ## # # ##
# # # ##### # #
# ##### ## ######
### ## # ## # # # ## # ##
## # ####### # # ### ## #
# # ###### ## # # ## # #
# # # ## # ###### ####### #
# #### ## # #### ## ## # ## #
# #### # # ###### ## ###
# # ## # ### # ## ## ###
####### # ## ## # #
#### ## ## #### ## ## ## # #
# # # ### ## ### # #### #
### ### # # ##### # # #
# # ### #### ## # ## ### ## #
## ## #### #### # # # #
# # ## ### ### ### #
## ## ### #### # ### ## #
## # #### # # # ## ### ## #
#### ## ## #### # # # # ### #
# ## ### # # ## # # # # # #
# # # ## ## # # ### ##
## # # ##### # # # # #
# ## # # ## ## # ### ###
# # # # # # ### ## ## #
### # ##### ###### ### ####### # ##
# # # ##### ## ##### #####
# ## # # # ## ### ###
#### ##### ######### # #
## # # ### # # # ### ###
# # #### ## ### ## ### ## ##
### # ## # ##### # # # ## ###
# ##### # # ## ## # # # #
###### #### ## # # ## # # ##
## # ### ## #### # ###
# # ##### # # ## # # #
## ### ####### # # ##
# # ## ## # ## #
# # #### ### ## #
# ## ### ## ##
##
##
Java
This implementation allows for sizes other than 100x100, marks the starting position with a green box (sometimes hard to see at smaller zoom levels and the box is smaller than the "pixels" so it doesn't cover up the color of the "pixel" it's in), and includes a "zoom factor" (ZOOM) in case the individual "pixels" are hard to see on your monitor.
<lang java>import java.awt.Color;
import java.awt.Graphics;
import javax.swing.JFrame; import javax.swing.JPanel;
public class Langton extends JFrame{ private JPanel planePanel; private static final int ZOOM = 4;
public Langton(final boolean[][] plane){ planePanel = new JPanel(){ @Override public void paint(Graphics g) { for(int y = 0; y < plane.length;y++){ for(int x = 0; x < plane[0].length;x++){ g.setColor(plane[y][x] ? Color.BLACK : Color.WHITE); g.fillRect(x * ZOOM, y * ZOOM, ZOOM, ZOOM); } } //mark the starting point g.setColor(Color.GREEN); g.fillRect(plane[0].length / 2 * ZOOM, plane.length / 2 * ZOOM, ZOOM/2, ZOOM/2); } }; planePanel.setSize(plane[0].length - 1, plane.length - 1); add(planePanel); setSize(ZOOM * plane[0].length, ZOOM * plane.length + 30); setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); setVisible(true); }
public static void main(String[] args){ new Langton(runAnt(100, 100)); }
private static boolean[][] runAnt(int height, int width){ boolean[][] plane = new boolean[height][width]; int antX = width/2, antY = height/2;//start in the middle-ish int xChange = 0, yChange = -1; //start moving up while(antX < width && antY < height && antX >= 0 && antY >= 0){ plane[antY][antX] = !plane[antY][antX]; if(plane[antY][antX]){ //turn left if(xChange == 0){ //if moving up or down xChange = yChange; yChange = 0; }else{ //if moving left or right yChange = -xChange; xChange = 0; } }else{ //turn right if(xChange == 0){ //if moving up or down xChange = -yChange; yChange = 0; }else{ //if moving left or right yChange = xChange; xChange = 0; } } antX += xChange; antY += yChange; } return plane; } }</lang> Output (click for a larger view):
OCaml
<lang ocaml>open Graphics
type dir = North | East | South | West
let turn_left = function
| North -> West | East -> North | South -> East | West -> South
let turn_right = function
| North -> East | East -> South | South -> West | West -> North
let move (x, y) = function
| North -> x, y + 1 | East -> x + 1, y | South -> x, y - 1 | West -> x - 1, y
let () =
open_graph ""; let rec loop (x, y as pos) dir = let color = point_color x y in set_color (if color = white then black else white); plot x y; let dir = (if color = white then turn_right else turn_left) dir in if not(key_pressed()) then loop (move pos dir) dir in loop (size_x()/2, size_y()/2) North</lang>
Run with:
$ ocaml graphics.cma langton.ml
PARI/GP
<lang parigp>langton()={
my(M=matrix(100,100),x=50,y=50,d=0); while(x && y && x<=100 && y<=100, d=(d+if(M[x,y],1,-1))%4; M[x,y]=!M[x,y]; if(d%2,x+=d-2,y+=d-1); ); M
}; show(M)={
my(d=sum(i=1,#M[,1],sum(j=1,#M,M[i,j])),u=vector(d),v=u,t); for(i=1,#M[,1],for(j=1,#M,if(M[i,j],v[t++]=i;u[t]=j))); plothraw(u,v)
}; show(langton())</lang>
Perl
<lang perl>#!/usr/bin/perl use strict;
- Perl 5 implementation of Langton's Ant
- Using screen coordinates - 0,0 in upper-left, +X right, +Y down -
- these directions (right, up, left, down) are counterclockwise
- so advance through the array to turn left, retreat to turn right
my @dirs = ( [1,0], [0,-1], [-1,0], [0,1] ); my $size = 100;
- we treat any false as white and true as black, so undef is fine for initial all-white grid
my @plane; for (0..$size-1) { $plane[$_] = [] };
- start out in approximate middle
my ($x, $y) = ($size/2, $size/2);
- pointing in a random direction
my $dir = int rand @dirs;
my $move; for ($move = 0; $x >= 0 && $x < $size && $y >= 0 && $y < $size; $move++) {
# toggle cell's value (white->black or black->white)
if ($plane[$x][$y] = 1 - $plane[$x][$y]) {
# if it's now true (black), then it was white, so turn right
$dir = ($dir - 1) % @dirs;
} else {
# otherwise it was black, so turn left
$dir = ($dir + 1) % @dirs;
}
$x += $dirs[$dir][0];
$y += $dirs[$dir][1];
}
print "Out of bounds after $move moves at ($x, $y)\n"; for (my $y=0; $y<$size; ++$y) {
for (my $x=0; $x<$size; ++$x) {
print $plane[$x][$y] ? '#' : '.';
}
print "\n";
}</lang>
Perl 6
In this version we use 4-bits-per-char graphics to shrink the output to a quarter the area of ASCII graphics. <lang perl6>constant @vecs = [1,0,1], [0,-1,1], [-1,0,1], [0,1,1]; constant @blocky = ' ▘▝▀▖▌▞▛▗▚▐▜▄▙▟█'.comb; constant $size = 100; enum Square <White Black>; my @plane = [White xx $size] xx $size; my ($x, $y) = $size/2, $size/2; my $dir = @vecs.keys.pick; my $moves = 0; loop {
given @plane[$x][$y] {
when :!defined { last }
when White { $dir--; $_ = Black; }
when Black { $dir++; $_ = White; }
}
($x,$y,$moves) »+=« @vecs[$dir %= @vecs];
} say "Out of bounds after $moves moves at ($x, $y)"; for 0,2,4 ... $size - 2 -> $y {
say join , gather for 0,2,4 ... $size - 2 -> $x {
take @blocky[ 1 * @plane[$x][$y]
+ 2 * @plane[$x][$y+1]
+ 4 * @plane[$x+1][$y]
+ 8 * @plane[$x+1][$y+1] ];
}
}</lang>
- Output:
Out of bounds after 11669 moves at (-1, 26)
▄▚▚
▟▟▜▟▚
▜▀▚▌▟▚
▜▘▗▌▟▚
▜▘▗▌▟▚
▜▘▗▌▟▚
▜▘▗▌▟▚
▜▘▗▌▟▚
▜▘▗▌▟▚
▜▘▗▌▟▚
▜▘▗▌▟▚
▜▘▗▌▟▚
▜▘▗▌▟▚
▜▘▗▌▟▚
▜▘▗▌▟▚
▜▘▗▌▟▚ ▄
▜▘▗▌▟▘▟▘▗
▞▀▚ ▜▘▗▌▄▙▝▜
▐█ ▌▄▘▘▗▗▞▐▚▌
▌▖▝ ▐▚▙▙ ▖▀▖
▐▄▝█▀▖▄▗▗▗▀▐▛▛▙
▞▚▝▟██▜▞ ▞▗▜▌ ▞▘▌
▐▗▄▌▙▜▐▄▛▀▜▞▜▛▛▄▐
▘▗▝▜▚▖▌▟▞▛▜▌▜▖ █▌
▄▄ ▄▜▛▜▙▖▟▗▛▟▘▌ ▌
▟▖ ▘▘▄▛▌▛▟█▖ ▚▜▀ ▌
▘▘ █▚▛▜▟▌▘▗█▞▛▞▌ ▌
▐▖ ▙▐▙▗█▌▐▀ ▟▛ ▄ ▌
▟▙▚▛▀▄▗▟▖▐▗▘▛▐▀▟▌ ▌
▘▀▞▛▗▘▘█▐▞▗▗▝▟▖▄▝▝
▗▜▞▖▗▘▝█▜▞▖▗▙ ▝ ▙▌
▟▞▖▟▄▌▟▄▙▐█▗▟▙▟▚▗▞
▘▌▚▖▝▛▀ ▐▘▞█▀▟▛█▖
▄ ▝▛▚ ▀▜▙▜▜▀▜▚▄▘▙▖
▟▖▘▐▜▌▛▄▟▛▝▌ ▜▘▛▗▖▟▌
▘▀█▙▙▚▄▛▗▛▖ ▞▗▖▚▗▚▞
▜ ▖▄▙▛▚▀▗▜▛ ▞▗▝▛
▞▌▜▌█▀▀▘▖ ▙ ▌▀
▐▗▌█▛ ▀▚▞▚▞
▜▖
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.
<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>
PureBasic
<lang purebasic>#White = $FFFFFF
- Black = 0
- planeHeight = 100
- planeWidth = 100
- canvasID = 0
- windowID = 0
OpenWindow(#windowID, 0, 0, 150, 150, "Langton's ant", #PB_Window_SystemMenu | #PB_Window_ScreenCentered) CanvasGadget(#canvasID, 25, 25, #planeWidth, #planeHeight) StartDrawing(CanvasOutput(#canvasID))
Box(0, 0, #planeWidth, #planeHeight, #White)
StopDrawing()
Define event, quit, ant.POINT, antDirection, antSteps
ant\x = #planeHeight / 2 ant\y = #planeWidth / 2 Repeat
Repeat
event = WindowEvent()
If event = #PB_Event_CloseWindow
quit = 1
event = 0
EndIf
Until event = 0
StartDrawing(CanvasOutput(#canvasID))
Select Point(ant\x, ant\y)
Case #Black
Plot(ant\x, ant\y, #White)
antDirection = (antDirection + 1) % 4 ;turn left
Case #White
Plot(ant\x, ant\y, #Black)
antDirection = (antDirection - 1 + 4) % 4 ;turn right
EndSelect
StopDrawing()
Select antDirection
Case 0 ;up
ant\y - 1
Case 1 ;left
ant\x - 1
Case 2 ;down
ant\y + 1
Case 3 ;right
ant\x + 1
EndSelect
antSteps + 1
If ant\x < 0 Or ant\x >= #planeWidth Or ant\y < 0 Or ant\y >= #planeHeight
MessageRequester("Langton's ant status", "Out of bounds after " + Str(antSteps) + " steps.")
quit = 1
EndIf
Delay(10) ;control animation speed and avoid hogging CPU
Until quit = 1</lang> Sample output:
Out of bounds after 11669 steps.
Python
<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.
REXX
<lang rexx>
xxx
</lang>
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.collect {|row|
row.collect {|cell| cell.white? ? "." : "#"}.join + "\n"
}.join
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
- 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) ..........................#.#....................................................................... ........................##.#.#...................................................................... .......................#.###.##..................................................................... ......................####.###.#.................................................................... ......................#####.#..##................................................................... .......................#...##.##.#.................................................................. ........................###...#..##................................................................. .........................#...##.##.#................................................................ ..........................###...#..##............................................................... ...........................#...##.##.#.............................................................. ............................###...#..##............................................................. .............................#...##.##.#............................................................ ..............................###...#..##........................................................... ...............................#...##.##.#.......................................................... ................................###...#..##......................................................... .................................#...##.##.#........................................................ ..................................###...#..##....................................................... ...................................#...##.##.#...................................................... ....................................###...#..##..................................................... .....................................#...##.##.#.................................................... ......................................###...#..##................................................... .......................................#...##.##.#.................................................. ........................................###...#..##................................................. .........................................#...##.##.#................................................ ..........................................###...#..##............................................... ...........................................#...##.##.#.............................................. ............................................###...#..##............................................. .............................................#...##.##.#............................................ ..............................................###...#..##........................................... ...............................................#...##.##.#.......................................... ................................................###...#..##......................................... .................................................#...##.##.#..##.................................... ..................................................###...#..##..##................................... ...................................................#...##.##..##...#................................ .............................................####...###...#...#..###................................ ............................................#....#...#...##.####...#................................ ...........................................###....#...#.#......#.##.#............................... ...........................................###....#.##.....#.##..#.##............................... ............................................#....#...##.#.#.....##.................................. ............................................#.#......#.#####..#...#................................. ...........................................#...#####..........##.######............................. ...........................................###..##..#.##.#.#.#...##.#.##............................ .........................................##..#.#######.#...#..###....##.#........................... ........................................#..#..######.##...#..#.##...#...#........................... .......................................#....#.#.##.#..######.#######...#............................ .......................................#.####.##.#.####....##..##.#.##.#............................ ........................................#....####...#..#.######.##....###........................... ...........................................#...#.##.#.###.#..##..##...###........................... ..............................................#######....#..##.##.#.....#........................... ......................................####..##.##..####.##.##.##..#.....#........................... .....................................#....#.#...###.##.###....#.####....#........................... ....................................###.......###.#.#.#####....#.#......#........................... ....................................#.#...###.####.##.#...##.###.##.....#........................... ..........................................##.##..####....####.#.#.#.....#........................... .....................................#....#..##...###..###.....###......#........................... .....................................##...##.###.####..#......###...##..#........................... .....................................##.#.####.....#...#..#.##.###.##...#........................... ....................................####.##...##.####..#.#..#..#..###...#........................... ....................................#.##.###..#.#.##.#.#.....#.#.....#.#............................ ........................................#.#..#....##.##..#.#..###.##................................ ........................................##.#....#..#####.#....#....#..#.#........................... .......................................#.##.#..#....##.##.#..###......###........................... .....................................#.#...#..#..#..#..###...##..##....#............................ ....................................###.#.#####.######.###.#######.#.##............................. ....................................#.#.#....#####...##..#####.#####................................ ......................................#..##...#......#..#.##..###.###............................... ...................................####...#####.#########...#.#..................................... ..............................##....#..#.....###.#.#...#.###..###................................... .............................#..#..####.##...###.##...###.##.....##................................. ............................###....#.##.#.#####...#....#..#..##.###................................. ............................#.#####.#.#...##..##.....#....#...#..#.................................. ................................######.####..##.#...#..##..#.#.##................................... ..............................##......#.###.##..####...#...###...................................... ...............................#..#.#####..#...#.##...#..#..#....................................... ...............................##.###.#######.....#.....#.##........................................ ..............................#.#..##.##......#...##....#........................................... .............................#..#.####........###..##..#............................................ .............................#.##.###............##..##............................................. ..............................##.................................................................... ...............................##................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... ....................................................................................................
Run BASIC
<lang Runbasic> 'move up=1 right=2 down=3 left=4 ' --------------------------------- dim plane(100,100) x = 50: y = 50 mx = 100
while (x>0) and (x<100) and (y>0) and (y<100) if plane(x,y) then
nxt = nxt - 1 if nxt < 1 then nxt = 4 else nxt = nxt + 1 if nxt > 4 then nxt = 1
end if
x = x + (nxt = 2) - (nxt = 4) y = y + (nxt = 3) - (nxt = 1) plane(x,y) =(plane(x,y) <> 1) mx = min(x,mx) wend
for x = mx to 100
for y = 1 to 100 print chr$((plane(x,y)*3) + 32); next y print x
next x </lang>
output
## 21
## 22
## ## ### ## # 23
# ## ### #### # # 24
# ## # ## ## # # 25
## # # ####### ### ## 26
# # # ## # # ##### # # 27
### # #### ## ### # ## 28
## # # ## # # ## #### ###### 29
# # # # ## ## # # ##### # 30
### ## # # # ##### # ## # ### 31
## ## ### ## ### ## #### # # 32
### ### # # # ### # # ## 33
# # ######### ##### #### 34
### ### ## # # # ## # 35
##### ##### ## ##### # # # 36
## # ####### ### ###### ##### # ### 37
# ## ## ### # # # # # # 38
### ### # ## ## # # ## # 39
# # # # # ##### # # ## 40
## ### # # ## ## # # # 41
# # # # # # ## # # ### ## # 42
# ### # # # # #### ## ## #### 43
# ## ### ## # # # #### # ## 44
# ## ### # #### ### ## ## 45
# ### ### ### ## # # 46
# # # # #### #### ## ## 47
# ## ### ## # ## #### ### # # 48
# # # ##### # # ### ### 49
# #### # ### ## ### # # # 50
# # ## ## ## #### ## ## #### 51
# # ## ## # ####### 52
### ## ## # ### # ## # # 53
### ## ###### # # #### # 54
# ## # ## ## #### # ## #### # 55
# ####### ###### # ## # # # 56
# # ## # # ## ###### # # 57
# ## ### # # ####### # ## 58
## # ## # # # ## # ## ### 59
###### ## ##### # 60
# # ##### # # # 61
## # # ## # # 62
## # ## # ## # ### 63
# ## # # # # ### 64
# #### ## # # # 65
### # # ### #### 66
# ## ## ## # 67
## ## # ### 68
## # ## ## # 69
## # ### 70
# ## ## # 71
## # ### 72
# ## ## # 73
## # ### 74
# ## ## # 75
## # ### 76
# ## ## # 77
## # ### 78
# ## ## # 79
## # ### 80
# ## ## # 81
## # ### 82
# ## ## # 83
## # ### 84
# ## ## # 85
## # ### 86
# ## ## # 87
## # ### 88
# ## ## # 89
## # ### 90
# ## ## # 91
## # ### 92
# ## ## # 93
## # ### 94
# ## ## # 95
## # ##### 96
# # #### 97
## ### # 98
# # ## 99
# 100
Tcl
<lang tcl>package require Tk
proc step {workarea} {
global x y dir
if {[lindex [$workarea get $x $y] 0]} {
$workarea put black -to $x $y if {[incr dir] > 3} {set dir 0}
} else {
$workarea put white -to $x $y if {[incr dir -1] < 0} {set dir 3}
}
switch $dir {
0 {incr x} 1 {incr y} 2 {incr x -1} 3 {incr y -1}
}
expr {$x < 0 || $x >= [image width $workarea] || $y < 0 || $y >= [image height $workarea]}
}
image create photo antgrid -width 100 -height 100 pack [label .l -image antgrid] antgrid put white -to 0 0 99 99 set x [set y 50] set dir 0
while 1 {
update
if {[step antgrid]} break
}
- Produce output in file
antgrid write ant.gif -format gif</lang>
TI-83 BASIC
The initial Pxl-On(0,0) calibrates the screen, otherwise it doesn't work, and the variable N counts the generation number. <lang TI-83b>PROGRAM:LANT
- ClrDraw
- 0→N
- Pxl-On(0,0)
- 47→X
- 31→Y
- 90→Θ
- Repeat getKey
- If pxl-Test(Y,X)
- Then
- Θ+90→Θ
- Else
- Θ-90→Θ
- End
- Pxl-Change(Y,X)
- X+cos(Θ°)→X
- Y+sin(Θ°)→Y
- N+1→N
- End
</lang>