Langton's ant: Difference between revisions
(Added PicoLisp implementation) |
(add Ruby) |
||
Line 371:
print "\n".join("".join(row) for row in M)</lang>
The output is the same as the basic D version.
=={{header|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
#
# 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
<pre style="height: 40ex; overflow: scroll">out of bounds after 11669 moves: (26, -1)
..........................#.#.......................................................................
........................##.#.#......................................................................
.......................#.###.##.....................................................................
......................####.###.#....................................................................
......................#####.#..##...................................................................
.......................#...##.##.#..................................................................
........................###...#..##.................................................................
.........................#...##.##.#................................................................
..........................###...#..##...............................................................
...........................#...##.##.#..............................................................
............................###...#..##.............................................................
.............................#...##.##.#............................................................
..............................###...#..##...........................................................
...............................#...##.##.#..........................................................
................................###...#..##.........................................................
.................................#...##.##.#........................................................
..................................###...#..##.......................................................
...................................#...##.##.#......................................................
....................................###...#..##.....................................................
.....................................#...##.##.#....................................................
......................................###...#..##...................................................
.......................................#...##.##.#..................................................
........................................###...#..##.................................................
.........................................#...##.##.#................................................
..........................................###...#..##...............................................
...........................................#...##.##.#..............................................
............................................###...#..##.............................................
.............................................#...##.##.#............................................
..............................................###...#..##...........................................
...............................................#...##.##.#..........................................
................................................###...#..##.........................................
.................................................#...##.##.#..##....................................
..................................................###...#..##..##...................................
...................................................#...##.##..##...#................................
.............................................####...###...#...#..###................................
............................................#....#...#...##.####...#................................
...........................................###....#...#.#......#.##.#...............................
...........................................###....#.##.....#.##..#.##...............................
............................................#....#...##.#.#.....##..................................
............................................#.#......#.#####..#...#.................................
...........................................#...#####..........##.######.............................
...........................................###..##..#.##.#.#.#...##.#.##............................
.........................................##..#.#######.#...#..###....##.#...........................
........................................#..#..######.##...#..#.##...#...#...........................
.......................................#....#.#.##.#..######.#######...#............................
.......................................#.####.##.#.####....##..##.#.##.#............................
........................................#....####...#..#.######.##....###...........................
...........................................#...#.##.#.###.#..##..##...###...........................
..............................................#######....#..##.##.#.....#...........................
......................................####..##.##..####.##.##.##..#.....#...........................
.....................................#....#.#...###.##.###....#.####....#...........................
....................................###.......###.#.#.#####....#.#......#...........................
....................................#.#...###.####.##.#...##.###.##.....#...........................
..........................................##.##..####....####.#.#.#.....#...........................
.....................................#....#..##...###..###.....###......#...........................
.....................................##...##.###.####..#......###...##..#...........................
.....................................##.#.####.....#...#..#.##.###.##...#...........................
....................................####.##...##.####..#.#..#..#..###...#...........................
....................................#.##.###..#.#.##.#.#.....#.#.....#.#............................
........................................#.#..#....##.##..#.#..###.##................................
........................................##.#....#..#####.#....#....#..#.#...........................
.......................................#.##.#..#....##.##.#..###......###...........................
.....................................#.#...#..#..#..#..###...##..##....#............................
....................................###.#.#####.######.###.#######.#.##.............................
....................................#.#.#....#####...##..#####.#####................................
......................................#..##...#......#..#.##..###.###...............................
...................................####...#####.#########...#.#.....................................
..............................##....#..#.....###.#.#...#.###..###...................................
.............................#..#..####.##...###.##...###.##.....##.................................
............................###....#.##.#.#####...#....#..#..##.###.................................
............................#.#####.#.#...##..##.....#....#...#..#..................................
................................######.####..##.#...#..##..#.#.##...................................
..............................##......#.###.##..####...#...###......................................
...............................#..#.#####..#...#.##...#..#..#.......................................
...............................##.###.#######.....#.....#.##........................................
..............................#.#..##.##......#...##....#...........................................
.............................#..#.####........###..##..#............................................
.............................#.##.###............##..##.............................................
..............................##....................................................................
...............................##...................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
....................................................................................................</pre>
|
Revision as of 19:37, 14 November 2011
Langton's ant models an ant sitting on a plane of cells, which initially are all white, facing in one of four directions. Each cell can either be black or white. The ant moves according to the color of the cell it is current sitting in based on the following rules. If the cell is black it turns left, if it is white it turns right. It then moves forward to the next cell and the color of the cell it was in is switched black/white. This rather simple ruleset leads some movement appearing like random (or maybe like some kind of edge detecion being run on random images) and after about 10000 a cyle appears that makes the ant move in a diagonal movements with a corridor about 10 pixels wide, which essentially means that the ant will move out of the screen. The program terminates when the ant moves off screen.
For this task, start the ant near the center of a 100 by 100 field of cells (coordinates 50,50 if you use zero origin indexing).
The problem has recieved some analysis, for more details, please take a look at the Wikipedia article.
C
Requires ANSI terminal. <lang c>#include <stdio.h>
- 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; printf("\033[%d;%dH\033[31m@\033[m", y + 1, x + 1);
k = 0; if (x < 0) { memmove(pix + 1, pix, w * h - 1); for (i = 0; i < w * h; i += w) pix[i] = 0; x++, k = 1; } else if (x >= w) { memmove(pix, pix + 1, w * h - 1); for (i = w-1; i < w * h; i += w) pix[i] = 0; x--, k = 1; }
if (y >= h) { memmove(pix, pix + w, w * (h - 1)); memset(pix + w * (h - 1), 0, w); y--, k = 1; } else if (y < 0) { memmove(pix + w, pix, w * (h - 1)); memset(pix, 0, w); y++, k = 1; } if (k) refresh(x, y);
fflush(stdout); usleep(10000); } }
int main(int c, char **v) { if (c > 1) w = atoi(v[1]); if (c > 2) h = atoi(v[2]); if (w < 40) w = 40; if (h < 25) h = 25;
walk(); return 0; }</lang>
D
A basic 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>
printf.icn provides formatting graphics.icn provides graphics support (WDone)
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>
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.
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
- 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) ..........................#.#....................................................................... ........................##.#.#...................................................................... .......................#.###.##..................................................................... ......................####.###.#.................................................................... ......................#####.#..##................................................................... .......................#...##.##.#.................................................................. ........................###...#..##................................................................. .........................#...##.##.#................................................................ ..........................###...#..##............................................................... ...........................#...##.##.#.............................................................. ............................###...#..##............................................................. .............................#...##.##.#............................................................ ..............................###...#..##........................................................... ...............................#...##.##.#.......................................................... ................................###...#..##......................................................... .................................#...##.##.#........................................................ ..................................###...#..##....................................................... ...................................#...##.##.#...................................................... ....................................###...#..##..................................................... .....................................#...##.##.#.................................................... ......................................###...#..##................................................... .......................................#...##.##.#.................................................. ........................................###...#..##................................................. .........................................#...##.##.#................................................ ..........................................###...#..##............................................... ...........................................#...##.##.#.............................................. ............................................###...#..##............................................. .............................................#...##.##.#............................................ ..............................................###...#..##........................................... ...............................................#...##.##.#.......................................... ................................................###...#..##......................................... .................................................#...##.##.#..##.................................... ..................................................###...#..##..##................................... ...................................................#...##.##..##...#................................ .............................................####...###...#...#..###................................ ............................................#....#...#...##.####...#................................ ...........................................###....#...#.#......#.##.#............................... ...........................................###....#.##.....#.##..#.##............................... ............................................#....#...##.#.#.....##.................................. ............................................#.#......#.#####..#...#................................. ...........................................#...#####..........##.######............................. ...........................................###..##..#.##.#.#.#...##.#.##............................ .........................................##..#.#######.#...#..###....##.#........................... ........................................#..#..######.##...#..#.##...#...#........................... .......................................#....#.#.##.#..######.#######...#............................ .......................................#.####.##.#.####....##..##.#.##.#............................ ........................................#....####...#..#.######.##....###........................... ...........................................#...#.##.#.###.#..##..##...###........................... ..............................................#######....#..##.##.#.....#........................... ......................................####..##.##..####.##.##.##..#.....#........................... .....................................#....#.#...###.##.###....#.####....#........................... ....................................###.......###.#.#.#####....#.#......#........................... ....................................#.#...###.####.##.#...##.###.##.....#........................... ..........................................##.##..####....####.#.#.#.....#........................... .....................................#....#..##...###..###.....###......#........................... .....................................##...##.###.####..#......###...##..#........................... .....................................##.#.####.....#...#..#.##.###.##...#........................... ....................................####.##...##.####..#.#..#..#..###...#........................... ....................................#.##.###..#.#.##.#.#.....#.#.....#.#............................ ........................................#.#..#....##.##..#.#..###.##................................ ........................................##.#....#..#####.#....#....#..#.#........................... .......................................#.##.#..#....##.##.#..###......###........................... .....................................#.#...#..#..#..#..###...##..##....#............................ ....................................###.#.#####.######.###.#######.#.##............................. ....................................#.#.#....#####...##..#####.#####................................ ......................................#..##...#......#..#.##..###.###............................... ...................................####...#####.#########...#.#..................................... ..............................##....#..#.....###.#.#...#.###..###................................... .............................#..#..####.##...###.##...###.##.....##................................. ............................###....#.##.#.#####...#....#..#..##.###................................. ............................#.#####.#.#...##..##.....#....#...#..#.................................. ................................######.####..##.#...#..##..#.#.##................................... ..............................##......#.###.##..####...#...###...................................... ...............................#..#.#####..#...#.##...#..#..#....................................... ...............................##.###.#######.....#.....#.##........................................ ..............................#.#..##.##......#...##....#........................................... .............................#..#.####........###..##..#............................................ .............................#.##.###............##..##............................................. ..............................##.................................................................... ...............................##................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... ....................................................................................................