22
\$\begingroup\$

Draw the path of Langton's ant.

Description

Squares on a plane are colored variously either black or white. We arbitrarily identify one square as the "ant". The ant can travel in any of the four cardinal directions at each step it takes. The ant moves according to the rules below:

  • 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

Specifications

  • Input: an integer N between 0 and 725 (inclusive).
  • Output: a 17 by 17 grid representing the "path" of the ant as of step N.

Rules

  • The ant starts facing right (3 o' clock).
  • The ant starts at the center of the grid.
  • Use _#@ for white squares, black squares and the ant respectively.
  • The grid is initially completely white.
  • You may make either a complete program or a function on an interpreted language.
  • Input by stdin or argument.

Examples

Update: case's N = 450 output was wrong.

N = 0

_________________
_________________
_________________
_________________
_________________
_________________
_________________
_________________
________@________
_________________
_________________
_________________
_________________
_________________
_________________
_________________
_________________

N = 1

_________________
_________________
_________________
_________________
_________________
_________________
_________________
_________________
________#________
________@________
_________________
_________________
_________________
_________________
_________________
_________________
_________________

N = 450

_________________
_________________
___________##____
____##______##___
___#__##___##_#__
__###_#@#__#__#__
__#_#_#_#__#_#___
_____###___#_____
_____#___________
_____#__###______
___#_#_#__#_#_#__
__#__#_#____###__
__#_##__##___#___
___##______##____
____##___________
_________________
_________________
\$\endgroup\$
  • \$\begingroup\$ @Joey: yes "Complete program or function. Input by argument or stdin.", freestyle :) \$\endgroup\$ – Eelvex Mar 14 '11 at 8:52
  • \$\begingroup\$ @Joey: Sorry if that was not clear: you may either make a function on an interpreted language or a complete program. You may take input from stdin or provide it as an argument. \$\endgroup\$ – Eelvex Mar 14 '11 at 13:54
  • \$\begingroup\$ @Joey: Note that at step 1 the ant first turns right (now facing north) and then advances. Are you sure you are taking that into account? \$\endgroup\$ – Eelvex Mar 14 '11 at 13:56
  • \$\begingroup\$ @Joey: Yes, I meant south at the previous comment and you are right, the last example was for different N :-/ (Updated the examples section). \$\endgroup\$ – Eelvex Mar 14 '11 at 14:12

13 Answers 13

10
\$\begingroup\$

GolfScript - 67 chars

~17.'_'*n+*\153:|;{|/()[124^.2/6+:6.1&17*)\2&(*|+:|;]@++}*|/();'@'@

hallvabo's Python solution is the most similar to this, so I'll only describe the main differences.

The board is stored as a string instead of an array. This is so we can update a value on the board with less characters (as strings are always flat), and so getting it to the desired output format is easy.

The ant position is incremented by the formula ((d&1)*17+1)*((d&2)-1) (i.e. .1&17*)\2&(*), where d is the direction. We use the variable 6 so we can skip initialization.

\$\endgroup\$
  • 1
    \$\begingroup\$ Awww, now I feel like a GolfScript noob. \$\endgroup\$ – aaaaaaaaaaaa Mar 19 '11 at 16:20
  • \$\begingroup\$ :6 - so hipster. I'd hate debugging your code :-) \$\endgroup\$ – John Dvorak Dec 9 '13 at 15:18
9
\$\begingroup\$

Ruby 1.9, 104 characters

