How to create a Langton's ant in latex?
Here's a simple approach in Metapost wrapped up in the luamplib library - compile with lualatex.
\RequirePackage{luatex85}
\documentclass[border=5mm]{standalone}
\usepackage{luamplib}
\begin{document}
\mplibtextextlabel{enable}
\mplibnumbersystem{double}
\begin{mplibcode}
beginfig(1);
numeric x,y,N;
boolean s[][];
pair heading;
N = 1000;
x = y = 0;
heading = up;
for i=0 upto N:
if not known s[x][y]: s[x][y] := false; fi
if s[x][y]:
s[x][y] := false;
heading := round(heading rotated -90);
else:
s[x][y] := true;
heading := round(heading rotated 90);
fi
x := x + xpart heading;
y := y + ypart heading;
endfor
z0 = (x,y);
numeric n;
n = 42;
for x=-n upto n:
for y=-n upto n:
if known s[x][y]:
if s[x][y]:
drawdot 3(x,y) withpen pencircle scaled 2;
fi
fi
endfor
endfor
drawdot 3z0 withpen pencircle scaled 2.2 withcolor 2/3 red;
%label.urt(decimal N, 3(-n,-n));
endfig;
\end{mplibcode}
\end{document}
With N=1000 (as above), you should get something like this:
If you crank it up a bit and set N=10000, then you get this:
and then at about N=10200 the "highway" starts to appear, so with N=11000 you get:
Note about number sizes and precision
In plain Metapost (even when wrapped up in luamplib) the default number system is Knuth's "scaled" system where the largest absolute value allowed is just under 4096. I've therefore added \mplibnumbersystem{double} in order to be able to set N to values large than 4096, so that we can see the interesting march of the ant.
This has an irritating side effect of making the results of simple operations less exact than in the default system. So with the default number system, when I set
heading = up;
heading gets the value (0,1) so that when I set
heading := heading rotated 90;
heading becomes (-1,0), and both xpart heading and ypart heading always look like integers, so that I can add them to the x and y indexes safely.
But with the double number system
heading := heading rotated 90;
sets heading to (-1,6.123233995736766e-17) which is not quite the same, and means that the parts cannot be used to add to the indexes.
My solution to this irritation was to add round() so that the tiny numbers are rounded to zero as required. round() is defined so that if you apply it to a pair variable it rounds both parts.
Here is a LaTeX solution that uses tikz to draw the world. The rules of Langton's ant according to Wikipedia:
At a white square, turn 90° right, flip the color of the square, move forward one unit.
At a black square, turn 90° left, flip the color of the square, move forward one unit.
The position and direction of the ant is indicated by a red arrow.
% Langton's ant
\documentclass[tikz]{standalone}
\usepackage{tikz}
% boundaries of the known universe
% The boundaries expand automatically as the ant runs.
% If you want to have a stable map that does not expand,
% set the boundaries to some values large enough before letting the ant run.
\newcounter{N}
\newcounter{E}
\newcounter{S}
\newcounter{W}
% position and direction of ant
\newcounter{antx}
\newcounter{anty}
\newcounter{antdir}% 0=N, 1=E, 2=S, 3=W
% \ifIsWhiteSquare{x}{y}{code for white}{code for black}
% white = "\square:x:y is undefined", black = "\square:x:y is defined"
\newcommand\ifIsWhiteSquare[4]{\ifcsname square:#1:#2\endcsname#4\else#3\fi}
\newcommand\setwhite% equate \square:x:y with an undefined macro
{\expandafter\let\csname square:\arabic{antx}:\arabic{anty}\endcsname\undefined}
\newcommand\setblack% define \square:x:y as a macro expanding to nothing
{\expandafter\def\csname square:\arabic{antx}:\arabic{anty}\endcsname{}}
\newcommand\turnright% +1 mod 4
{\stepcounter{antdir}\ifnum\value{antdir}>3\addtocounter{antdir}{-4}\fi}
\newcommand\turnleft% -1 mod 4
{\addtocounter{antdir}{3}\ifnum\value{antdir}>3\addtocounter{antdir}{-4}\fi}
\newcommand\stepforward% add +1/-1 to antx/anty and expand known universe
{\ifcase\value{antdir}%
\stepcounter{anty}%
\ifnum\value{anty}>\value{N}\stepcounter{N}\fi
\or
\stepcounter{antx}%
\ifnum\value{antx}>\value{E}\stepcounter{E}\fi
\or
\addtocounter{anty}{-1}%
\ifnum\value{anty}<\value{S}\addtocounter{S}{-1}\fi
\else
\addtocounter{antx}{-1}%
\ifnum\value{antx}<\value{W}\addtocounter{W}{-1}\fi
\fi
}
% Rules for Langton's ant according to Wikipedia
% - At a white square, turn 90° right, flip the color of the square, move forward one unit.
% - At a black square, turn 90° left, flip the color of the square, move forward one unit.
\newcommand\antstep
{\ifIsWhiteSquare{\arabic{antx}}{\arabic{anty}}%
{\setblack\turnright}%
{\setwhite\turnleft}%
\stepforward
}
% \run does "timer" steps in a row
\newcounter{timer}
\newcommand\run
{\addtocounter{timer}{-1}%
\ifnum\value{timer}<0%
\else
% \expandafter\theUniverse % uncomment for snapshots between steps
\expandafter\antstep
\expandafter\run
\fi
}
\newcommand\ant% mark position and direction of ant with an arrow
{{\boldmath$\ifcase\value{antdir}\uparrow\or\rightarrow\or\downarrow\or\leftarrow\fi$}}
\newcommand\theUniverse
{\begin{tikzpicture}
\draw (\value{W},\value{S}) rectangle (\value{E}+1,\value{N}+1);
\foreach \i in {\arabic{W},...,\arabic{E}}
\foreach \j in {\arabic{S},...,\arabic{N}}
{\ifIsWhiteSquare{\i}{\j}%
{}%
{\draw[fill] (\i,\j) rectangle +(1,1);}%
}
\node[red] at (\arabic{antx}+0.5,\arabic{anty}+0.5) {\ant};
\end{tikzpicture}%
}
\begin{document}
% 11 x 11 grid with ant in the middle heading north
\setcounter{N}{5}%
\setcounter{E}{5}%
\setcounter{S}{-5}%
\setcounter{W}{-5}%
\setcounter{timer}{11000}%
\run
\theUniverse
\end{document}
The gif image was generated by the command
convert -density 300 -delay 30 -loop 0 -background white -alpha remove ant.pdf ant.gif
The pure LaTeX solution is slower than the Lualatex versions, but still fast enough to do 12000 steps within fractions of a second (faster than it takes to draw the final picture).
Requires lualatex. As usual the translation from lua to tikz is a bit clumsy and for speed just the colored cells are extracted and passed to the drawing part.
\RequirePackage{luatex85}
\documentclass[tikz,border=5]{standalone}
\begin{document}
\directlua{
minx = 1; miny = 1; maxx = -1; maxy = -1
x = 0; y = 0; a = 0; t = {}; p = {}; n = 0
for i = 0,10000 do
if x > maxx then maxx = x end; if x < minx then minx = x end
if y > maxy then maxy = y end; if y < miny then miny = y end
t[x] = t[x] or {}
t[x][y] = 1 - (t[x][y] or 0)
a = a - (t[x][y] * 2 - 1) * 90
if a < 0 then a = a + 360 end; if a >= 360 then a = a - 360 end
x = x + ((a == 0) and 1 or 0) - ((a == 180) and 1 or 0)
y = y + ((a == 90) and 1 or 0) - ((a == 270) and 1 or 0)
end
for j = minx,maxx do; for i = miny,maxy do
if (t[j] or {})[i] == 1 then
n = n + 1
p[n] = '(' .. j .. ',' .. i .. ')'
end
end; end
ant = '(' .. x .. ',' .. y .. ')'
}
\edef\n{\directlua{tex.print(n)}}
\begin{tikzpicture}[fill1/.style={fill=black}, x=1pt, y=-1pt]
\foreach \i in {1,...,\n}\fill \directlua{tex.print(p[\i])} circle [radius=0.5];
\fill[red] \directlua{tex.print(ant)} circle [radius=0.375];
\end{tikzpicture}
\end{document}
And here's a more colorful variant where the shade is determined as the number of visits to a cell modulo 20:
\RequirePackage{luatex85}
\documentclass[tikz,border=5]{standalone}
\usepackage{luacode}
\begin{document}
\begin{luacode*}
minx = 1; miny = 1; maxx = -1; maxy = -1
x = 0; y = 0; a = 0; t = {}; p = {}; b = {}; n = 0
for i = 0,10500 do
if x > maxx then maxx = x end; if x < minx then minx = x end
if y > maxy then maxy = y end; if y < miny then miny = y end
t[x] = t[x] or {}
t[x][y] = ((t[x][y] or 0) + 1) % 20
a = a - ((((t[x][y] % 2) == 0) and 1 or 0)* 2 - 1) * 90
if a < 0 then a = a + 360 end; if a >= 360 then a = a - 360 end
x = x + ((a == 0) and 1 or 0) - ((a == 180) and 1 or 0)
y = y + ((a == 90) and 1 or 0) - ((a == 270) and 1 or 0)
end
for j = minx,maxx do; for i = miny,maxy do
c = (t[j] or {})[i] or 0
if c > 0 then
n = n + 1
p[n] = '[fill' .. c .. '/.try] (' .. j .. ',' .. i .. ')'
b[n] = c
end; end
end
ant = '(' .. x .. ',' .. y .. ')'
\end{luacode*}
\edef\n{\directlua{tex.print(n)}}
\begin{tikzpicture}[x=-5pt,y=5pt]
\foreach \i [evaluate={\o=\directlua{tex.print{b[\i]}}*5;}] in {1,...,\n}
\fill \directlua{tex.print(p[\i])} [blue!\o] circle [radius=0.5];
\fill[red] \directlua{tex.print(ant)} circle [radius=0.375];
\end{tikzpicture}
\end{document}
