Narysuj ścieżkę mrówki Langtona .

Opis

Kwadraty na płaszczyźnie mają różne kolory, albo czarny, albo biały. Dowolnie identyfikujemy jeden kwadrat jako „mrówkę”. Mrówka może podróżować w dowolnym z czterech głównych kierunków na każdym kroku. Mrówka porusza się zgodnie z poniższymi zasadami:

• Na białym kwadracie obróć o 90 ° w prawo, odwróć kolor kwadratu, idź o jedną jednostkę do przodu
• Na czarnym kwadracie obróć o 90 ° w lewo, odwróć kolor kwadratu, przejdź o jedną jednostkę do przodu

Dane techniczne

• Dane wejściowe: liczba całkowita N od 0 do 725 (włącznie).
• Wyjście: siatka 17 na 17 reprezentująca „ścieżkę” mrówki z kroku N.

Zasady

• Mrówka zaczyna być skierowana w prawo (godzina 3).
• Mrówka zaczyna się na środku siatki.
• Użyj odpowiednio _#@do białych kwadratów, czarnych kwadratów i mrówek.
• Siatka jest początkowo całkowicie biała.
• Możesz stworzyć kompletny program lub funkcję w interpretowanym języku.
• Wprowadzanie przez stdin lub argument.

Przykłady

Aktualizacja: wynik N = 450 sprawy był niepoprawny.

N = 0

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

N = 1

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

N = 450

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

GolfScript - 67 znaków

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

Rozwiązanie hallvabo w języku Python jest najbardziej podobne do tego, dlatego opiszę tylko główne różnice.

Tablica jest przechowywana jako ciąg zamiast tablicy. Dzięki temu możemy zaktualizować wartość na tablicy o mniej znaków (ponieważ ciągi są zawsze płaskie), a więc przejście do pożądanego formatu wyjściowego jest łatwe.

Pozycja mrówki jest zwiększana przez wzór ((d&1)*17+1)*((d&2)-1)(tj. .1&17*)\2&(*), Gdzie d jest kierunkiem. Używamy zmiennej 6, abyśmy mogli pominąć inicjalizację.

Ruby 1.9, 104 znaki

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

Wprowadź za pomocą argumentu funkcji.

• (146 -> 142) Inline m
• (142 -> 140) Sprawdź r*r>1zamiastr.abs>1
• (142 -> 128) Służy String#scando generowania wyniku. Zmieniono ==na>
• (128 -> 125) Usunięto przestarzałą zmienną
• (125 -> 122) Zamień String#trna warunkowy
• (122 -> 122) Teraz generuje to samo wyjście, co zaktualizowane przykłady
• (122 -> 111) Używaj liczb całkowitych zamiast znaków podczas generowania ścieżki mrówki.
• (111 -> 109) Zmień kolejność niektórych wyrażeń, aby zapisać nawiasy
• (109 -> 108) Kod jest teraz funkcją
• (108 -> 104) Wydrukuj każdą postać osobno

Python, 123

n = input ()
d = x = 152
g = (17 * [95] + [10]) * 17
podczas gdy n: d + = g [x] / 2; g [x] ^ = 124; x + = (1, -18, -1,18) [d% 4]; n- = 1
g [x] = 64
wydrukuj „% c” * 306% krotek (g)

Wystarczy drobna przeróbka mojego rozwiązania Python z http://golf.shinh.org/p.rb?Langtons+Ant .

GolfScript 96 94 89

Mój ulubiony język nienawiści powrócił z kolejną wiązką częściowo czytelnego sortowania kodu bajtowego.

Wersja 89, w końcu udało mi się zintegrować @ z pętlą wyjściową.

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

94 wersja:

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

Skomentowano:

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

Edytuj, równie dobrze mógłbym stworzyć dużą wersję, tutaj jest 59 * 59 i 10500 iteracji:

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

Nie golfił

$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: Różne techniki kompresji za pomocą pętli for (), również zaktualizowane, aby wyświetlały prawidłowe dane wyjściowe.
309 -> 307: Przekształcona główna pętla for () w pętlę while ().
307 -> 312: Zapomniałem go zmienić, aby użyć argv.
312 -> 174: Przekodowany na podstawie innej odpowiedzi.
174 -> 161: Nie ma już domyślnej wartości całej tablicy.
161 -> 166: Argv wygrywa ponownie.
166 -> 159: Nie ma potrzeby redefiniowania argumentu [1].
159 -> 151: Nic już nie domyślnie, PHP robi to automatycznie.
151 -> 149: Usunięto zestaw nawiasów, kolejność operacji eliminuje potrzebę.
149 -> 147: Skrócono ostatnią pętlę for (), nawiasy klamrowe nie są potrzebne.
147 -> 144:Pętla Last for () jest teraz pętlą while ().
144 -> 143: Użyto zmiennej tymczasowej do zapisania znaku.

C, 166 162

Oto tłumaczenie mojego podejścia Delphi do C, pokazujące, jak kompaktowe może być C. Pożyczyłem warunkową sztuczkę nowego wiersza od fR0DDY (dzięki kolego!):

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

Wersja z wciętymi komentarzami wygląda następująco:

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

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.

Wcięty i skomentowany kod brzmi następująco:

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.

Wkład:

450

Wyjście:

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

C 195 znaków

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

Dostaję to za 725.

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

sed, 481 znaków

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

Można zmniejszyć do 478 znaków, usuwając pierwszą linię i uruchamiając z -n

Wymaga N linii wejściowych, np. gdy działa jako

seq 450 | sed -f ant.sed

wyjścia:

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

Perl, 110 znaków

$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

Numer jest odczytywany z pierwszego wiersza STDIN. Reszta danych wejściowych jest ignorowana.

Nieco bardziej czytelny:

$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

Edycje

• (112 → 111) Nie trzeba aktualizować $dz wartością modulo-4.

• (111 → 110) Można teraz wstawić $dprzyrost

Dodatek (109 znaków)

Możemy mieć go o jedną postać krótszą, jeśli będziesz szczęśliwy, że wystąpi szczególny przypadek N=0niepowodzenia (nie wyświetla @postaci dla mrówki). Wszystkie pozostałe dane wejściowe działają poprawnie:

$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

Różnice polegają na tym, że teraz używamy %fzamiast @f, abyśmy mogli używać ujemnych wskaźników i powtarzamy -144..144zamiast 0..288. Oszczędza to konieczności inicjalizacji $p.

Mathematica, 94 znaki

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

> <>, 122 bajty

Ryzykując małą nekromancję wątków, pomyślałem, że napisanie odpowiedzi w> <> będzie ciekawym wyzwaniem ...

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

Ten program oczekuje, że liczba kroków do obliczenia będzie obecna na stosie przed wykonaniem.