Dibuja el camino de la hormiga de Langton .

Descripción

Los cuadrados en un avión son de diferentes colores, ya sea negro o blanco. Identificamos arbitrariamente un cuadrado como la "hormiga". La hormiga puede viajar en cualquiera de las cuatro direcciones cardinales en cada paso que da. La hormiga se mueve de acuerdo con las siguientes reglas:

• En un cuadrado blanco, gire 90 ° a la derecha, voltee el color del cuadrado, avance una unidad
• En un cuadrado negro, gire 90 ° a la izquierda, voltee el color del cuadrado, avance una unidad

Presupuesto

• Entrada: un entero N entre 0 y 725 (inclusive).
• Salida: una cuadrícula de 17 por 17 que representa la "ruta" de la hormiga a partir del paso N.

Reglas

• La hormiga comienza a mirar hacia la derecha (3 en punto).
• La hormiga comienza en el centro de la cuadrícula.
• Úselo _#@para cuadrados blancos, cuadrados negros y la hormiga respectivamente.
• La cuadrícula es inicialmente completamente blanca.
• Puede realizar un programa completo o una función en un idioma interpretado.
• Entrada por stdin o argumento.

Ejemplos

Actualización: la salida de N = 450 del caso fue incorrecta.

N = 0

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

N = 1

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

N = 450

_________________
_________________
___________##____
____##______##___
___#__##___##_#__
__###_#@#__#__#__
__#_#_#_#__#_#___
_____###___#_____
_____#___________
_____#__###______
___#_#_#__#_#_#__
__#__#_#____###__
__#_##__##___#___
___##______##____
____##___________
_________________
_________________

GolfScript - 67 caracteres

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

La solución Python de hallvabo es la más similar a esta, por lo que solo describiré las principales diferencias.

El tablero se almacena como una cadena en lugar de una matriz. Esto es para que podamos actualizar un valor en el tablero con menos caracteres (ya que las cadenas son siempre planas), y así es fácil llevarlo al formato de salida deseado.

La posición de la hormiga se incrementa con la fórmula ((d&1)*17+1)*((d&2)-1)(es decir .1&17*)\2&(*), donde d es la dirección. Usamos la variable 6para poder omitir la inicialización.

Ruby 1.9, 104 caracteres

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]}}

Entrada a través del argumento de función.

• (146 -> 142) en línea m
• (142 -> 140) Verificar en r*r>1lugar der.abs>1
• (142 -> 128) Se usa String#scanpara generar la salida. Cambiado ==a>
• (128 -> 125) Se eliminó la variable obsoleta
• (125 -> 122) Reemplazar String#trcon un condicional
• (122 -> 122) Ahora genera el mismo resultado que los ejemplos actualizados
• (122 -> 111) Use ints en lugar de caracteres al generar el camino de la hormiga.
• (111 -> 109) Reordenar algunas expresiones para guardar paréntesis
• (109 -> 108) El código ahora es una función
• (108 -> 104) Imprime cada personaje individualmente

Python, 123

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

Solo una ligera reelaboración de mi solución Python de http://golf.shinh.org/p.rb?Langtons+Ant .

GolfScript 96 94 89

Mi lenguaje de odio favorito está de vuelta con otro montón de códigos de sorteo semi legibles.

89 versión, finalmente logré integrar @ en el bucle de salida.

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

94 versión:

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

Comentado:

               #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.

Editar, también podría hacer una versión grande, aquí van las iteraciones 59 * 59 y 10500:

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

.

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

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}',"$&
"

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";

Sin golf

$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: varias técnicas de compresión con los bucles for (), también actualizados para mostrar la salida correcta.
309 -> 307: Se convirtió el bucle principal for () en un bucle while ().
307 -> 312: Olvidé cambiarlo para usar argv.
312 -> 174: Recodificado en base a otra respuesta.
174 -> 161: ya no está predeterminado todo el conjunto.
161 -> 166: Argv gana de nuevo.
166 -> 159: No es necesario redefinir argv [1].
159 -> 151: ya no está predeterminado, PHP lo hace automáticamente.
151 -> 149: se eliminó un conjunto de paréntesis, el orden de las operaciones elimina la necesidad.
149 -> 147: se acortó el último bucle for (), no se necesitan llaves.
147 -> 144:El último bucle for () ahora es un bucle while ().
144 -> 143: se utilizó una variable temporal para guardar un carácter.

C, 166 162

Aquí una traducción de mi enfoque Delphi a C, mostrando cuán compacto puede ser C. Tomé prestado el truco condicional de nueva línea de fR0DDY (¡gracias amigo!):

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]]);}

La versión comentada con sangría se ve así:

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 > '#'
}

Delfos, 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.

El código sangrado y comentado se lee así:

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.

Entrada:

450

Salida:

_________________
_________________
___________##____
____##______##___
___#__##___##_#__
__###_#@#__#__#__
__#_#_#_#__#_#___
_____###___#_____
_____#___________
_____#__###______
___#_#_#__#_#_#__
__#__#_#____###__
__#_##__##___#___
___##______##____
____##___________
_________________
_________________

C 195 Personajes

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

Me sale esto por 725.

_________________
_________________
___________##____
____##______##___
___#___##__##_#__
__###____#_#__#__
__#_#_#__#_#_#___
______###____#__@
_______###__#__#_
_____#_#____#___#
___#_#_#_##____#_
__#__#_#_#_#_###_
__#_##_#_____####
___##_#____#_####
____###___####_#_
_______#__#__##__
________####_____

sed, 481 caracteres

#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}

Se puede reducir a 478 caracteres al eliminar la primera línea y ejecutar con -n

Requiere N líneas para la entrada, por ejemplo. cuando se ejecuta como

seq 450 | sed -f ant.sed

salidas:

_________________
_________________
___________##____
____##______##___
___#__##___##_#__
__###_#@#__#__#__
__#_#_#_#__#_#___
_____###___#_____
_____#___________
_____#__###______
___#_#_#__#_#_#__
__#__#_#____###__
__#_##__##___#___
___##______##____
____##___________
_________________
_________________

Perl, 110 caracteres

$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

El número se lee desde la primera línea de STDIN. El resto de la entrada se ignora.

Ligeramente más legible:

$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

Ediciones

• (112 → 111) No es necesario actualizar $dcon el valor del módulo 4.

• (111 → 110) Ahora puede alinear el $dincremento

Anexo (109 caracteres)

Podemos tener un carácter más corto si está contento de tener el caso especial de N=0falla (no genera el @carácter para la hormiga). Todas las demás entradas funcionan correctamente:

$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

Las diferencias son que ahora usamos en %flugar de @fpara poder usar índices negativos, e iteramos desde en -144..144lugar de 0..288. Ahorra tener que inicializar $p.

Mathematica, 94 caracteres

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

> <>, 122 bytes

A riesgo de una pequeña necromancia de hilos, pensé que escribir una respuesta en> <> sería un desafío interesante ...

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_#@

Este programa espera que el número de pasos para calcular esté presente en la pila antes de la ejecución.