f=->z{l=[*[r=1]*17,2]*17;c=152;z.times{c+=r=(r*r>1?r/18:-r*18)*l[c]*=-1};l[c]=0;l.map{|a|putc"@_
#"[a]}}

Input via function argument.

  • (146 -> 142) Inlined m
  • (142 -> 140) Check for r*r>1 instead of r.abs>1
  • (142 -> 128) Use String#scan to generate the output. Changed a == to >
  • (128 -> 125) Removed obsolete variable
  • (125 -> 122) Replace String#tr with a conditional
  • (122 -> 122) Now generates the same output as the updated examples
  • (122 -> 111) Use ints instead of chars when generating the ant's path.
  • (111 -> 109) Reorder some expressions to save parentheses
  • (109 -> 108) Code is now a function
  • (108 -> 104) Print every character individually
\$\endgroup\$
  • \$\begingroup\$ Functions are permitted. \$\endgroup\$ – Eelvex Mar 14 '11 at 16:42
  • \$\begingroup\$ @Eelvex: Does the function have to return a string, or does it have to output it? \$\endgroup\$ – Ventero Mar 14 '11 at 16:51
  • \$\begingroup\$ output. \$\endgroup\$ – Eelvex Mar 14 '11 at 17:39
6
\$\begingroup\$

Python, 123

n=input()
d=x=152
g=(17*[95]+[10])*17
while n:d+=g[x]/2;g[x]^=124;x+=(1,-18,-1,18)[d%4];n-=1
g[x]=64
print"%c"*306%tuple(g)

Just a slight reworking of my Python solution from http://golf.shinh.org/p.rb?Langtons+Ant.

\$\endgroup\$
5
\$\begingroup\$

GolfScript 96 94 89

My favourite hate language is back with another bunch of of semi-readable sorta-bytecode.

89 version, I finally managed to integrate @ into the output loop.

~289[0:c]*145:b;{.b>\b<)!..c++(4%:c[1 17-1-17]=b+:b;@++}@*{{(b(:b!.++'_#@@'1/=\}17*n\}17*

94 version:

~306[0:c]*152:b;{.b<\b>(!..c++(4%:c[1 18-1-18]=b+:b;\++}@*{{('_#'1/=\}17*(;n\}17*].b<\b>(;'@'\

Commented:

               #Initialization.
~                  #Parse input.
306[0:c]*          #Make array of 306 0s, set c to 0 in the middle of that operation.
152:b;             #Set b to 152, remove 152 from the stack.
                   #b is a value for the ant's position, c for its rotation.

               #Run the algorithm.
{                  #Start of block.
    .b<\b>(        #Split the array at index b into before, after and value at b.
    !..            #Not the value and make 2 copies of it.
    c++            #Add the 2 copies to c.
    (4%:c          #Subtract 1, modulus by 4 and save the result to c.
    [1 18-1-18]=   #Define an array and take element number c.
    b+:b;          #Add b to the value, save result to b, remove result from stack.
    \++            #Reform the array.
}@*                #Switch the input to the top of the stack and run the block input times.

               #Convert array of 1s and 0s to the correct characters.
{                  #Start of block.
    {              #Start of block.
        ('_#'1/=   #Take the first array element, convert it to either '_' or '#'.
        \          #Switch the array to the top of the stack.
    }17*           #Execute block 17 times.
    (;n\           #Discard the 18th element of the line, write a lineshift.
}17*               #Execute block 17 times.

               #Insert the @.
]                  #Put everything in an array.
.b<\b>(            #Split the array at index b into before, after and value at b.
;'@'\              #Ditch the value at b, write a @ and shift it into place.

Edit, I might as well make a big version, here goes 59*59 and 10500 iterations:

~59:a.*[0:c]*1741:b;{.b>\b<)!..c++(4%:c[1 a-1-59]=b+:b;@++}@*{{(b(:b!.++'_#@@'1/=\}a*n\}a*

.

___________________________________________________________
___________________________________________________________
_________________________##__##____________________________
________________________#__@_###___________________________
_______________________###__#_#_#__________________________
_______________________#####_#__##_________________________
________________________#___##_##_#________________________
_________________________###___#__##_______________________
__________________________#___##_##_#______________________
___________________________###___#__##_____________________
____________________________#___##_##_#__##________________
_____________________________###___#__##__##_______________
______________________________#___##_##__##___#____________
________________________####___###___#___#__###____________
_______________________#____#___#___##_####___#____________
______________________###____#___#_#______#_##_#___________
______________________###____#_##_____#_##__#_##___________
_______________________#____#___##_#_#_____##______________
_______________________#_#______#_#####__#___#_____________
______________________#___#####__________##_######_________
______________________###__##__#_##_#_#_#___##_#_##________
____________________##__#_#######_#___#__###____##_#_______
___________________#__#__######_##___#__#_##___#___#_______
__________________#____#_#_##_#__######_#######___#________
__________________#_####_##_#_####____##__##_#_##_#________
___________________#____####___#__#_######_##____###_______
______________________#___#_##_#_###_#__##__##___###_______
_________________________#######____#__##_##_#_____#_______
_________________####__##_##__####_##_##_##__#_____#_______
________________#____#_#___###_##_###____#_####____#_______
_______________###_______###_#_#_#####____#_#______#_______
_______________#_#___###_####_##_#___##_###_##_____#_______
_____________________##_##__####____####_#_#_#_____#_______
________________#____#__##___###__###_____###______#_______
________________##___##_###_####__#______###___##__#_______
________________##_#_####_____#___#__#_##_###_##___#_______
_______________####_##___##_####__#_#__#__#__###___#_______
_______________#_##_###__#_#_##_#_#_____#_#_____#_#________
___________________#_#__#____##_##__#_#__###_##____________
___________________##_#____#__#####_#____#____#__#_#_______
__________________#_##_#__#____##_##_#__###______###_______
________________#_#___#__#__#__#__###___##__##____#________
_______________###_#_#####_######_###_#######_#_##_________
_______________#_#_#____#####___##__#####_#####____________
_________________#__##___#______#__#_##__###_###___________
______________####___#####_#########___#_#_________________
_________##____#__#_____###_#_#___#_###__###_______________
________#__#__####_##___###_##___###_##_____##_____________
_______###____#_##_#_#####___#____#__#__##_###_____________
_______#_#####_#_#___##__##_____#____#___#__#______________
___________######_####__##_#___#__##__#_#_##_______________
_________##______#_###_##__####___#___###__________________
__________#__#_#####__#___#_##___#__#__#___________________
__________##_###_#######_____#_____#_##____________________
_________#_#__##_##______#___##____#_______________________
________#__#_####________###__##__#________________________
________#_##_###____________##__##_________________________
_________##________________________________________________
__________##_______________________________________________
\$\endgroup\$
5
\$\begingroup\$

Windows PowerShell, 119 118

for($p,$n,$g=144,+"$args"+,1*289;$n--){$d+=$g[$p]*=-1
$p+='B0@R'[$d%4]-65}$g[$p]=0
-join'@_#'[$g]-replace'.{17}',"$&
"
\$\endgroup\$
4
\$\begingroup\$

PHP, 350 309 307 312 174 161 166 159 151 149 147 144 143

<?$p=144;while($i=$argv[1]--){$g[$p]=$a=2-$g[$p];$d+=--$a;$p+=(1-($d&2))*(1+16*($d&1));}while($i++<288)echo$i%17?$i!=$p?$g[$i]?"#": _:"@":"\n";

Ungolfed

$p = 144; // Set initial pointer

while($i = $argv[1]--){ // Ends at -1
    $g[$p] = $a = 2 - $g[$p]; // Either returns true (2) or false(0)

    $d += --$a; // Adds 1 (2-1) or removes 1 (0-1) from the direction

    $p += (1 - ($d & 2)) * (1 + 16 * ($d & 1));
}

while($i++ < 288)
    echo $i % 17? $i != $p? $g[$i]? "#" : @_ : "@" : "\n"; // Prints the correct character

350 -> 309: Various compression techniques with the for() loops, also updated to show correct output.
309 -> 307: Converted main for() loop to a while() loop.
307 -> 312: Forgot to change it to use argv.
312 -> 174: Recoded based on another answer.
174 -> 161: No longer defaults entire array.
161 -> 166: Argv wins again.
166 -> 159: No need to redefine argv[1].
159 -> 151: No longer defaults anything, PHP does it automatically.
151 -> 149: Removed a set of parenthesis, order of operations removes the need.
149 -> 147: Shortened the last for() loop, braces not needed.
147 -> 144: Last for() loop is now a while() loop.
144 -> 143: Used a temporary variable to save a character.

\$\endgroup\$
  • \$\begingroup\$ I see you used my grid & direction tricks, and that it removed 138 chars from your code, nice! \$\endgroup\$ – PatrickvL Mar 15 '11 at 7:57
4
\$\begingroup\$

C, 166 162

Here a translation of my Delphi-approach to C, showing off how compact C can be. I borrowed the conditional newline trick from fR0DDY (thanks mate!) :

g[289]={0},a=144,d,i,N;main(){scanf("%d",&N);while(N--)g[a]=2-g[a],d+=g[a]-1,a+=(1-(d&2))*(1+d%2*16);for(g[a]=1;i<289;)printf("%s%c",i++%17?"":"\n","_@#"[g[i]]);}

The indented, commented version looks like this :

g[289]={0}, // g: The grid is initially completely white. (size=17*17=289)
a=144, // a: Ant position starts at the center of the grid (=8*17+8=144)
d, // Assume 0=d: Ant start 'd'irection faces right (=0, see below)
i,
N;
main(){
  scanf("%d",&N);
  while(N--)
    // Flip the color of the square:
    g[a]=2-g[a],
    // Turn 90° right if at an '_' space, 90° left otherwise :
    d+=g[a]-1,
    // Move one unit forward;
    //   For this, determine the step size, using the two least significant bits of d.
    //   This gives the following relation :
    //     00 = 0 =  90° = right =   1
    //     01 = 1 = 180° = down  =  17
    //     10 = 2 = 270° = left  = - 1
    //     11 = 3 =   0° = up    = -17
    //   (d and 2) gives 0 or 2, translate that to 1 or -1
    //   (d and 1) gives 0 or 1, translate that to 1 or 17
    //   Multiply the two to get an offset 1, 17, -1 or -17 :
    a+=(1-(d&2))*(1+d%2*16);
  // Place the ant and print the grid :
  for(g[a]=1;i<289;)
    printf("%s%c",i++%17?"":"\n","_@#"[g[i]]); // 0 > '_', 1='@', 2 > '#'
}
\$\endgroup\$
  • \$\begingroup\$ +1. I like the tricks "_@#"[g[i]] and a+=(1-(d&2))*(1+(16*(d&1))) \$\endgroup\$ – fR0DDY Mar 15 '11 at 3:21
  • \$\begingroup\$ (1+d%2*16) saves a few chars. \$\endgroup\$ – Nabb Mar 19 '11 at 4:35
  • \$\begingroup\$ @Nabb: Indeed, that saves 4 characters, thanks for the suggestion! \$\endgroup\$ – PatrickvL Mar 23 '11 at 20:13
4
\$\begingroup\$

Delphi, 217

var g,a:PByte;i,d,Word;begin g:=AllocMem(306);a:=g+153;Read(i);for n:=1to i do begin a^:=2-a^;d:=d-1+a^;a:=a+(1-2and d)*(1+17*(1and d))end;a^:=1;for n:=1to 306do if n mod 18=0then WriteLn else Write('_@#'[1+g[n]])end.

The indented & commented code reads like this:

var
  g,a:PByte;
  i,d,n:Int32;
begin
  g:=AllocMem(306); // g: The grid is initially completely white. (size=18*17=306)
  // Assume 0=d: Ant start 'd'irection faces right (=0, see below)
  a:=g+153; // a: Ant position starts at the center of the grid (=8*18+9=153)
  Read(i);
  for n:=1to i do
  begin
    // Flip the color of the square;
    a^:=2-a^;
    // Turn 90° right if at an '_' space, 90° left otherwise;
    d:=d-1+a^;
    // Move one unit forward;
    //   For this, determine the step size, using the two least significant bits of d.
    //   This gives the following relation :
    //     00 = 0 =  90° = right =   1
    //     01 = 1 = 180° = down  =  18
    //     10 = 2 = 270° = left  = - 1
    //     11 = 3 =   0° = up    = -18
    //   (d and 2) gives 0 or 2, translate that to 1 or -1
    //   (d and 1) gives 0 or 1, translate that to 1 or 18
    //   Multiply the two to get an offset 1, 18, -1 or -18 :
    a:=a+(1-2and d)*(1+17*(1and d))
  end;
  // Place the ant and print the grid :
  a^:=1; // 0 > '_', 1='@', 2 > '#'
  for i:=1to 306do
    if i mod 18=0then // we insert & abuse column 0 for newlines only (saves a begin+end pair)
      WriteLn
    else
      Write('_@#'[1+g[i]])
end.

Input:

450

Output :

_________________
_________________
___________##____
____##______##___
___#__##___##_#__
__###_#@#__#__#__
__#_#_#_#__#_#___
_____###___#_____
_____#___________
_____#__###______
___#_#_#__#_#_#__
__#__#_#____###__
__#_##__##___#___
___##______##____
____##___________
_________________
_________________
\$\endgroup\$
  • \$\begingroup\$ @Patrick: the example was wrong, please check the updates. (and it seems that you output step 451 :) ). \$\endgroup\$ – Eelvex Mar 14 '11 at 14:24
  • \$\begingroup\$ @Eelvex : Thanks. I fixed the case 'N=0' at a cost of 4 chars... now I gotta win them back again! ;-) \$\endgroup\$ – PatrickvL Mar 14 '11 at 14:43
  • \$\begingroup\$ @Eelvex : PS: No +1 for spotting your error 3 hours ago with just a humble remark it could be my fault? ;) \$\endgroup\$ – PatrickvL Mar 14 '11 at 14:51
  • \$\begingroup\$ @Patrick: I was waiting for <200 but ok... :) \$\endgroup\$ – Eelvex Mar 14 '11 at 15:23
  • \$\begingroup\$ @Eelvex: LOL, getting there... (down to 238 already) \$\endgroup\$ – PatrickvL Mar 14 '11 at 15:51
3
\$\begingroup\$

C 195 Characters

x=144,T,p=1,i,N[289]={0},a[]={-17,1,17,-1};c(t){p=(p+t+4)%4;x+=a[p];}main(){scanf("%d",&T);while(T--)N[x]=(N[x]+1)%2,c(N[x]?1:-1);for(;i<289;i++)printf("%s%c",i%17?"":"\n",i-x?N[i]?'#':'_':'@');}

http://www.ideone.com/Dw3xW

I get this for 725.

_________________
_________________
___________##____
____##______##___
___#___##__##_#__
__###____#_#__#__
__#_#_#__#_#_#___
______###____#__@
_______###__#__#_
_____#_#____#___#
___#_#_#_##____#_
__#__#_#_#_#_###_
__#_##_#_____####
___##_#____#_####
____###___####_#_
_______#__#__##__
________####_____
\$\endgroup\$
  • \$\begingroup\$ Using p+=t+4;x+=a[p%4]; instead of p=(p+t+4)%4;x+=a[p]; saves three characters. \$\endgroup\$ – Joey Jul 13 '14 at 18:08
3
\$\begingroup\$

sed, 481 chars

#n
1{s/.*/_________________/;h;H;H;H;G;G;G;G;s/^\(.\{152\}\)_/\1@/;s/$/;r/;ta;};x;:a;/;r/br;/;d/bd;/;l/bl;/;u/bu;:w;y/rdlu/dlur/;bz;:b;y/rdlu/urdl/;bz;:r;s/@\(.\{17\}\)_/#\1@/;tw;s/@\(.\{17\}\)#/#\1!/;tw;s/_\(.\{17\}\)!/@\1_/;tb;s/#\(.\{17\}\)!/!\1_/;tb;:d;s/_@/@#/;tw;s/#@/!#/;tw;s/!_/_@/;tb;s/!#/_!/;tb;:l;s/_\(.\{17\}\)@/@\1#/;tw;s/#\(.\{17\}\)@/!\1#/;tw;s/!\(.\{17\}\)_/_\1@/;tb;s/!\(.\{17\}\)#/_\1!/;tb;:u;s/@_/#@/;tw;s/@#/#!/;tw;s/_!/@_/;tb;s/#!/!_/;tb;:z;h;${s/!/@/;s/;.//p}

May be reduced to 478 chars by removing first line and running with -n

Requires N lines for input, eg. when run as

seq 450 | sed -f ant.sed

outputs:

_________________
_________________
___________##____
____##______##___
___#__##___##_#__
__###_#@#__#__#__
__#_#_#_#__#_#___
_____###___#_____
_____#___________
_____#__###______
___#_#_#__#_#_#__
__#__#_#____###__
__#_##__##___#___
___##______##____
____##___________
_________________
_________________
\$\endgroup\$
3
\$\begingroup\$

Perl, 110 characters

$p=144;$p+=(1,-17,-1,17)[($d+=($f[$p]^=2)+1)%4]for 1..<>;$f[$p]=1;print$_%17?'':$/,qw(_ @ #)[$f[$_]]for 0..288

Number is read from the first line of STDIN. Rest of input is ignored.

Slightly more readable:

$p=144;
$p += (1,-17,-1,17)[($d+=($f[$p]^=2)+1) % 4] for 1..<>;
$f[$p]=1;
print $_%17 ? '' : $/, qw(_ @ #)[$f[$_]] for 0..288

Edits

  • (112 → 111) No need to update $d with the modulo-4 value.

  • (111 → 110) Can now inline the $d increment

Addendum (109 characters)

We can have it one character shorter if you’re happy to have the special case of N=0 fail (it doesn’t output the @ character for the ant). All other inputs work correctly:

$p+=(1,-17,-1,17)[($d+=($f{$p+0}^=2)+1)%4]for 1..<>;$f{$p}=1;print$_%17-9?'':$/,qw(_ @ #)[$f{$_}]for-144..144

The differences are that we now use %f instead of @f so we can use negative indices, and we iterate from -144..144 instead of 0..288. It saves having to initialise $p.

\$\endgroup\$
1
\$\begingroup\$

Mathematica, 94 chars

a@_=d=1;a@Nest[#+(d*=(a@#*=-1)I)&,9-9I,Input[]]=0;Grid@Array["@"[_,"#"][[a[#2-# I]]]&,17{1,1}]
\$\endgroup\$
1
\$\begingroup\$

><>, 122 bytes

At the risk of a little thread necromancy, I thought writing an answer in ><> would be an interesting challenge...

1&f8r\
1-:?!\r:@@:@$:@@:@g:2*1+&+4%:&}1$-@p{:3$-5gaa*-$@+@5gaa*-+r
2}p70\~
a7+=?\:@@:@g4+5go$1+:
o053.>~1+:64*=?;a
dedc_#@

This program expects the number of steps to compute to be present on the stack before execution.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.