Sztuka ASCII mrówki Langtona.

22

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

_________________
_________________
___________##____
____##______##___
___#__##___##_#__
__###_#@#__#__#__
__#_#_#_#__#_#___
_____###___#_____
_____#___________
_____#__###______
___#_#_#__#_#_#__
__#__#_#____###__
__#_##__##___#___
___##______##____
____##___________
_________________
_________________
Eelvex
źródło
@Joey: tak "Kompletny program lub funkcja. Wejście przez argument lub standardowe.", Freestyle :)
Eelvex
@Joey: Przepraszam, jeśli nie było to jasne: możesz wykonać funkcję w tłumaczonym języku lub w pełnym programie. Możesz wziąć dane wejściowe ze standardowego wejścia lub podać je jako argument.
Eelvex
@Joey: Zauważ, że w kroku 1 mrówka najpierw skręca w prawo (teraz przodem do północy), a następnie przesuwa się. Czy jesteś pewien, że bierzesz to pod uwagę?
Eelvex
@Joey: Tak, miałem na myśli południe w poprzednim komentarzu i masz rację, ostatni przykład dotyczył innego N: - / (Zaktualizowano sekcję przykładów).
Eelvex

Odpowiedzi:

10

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

Nabb
źródło
1
Awww, teraz czuję się jak golfista noob.
aaaaaaaaaaaa
:6- tak bardzo hipster. Nienawidzę debugowania twojego kodu :-)
John Dvorak
9

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
Ventero
źródło
Funkcje dozwolone.
Eelvex
@Eelvex: Czy funkcja musi zwrócić ciąg, czy musi go wyprowadzić?
Ventero
wydajność.
Eelvex
6

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 .

hallvabo
źródło
5

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*

.

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

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}',"$&
"
Joey
źródło
4

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.

Kevin Brown
źródło
Widzę, że użyłeś moich sztuczek siatki i kierunku i że usunął 138 znaków z twojego kodu, fajnie!
PatrickvL,
4

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 > '#'
}
PatrickvL
źródło
+1. Lubię sztuczki "_@#"[g[i]]ia+=(1-(d&2))*(1+(16*(d&1)))
fR0DDY
(1+d%2*16)oszczędza kilka znaków.
Nabb,
@Nabb: Rzeczywiście, to oszczędza 4 znaki, dzięki za sugestię!
PatrickvL,
4

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:

_________________
_________________
___________##____
____##______##___
___#__##___##_#__
__###_#@#__#__#__
__#_#_#_#__#_#___
_____###___#_____
_____#___________
_____#__###______
___#_#_#__#_#_#__
__#__#_#____###__
__#_##__##___#___
___##______##____
____##___________
_________________
_________________
PatrickvL
źródło
@Patrick: przykład był niepoprawny, sprawdź aktualizacje. (i wydaje się, że wyprowadzasz krok 451 :)).
Eelvex
@Eelvex: Dzięki. Naprawiłem przypadek „N = 0” kosztem 4 znaków ... teraz muszę je odzyskać! ;-)
PatrickvL
@Eelvex: PS: Brak +1 za wykrycie twojego błędu 3 godziny temu tylko z drobną uwagą, czy to może być moja wina? ;)
PatrickvL
@Patrick: Czekałem na <200, ale ok ... :)
Eelvex
@Eelvex: LOL, się tam dostaję ... (już do 238)
PatrickvL
3

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.

_________________
_________________
___________##____
____##______##___
___#___##__##_#__
__###____#_#__#__
__#_#_#__#_#_#___
______###____#__@
_______###__#__#_
_____#_#____#___#
___#_#_#_##____#_
__#__#_#_#_#_###_
__#_##_#_____####
___##_#____#_####
____###___####_#_
_______#__#__##__
________####_____
fR0DDY
źródło
Użycie p+=t+4;x+=a[p%4];zamiast p=(p+t+4)%4;x+=a[p];zapisuje trzy znaki.
Joey,
3

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:

_________________
_________________
___________##____
____##______##___
___#__##___##_#__
__###_#@#__#__#__
__#_#_#_#__#_#___
_____###___#_____
_____#___________
_____#__###______
___#_#_#__#_#_#__
__#__#_#____###__
__#_##__##___#___
___##______##____
____##___________
_________________
_________________
Hasturkun
źródło
3

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.

Timwi
źródło
1

Mathematica, 94 znaki

a@_=d=1;a@Nest[#+(d*=(a@#*=-1)I)&,9-9I,Input[]]=0;Grid@Array["@"[_,"#"][[a[#2-# I]]]&,17{1,1}]
alephalpha
źródło
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.

Sok
źródło