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 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 if Is_Black(Ant_X, Ant_Y) then Left(Ant_North, Ant_West); else Right(Ant_North, Ant_West); end if; Is_Black(Ant_X, Ant_Y) := not Is_Black(Ant_X, Ant_Y); 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: 11656
Aime
<lang aime>integer is_white(list map, integer x, integer y) {
integer p, w; data b;
b = l_q_data(map, y); w = b_character(b, x >> 3); p = 1 << (7 - (x & 7)); b_replace(b, x >> 3, w ^ p);
return !(w & p);
}
void ant(integer x, integer y, integer d, list map) {
while (-1 < x && x < 100 && -1 < y && y < 100) { if (is_white(map, x, y)) { d += 3; d &= 3; } else { d += 1; d &= 3; }
if (d & 1) { y += (d & 2) - 1; } else { x += 1 - (d & 2); } }
}
integer main(void) {
integer i; file f; list l;
i = 100; while (i) { data b; integer j;
i -= 1; j = 13; while (j) { j -= 1; b_append(b, 0); }
l_l_data(l, -1, b); }
ant(50, 50, 2, l);
f_open(f, "ant.pbm", OPEN_CREATE | OPEN_TRUNCATE | OPEN_WRITEONLY, 00644);
f_text(f, "P4\n100 100\n"); i = 100; while (i) { f_b_post(f, l_q_data(l, -i)); i -= 1; }
return 0;
}</lang>
AutoHotkey
ahk forum: discussion
(Fixed by just me)
<lang AutoHotkey>#NoEnv SetBatchLines, -1
- Directions
Directions := {0: "North", 1: "East", 2: "South", 3: "West"}
- Initialize the plane (set all cells to white)
White := 0xFFFFFF Plane := [] PW := PH := 100 loop, % PH {
I := A_Index loop, % PW Plane[I, A_Index] := White
}
- Let it run
DI := D := 0 ; initial direction X := Y := 50 ; initial coordinates while (X > 0) && (X <= PW) && (Y > 0) && (Y <= PH) {
D := (D + ((Plane[X, Y] ^= White) ? 1 : 3)) & 3 if (D & 1) X += -(D = 3) + (D = 1) else Y += -(D = 0) + (D = 2)
}
- Show the result
HBM := CreateDIB(Plane, PW, PH, 400, 400, 0) Gui, Margin, 0, 0 Gui, Add, Text, x0 y0 w20 h440 Center 0x200, W Gui, Add, Text, x20 y0 w400 h20 Center 0x200, N Gui, Add, Picture, x20 y20 w400 h400 0x4E hwndHPIC ; SS_REALSIZECONTROL = 0x40 | SS_BITMAP = 0xE DllCall("User32.dll\SendMessage", "Ptr", HPIC, "UInt", 0x172, "Ptr", 0, "Ptr", HBM) ; STM_SETIMAGE = 0x172 Gui, Add, Text, xp+5 yp h20 0x200 BackgroundTrans, % "Initial direction: " . Directions[DI] Gui, Add, Text, x20 y420 w400 h20 Center 0x200, S Gui, Add, Text, x420 y0 w20 h440 Center 0x200, E Gui, Show, , Langton's ant (%PW%x%PH%) Return
GuiClose: ExitApp
CreateDIB(PixelArray, PAW, PAH, BMW := 0, BMH := 0, Gradient := 1) { ; SKAN, 01-Apr-2014 / array version by just me
SLL := (PAW * 3) + (PAW & 1) VarSetCapacity(BMBITS, SLL * PAH, 0) P := &BMBITS loop, % PAH { R := A_Index loop, % PAW P := Numput(PixelArray[R, A_Index], P + 0, "UInt") - 1 P += (PAW & 1) } HBM := DllCall("Gdi32.dll\CreateBitmap", "Int", PAW, "Int", PAH, "UInt", 1, "UInt", 24, "Ptr", 0, "UPtr") HBM := DllCall("User32.dll\CopyImage", "Ptr", HBM, "UInt", 0, "Int", 0, "Int", 0, "UInt", 0x2008, "UPtr") DllCall( "Gdi32.dll\SetBitmapBits", "Ptr", HBM, "UInt", SLL * PAH, "Ptr", &BMBITS) if (!Gradient) HBM := DllCall("User32.dll\CopyImage", "Ptr", HBM, "UInt", 0, "Int", 0, "Int", 0, "Int", 8, "UPtr") return DllCall("User32.dll\CopyImage", "Ptr", HBM, "UInt", 0, "Int", BMW, "Int", BMH, "UInt", 0x200C, "UPtr")
} ; http://ahkscript.org/boards/viewtopic.php?f=6&t=3203</lang>
AutoIt
<lang AutoIt> Global $iCountMax = 100000 Global $aFields[100][100][2] Global $iDelayStep = 10 ; stop between steps in msec
Global $aDirection[4][4] = [ _ ; [ direction 0-3 ][ left change x, y, right change x, y ] [-1, 0, +1, 0], _ ; == direction 0 [ 0, -1, 0, +1], _ ; == direction 1 [+1, 0, -1, 0], _ ; == direction 2 [ 0, +1, 0, -1]] ; == direction 3
Global $hGui = GUICreate("Langton's ant", 100*8, 100*8) GUISetBkColor(0xFFFFFF)
For $i = 0 To 99 For $j = 0 To 99 $aFields[$i][$j][0] = GUICtrlCreateLabel(, $j*8, $i*8) GUICtrlSetColor(-1, 0xFF0000) $aFields[$i][$j][1] = 0 Next Next
GUISetState()
GUICtrlSetData($aFields[49][49][0], '#')
Do Sleep($iDelayStep) Until Not _SetAnt()
Do Until GUIGetMsg() = -3
Func _SetAnt()
Local Static $iRowLast = 49, $iColLast = 49, $iCount = 0
Local Static $aCol[2] = [0xFFFFFF,0x000000], $iDirection = 0
Local $iRow, $iCol, $fRight = False
If $iCount = $iCountMax Then Return 0
; == get current color Local $iLastColor = $aFields[$iRowLast][$iColLast][1]
; == go to left/right If $iLastColor = 0 Then $fRight = True
; == set the ant to the next field Local $indexX = 0, $indexY = 1 If $fRight Then $indexX = 2 $indexY = 3 EndIf $iRow = $iRowLast + ($aDirection[$iDirection][$indexX]) $iCol = $iColLast + ($aDirection[$iDirection][$indexY]) If $iRow < 0 Or $iRow > 99 Or $iCol < 0 Or $iCol > 99 Then Return 0 GUICtrlSetData($aFields[$iRowLast][$iColLast][0], ) GUICtrlSetData($aFields[$iRow][$iCol][0], '#')
; == direction for next step If $fRight Then $iDirection += 1 If $iDirection = 4 Then $iDirection = 0 Else $iDirection -= 1 If $iDirection = -1 Then $iDirection = 3 EndIf
; == change the color of the current field GUICtrlSetBkColor($aFields[$iRowLast][$iColLast][0], $aCol[(Not $iLastColor)*1]) $aFields[$iRowLast][$iColLast][1] = (Not $iLastColor)*1
$iRowLast = $iRow $iColLast = $iCol $iCount += 1 WinSetTitle($hGui, , "Langton's ant [ step: " & StringFormat('%06d', $iCount) & " ]") Return 1 EndFunc ;==>_SetAnt </lang> To see the GUI output, click here. --BugFix (talk) 14:48, 16 November 2013 (UTC)
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>
bc
The output function o
prints the resulting image (as a PBM image) to stdout
. One can either store it into a file or pipe it through an image viewer (e.g. bc langton.bc | display
).
<lang bc>define o() {
auto i, j "P1 " w h for (j = 0; j < h; j++) { for (i = 0; i < w; i++) { a[j * w + i] } }
}
define l(w, h, x, y) {
auto a[], d, i, x[], y[]
/* d represents one of the four possible directions: * 0 * ⇑ * 3⇐ ⇒1 * ⇓ * 2 * The arrays x[] and y[] contain the changes to the x and y direction for * each value of d. */ x[1] = 1 x[3] = -1 y[0] = -1 y[2] = 1
while (1) { i = y * w + x if (a[i] == 0) d += 1 /* turn right if white */ if (a[i] == 1) d -= 1 /* turn left if black */ if (d < 0) d = 3 if (d > 3) d = 0 x += x[d] y += y[d] a[i] = 1 - a[i] /* toggle cell colour */ if (x < 0) break if (x == w) break if (y < 0) break if (y == h) break }
o()
}
l(100, 100, 50, 50) quit</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++
If you want to see it running infinitely, set the const bool INFINIT_RUN = true <lang cpp>
- include <windows.h>
- include <string>
//-------------------------------------------------------------------------------------------------- using namespace std;
//-------------------------------------------------------------------------------------------------- const int BMP_SIZE = 600, CELL_SIZE = 4, GRID_SIZE = BMP_SIZE / CELL_SIZE; const bool INFINIT_RUN = false;
enum cellState { WHITE, BLACK, ANT }; enum facing { NOR, EAS, SOU, WES }; enum state { RUNNING, RESTING };
//-------------------------------------------------------------------------------------------------- class myBitmap { public:
myBitmap() : pen( NULL ) {} ~myBitmap() {
DeleteObject( pen ); DeleteDC( hdc ); DeleteObject( bmp );
}
bool create( int w, int h ) {
BITMAPINFO bi; ZeroMemory( &bi, sizeof( bi ) );
bi.bmiHeader.biSize = sizeof( bi.bmiHeader ); bi.bmiHeader.biBitCount = sizeof( DWORD ) * 8; bi.bmiHeader.biCompression = BI_RGB; bi.bmiHeader.biPlanes = 1; bi.bmiHeader.biWidth = w; bi.bmiHeader.biHeight = -h;
HDC dc = GetDC( GetConsoleWindow() ); bmp = CreateDIBSection( dc, &bi, DIB_RGB_COLORS, &pBits, NULL, 0 ); if( !bmp ) return false;
hdc = CreateCompatibleDC( dc ); SelectObject( hdc, bmp ); ReleaseDC( GetConsoleWindow(), dc );
width = w; height = h;
return true;
}
void clear() {
ZeroMemory( pBits, width * height * sizeof( DWORD ) );
}
void setPenColor( DWORD clr ) {
if( pen ) DeleteObject( pen ); pen = CreatePen( PS_SOLID, 1, clr ); SelectObject( hdc, pen );
}
void saveBitmap( string path ) {
BITMAPFILEHEADER fileheader; BITMAPINFO infoheader; BITMAP bitmap; DWORD wb;
GetObject( bmp, sizeof( bitmap ), &bitmap );
DWORD* dwpBits = new DWORD[bitmap.bmWidth * bitmap.bmHeight]; ZeroMemory( dwpBits, bitmap.bmWidth * bitmap.bmHeight * sizeof( DWORD ) ); ZeroMemory( &infoheader, sizeof( BITMAPINFO ) ); ZeroMemory( &fileheader, sizeof( BITMAPFILEHEADER ) );
infoheader.bmiHeader.biBitCount = sizeof( DWORD ) * 8; infoheader.bmiHeader.biCompression = BI_RGB; infoheader.bmiHeader.biPlanes = 1; infoheader.bmiHeader.biSize = sizeof( infoheader.bmiHeader ); infoheader.bmiHeader.biHeight = bitmap.bmHeight; infoheader.bmiHeader.biWidth = bitmap.bmWidth; infoheader.bmiHeader.biSizeImage = bitmap.bmWidth * bitmap.bmHeight * sizeof( DWORD );
fileheader.bfType = 0x4D42; fileheader.bfOffBits = sizeof( infoheader.bmiHeader ) + sizeof( BITMAPFILEHEADER ); fileheader.bfSize = fileheader.bfOffBits + infoheader.bmiHeader.biSizeImage;
GetDIBits( hdc, bmp, 0, height, ( LPVOID )dwpBits, &infoheader, DIB_RGB_COLORS );
HANDLE file = CreateFile( path.c_str(), GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL ); WriteFile( file, &fileheader, sizeof( BITMAPFILEHEADER ), &wb, NULL ); WriteFile( file, &infoheader.bmiHeader, sizeof( infoheader.bmiHeader ), &wb, NULL ); WriteFile( file, dwpBits, bitmap.bmWidth * bitmap.bmHeight * 4, &wb, NULL ); CloseHandle( file );
delete [] dwpBits;
}
HDC getDC() const { return hdc; } int getWidth() const { return width; } int getHeight() const { return height; }
private:
HBITMAP bmp; HDC hdc; HPEN pen; void *pBits; int width, height;
}; //-------------------------------------------------------------------------------------------------- class Ant { public:
Ant() {
_bmp.create( BMP_SIZE, BMP_SIZE ); ZeroMemory( _grid, sizeof( _grid ) ); RED_BRUSH = CreateSolidBrush( 255 ); _antState = RUNNING;
}
~Ant() {
DeleteObject( RED_BRUSH );
}
void setPosition( int x, int y ) {
_sx = x; _sy = y; _facing = WES;
}
void mainLoop() {
switch( _antState ) { case RUNNING: simulate(); // fall thru case RESTING: display(); }
}
void setHWND( HWND hwnd ) { _hwnd = hwnd; }
private:
void simulate() {
switch( _grid[_sx][_sy] ) { case BLACK: _grid[_sx][_sy] = WHITE; if( --_facing < NOR ) _facing = WES; break; case WHITE: _grid[_sx][_sy] = BLACK; if( ++_facing > WES ) _facing = NOR; } switch( _facing ) { case NOR: if( --_sy < 0 ) { if( INFINIT_RUN ) _sy = GRID_SIZE - 1; else _antState = RESTING; } break; case EAS: if( ++_sx >= GRID_SIZE ) { if( INFINIT_RUN ) _sx = 0; else _antState = RESTING; } break; case SOU: if( ++_sy >= GRID_SIZE ) { if( INFINIT_RUN ) _sy = 0; else _antState = RESTING; } break; case WES: if( --_sx < 0 ) { if( INFINIT_RUN ) _sx = GRID_SIZE - 1; else _antState = RESTING; } }
}
void display() { _bmp.clear();
HBRUSH br; RECT rc; int xx, yy; HDC dc = _bmp.getDC();
for( int y = 0; y < GRID_SIZE; y++ )
for( int x = 0; x < GRID_SIZE; x++ ) { switch( _grid[x][y] ) { case BLACK: br = static_cast<HBRUSH>( GetStockObject( BLACK_BRUSH ) ); break; case WHITE: br = static_cast<HBRUSH>( GetStockObject( WHITE_BRUSH ) ); } if( x == _sx && y == _sy ) br = RED_BRUSH;
xx = x * CELL_SIZE; yy = y * CELL_SIZE; SetRect( &rc, xx, yy, xx + CELL_SIZE, yy + CELL_SIZE ); FillRect( dc, &rc, br ); }
HDC wdc = GetDC( _hwnd ); BitBlt( wdc, 0, 0, BMP_SIZE, BMP_SIZE, dc, 0, 0, SRCCOPY ); ReleaseDC( _hwnd, wdc ); }
myBitmap _bmp; HWND _hwnd; HBRUSH RED_BRUSH; BYTE _grid[GRID_SIZE][GRID_SIZE]; int _sx, _sy, _facing; state _antState;
}; //-------------------------------------------------------------------------------------------------- class wnd { public:
int wnd::Run( HINSTANCE hInst ) {
_hInst = hInst; _hwnd = InitAll();
_ant.setHWND( _hwnd ); _ant.setPosition( GRID_SIZE / 2, GRID_SIZE / 2 );
ShowWindow( _hwnd, SW_SHOW ); UpdateWindow( _hwnd );
MSG msg; ZeroMemory( &msg, sizeof( msg ) ); while( msg.message != WM_QUIT ) { if( PeekMessage( &msg, NULL, 0, 0, PM_REMOVE ) != 0 ) { TranslateMessage( &msg ); DispatchMessage( &msg ); } else { _ant.mainLoop(); } } return UnregisterClass( "_LANGTONS_ANT_", _hInst );
}
private:
static int WINAPI wnd::WndProc( HWND hWnd, UINT msg, WPARAM wParam, LPARAM lParam ) {
switch( msg ) { case WM_DESTROY: PostQuitMessage( 0 ); break; default: return DefWindowProc( hWnd, msg, wParam, lParam ); } return 0;
}
HWND InitAll() {
WNDCLASSEX wcex; ZeroMemory( &wcex, sizeof( wcex ) ); wcex.cbSize = sizeof( WNDCLASSEX ); wcex.style = CS_HREDRAW | CS_VREDRAW; wcex.lpfnWndProc = ( WNDPROC )WndProc; wcex.hInstance = _hInst; wcex.hCursor = LoadCursor( NULL, IDC_ARROW ); wcex.hbrBackground = ( HBRUSH )( COLOR_WINDOW + 1 ); wcex.lpszClassName = "_LANGTONS_ANT_";
RegisterClassEx( &wcex );
return CreateWindow( "_LANGTONS_ANT_", ".: Langton's Ant -- PJorente :.", WS_SYSMENU, CW_USEDEFAULT, 0, BMP_SIZE, BMP_SIZE, NULL, NULL, _hInst, NULL );
}
HINSTANCE _hInst; HWND _hwnd; Ant _ant;
}; //-------------------------------------------------------------------------------------------------- int APIENTRY _tWinMain( HINSTANCE hInstance, HINSTANCE hPrevInstance, LPTSTR lpCmdLine, int nCmdShow ) {
wnd myWnd; return myWnd.Run( hInstance );
} //-------------------------------------------------------------------------------------------------- </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> # # ## # # # ### ## #### ### # ##### # ## # ## ## # ### # ## # ## ## # ### # ## # ## ## # ### # ## # ## ## # ### # ## # ## ## # ### # ## # ## ## # ### # ## # ## ## # ### # ## # ## ## # ### # ## # ## ## # ### # ## # ## ## # ### # ## # ## ## # ### # ## # ## ## # ### # ## # ## ## # ### # ## # ## ## # ## ### # ## ## # ## ## ## # #### ### # # ### # # # ## #### # ### # # # # ## # ### # ## # ## # ## # # ## # # ## # # # ##### # # # ##### ## ###### ### ## # ## # # # ## # ## ## # ####### # # ### ## # # # ###### ## # # ## # # # # # ## # ###### ####### # # #### ## # #### ## ## # ## # # #### # # ###### ## ### # # ## # ### # ## ## ### ####### # ## ## # # #### ## ## #### ## ## ## # # # # # ### ## ### # #### # ### ### # # ##### # # # # # ### #### ## # ## ### ## # ## ## #### #### # # # # # # ## ### ### ### # ## ## ### #### # ### ## # ## # #### # # # ## ### ## # #### ## ## #### # # # # ### # # ## ### # # ## # # # # # # # # # ## ## # # ### ## ## # # ##### # # # # # # ## # # ## ## # ### ### # # # # # # ### ## ## # ### # ##### ###### ### ####### # ## # # # ##### ## ##### ##### # ## # # # ## ### ### #### ##### ######### # # ## # # ### # # # ### ### # # #### ## ### ## ### ## ## ### # ## # ##### # # # ## ### # ##### # # ## ## # # # # ###### #### ## # # ## # # ## ## # ### ## #### # ### # # ##### # # ## # # # ## ### ####### # # ## # # ## ## # ## # # # #### ### ## # # ## ### ## ## ## ##
Clojure
In keeping with the spirit of Clojure, this program eschews mutable state entirely. Instead, all computation occurs within a single recursive loop whose "variables" are "adjusted" at each iteration, a natural fit for this particular execution model. <lang Clojure>(let [bounds (set (range 100))
xs [1 0 -1 0] ys [0 -1 0 1]] (loop [dir 0 x 50 y 50 grid {[x y] false}] (if (and (bounds x) (bounds y)) (let [cur (not (grid [x y])) dir (mod (+ dir (if cur -1 1)) 4)] (recur dir (+ x (xs dir)) (+ y (ys dir)) (merge grid {[x y] cur}))) (doseq [col (range 100)] (println (apply str (map #(if (grid [% col]) \# \.) (range 100))))))))</lang>
COBOL
The following program displays the simulation in the console, and a very small font size (~4pt) will be needed to fit it into the window.
<lang cobol> IDENTIFICATION DIVISION.
PROGRAM-ID. langtons-ant.
DATA DIVISION. WORKING-STORAGE SECTION. 78 Grid-Size VALUE 100. 01 grid-area. 03 grid-x OCCURS Grid-Size TIMES. 05 grid-y OCCURS Grid-Size TIMES. 07 cell-colour PIC X VALUE "W". 88 black VALUE "B". 88 white VALUE "W".
01 ant-x PIC 999. 01 ant-y PIC 999.
01 ant-direction PIC 9. 88 upward VALUE 0. 88 rightward VALUE 1. 88 downward VALUE 2. 88 leftward VALUE 3.
78 Pause-Time-Ns VALUE 10000000.
01 display-y PIC 999.
78 Black-Background VALUE 0. 78 White-Background VALUE 7.
01 i PIC 999. 01 j PIC 999.
01 pause PIC X.
PROCEDURE DIVISION. main-line. DIVIDE Grid-Size BY 2 GIVING ant-x, ant-y
PERFORM display-initial-grid PERFORM UNTIL (ant-x = Grid-Size OR 0) OR (ant-y = Grid-Size OR 0) PERFORM step-simulation CALL "CBL_OC_NANOSLEEP" USING Pause-Time-Ns END-PERFORM
DISPLAY "Press enter to quit." AT LINE 1 COLUMN 1 ACCEPT pause
GOBACK . step-simulation. IF black (ant-x, ant-y) SET white (ant-x, ant-y) TO TRUE PERFORM display-ant-cell COMPUTE ant-direction = FUNCTION MOD(ant-direction + 1, 4) ELSE SET black (ant-x, ant-y) TO TRUE PERFORM display-ant-cell COMPUTE ant-direction = FUNCTION MOD(ant-direction - 1, 4) END-IF
EVALUATE TRUE WHEN upward ADD 1 TO ant-y WHEN rightward ADD 1 TO ant-x WHEN downward SUBTRACT 1 FROM ant-y WHEN leftward SUBTRACT 1 FROM ant-x END-EVALUATE . display-ant-cell. SUBTRACT ant-y FROM Grid-Size GIVING display-y IF black (ant-x, ant-y) DISPLAY SPACE AT LINE display-y COLUMN ant-x WITH BACKGROUND-COLOR Black-Background ELSE DISPLAY SPACE AT LINE display-y COLUMN ant-x WITH BACKGROUND-COLOR White-Background END-IF . display-initial-grid. PERFORM VARYING i FROM 1 BY 1 UNTIL i > Grid-Size AFTER j FROM 1 BY 1 UNTIL j > Grid-Size DISPLAY SPACE AT LINE i COLUMN j WITH BACKGROUND-COLOR White-Background END-PERFORM .</lang>
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>
Common Lisp
<lang lisp>(defmacro toggle (gv) `(setf ,gv (not ,gv)))
(defun langtons-ant (width height start-x start-y start-dir)
(let ( (grid (make-array (list width height))) (x start-x) (y start-y) (dir start-dir) ) (loop while (and (< -1 x width) (< -1 y height)) do (if (toggle (aref grid x y)) (setq dir (mod (1+ dir) 4)) (setq dir (mod (1- dir) 4))) (case dir (0 (decf y)) (1 (incf x)) (2 (incf y)) (3 (decf x))) ) grid )
)
(defun show-grid (grid)
(destructuring-bind (width height) (array-dimensions grid) (dotimes (y height) (dotimes (x width) (princ (if (aref grid x y) "#" "."))) (princ #\Newline)) )
)
(setf *random-state* (make-random-state t)) (show-grid (langtons-ant 100 100 (+ 45 (random 10)) (+ 45 (random 10)) (random 4)))</lang>
D
Textual Version
<lang d>void main() @safe {
import std.stdio, std.traits;
enum width = 75, height = 52; enum maxSteps = 12_000; enum Direction { up, right, down, left } enum Color : char { white = '.', black = '#' } uint x = width / 2, y = height / 2; auto M = new Color[][](height, width); auto dir = Direction.up;
with (Color) for (int i = 0; i < maxSteps && x < width && y < height; i++) { immutable turn = M[y][x] == black; dir = [EnumMembers!Direction][(dir + (turn ? 1 : -1)) & 3]; M[y][x] = (M[y][x] == black) ? white : black; final switch(dir) with (Direction) { case up: y--; break; case right: x--; break; case down: y++; break; case left: x++; break; } }
writefln("%(%-(%c%)\n%)", M);
}</lang>
- Output:
........................................................................... ........................................................................... ........................................................................... ........................................................................... .............................##..############..##.......................... ............................#..####..........#..##......................... ...........................###...##............##.#........................ ...........................#.#..#.........#..#....#........................ .......................##..##.#.#.........###.......#...................... ....................###.#..#...#.....#.....##.##..###...................... .....................#.#..###..##.####.##...#.#..#.##..##.................. .....................#.###.##..#.##..###.#.#.....###...###................. ...................#.....#...#####.#.#..####..#...###.#.#.#................ ..................###.##...#.####..##.##.######.#.###.#...#................ ..................#.###.#.##.#.#.##.##.##.#...#####.###.##................. ......................#.#...#.##.###...#...#.#..####....#.##............... ...................#..#.........##.##...#..##.....##.#.....##.............. ..................###...#.#.##.###..#..##.....#...###.##..##.#............. .................#..###..##...##.##...###..#....#..##.####...#............. ................###...#...#.#..#.#.####.##..#.##.###..#.....#.............. ...............#..###..#.##....#..#.###..#......###.##.#..#..##............ ..............###...#.....#.##.#.##..##..#####.####..####.##...#........... .............#..###..#.#.#..#.###.#.#.##......##...#.#.#....#...#.......... ............###...#..##.###..##.#...##.......####.####...#......#.......... ...........#..###..#.#..#...##..###########.#..####..#....#....#........... ..........###...#..##......#.####..##..#########..#..##....#..##........... .........#..###..#.#...##..#.##...##.##.###.###...#..#.##..####.#.......... ........###...#..##...#..#.######.##.#.##.#.#....###.###...##...#.......... .......#..###..#.#...#.....#####.#.#####.....#.#..##.#....##...#........... ......###...#..##....#.....#.##.#####.##..#.#...#..#..##.#..#..#........... .....#..###..#.#.....#....#...####.#..#####.##...##########...##........... ....###...#..##......#.##...##...#..#...####..#...##.####.##............... ...#..###..#.#........#####.#..##...##.#...#....#.#..#..#..#.#............. ..###...#..##..........##..##.#.#.#....##.##.#.#.##..#..##..##............. .#..###..#.#.................#..#....#.########.#.#.##..####.#............. ###...#..##..................#..#...#.......##.##...#..#..##.#............. ...##..#.#....................#..#..#......#..##..##...##.####............. ##..#..##......................##...#.......##..##....#...#.###............ .#.#.#.#............................#.##..####....####.###.####............ ####.##..............................##..####....##..#.##.#.#..#........... #.##.#................................##....##....##.###.##.#####.......... .####................................................#.##.#..####.......... ..##.....................................................##.##.##.......... .........................................................##................ .......................................................#.##..####.#........ ......................................................#..#.###..###........ ......................................................#.##.#..#..#......... .......................................................##......##.......... ........................................................##................. ........................................................................... ........................................................................... ...........................................................................
Image Version
This similar version requires the module from the Grayscale Image Task to generate and save a PGM image. <lang d>import std.stdio, std.algorithm, std.traits, grayscale_image;
void main() {
enum width = 100, height = 100; enum nSteps = 12_000; enum Direction { up, right, down, left } auto M = new Image!Gray(width, height); M.clear(Gray.white); uint x = width / 2, y = height / 2; auto dir = Direction.up;
for (int i = 0; i < nSteps && x < width && y < height; i++) { immutable turn = M[x, y] == Gray.black; dir = [EnumMembers!Direction][(dir + (turn ? 1 : -1)) & 3]; M[x, y] = (M[x, y] == Gray.black) ? Gray.white : Gray.black; final switch(dir) with (Direction) { case up: y--; break; case right: x--; break; case down: y++; break; case left: x++; break; } }
M.savePGM("langton_ant.pgm");
}</lang>
Ela
A straightforward implementation (assumes that we start with ant looking forward):
<lang ela>open list core generic
type Field = Field a type Color = White | Black type Direction = Lft | Fwd | Rgt | Bwd field s = Field [[White \\ _ <- [1..s]] \\ _ <- [1..s]]
isBlack Black = true isBlack _ = false
newfield xc yc (Field xs) = Field (newfield' 0 xs)
where newfield' _ [] = [] newfield' n (x::xs) | n == yc = row 0 x :: xs | else = x :: newfield' (n+1) xs where row _ [] = [] row n (x::xs) | n == xc = toggle x :: xs | else = x :: row (n+1) xs where toggle White = Black toggle Black = White
showPath (Field xs) = toString <| show' "" xs
where show' sb [] = sb +> "" show' sb (x::xs) = show' (showRow sb x +> "\r\n") xs where showRow sb [] = sb +> "" showRow sb (x::xs) = showRow (sb +> s) xs where s | isBlack x = "#" | else = "_"
move s xc yc = move' (Fwd,xc,yc) (field s)
where move' (pos,xc,yc)@coor fld | xc >= s || yc >= s || xc < 0 || yc < 0 = fld | else = fld |> newfield xc yc |> move' (matrix (dir fld) coor) where dir (Field xs) | `isBlack` (xs:yc):xc = Lft | else = Rgt matrix Lft (pos,x,y) = go (left pos,x,y) matrix Rgt (pos,x,y) = go (right pos,x,y) go (Lft,x,y) = (Lft,x - 1,y) go (Rgt,x,y) = (Rgt,x+1,y) go (Fwd,x,y) = (Fwd,x,y - 1) go (Bwd,x,y) = (Bwd,x,y+1) right Lft = Fwd right Fwd = Rgt right Rgt = Bwd right Bwd = Lft left Lft = Bwd left Bwd = Rgt left Rgt = Fwd left Fwd = Lft</lang>
This implementation is pure (doesn't produce side effects).
Testing:
<lang ela>showPath <| move 100 50 50</lang>
Output (empty lines are skipped to save space):
__________________________________________##__############__##______________________________________ _________________________________________#__####__________#__##_____________________________________ ________________________________________###___##____________##_#____________________________________ ________________________________________#_#__#_________#__#____#____________________________________ ____________________________________##__##_#_#_________###_______#__________________________________ _________________________________###_#__#___#_____#_____##_##__###__________________________________ __________________________________#_#__###__##_####_##___#_#__#_##__##______________________________ __________________________________#_###_##__#_##__###_#_#_____###___###_____________________________ ________________________________#_____#___#####_#_#__####__#___###_#_#_#____________________________ _______________________________###_##___#_####__##_##_######_#_###_#___#____________________________ _______________________________#_###_#_##_#_#_##_##_##_#___#####_###_##_____________________________ ___________________________________#_#___#_##_###___#___#_#__####____#_##___________________________ ________________________________#__#_________##_##___#__##_____##_#_____##__________________________ _______________________________###___#_#_##_###__#__##_____#___###_##__##_#_________________________ ______________________________#__###__##___##_##___###__#____#__##_####___#_________________________ _____________________________###___#___#_#__#_#_####_##__#_##_###__#_____#__________________________ ____________________________#__###__#_##____#__#_###__#______###_##_#__#__##________________________ ___________________________###___#_____#_##_#_##__##__#####_####__####_##___#_______________________ __________________________#__###__#_#_#__#_###_#_#_##______##___#_#_#____#___#______________________ _________________________###___#__##_###__##_#___##_______####_####___#______#______________________ ________________________#__###__#_#__#___##__###########_#__####__#____#____#_______________________ _______________________###___#__##______#_####__##__#########__#__##____#__##_______________________ ______________________#__###__#_#___##__#_##___##_##_###_###___#__#_##__####_#______________________ _____________________###___#__##___#__#_######_##_#_##_#_#____###_###___##___#______________________ ____________________#__###__#_#___#_____#####_#_#####_____#_#__##_#____##___#_______________________ ___________________###___#__##____#_____#_##_#####_##__#_#___#__#__##_#__#__#_______________________ __________________#__###__#_#_____#____#___####_#__#####_##___##########___##_______________________ _________________###___#__##______#_##___##___#__#___####__#___##_####_##___________________________ ________________#__###__#_#________#####_#__##___##_#___#____#_#__#__#__#_#_________________________ _______________###___#__##__________##__##_#_#_#____##_##_#_#_##__#__##__##_________________________ ______________#__###__#_#_________________#__#____#_########_#_#_##__####_#_________________________ _____________###___#__##__________________#__#___#_______##_##___#__#__##_#_________________________ ____________#__###__#_#____________________#__#__#______#__##__##___##_####_________________________ ___________###___#__##______________________##___#_______##__##____#___#_###________________________ __________#__###__#_#____________________________#_##__####____####_###_####________________________ _________###___#__##______________________________##__####____##__#_##_#_#__#_______________________ ________#__###__#_#________________________________##____##____##_###_##_#####______________________ _______###___#__##________________________________________________#_##_#__####______________________ ______#__###__#_#_____________________________________________________##_##_##______________________ _____###___#__##______________________________________________________##____________________________ ____#__###__#_#_____________________________________________________#_##__####_#____________________ ___###___#__##_____________________________________________________#__#_###__###____________________ __#__###__#_#______________________________________________________#_##_#__#__#_____________________ _###___#__##________________________________________________________##______##______________________ #__###__#_#__________________________________________________________##_____________________________ _###_#__##__________________________________________________________________________________________ #_#_#_#_#___________________________________________________________________________________________ _####_##____________________________________________________________________________________________ _#_##_#_____________________________________________________________________________________________ __####______________________________________________________________________________________________ ___##_______________________________________________________________________________________________
Erlang
Over-engineered sine I have summer vacation. Ex: Display function only display lines with black cells. <lang Erlang> -module( langtons_ant ).
-export( [task/0] ).
-record( neighbour, {north, south, east, west} ). -record( state, {colour=white, controller, max_x, max_y, neighbour, position} ).
task() ->
Controller = erlang:self(), Max_x = Max_y = 100, Pid_positions = plane_create( Controller, Max_x, Max_y ), Pids = [X || {X, _} <- Pid_positions], [X ! {pid_positions, Pid_positions} || X <- Pids], {Pid, _Position} = lists:keyfind( {Max_x div 2, Max_y div 2}, 2, Pid_positions ), Pid ! {ant_start, north, Controller}, receive {ant_arrives, _Pid} -> ok end, display( Controller, Max_x, Max_y, Pids ), [X ! {stop, Controller} || X <- Pids].
display( Controller, Max_x, Max_y, Pids ) ->
Positions_colours = display_positions_colours( Pids, Controller ), All_lines = [display_line( Max_x, Positions_colours, Y ) || Y <- lists:seq(Max_y, 1, -1)], Lines_with_black = [X || X <- All_lines, lists:member(black, X)], [io:fwrite( "~s~n", | X <- Lines ) || Lines <- Lines_with_black].
display_line( Max_x, Positions_colours, Y ) -> [proplists:get_value({X,Y}, Positions_colours, white) || X <- lists:seq(1, Max_x)].
display_on_screen( white ) -> $_; display_on_screen( black ) -> $#.
display_positions_colours( Pids, Controller ) ->
[X ! {position_colour, Controller} || X <- Pids], [display_positions_colours_receive() || _X <- Pids].
display_positions_colours_receive( ) ->
receive {position_colour, Position, Colour} -> {Position, Colour} end.
loop( State ) ->
receive {pid_positions, Pid_positions} -> {_My_position, Neighbour} = lists:foldl( fun loop_neighbour/2, {State#state.position, #neighbour{}}, Pid_positions ), erlang:garbage_collect(), % Shrink process after using large Pid_positions. For memory starved systems. loop( State#state{neighbour=Neighbour} ); {ant_start, Direction, Controller} when Controller =:= State#state.controller -> {Pid, New_state} = loop_ant_departs( Direction, State ), Pid ! {ant_arrives, erlang:self()}, loop( New_state ); {ant_arrives, From} -> {Direction, New_state} = loop_ant_arrives( From, State ), {To, Newest_state} = loop_ant_departs( Direction, New_state ), To ! {ant_arrives, erlang:self()}, loop( Newest_state ); {position_colour, Controller} when Controller =:= State#state.controller -> Controller ! {position_colour, State#state.position, State#state.colour}, loop( State ); {stop, Controller} when Controller =:= State#state.controller -> ok end.
loop_ant_arrives( Pid, State ) ->
Neighbour = State#state.neighbour, From = loop_ant_arrives_direction( Pid, Neighbour ), {loop_ant_arrives_new_direction(From, State), State}.
loop_ant_arrives_direction( Pid, #neighbour{north=Pid} ) -> north; loop_ant_arrives_direction( Pid, #neighbour{south=Pid} ) -> south; loop_ant_arrives_direction( Pid, #neighbour{east=Pid} ) -> east; loop_ant_arrives_direction( Pid, #neighbour{west=Pid} ) -> west.
loop_ant_arrives_new_direction( north, #state{colour=white} ) -> west; loop_ant_arrives_new_direction( north, #state{colour=black} ) -> east; loop_ant_arrives_new_direction( south, #state{colour=white} ) -> east; loop_ant_arrives_new_direction( south, #state{colour=black} ) -> west; loop_ant_arrives_new_direction( east, #state{colour=white} ) -> north; loop_ant_arrives_new_direction( east, #state{colour=black} ) -> south; loop_ant_arrives_new_direction( west, #state{colour=white} ) -> south; loop_ant_arrives_new_direction( west, #state{colour=black} ) -> north.
loop_ant_departs( north, #state{position={_X,Y}, max_y=Y}=State ) ->
{State#state.controller, State};
loop_ant_departs( south, #state{position={_X,1}}=State ) ->
{State#state.controller, State};
loop_ant_departs( east, #state{position={X,_Y}, max_x=X}=State ) ->
{State#state.controller, State};
loop_ant_departs( west, #state{position={1,_Y}}=State ) ->
{State#state.controller, State};
loop_ant_departs( Direction, State ) ->
Neighbour = State#state.neighbour, Pid = loop_ant_departs_pid( Direction, Neighbour ), {Pid, State#state{colour=other_colour(State)}}.
loop_ant_departs_pid( north, #neighbour{north=Pid} ) -> Pid; loop_ant_departs_pid( south, #neighbour{south=Pid} ) -> Pid; loop_ant_departs_pid( east, #neighbour{east=Pid} ) -> Pid; loop_ant_departs_pid( west, #neighbour{west=Pid} ) -> Pid.
loop_neighbour( {Pid, {X, Y}}, {{X, My_y}, Neighbour} ) when Y =:= My_y + 1 -> {{X, My_y}, Neighbour#neighbour{north=Pid}}; loop_neighbour( {Pid, {X, Y}}, {{X, My_y}, Neighbour} ) when Y =:= My_y - 1 -> {{X, My_y}, Neighbour#neighbour{south=Pid}}; loop_neighbour( {Pid, {X, Y}}, {{My_x, Y}, Neighbour} ) when X =:= My_x + 1 -> {{My_x, Y}, Neighbour#neighbour{east=Pid}}; loop_neighbour( {Pid, {X, Y}}, {{My_x, Y}, Neighbour} ) when X =:= My_x - 1 -> {{My_x, Y}, Neighbour#neighbour{west=Pid}}; loop_neighbour( _Pid_position, Acc ) -> Acc.
other_colour( #state{colour=white} ) -> black; other_colour( #state{colour=black} ) -> white.
plane_create( Controller, Max_x, Max_y ) -> [{plane_create_cell(Controller, Max_x, Max_y, {X, Y}), {X,Y}} || X <- lists:seq(1, Max_x), Y<- lists:seq(1, Max_y)]. plane_create_cell( Controller, Max_x, Max_y, Position ) -> erlang:spawn_link( fun() -> loop( #state{controller=Controller, max_x=Max_x, max_y=Max_y, position=Position} ) end ). </lang>
- Output:
___________________________________________________________________##_______________________________ ____________________________________________________________________##______________________________ _____________________________________________##__##____________###_##_#_____________________________ ____________________________________________#__##__###________####_#__#_____________________________ ___________________________________________#____##___#______##_##__#_#______________________________ ________________________________________##_#_____#_____#######_###_##_______________________________ _______________________________________#__#__#___##_#___#__#####_#__#_______________________________ ______________________________________###___#___####__##_###_#______##______________________________ ___________________________________##_#_#__##__#___#_##__####_######________________________________ __________________________________#__#___#____#_____##__##___#_#_#####_#____________________________ _________________________________###_##__#__#____#___#####_#_##_#____###____________________________ _________________________________##_____##_###___##_###___##_####__#__#_____________________________ ___________________________________###__###_#___#_#_###_____#__#____##______________________________ _____________________________________#_#___#########_#####___####___________________________________ _______________________________###_###__##_#__#______#___##__#______________________________________ ________________________________#####_#####__##___#####____#_#_#____________________________________ _____________________________##_#_#######_###_######_#####_#_###____________________________________ ____________________________#____##__##___###__#__#__#__#___#_#_____________________________________ ___________________________###______###__#_##_##____#__#_##_#_______________________________________ ___________________________#_#__#____#____#_#####__#____#_##________________________________________ ________________________________##_###__#_#__##_##____#__#_#________________________________________ ____________________________#_#_____#_#_____#_#_##_#_#__###_##_#____________________________________ ___________________________#___###__#__#__#_#__####_##___##_####____________________________________ ___________________________#___##_###_##_#__#___#_____####_#_##_____________________________________ ___________________________#__##___###______#__####_###_##___##_____________________________________ ___________________________#______###_____###__###___##__#____#_____________________________________ ___________________________#_____#_#_#_####____####__##_##__________________________________________ ___________________________#_____##_###_##___#_##_####_###___#_#____________________________________ ___________________________#______#_#____#####_#_#_###_______###____________________________________ ___________________________#____####_#____###_##_###___#_#____#_____________________________________ ___________________________#_____#__##_##_##_####__##_##__####______________________________________ ___________________________#_____#_##_##__#____#######______________________________________________ ___________________________###___##__##__#_###_#_##_#___#___________________________________________ ___________________________###____##_######_#__#___####____#________________________________________ ____________________________#_##_#_##__##____####_#_##_####_#_______________________________________ ____________________________#___#######_######__#_##_#_#____#_______________________________________ ___________________________#___#___##_#__#___##_######__#__#________________________________________ ___________________________#_##____###__#___#_#######_#__##_________________________________________ ____________________________##_#_##___#_#_#_##_#__##__###___________________________________________ _____________________________######_##__________#####___#___________________________________________ _________________________________#___#__#####_#______#_#____________________________________________ __________________________________##_____#_#_##___#____#____________________________________________ _______________________________##_#__##_#_____##_#____###___________________________________________ _______________________________#_##_#______#_#___#____###___________________________________________ ________________________________#___####_##___#___#____#____________________________________________ ________________________________###__#___#___###___####_____________________________________________ ________________________________#___##__##_##___#___________________________________________________ ___________________________________##__##__#___###__________________________________________________ ____________________________________##__#_##_##___#_________________________________________________ _________________________________________##__#___###________________________________________________ __________________________________________#_##_##___#_______________________________________________ ___________________________________________##__#___###______________________________________________ ____________________________________________#_##_##___#_____________________________________________ _____________________________________________##__#___###____________________________________________ ______________________________________________#_##_##___#___________________________________________ _______________________________________________##__#___###__________________________________________ ________________________________________________#_##_##___#_________________________________________ _________________________________________________##__#___###________________________________________ __________________________________________________#_##_##___#_______________________________________ ___________________________________________________##__#___###______________________________________ ____________________________________________________#_##_##___#_____________________________________ _____________________________________________________##__#___###____________________________________ ______________________________________________________#_##_##___#___________________________________ _______________________________________________________##__#___###__________________________________ ________________________________________________________#_##_##___#_________________________________ _________________________________________________________##__#___###________________________________ __________________________________________________________#_##_##___#_______________________________ ___________________________________________________________##__#___###______________________________ ____________________________________________________________#_##_##___#_____________________________ _____________________________________________________________##__#___###____________________________ ______________________________________________________________#_##_##___#___________________________ _______________________________________________________________##__#___###__________________________ ________________________________________________________________#_##_##___#_________________________ _________________________________________________________________##__#___###________________________ __________________________________________________________________#_##_##___#_______________________ ___________________________________________________________________##__#_#####______________________ ____________________________________________________________________#_#___####______________________ _____________________________________________________________________##_###_#_______________________ ______________________________________________________________________#___##________________________
Euphoria
<lang euphoria>include std\console.e include std\graphics.e
sequence grid = repeat(repeat(1,100),100) --fill 100 by 100 grid with white (1) sequence antData = {48, 53, 360} --ant x coordinate, y coordinate, facing angle integer iterations = 0
--while ant isn't out of bounds of the 100 by 100 area.. while antData[1] > 0 and antData[1] < 100 and antData[2] > 0 and antData[2] < 100 do
switch grid[antData[1]][antData[2]] do case 1 then--cell is already white grid[antData[1]][antData[2]] = 0 --cell turns black, ant turns right antData[3] += 90 break case 0 then--cell is already black grid[antData[1]][antData[2]] = 1 --cell turns white, ant turns left antData[3] -= 90 break end switch --wrap ant directions if > 360 or < 90 (by 90) switch antData[3] do case 450 then antData[3] = 90 break case 0 then antData[3] = 360 break end switch --move ant based on its new facing, one square --first north, then south, east, west switch antData[3] do case 360 then antData[2] -= 1 break case 180 then antData[2] += 1 break case 90 then antData[1] += 1 break case 270 then antData[1] -= 1 break end switch
iterations += 1 end while
wrap(0) --don't wrap text output, the grid wouldnt display as a square
for y=1 to 100 do
printf(1,"\n") for x=1 to 100 do switch grid[x][y] do--each grid block , based on color case 0 then printf(1,".") break case 1 then printf(1,"#") break end switch end for
end for
printf(1,"\n%d Iterations\n",iterations)
any_key()--wait for keypress, put default message 'press any key..'</lang>
Code needed to run SDL example with Mark Akita's SDL_gfx_Test1.exw (as template) included with his SDL_gfx package from rapideuphoria.com's archive - In initialization section :<lang euphoria> sequence grid = repeat(repeat(1,100),100) --fill 100 by 100 grid with white (1) sequence antData = {48, 53, 360} --x coordinate, y coordinate, facing angle</lang> In main() , after keystate=SDL_GetKeyState(NULL) , you can adapt the program above to draw the ant's step each frame. Use dummy=pixelColor(surface,x+20,y+12,#000000FF) (for example) to replace the text output. Just before the close of the while loop, use dummy=pixelColor(surface,antData[1]+20,antData[2]+12,#FF0000FF) for the ant and SDL_UpdateRect(surface,0,0,0,0) to display the graphic.
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
Fortran
<lang fortran> program langtons_ant
implicit none
integer, parameter :: dp = selected_real_kind(15,300) real(kind=dp), parameter :: pi = 3.1415926535897932_dp
integer, parameter :: grid_size = 100 integer, dimension(:,:), allocatable :: grid integer, dimension(3) :: ant = (/ grid_size/2, grid_size/2, 0 /) integer :: i
allocate(grid(1:grid_size, 1:grid_size)) grid = 1 !Grid initially white
do grid(ant(1) , ant(2)) = -grid(ant(1) , ant(2)) ! Flip the color of the current square ant(3) = modulo(ant(3) + grid(ant(1),ant(2)),4) ! Rotate the ant depending on the current square ant(1) = ant(1) + nint( sin(ant(3) * pi / 2.0_dp) ) ! Move the ant in x ant(2) = ant(2) + nint( cos(ant(3) * pi / 2.0_dp) ) ! Move the ant in y
!exit if the ant is outside the grid if (((ant(1) < 1) .or. (ant(1) > grid_size)) .or. ((ant(2) < 1) .or. (ant(2) > grid_size))) exit
end do
!Print out the final grid open(unit=21, file="ant.dat") do i = 1, grid_size write(21,*) int(grid(:,i) + 1 / 2.0_dp) end do close(21)
deallocate(grid)
end program langtons_ant </lang>
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){ 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; } } plane[antY][antX] = !plane[antY][antX]; antX += xChange; antY += yChange; } return plane; } }</lang> Output (click for a larger view):
JavaScript
Utilises the HTML5 canvas element to procedurally generate the image... I wanted to see the progress of the grid state as it was generated, so this implementation produces a incrementally changing image until an 'ant' hits a cell outside of the coordinate system. It can also accept multiple ants, this adds minimal complexity with only the addition of an 'ants' array which is iterated in each step, no additional conditions are necessary to simulate multiple ants, they coexist quite well... good ants ! 1st argument is an array of ant objects, 2nd argument is an object property list of options to change grid size, pixel size and interval (animation speed).
<lang JavaScript> // create global canvas var canvas = document.createElement('canvas'); canvas.id = 'globalCanvas'; document.body.appendChild(canvas);
function langtonant(antx, optx) { 'use strict'; var x, y, i;
// extend default opts var opts = { gridsize: 100, pixlsize: 4, interval: 4 }; for (i in optx) { opts[i] = optx[i]; }
// extend default ants var ants = [{ x: 50, y: 50, d: 0 }]; for (i in antx) { ants[i] = antx[i]; }
// initialise grid var grid = []; for (x = 0; x < opts.gridsize; x ++) { grid[x] = []; for (y = 0; y < opts.gridsize; y ++) { grid[x][y] = true; } }
// initialise directions var dirs = [ {x: 1, y: 0}, {x: 0, y: -1}, {x: -1, y: 0}, {x: 0, y: 1} ];
// initialise canvas var canv = document.getElementById('globalCanvas'); var cont = canv.getContext('2d'); canv.width = opts.gridsize * opts.pixlsize; canv.height = opts.gridsize * opts.pixlsize;
// initialise pixels var pixlblac = cont.createImageData(opts.pixlsize, opts.pixlsize); for (i = 0; i < (opts.pixlsize * opts.pixlsize * 4); i += 4) { pixlblac.data[i + 3] = 255; } var pixlwhit = cont.createImageData(opts.pixlsize, opts.pixlsize); for (i = 0; i < (opts.pixlsize * opts.pixlsize * 4); i += 4) { pixlwhit.data[i + 3] = 0; }
// run simulation function simulate() { var sane = true;
// iterate over ants for (i = 0; i < ants.length; i ++) { var n = ants[i];
// invert, draw, turn if (grid[n.x][n.y]) { grid[n.x][n.y] = false; cont.putImageData(pixlblac, n.x * opts.pixlsize, n.y * opts.pixlsize); n.d --; } else { grid[n.x][n.y] = true; cont.putImageData(pixlwhit, n.x * opts.pixlsize, n.y * opts.pixlsize); n.d ++; }
// modulus wraparound n.d += dirs.length; n.d %= dirs.length;
// position + direction n.x += dirs[n.d].x; n.y += dirs[n.d].y;
// sanity check sane = (n.x < 0 || n.x > opts.gridsize || n.y < 0 || n.y > opts.gridsize) ? false : sane; }
// loop with interval if (sane) { setTimeout(simulate, opts.interval); } }
simulate(); } </lang>
Usage: default ants, custom opts
<lang JavaScript> langtonant({}, { gridsize: 100, pixlsize: 4, interval: 4 }); </lang>
- Output:
Usage: custom ants, default opts
<lang JavaScript> langtonant([ { x: (100 / 2) + 7, y: (100 / 2) + 7, d: 1 }, { x: (100 / 2) + 7, y: (100 / 2) - 7, d: 2 }, { x: (100 / 2) - 7, y: (100 / 2) - 7, d: 3 }, { x: (100 / 2) - 7, y: (100 / 2) + 7, d: 0 } ]); </lang>
- Output:
Liberty BASIC
Native graphics. <lang lb>dim arena(100,100) black=0 white=not(black) for i = 1 to 100
for j = 1 to 100 arena(i,j)=white next
next 'north=1 east=2 south=3 west=4
nomainwin graphicbox #1.g, 0, 0, 100, 100 open "Langton's Ant" for window as #1
- 1 "trapclose Quit"
- 1.g "down"
antX=50:antY=50 nsew=1 'ant initially points north
while (antX>0) and (antX<100) and (antY>0) and (antY<100)
if arena(antX,antY) then nsew=nsew-1 if nsew<1 then nsew=4 else nsew=nsew+1 if nsew>4 then nsew=1 end if
select case nsew case 1: antY=antY-1 case 2: antX=antX+1 case 3: antY=antY+1 case 4: antX=antX-1 end select
arena(antX,antY)=not(arena(antX,antY)) #1.g "color ";GetColor$(antX,antY) #1.g "set ";antX;" ";antY
wend
- 1.g "flush"
wait
function GetColor$(x,y)
if arena(x,y) then GetColor$="white" else GetColor$="black" end if end function
sub Quit handle$
close #handle$ end end sub </lang>
Text version. <lang lb> '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>
Locomotive Basic
<lang locobasic>10 mode 1:defint a-z:deg 20 ink 1,0:ink 0,26 30 x=50:y=50:ang=270 40 dim play(100,100) 50 graphics pen 3:move 220,100:drawr 200,0:drawr 0,200:drawr -200,0:drawr 0,-200 60 ' move ant 70 if play(x,y) then ang=ang-90 else ang=ang+90 80 play(x,y)=1-play(x,y) 90 plot 220+2*x,100+2*y,play(x,y) 100 ang=ang mod 360 110 x=x+sin(ang) 120 y=y+cos(ang) 130 if x<1 or x>100 or y<1 or y>100 then end 140 goto 70</lang>
Output:
LOLCODE
<lang LOLCODE>HAI 1.3
I HAS A plane ITZ A BUKKIT IM IN YR init UPPIN YR i TIL BOTH SAEM i AN 10000
plane HAS A SRS i ITZ FAIL
IM OUTTA YR init
I HAS A x ITZ 50, I HAS A y ITZ 50 I HAS A dir ITZ 0, I HAS A pos, I HAS A cell
BTW, WE PURRTIND WE HAS A 2D STRUKSHUR FUR EZ AKSESS IM IN YR walker
pos R SUM OF PRODUKT OF y AN 100 AN x cell R NOT plane'Z SRS pos plane'Z SRS pos R cell dir R MOD OF SUM OF dir AN SUM OF 5 AN PRODUKT OF cell AN 2 AN 4
dir, WTF? OMG 0, x R SUM OF x AN 1, GTFO OMG 1, y R DIFF OF y AN 1, GTFO OMG 2, x R DIFF OF x AN 1, GTFO OMG 3, y R SUM OF y AN 1, GTFO OIC
BTW, CHEKIN TEH ANTZ BOUNDZ WON OF BOTH SAEM x AN -1 AN BOTH SAEM x AN 100, O RLY?, YA RLY, GTFO, OIC WON OF BOTH SAEM y AN -1 AN BOTH SAEM y AN 100, O RLY?, YA RLY, GTFO, OIC
IM OUTTA YR walker
IM IN YR printer UPPIN YR cell TIL BOTH SAEM cell AN 10000
plane'Z SRS cell, O RLY? YA RLY, VISIBLE "#"! NO WAI, VISIBLE "."! OIC
NOT MOD OF SUM OF cell AN 1 AN 100, O RLY?, YA RLY, VISIBLE "", OIC
IM OUTTA YR printer BTW, UR OUTTA CYAN
KTHXBYE</lang>
Lua
For this example, the lua Socket and Curses modules and a terminal with enough lines are needed. <lang LUA>local socket = require 'socket' -- needed for socket.sleep local curses = require 'curses' -- used for graphics
local naptime = 0.02 -- seconds local world_x, world_y = 100, 100
local world = (function (x, y) local wrl = {} for i = 1, y do wrl[i] = {} for j = 1, x do wrl[i][j] = 0 end end return wrl end)(world_x, world_y)
-- directions: 0 up, clockwise local ant = { x = math.floor(world_x / 2), y = math.floor(world_y / 2), dir = 0, step = function(self) if self.dir == 0 then self.y = self.y - 1 elseif self.dir == 1 then self.x = self.x + 1 elseif self.dir == 2 then self.y = self.y + 1 else self.x = self.x - 1 end end }
world.step = function (self, ant) if self[ant.y][ant.x] == 0 then -- white -- change cell color self[ant.y][ant.x] = 1 -- change dir ant.dir = (ant.dir + 1) % 4 ant:step() -- boundary conditions if ant.x < 1 then ant.x = world_x elseif ant.x > world_x then ant.x = 1 end if ant.y < 1 then ant.y = world_y elseif ant.y > world_y then ant.y = 1 end else -- change cell color self[ant.y][ant.x] = 0 -- change dir ant.dir = (ant.dir - 1) % 4 ant:step() -- boundary conditions if ant.x < 1 then ant.x = world_x elseif ant.x > world_x then ant.x = 1 end if ant.y < 1 then ant.y = world_y elseif ant.y > world_y then ant.y = 1 end end end
world.draw = function (self, ant) for i = 1, #self do for j = 1, #self[i] do if i == ant.y and j == ant.x then win:attron(curses.color_pair(3)) win:mvaddch(i,j,"A") --win:attroff(curses.color_pair(3)) elseif self[i][j] == 0 then win:attron(curses.color_pair(1)) win:mvaddch(i,j," ") --win:attroff(curses.color_pair(1)) elseif self[i][j] == 1 then win:attron(curses.color_pair(2)) win:mvaddch(i,j," ") --win:attroff(curses.color_pair(2)) else error("self[" .. i .. "][" .. j .. "] is " .. self[i][j] .. "!") end end end end
local it = 1 curses.initscr() curses.start_color() curses.echo(false) curses.init_pair(1, curses.COLOR_WHITE, curses.COLOR_WHITE) curses.init_pair(2, curses.COLOR_BLACK, curses.COLOR_BLACK) curses.init_pair(3, curses.COLOR_RED, curses.COLOR_WHITE) curses.init_pair(4, curses.COLOR_WHITE, curses.COLOR_BLACK) win = curses.newwin(world_y + 1, world_x, 0, 0) win:clear() repeat world:draw(ant) win:move(world_y, 0) win:clrtoeol() win:attron(curses.color_pair(4)) win:addstr("Iteration: " .. it .. ", nap = " .. naptime*1000 .. "ms") win:refresh() world:step(ant) it = it + 1 --local c = stdscr:getch() --if c == '+' then naptime = naptime - (naptime / 10) --elseif c == '-' then naptime = naptime + (naptime / 10) --end socket.sleep(naptime) until false </lang>
MATLAB / Octave
<lang MATLAB>function u = langton_ant(n) if nargin<1, n=100; end; A = sparse(n,n); % white P = [n/2;n/2]; % Positon D = 3; % index of direction 0-3 T = [1,0,-1,0;0,1,0,-1]; % 4 directions k = 0; while (1) k = k+1; a = A(P(1),P(2)); A(P(1),P(2)) = ~a; if ( a ) D = mod(D+1,4); else D = mod(D-1,4); end; P = P+T(:,D+1);
if (~mod(k,100)),spy(A);pause(.1);end; %display after every 100 interations end; end</lang>
Mathematica
<lang mathematica>direction = 1; data = SparseArray[{{50, 50} -> -1}, {100, 100}, 1]; NestWhile[
{Re@#, Im@#} &@(direction *= (dataSequence @@ # *= -1) I) + # &, {50, 50}, 1 <= Min@# <= Max@# <= 100 &];
Image@data</lang>
Nimrod
<lang nimrod>import strutils
type
Direction = enum up, right, down, left Color = enum white, black
const
width = 75 height = 52 maxSteps = 12_000
var
m: array[height, array[width, Color]] dir = up x = width div 2 y = height div 2
var i = 0 while i < maxSteps and x in 0 .. < width and y in 0 .. < height:
let turn = m[y][x] == black m[y][x] = if m[y][x] == black: white else: black
dir = Direction((4 + int(dir) + (if turn: 1 else: -1)) mod 4) case dir of up: dec y of right: dec x of down: inc y of left: inc x
inc i
for row in m:
echo map(row, proc(x): string = if x == white: "." else: "#").join("")</lang>
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] ||= 0)) { # 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>
PHP
This is an implementation of Langton`s Ant in PHP
(The TEXT TO IMAGE - part is obviously not necessary.
Additionally the x and y startpositions could be set
to the halves of width and height.)
<lang php>
// INIT AND DEFINITION
define('dest_name', 'output.png'); // destination image
define('width', 100);
define('height', 100);
$x = 50; $y = 70; $dir = 0; // 0-up, 1-left, 2-down, 3-right $field = array(); $step_count = 0;
// LANGTON´S ANT PROCEDURE while(0 <= $x && $x <= width && 0 <= $y && $y <= height){ if(isset($field[$x][$y])){ unset($field[$x][$y]); $dir = ($dir + 3) % 4; }else{ $field[$x][$y] = true; $dir = ($dir + 1) % 4; } switch($dir){ case 0: $y++; break; case 1: $x--; break; case 2: $y--; break; case 3: $x++; break; } $step_count++; } // ARRAY TO IMAGE $img = imagecreatetruecolor(width, height); $white = imagecolorallocate($img, 255, 255, 255); for($x = 0; $x < width; $x++){ for($y = 0; $y < height; $y++){ if(isset($field[$x][$y])){ imagesetpixel($img, $x, $y, $white); } } } // TEXT TO IMAGE $color = array(); $color[0] = imagecolorallocate($img, 255, 0, 0); $color[1] = imagecolorallocate($img, 0, 255, 0); $color[2] = imagecolorallocate($img, 0, 0, 255); $print_array = array( 0 => 'Langton`s Ant', 1=>'PHP Version', 2=>'Steps: ' . $step_count ); foreach($print_array as $key => $line){ imagestring($img, 3, 3, 3 + $key*11, $line, $color[$key]); } // SAVE IMAGE imagepng($img, dest_name); </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: left, 2: down: 3: right * * 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; //white =-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>
Prolog
This sort of problem, when stated in Prolog, reads a bit like a story book. Our main goal (go) succeeds if we can move north from the middle of the 100x100 matrix, and update_win- which outputs the black/1 blocks. The move/3 and direction/3 goals are really quite self explanatory, mirroring the instructions for the task.
<lang prolog>%_______________________________________________________________ % Langtons ant.
- -dynamic
black/1.
plot_point(Row, Col) :- % Output a 5x5 black box at R,C new(C, box(5,5)), X is Col * 5 - 2, Y is Row * 5 - 2, send(C, colour, colour(black)), send(C, fill_pattern, colour(blue)), send(C, center(point(X,Y))), send(@win, display, C). update_win :- % Make a 500x500 window, find all the black points and plot them new(@win, window('Langtons Ant')), send(@win, size, size(500,500)), send(@win, open), black(Row/Col),plot_point(Row,Col),fail. update_win.
direction(Row, Col, left) :- black(Row/Col), !, retract(black(Row/Col)). direction(Row, Col, right):- not(black(Row/Col)), !, assert(black(Row/Col)).
move(_, Row,Col) :- (Row < 0; Col < 0; Row > 99; Col > 99), !. move(north,Row,Col) :- (direction(Row,Col,left), C is Col - 1, !, move(west, Row, C)); (direction(Row,Col,right), C is Col + 1, !, move(east, Row, C)). move(south,Row,Col) :- (direction(Row,Col,right), C is Col - 1, !, move(west, Row, C)); (direction(Row,Col,left), C is Col + 1, !, move(east, Row, C)). move(east,Row,Col) :- (direction(Row,Col,right), R is Row + 1, !, move(south, R, Col)); (direction(Row,Col,left), R is Row - 1, !, move(north, R, Col)). move(west,Row,Col) :- (direction(Row,Col,left), R is Row + 1, !, move(south, R, Col)); (direction(Row,Col,right), R is Row - 1, !, move(north, R, Col)).
go :- retractall(black(_)), move(north,49,49), update_win.</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.
R
<lang R> langton.ant = function(n = 100) { map = matrix(data = 0, nrow = n, ncol = n) p = floor(c(n/2, n/2)) d = sample(1:4, 1) i = 1 while(p[1] > 0 & p[1] <= n & p[2] > 0 & p[2] <= n) { if(map[p[1], p[2]] == 1) { map[p[1], p[2]] = 0 p = p + switch(d, c(0, 1), c(-1, 0), c(0, -1), c(1, 0)) d = ifelse(d == 4, 1, d + 1) } else { map[p[1], p[2]] = 1 p = p + switch(d, c(0, -1), c(1, 0), c(0, 1), c(-1, 0)) d = ifelse(d == 1, 4, d - 1) } } return(map) }
image(langton.ant(), xaxt = "n", yaxt = "n", bty = "n") </lang>
Racket
This Racket program attempts to avoid mutation.
<lang racket>#lang racket
- contracts allow us to describe expected behaviour of funcitons
(define direction/c (or/c 'u 'r 'l 'd)) (define turn/c (-> direction/c direction/c)) (define grid/c (hash/c integer? (hash/c integer? boolean?))) (define-struct/contract ant ([d direction/c] [x integer?] [y integer?]))
(define/contract (turn-right dir) turn/c
(case dir ((u) 'r) ((d) 'l) ((r) 'd) ((l) 'u)))
(define/contract (turn-left dir) turn/c
(case dir ((u) 'l) ((d) 'r) ((r) 'u) ((l) 'd)))
(define/contract (move d x y)
(-> direction/c integer? integer? (list/c direction/c integer? integer?)) (list d (+ x (case d ((l) -1) ((r) 1) (else 0))) (+ y (case d ((u) -1) ((d) 1) (else 0)))))
(define/contract (move-ant d a) (-> direction/c ant? ant?)
(apply make-ant (move d (ant-x a) (ant-y a))))
(define/contract (langton a grid) (-> ant? grid/c grid/c)
(let ((ax (ant-x a)) (ay (ant-y a))) (if (and (<= 1 ax 100) (<= 1 ay 100)) (let* ((grid-row (hash-ref grid ay hash)) (cell-black? (hash-ref grid-row ax #f))) (langton (move-ant ((if cell-black? turn-left turn-right) (ant-d a)) a) (hash-set grid ay (hash-set grid-row ax (not cell-black?))))) grid)))
(define/contract (show-grid/text grid) (-> grid/c void?)
(for* ; for* allows us to refer to y in rw ((y (in-range 1 101)) (rw (in-value (hash-ref grid y #f))) #:when rw ; if there is no row, the ant never visisted it #:when (newline) ; when can be used simply for its side effect (x (in-range 1 101))) (case (hash-ref rw x #\?) ((#\?) (display #\space)) ; distingush between "ant-visited white" vs. pure white ((#f) (display #\:)) ; little anty footprints left ((#t) (display #\#)))))
(show-grid/text (langton (make-ant 'u 50 50) (hash)))
(require 2htdp/image) (define/contract (show-grid/png grid) (-> grid/c image?)
(for*/fold ((scn (empty-scene 408 408))) ((y (in-range 1 101)) (rw (in-value (hash-ref grid y #f))) #:when rw ; if there is no row, the ant never visisted it (x (in-range 1 101))) (case (hash-ref rw x #\?) ((#\?) scn) ; distingush between "ant-visited white" vs. pure white ((#f) (place-image (circle 2 "outline" "gray") (* x 4) (* y 4) scn)) ; little anty footprints left ((#t) (place-image (circle 2 "solid" "black") (* x 4) (* y 4) scn)))))
(show-grid/png (langton (make-ant 'u 50 50) (hash))) </lang> Output (text):
## ############ ## #::####::::::::::# :## ###:::##::::::::::::##:# #:#::#:::::::::#::#::::# ## ##:#:#:::::::::###:::::::# ###:#::#:::#:::::#:::::##:##::### :#:#::###::##:####:##:::#:#::#:## ## :#:###:##: #:##::###:#:#:::::###:::### #:::::#:::#####:#:#::####::#:::###:#:#:# ###:##:::#:####::##:##:######:#:###:#:::# #:###:#:##:#:#:##:##:##:#:::#####:###:## ::#:#:::#:##:###:::#:::#:#::####::::# ## #::#:::::::::##:##:::#::##:::::##:#::: :## ###:::#:#:##:###::#::##:::::#:::###:##::##:# #::###::##:::##:##:::###::#::::#::##:####:::# ###:::#:::#:#::#:#:####:##::#:##:###::#:::::# #::###::#:##::::#::#:###::#::::::###:##:#::#: ## ###:::#::: #:##:#:##::##::#####:####::####:##:::# #::###::#:# #::#:###:#:#:##::::::##:::#:#:#:: #:::# ###:::#::## ###::##:#:::##:::::::####:####:::#::::::# #::###::#:# #:::##::###########:#::####::#::: #::::# ###:::#::## :#:####::##::#########::#::##::::#::## #::###::#:# ## :#:##:::##:##:###:###:::#::#:##::####:# ###:::#::## #::#:######:##:#:##:#:#::::###:###:::##:::# #::###::#:# #:::::#####:#:#####:::::#:#::##:#::::##:::# ###:::#::## #:::::#:##:#####:##::#:#:::#::#::##:# :#::# #::###::#:# #::::#:::####:#::#####:##:::##########:::## ###:::#::## #:##:::##:::#::#:::####::#:::##:####:##::: #::###::#:# #####:#::##:::##:#:::#::::#:#::#::#::#:#: ###:::#::## ## ## #:#:#::::##:##:#:#:##::#::##::##: #::###::#:# #::#: #:########:#:#:##::####:#: ###:::#::## #::#: #:::::::##:##:::#::#::##:#: #::###::#:# #::# #::::::#::##::##:::##:####: ###:::#::## ## #:::::::##::##::::#:::#:### #::###::#:# #:##::####::::####:###:#### ###:::#::## ##: ####: ##: #:##:#:#::# #::###::#:# ## ## ## ###:##:##### ###:::#::## #:##:#::#### #::###::#:# :##:##:## ###:::#::## :##:::::: #::###::#:# #:##::####:# ###:::#::## #::#:###::### #::###::#:# #:##:# #::# ###:::#::## ##: ## :::##::#:# ## ##::#::## #:#:#:# ####:## #:##:# #### ##
REXX
This REXX program automatically justifies (or crops) the left, right, top and bottom of the ant's walk field on the screen.
Or in other words, this REXX program only shows the pertinent part of the ant's walk-field.
<lang rexx>/*REXX program implements Langton's ant and displays the path it walked.*/
parse arg dir . /*allow specification: ant facing*/
/*binary colors: 0=white, 1=black*/
@.=0 /*define stem array (all white).*/ lb=1 ; rb=100 /* left boundry, right boundry.*/ bb=1 ; tb=100 /*bottom " top " */ x=(rb-lb)%2 ; y=(tb-bb)%2 /*approximate center (walk start)*/ if dir== then dir=random(1,4) /*ant is facing random direction,*/
/*1=north 2=east 3=south 4=west*/
/*───────────────────────────────────────────ant walks hither & thither.*/
do steps=1 until x<lb | x>rb | y<bb | y>tb /*walk until out-of-bounds*/ black=@.x.y /*get color code of ant's cell. */ @.x.y=\@.x.y /*"flip" the color of the cell. */ if black then dir=dir-1 /*if cell was black, turn left. */ else dir=dir+1 /* " " " white, " right. */ if dir==0 then dir=4 /*ant should be facing "west". */ if dir==5 then dir=1 /* " " " " "north". */ select /*ant walks direction it's facing*/ when dir==1 then y=y+1 /*walking north? Then go "up". */ when dir==2 then x=x+1 /* " east? " " "right"*/ when dir==3 then y=y-1 /* " south? " " "down".*/ when dir==4 then x=x-1 /* " west? " " "left".*/ end /*select*/ end /*steps*/
/*───────────────────────────────────────────the ant is finished walking*/ say center(" Langton's ant walked" steps 'steps. ',79,"─"); say
/*Display Langton's ant's trail. */ do minx =lb to rb /*find leftmost non-blank column.*/ do y=bb to tb /*search row by row for it. */ if @.minx.y then leave minx /*found one, now quit searching. */ end /*y*/ end /*minx*/ /*above code crops left of array.*/
do y=tb to bb by -1; _= /*display a plane (row) of cells.*/ do x=minx to rb /*process a "row" of cells. */ _=_ || @.x.y /*build a cell row for display. */ end /*x*/ _=translate(_,'#',10) /*color the cells: black | white.*/ if _\= then say strip(_,'T') /*say line, strip trailing blanks*/ end /*y*/ /*stick a fork in it, we're done.*/</lang>
output
────────────────────── Langton's ant walked 11759 steps. ────────────────────── ## #### # ## # ## #### # # # # ## # ## # # ## ## # ### ## # # ### # ## ## ## # ### # # # ## # # # ### # ### ### # # ## # ### # #### ## # # # ### # ## ## # ### ## ## ## # # ### # #### # ## # ## # ### ##### ## ### ## ## ## # # ### # # # # ## # ## #### ## ## # ### #### ### #### #### ## # # # ### # ### # # ## ## # ## ## # ### #### ## ## ## # # # # # # ### # # ## # # ## ## # # # ## # ### # #### ## # # ######## # # # # # ### # ## ## # ## # # ## ## # # # ## ## ## # ### # # # # # # # # ## ## # ##### # # ### # ## #### ## # #### # # ## ## # ## # ### ## ########## ## ##### # #### # # # # ### # # # # ## # # # # ## ##### ## # # ## # ### # ## # ## # # ##### # ##### # # # ### # # ## ### ### # # ## # ## ###### # # ## # ### # #### ## # # ### ### ## ## ## # ## # # ### # ## # ## # ######### ## #### # ## # ### # # # #### # ########### ## # # # ### # # # #### #### ## # ## ### ## # ### # # # # # ## ## # # ### # # # # ### # # ## #### #### ##### ## ## # ## # # ### ## # # ## ### # ### # # ## # ### # # # ### ## # ## #### # # # # # ### # #### ## # # ### ## ## ## ### # # ## ## ### # ## # ### ## # # ### ## # ## ## # ## ## # # ## # #### # # # ### ## # # # ## ### ##### # ## ## ## # # ## # ### # # # ### # ###### ## ## #### # ## ### # # # ### # #### # # ##### # # ### ### # # ### ## # ## ### # ## ## # # # ## #### ## ### # # ### ## ## # # # # ### # ### # # ## ## # # # # # # # ## ## ### ## # #### # ## ############ ##
Ruby
<lang ruby>class Ant
class OutOfBoundsException < StandardError; end class Plane def initialize(x, y) @size_x, @size_y = x, y @cells = Array.new(y) {Array.new(x, :white)} end def white?(px, py) @cells[py][px] == :white end def toggle_colour(px, py) @cells[py][px] = (white?(px, py) ? :black : :white) end def check_bounds(px, py) unless (0 <= px and px < @size_x) and (0 <= py and py < @size_y) raise OutOfBoundsException, "(#@size_x, #@size_y)" end end def to_s @cells.collect {|row| row.collect {|cell| cell == :white ? "." : "#"}.join + "\n" }.join end end dir_move = [[:north, [0,-1]], [:east, [1,0]], [:south, [0,1]], [:west, [-1,0]]] Move = Hash[dir_move] directions = dir_move.map{|dir, move| dir} # [:north, :east, :south, :west] Right = Hash[ directions.zip(directions.rotate).to_a ] Left = Right.invert def initialize(size_x, size_y, pos_x=size_x/2, pos_y=size_y/2) @plane = Plane.new(size_x, size_y) @pos_x, @pos_y = pos_x, pos_y @direction = :south @plane.check_bounds(@pos_x, @pos_y) end def run moves = 0 loop do begin moves += 1 move rescue OutOfBoundsException break end end moves end def move @plane.toggle_colour(@pos_x, @pos_y) advance if @plane.white?(@pos_x, @pos_y) @direction = Right[@direction] else @direction = Left[@direction] end end def advance dx, dy = Move[@direction] @pos_x += dx @pos_y += dy @plane.check_bounds(@pos_x, @pos_y) end def position "(#@pos_x, #@pos_y)" end def to_s @plane.to_s end
end
- the simulation
ant = Ant.new(100, 100) moves = ant.run puts "out of bounds after #{moves} moves: #{ant.position}" puts ant</lang>
- Output:
out of bounds after 11669 moves: (26, -1) ..........................#.#....................................................................... ........................##.#.#...................................................................... .......................#.###.##..................................................................... ......................####.###.#.................................................................... ......................#####.#..##................................................................... .......................#...##.##.#.................................................................. ........................###...#..##................................................................. .........................#...##.##.#................................................................ ..........................###...#..##............................................................... ...........................#...##.##.#.............................................................. ............................###...#..##............................................................. .............................#...##.##.#............................................................ ..............................###...#..##........................................................... ...............................#...##.##.#.......................................................... ................................###...#..##......................................................... .................................#...##.##.#........................................................ ..................................###...#..##....................................................... ...................................#...##.##.#...................................................... ....................................###...#..##..................................................... .....................................#...##.##.#.................................................... ......................................###...#..##................................................... .......................................#...##.##.#.................................................. ........................................###...#..##................................................. .........................................#...##.##.#................................................ ..........................................###...#..##............................................... ...........................................#...##.##.#.............................................. ............................................###...#..##............................................. .............................................#...##.##.#............................................ ..............................................###...#..##........................................... ...............................................#...##.##.#.......................................... ................................................###...#..##......................................... .................................................#...##.##.#..##.................................... ..................................................###...#..##..##................................... ...................................................#...##.##..##...#................................ .............................................####...###...#...#..###................................ ............................................#....#...#...##.####...#................................ ...........................................###....#...#.#......#.##.#............................... ...........................................###....#.##.....#.##..#.##............................... ............................................#....#...##.#.#.....##.................................. ............................................#.#......#.#####..#...#................................. ...........................................#...#####..........##.######............................. ...........................................###..##..#.##.#.#.#...##.#.##............................ .........................................##..#.#######.#...#..###....##.#........................... ........................................#..#..######.##...#..#.##...#...#........................... .......................................#....#.#.##.#..######.#######...#............................ .......................................#.####.##.#.####....##..##.#.##.#............................ ........................................#....####...#..#.######.##....###........................... ...........................................#...#.##.#.###.#..##..##...###........................... ..............................................#######....#..##.##.#.....#........................... ......................................####..##.##..####.##.##.##..#.....#........................... .....................................#....#.#...###.##.###....#.####....#........................... ....................................###.......###.#.#.#####....#.#......#........................... ....................................#.#...###.####.##.#...##.###.##.....#........................... ..........................................##.##..####....####.#.#.#.....#........................... .....................................#....#..##...###..###.....###......#........................... .....................................##...##.###.####..#......###...##..#........................... .....................................##.#.####.....#...#..#.##.###.##...#........................... ....................................####.##...##.####..#.#..#..#..###...#........................... ....................................#.##.###..#.#.##.#.#.....#.#.....#.#............................ ........................................#.#..#....##.##..#.#..###.##................................ ........................................##.#....#..#####.#....#....#..#.#........................... .......................................#.##.#..#....##.##.#..###......###........................... .....................................#.#...#..#..#..#..###...##..##....#............................ ....................................###.#.#####.######.###.#######.#.##............................. ....................................#.#.#....#####...##..#####.#####................................ ......................................#..##...#......#..#.##..###.###............................... ...................................####...#####.#########...#.#..................................... ..............................##....#..#.....###.#.#...#.###..###................................... .............................#..#..####.##...###.##...###.##.....##................................. ............................###....#.##.#.#####...#....#..#..##.###................................. ............................#.#####.#.#...##..##.....#....#...#..#.................................. ................................######.####..##.#...#..##..#.#.##................................... ..............................##......#.###.##..####...#...###...................................... ...............................#..#.#####..#...#.##...#..#..#....................................... ...............................##.###.#######.....#.....#.##........................................ ..............................#.#..##.##......#...##....#........................................... .............................#..#.####........###..##..#............................................ .............................#.##.###............##..##............................................. ..............................##.................................................................... ...............................##................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... ....................................................................................................
Simple Version: <lang ruby>class Ant
MOVE = [[1,0], [0,1], [-1,0], [0,-1]] # [0]:east, [1]:south, [2]:west, [3]:north def initialize(size_x, size_y, pos_x=size_x/2, pos_y=size_y/2) @plane = Array.new(size_y) {Array.new(size_x, true)} # true -> white, false -> black @sx, @sy = size_x, size_y @px, @py = pos_x, pos_y # start position @direction = 0 # south @moves = 0 move while (0 <= @px and @px < @sx) and (0 <= @py and @py < @sy) end def move @moves += 1 @direction = (@plane[@py][@px] ? @direction+1 : @direction-1) % 4 @plane[@py][@px] = !@plane[@py][@px] @px += MOVE[@direction][0] @py += MOVE[@direction][1] end def to_s ["out of bounds after #{@moves} moves: (#@px, #@py)"] + (0...@sy).map {|y| (0...@sx).map {|x| @plane[y][x] ? "." : "#"}.join} end
end
puts Ant.new(100, 100).to_s</lang>
- Output is the same above.
Run BASIC
<lang Runbasic>dim plane(100,100) x = 50: y = 50: minY = 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) minY = min(y,minY) ' find lowest and maxY = max(y,maxY) ' highest y to prevent printing blank lines
wend
graphic #g, 100,100 for y = minY to maxY
for x = 1 to 100 print chr$((plane(x,y)*3) + 32); if plane(x,y) = 1 then #g "color green ; set "; x; " "; y else #g "color blue ; set "; x; " "; y next x print y
next y render #g
- g "flush""</lang>
Ouptut (Produces both character and graphic):
20 ## 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
Rust
<lang Rust> struct Ant { x: uint, y: uint, dir: Direction }
impl Ant { fn move(&mut self, vec: &mut Vec<Vec<u8>>) {
let pointer = vec.get_mut(self.y).get_mut(self.x); //change direction match *pointer { 0 => self.dir = self.dir.right(), 1 => self.dir = self.dir.left(), _ => fail!("Unexpected colour in grid") } //flip colour //if it's 1 it's black //if it's 0 it's white *pointer ^= 1;
//move direction match self.dir { North => self.y -= 1, South => self.y += 1, East => self.x += 1, West => self.x -= 1, }
} }
enum Direction { North, East, South, West }
impl Direction { fn right(self) -> Direction { match self { North => East, East => South, South => West, West => North, } }
fn left(self) -> Direction { //3 rights equal a left self.right().right().right() } }
fn main(){ //create a 100x100 grid using vectors let mut grid: Vec<Vec<u8>> = Vec::from_elem(100, Vec::from_elem(100, 0u8)); let mut ant = Ant { x: 50, y: 50, dir: North };
while ant.x < 100 && ant.y < 100 { ant.move(&mut grid); } for each in grid.iter() { //construct string //using iterator methods to quickly convert the vector //to a string let string = each.iter() .map(|&x| String::from_byte(x+32)) .fold(String::new(), |x, y| x+y) .replace("!", "#"); println!("{}", string); } } </lang>
Scala
<lang scala>class Langton(matrix:Array[Array[Char]], ant:Ant) {
import Langton._ val rows=matrix.size val cols=matrix(0).size
def isValid = 0 <= ant.row && ant.row < cols && 0 <= ant.col && ant.col < rows def isBlack=matrix(ant.row)(ant.col)==BLACK def changeColor(c:Char)={matrix(ant.row)(ant.col)=c; matrix}
def evolve():Langton={ val (newCol, newAnt)=if(isBlack) (WHITE, ant.turnLeft) else (BLACK, ant.turnRight) new Langton(changeColor(newCol), newAnt.move) } override def toString()=matrix map (_.mkString("")) mkString "\n"
}
case class Ant(row:Int, col:Int, d:Int=0) {
def turnLeft=Ant(row,col,(d-1)&3) def turnRight=Ant(row,col,(d+1)&3) def move=d match { case 0 => Ant(row-1,col,d) // north case 1 => Ant(row,col+1,d) // east case 2 => Ant(row+1,col,d) // south case 3 => Ant(row,col-1,d) // west }
}
object Langton {
val BLACK='#' val WHITE='.' def apply(x:Int=100, y:Int=100)=new Langton(Array.fill(y, x)(WHITE), Ant(x>>>1, y>>>1, 0))
def main(args: Array[String]): Unit = { var l=Langton(100,100) var moves=0 while (l.isValid) { moves += 1 l=l.evolve } println("Out of bounds after "+moves+" moves") println(l) }
}</lang> Output:
Out of bounds after 11669 moves .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... ..........................................##..############..##...................................... .........................................#..####..........#..##..................................... ........................................###...##............##.#.................................... ........................................#.#..#.........#..#....#.................................... ....................................##..##.#.#.........###.......#.................................. .................................###.#..#...#.....#.....##.##..###.................................. ..................................#.#..###..##.####.##...#.#..#.##..##.............................. ..................................#.###.##..#.##..###.#.#.....###...###............................. ................................#.....#...#####.#.#..####..#...###.#.#.#............................ ...............................###.##...#.####..##.##.######.#.###.#...#............................ ...............................#.###.#.##.#.#.##.##.##.#...#####.###.##............................. ...................................#.#...#.##.###...#...#.#..####....#.##........................... ................................#..#.........##.##...#..##.....##.#.....##.......................... ...............................###...#.#.##.###..#..##.....#...###.##..##.#......................... ..............................#..###..##...##.##...###..#....#..##.####...#......................... .............................###...#...#.#..#.#.####.##..#.##.###..#.....#.......................... ............................#..###..#.##....#..#.###..#......###.##.#..#..##........................ ...........................###...#.....#.##.#.##..##..#####.####..####.##...#....................... ..........................#..###..#.#.#..#.###.#.#.##......##...#.#.#....#...#...................... .........................###...#..##.###..##.#...##.......####.####...#......#...................... ........................#..###..#.#..#...##..###########.#..####..#....#....#....................... .......................###...#..##......#.####..##..#########..#..##....#..##....................... ......................#..###..#.#...##..#.##...##.##.###.###...#..#.##..####.#...................... .....................###...#..##...#..#.######.##.#.##.#.#....###.###...##...#...................... ....................#..###..#.#...#.....#####.#.#####.....#.#..##.#....##...#....................... ...................###...#..##....#.....#.##.#####.##..#.#...#..#..##.#..#..#....................... ..................#..###..#.#.....#....#...####.#..#####.##...##########...##....................... .................###...#..##......#.##...##...#..#...####..#...##.####.##........................... ................#..###..#.#........#####.#..##...##.#...#....#.#..#..#..#.#......................... ...............###...#..##..........##..##.#.#.#....##.##.#.#.##..#..##..##......................... ..............#..###..#.#.................#..#....#.########.#.#.##..####.#......................... .............###...#..##..................#..#...#.......##.##...#..#..##.#......................... ............#..###..#.#....................#..#..#......#..##..##...##.####......................... ...........###...#..##......................##...#.......##..##....#...#.###........................ ..........#..###..#.#............................#.##..####....####.###.####........................ .........###...#..##..............................##..####....##..#.##.#.#..#....................... ........#..###..#.#................................##....##....##.###.##.#####...................... .......###...#..##................................................#.##.#..####...................... ......#..###..#.#.....................................................##.##.##...................... .....###...#..##......................................................##............................ ....#..###..#.#.....................................................#.##..####.#.................... ...###...#..##.....................................................#..#.###..###.................... ..#..###..#.#......................................................#.##.#..#..#..................... .###...#..##........................................................##......##...................... #..###..#.#..........................................................##............................. .###.#..##.......................................................................................... #.#.#.#.#........................................................................................... .####.##............................................................................................ .#.##.#............................................................................................. ..####.............................................................................................. ...##............................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... ....................................................................................................
Seed7
<lang seed7>$ include "seed7_05.s7i";
const type: direction is new enum UP, RIGHT, DOWN, LEFT end enum;
const proc: main is func
local const integer: width is 75; const integer: height is 52; var array array boolean: m is height times width times FALSE; var direction: dir is UP; var integer: x is width div 2; var integer: y is height div 2; begin while x in {1 .. width} and y in {1 .. height} do dir := direction conv ((ord(dir) + 2 * ord(m[y][x]) - 1) mod 4); m[y][x] := not m[y][x]; case dir of when {UP}: decr(y); when {RIGHT}: decr(x); when {DOWN}: incr(y); when {LEFT}: incr(x); end case; end while; for key x range m do for y range 1 to width do write(".#"[succ(ord(m[x][y]))]); end for; writeln; end for; end func;</lang>
- Output:
........................................................................... ........................................................................... ........................................................................... ............................##..############..##........................... ...........................#..####..........#..##.......................... ..........................###...##............##.#......................... ..........................#.#..#.........#..#....#......................... ......................##..##.#.#.........###.......#....................... ...................###.#..#...#.....#.....##.##..###....................... ....................#.#..###..##.####.##...#.#..#.##..##................... ....................#.###.##..#.##..###.#.#.....###...###.................. ..................#.....#...#####.#.#..####..#...###.#.#.#................. .................###.##...#.####..##.##.######.#.###.#...#................. .................#.###.#.##.#.#.##.##.##.#...#####.###.##.................. .....................#.#...#.##.###...#...#.#..####....#.##................ ..................#..#.........##.##...#..##.....##.#.....##............... .................###...#.#.##.###..#..##.....#...###.##..##.#.............. ................#..###..##...##.##...###..#....#..##.####...#.............. ...............###...#...#.#..#.#.####.##..#.##.###..#.....#............... ..............#..###..#.##....#..#.###..#......###.##.#..#..##............. .............###...#.....#.##.#.##..##..#####.####..####.##...#............ ............#..###..#.#.#..#.###.#.#.##......##...#.#.#....#...#........... ...........###...#..##.###..##.#...##.......####.####...#......#........... ..........#..###..#.#..#...##..###########.#..####..#....#....#............ .........###...#..##......#.####..##..#########..#..##....#..##............ ........#..###..#.#...##..#.##...##.##.###.###...#..#.##..####.#........... .......###...#..##...#..#.######.##.#.##.#.#....###.###...##...#........... ......#..###..#.#...#.....#####.#.#####.....#.#..##.#....##...#............ .....###...#..##....#.....#.##.#####.##..#.#...#..#..##.#..#..#............ ....#..###..#.#.....#....#...####.#..#####.##...##########...##............ ...###...#..##......#.##...##...#..#...####..#...##.####.##................ ..#..###..#.#........#####.#..##...##.#...#....#.#..#..#..#.#.............. .###...#..##..........##..##.#.#.#....##.##.#.#.##..#..##..##.............. #..###..#.#.................#..#....#.########.#.#.##..####.#.............. .###.#..##..................#..#...#.......##.##...#..#..##.#.............. #.#.#.#.#....................#..#..#......#..##..##...##.####.............. .####.##......................##...#.......##..##....#...#.###............. .#.##.#............................#.##..####....####.###.####............. ..####..............................##..####....##..#.##.#.#..#............ ...##................................##....##....##.###.##.#####........... ....................................................#.##.#..####........... ........................................................##.##.##........... ........................................................##................. ......................................................#.##..####.#......... .....................................................#..#.###..###......... .....................................................#.##.#..#..#.......... ......................................................##......##........... .......................................................##.................. ........................................................................... ........................................................................... ........................................................................... ...........................................................................
Sidef
<lang ruby># 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
const dirs = [[1,0], [0,-1], [-1,0], [0,1]]; const size = 100;
enum |White, Black|;
- initialize the plane with white values
var plane = [];
- start out in approximate middle
- point in a random direction
- initialize the moves counter
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 variable N counts the generation number. <lang TI-83b>PROGRAM:LANT
- ClrDraw
- 0→N
- 47→A
- 31→B
- 90→Θ
- Repeat getKey
- If pxl-Test(B,A)
- Then
- Θ+90→Θ
- Else
- Θ-90→Θ
- End
- Pxl-Change(B,A)
- A+cos(Θ°)→A
- B+sin(Θ°)→B
- N+1→N
- End
</lang>
Whitespace
<lang Whitespace>
</lang>
Following is the pseudo-Assembly from which the above was generated.
<lang asm>; For easier access, the direction vector is stored at the end of the heap. push 10003 dup push 100 store push 1 sub dup push -1 store push 1 sub dup push -100 store push 1 sub dup push 1 store
0: ; Initialize the grid.
push 1 sub dup push 0 store dup push 0 swap sub jn 0 push 5050 ; Start the ant at the center.
1: ; Make sure the ant's in bounds.
dup push 100 mod jn 2 dup push 100 div jn 2 push 100 copy 1 copy 1 mod sub jz 2 push 100 copy 1 copy 1 div sub jz 2
swap copy 1 load ; Get current cell state. push 1 add push 2 mod ; Invert it. copy 2 copy 1 store ; Then store it back. push 2 mul push 5 add add push 4 mod ; Determine new direction. swap copy 1 push 10000 add load add ; Update position accordingly. jump 1
2: ; Initialize a counter and flow into the printer.
pop dup sub
3: ; Iterate over the cells.
dup load push 32 add ochr ; Print ' ' for off, '!' for on. push 1 add dup ; Increment the counter. push 100 mod jz 5 ; Branch at the end of a row. 4: dup push 10000 sub jn 3 ; Go again unless counter is 10000. pop exit ; All done, exit clean.
5: ; Print a newline and jump back to the counter check.
push 10 ochr jump 4</lang>
XPL0
<lang XPL0>include c:\cxpl\codes; \intrinsic 'code' declarations int X, Y, Dir; [SetVid($13); \set 320x200 graphic video mode X:= 50; Y:= 50; Dir:= 0; \start in middle facing east repeat if ReadPix(X,Y) then \(black and white are reversed)
[Dir:= Dir-1;\left\ Point(X,Y, 0\black\)] else [Dir:= Dir+1;\right\ Point(X,Y,$F\white\)]; case Dir & 3 of 0: X:= X+1; \east 1: Y:= Y+1; \south 2: X:= X-1; \west 3: Y:= Y-1 \north other [];
until X<0 ! X>=100 ! Y<0 ! Y>=100; X:= ChIn(1); \wait for keystroke SetVid(3); \restore normal text mode ]</lang>
zkl
Uses the PPM class from http://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm#zkl <lang zkl>white:=0xff|ff|ff; black:=0; w:=h:=100; bitmap:=PPM(w,h,white); x:=w/2; y:=h/2; dir:=0; // start in middle facing east do{
if(bitmap[x,y]){ dir-=1; bitmap[x,y]=black; } // white-->black, turn left else { dir+=1; bitmap[x,y]=white; } // black-->white, turn right switch(dir.bitAnd(3)){ // dir is always <0 case(0){ x+=1; } // east case(1){ y-=1; } // south case(2){ x-=1; } // west case(3){ y+=1; } // north }
}while((0<=x<w) and (0<=y<h));
bitmap.write(File("foo.ppm","wb"));</lang>
- Output:
Same as XPL0 (and using their image).
- Programming Tasks
- Cellular automata
- Ada
- Aime
- AutoHotkey
- AutoIt
- BBC BASIC
- Bc
- C
- C++
- C sharp
- Clojure
- COBOL
- CoffeeScript
- Common Lisp
- D
- Ela
- Erlang
- Euphoria
- Fantom
- Fortran
- Go
- Haskell
- Icon
- Unicon
- Icon Programming Library
- J
- Java
- JavaScript
- Liberty BASIC
- Locomotive Basic
- LOLCODE
- Lua
- MATLAB
- Octave
- Mathematica
- Nimrod
- OCaml
- PARI/GP
- Perl
- Perl 6
- PicoLisp
- PHP
- Processing
- Prolog
- PureBasic
- Python
- R
- Racket
- REXX
- Ruby
- Run BASIC
- Rust
- Scala
- Seed7
- Sidef
- Tcl
- Tk
- TI-83 BASIC
- Whitespace
- XPL0
- Zkl