Uruchom system Lindenmayer

Lindenmayer systemu (lub L-System) jest związana z Thue i posta systemów i jest stosowany w modelowaniu botanicznego i fraktalnej pokolenia .

Układ L jest opisany przez przepisywanie ciągów, w którym symbol z alfabetu symbolu jest odwzorowany na zastępującą sekwencję symboli. Zbiór tych mapowań stanowi właściwy system L.

Graficzna metoda wyjściowa opracowana przez Prusinkiewicza interpretuje wynikową sekwencję po zastosowaniu odwzorowań do sekwencji początkowej dla określonej liczby iteracji , jako polecenia Rysowania Żółwia: do przodu, do tyłu, w lewo, w prawo, tego rodzaju rzeczy. Może to wymagać dodatkowego kodu do kontrolowania skali rysunku, ponieważ różne liczby iteracji mogą powodować drastycznie różnej wielkości obrazy.

Twoim zadaniem jest wykonanie systemu L przy jak najmniejszej liczbie znaków. Twój program musi być w stanie renderować zarówno Dragon Curve, jak i Rozgałęzione Pędy ze strony Wikipedii, podając odpowiednie dane wejściowe (plik, wiersz poleceń, ale zewnętrznie do źródła, proszę).

To jest kod golfowy.

Edycja: Oto kilka przykładów, które opublikowałem w mieście. odpowiedz na SO / rotate-to-north { Gdzie pierwszy raz odkryłem system L } , odpowiedz na SO / how-to-program-a-fractal , odpowiedź na SO / recursion-in-postscript , comp.lang.postscript / recital , PostScript l-system collection , codegolf.SE/draw-a-sierpinski-triangle {geneza konkurencji między mną a Thomasem W} .

Mathematica 200 198 188 171 168

Dodano spacje dla przejrzystości:

f[i_, b_, h_, j_, r_, n_] :=
 (a = h; p = j; s = k = {}; t = Flatten;
  (Switch[#,
      6, s = {a, p, s},
      8, {a, p, s} = s,
      _C, k = {k, Line@{p, p += {Cos@a, Sin@a}}}];
     If[# < 9, a += I^# b ]) & /@ t@Nest[# /. r &, i, n];
  Graphics@t@k)

Gdzie:

i: stan początkowy;
b: kąt obrotu
h: kąt początkowy
j: pozycja początkowa
r: reguły produkcji
n: iteracje

Gramatyka zasad produkcji:

2 = Skręć w lewo (-);
4 = Skręć w prawo (+);
6 = Naciśnij i skręć w lewo („[”);
8 = Pop i skręć w prawo („]”);
C [i] = Rysuj (Dowolna liczba symboli)
Dowolny inny symbol = Nic nie rób, po prostu użyj go do utworzenia następnego stanu (Dowolna liczba symboli)

Sekwencja {2,4,6,8} istnieje, ponieważ używam I^n( I= jednostki urojonej) do wykonywania zwrotów.

Przykłady:

f[{C[1], X}, Pi/2, 0, {0, 0}, {X -> {X, 4, Y, C[1]}, Y -> {C[1], X, 2, Y}}, 10]

f[{C@1}, Pi/2, 0, {0,0}, {C@1->{C@1, 2, C@1, 4, C@1, 4, C@1, 2, C@1}}, 6]

f[{C[1]}, Pi/4, Pi/2, {0, 0}, {C[2] -> {C[2], C[2]}, C[1] -> {C[2], 6, C[1], 8, C[1]}}, 10]

f[{C[1]}, Pi/3, 0, {0, 0}, {C@1 -> {C@2, 4, C@1, 4, C@2}, C@2 -> {C@1, 2, C@2, 2, C@1}}, 10]

f[{X},5/36 Pi, Pi/3, {0,0},{X->{C@1, 4, 6, 6, X, 8, 2, X, 8, 2, C@1, 6, 2, C@1, X, 8, 4, X},
                            C@1->{C@1, C@1}}, 6]

Python, 369 294

Nie jestem zwycięzcą, ale i tak opublikuję to, co próbowałem.

from turtle import*
I=open('l').read().split()
s,S,p=I[0],'',[]
for j in range(8):
    for i in s:S+=eval('{'+I[1]+'}')[i]
    s,S=S,''
for k in s:
    if k=='[':p+=[heading(),pos()];continue
    if k==']':pu();goto(p.pop());seth(p.pop());pd();continue
    try:{'f':fd,'F':fd,'+':rt,'-':lt}[k](5)
    except:pass

Nie jest dobry w golfie w Pythonie ...... Może ktoś inny może to zrobić.

Wkład

Dane wejściowe pochodzą z zewnętrznego pliku o nazwie „l” (bez rozszerzenia), w następującym formacie:
Wiersz 1 : Stan początkowy (Axiom)
Wiersz 2 : Reguły oddzielone przecinkami

Symbole
f i F: Rysuj do przodu
+: Skręć w prawo o 5 stopni
-: Skręć w lewo o 5 stopni
[: Zapisz pozycję i nagłówek
]: Pozycja pop i nagłówek
Inne funkcje są ignorowane przez funkcję rysowania.

Reguły
Reguła ma format "predecessor":"successor(s)"
Należy pamiętać, że cytaty są konieczne, zarówno pojedyncze, jak i podwójne.
predecessormusi być pojedynczym znakiem.
Ponadto nie ma żadnych niejawnych stałych: należy jawnie określić dla nich regułę bez zmian.

Przykłady

Rozgałęzione pędy

------------------f
'-':'-','+':'+','[':'[',']':']','F':'FF','f':'F[+++++++++f]---------f'

Wyjście

Zauważ, że źródło zostało zmodyfikowane, aby to udostępnić WYŁĄCZNIE W CELU SKALOWANIA WYKRESU DO WIDOCZNEGO OBSZARU. Konsola służy również do ukrywania „żółwia”.

Krzywa smoka

fx
'-':'-','+':'+','[':'[',']':']','f':'f','x':'x++++++++++++++++++yf','y':'fx------------------y'

Wyjście

Ponownie, konsola służy do ukrywania „żółwia”.

Trójkąt Sierpińskiego

f------------------------F------------------------F
'-':'-','+':'+','[':'[',']':']','f':'f------------------------F++++++++++++++++++++++++f++++++++++++++++++++++++F------------------------f','F':'FF'

Generacje wyjściowe zmniejszono tutaj do 5.

JavaScript (179 bajtów)

Nie do końca wiem, czy to się kwalifikuje, ponieważ obiekt reguł wykonuje cały rysunek.

Demo (Dragon, animowane):
- Rozszerzone: http://jsfiddle.net/SVkMR/9/show/light
- Z kodem: http://jsfiddle.net/SVkMR/9/

Zminimalizowane:

function L(c,r,n){o=(function g(d,s,o,i){for(o=i='';a=d&&s[i++];)o+=r.r[a]?g(d-1,r.r[a]):a;return o||s;})(n,r.r[r.s]);(function z(i){r[s=o[i]]&&r[s](c)||setTimeout(z,10,i+1)})(0)}

Czytelny (ish):

function L(c,r,n){
    o=(function g(d,s,o,i){
        for(o=i='';a=d&&s[i++];)o+=r.r[a]?g(d-1,r.r[a]):o+=a
        return o||s
    })(n,r.r[r.s]);

    (function p(i){
        r[s=o[i]]&&r[s](c)||setTimeout(p,10,i+1)
    })(0)
}

Wkład:

var sierspinski = {
    r:{'A':'B-A-B','B':'A+B+A'},
    '+':function(c){c.rotate(-this.a);c.rotate(this.a-=Math.PI/3)},
    '-':function(c){c.rotate(-this.a);c.rotate(this.a+=Math.PI/3)},
    'A':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    'B':function(c){this['A'](c)},
    s:'A',
    a:0,
    m:1
};

var koch = {
    r: {'F':'F+F-F-F+F'},
    '+':function(c){c.rotate(-this.a);c.rotate(this.a-=Math.PI/2)},
    '-':function(c){c.rotate(-this.a);c.rotate(this.a+=Math.PI/2)},
    'F':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    s:'F',
    a:0,
    m:2
};
var dragon = {
    r: {'X':'X+YF','Y':'FX-Y'},
    '+':function(c){c.rotate(-this.a);c.rotate(this.a-=Math.PI/2)},
    '-':function(c){c.rotate(-this.a);c.rotate(this.a+=Math.PI/2)},
    'F':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    s:'X',
    a:0,
    m:5
};

var algae = {
    r: {'A':'B[A]A','B':'BB'},
    '[':function(c){c.save();c.rotate(Math.PI/4);},  // save/restore will push/pop current state of context. 
    ']':function(c){c.restore();c.rotate(-Math.PI/4);},
    'A':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    'B':function(c){this['A'](c);},
    s:'A',
    a:-Math.PI/2,
    m:1
};

var tree = {
    r:{'X':'F-[[X]+X]+F[+FX]-X','F':'FF'},
    '+':function(c){c.rotate(-this.a);c.rotate(this.a+=Math.PI/180*25)},
    '-':function(c){c.rotate(-this.a);c.rotate(this.a-=Math.PI/180*25)},
    '[':function(c){c.save();},
    ']':function(c){c.restore();},
    'F':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    s:'X',
    a:-Math.PI/180*25,
    m:5
};

Stosowanie:

var ctx = document.getElementById('l').getContext('2d'); // grab context
ctx.translate(299.5,199.5); // start drawing from center, fractional pixels because the canvas draws lines centered on the x/y coord specified
L(ctx, dragon, 8); // pass in context, rules object, and recursion cap

Bonus: Golden Spiral http://jsfiddle.net/SVkMR/35/show/light/

var golden = {
    r:{'A':'FT[TT]A','T':'+F'},
    'F':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    '[':function(c){c.save();},
    ']':function(c){
        c.restore();

        c.beginPath();
        c.arc(0,-this.m,this.m,Math.PI/2,Math.PI);
        c.stroke();

        this.m+=this.d;this.d=this.m-this.d
    },
    '+':function(c){c.rotate(-Math.PI/2);},
    s:'A',
    a:-Math.PI/2,
    m:1,
    d:0
};

Postscriptum 264 298 295 255

Oto moja próba zrobienia tego inaczej. Zamiast makropolecenia, którego zwykle używam, ten sprawdza rozmiar stosu wykonania w celu ograniczenia rekurencji. Jeśli granica zostanie przekroczona, przestaje rekurencyjnie sprawdzać procedurę i próbuje interpretować polecenia żółwia (i odrzuca w pop popinny sposób). Zaletą tej metody jest to, że nie wymaga ona ogromnej ilości pamięci. Wadą jest to, że kontrola rekurencji jest raczej niezdarna, ponieważ rozmiar stosu rośnie o więcej niż tylko 1 z jednego poziomu rekurencji na następny.

Edycja: +34 znaków do rozgałęzienia.
Edycja: -3 znaki. Przeprojektowany, aby używać stosu operandów do kontroli rekurencji. To sprawia, że ​​podstawowy system jest znacznie prostszy. Ale nawiasy potrzebują niezależnego stosu, więc umieściłem zapisaną pozycję w stosie słownika i prawie zwróciłem wszystkie oszczędności.

Również przeprojektowany, aby używać ciągów i liczb całkowitych zamiast tablic i nazw.

Edycja: -40 znaków. Dodano dwie procedury wywoływania nazw systemowych według numerów (wydaje mi się, że nie mogę uruchomić surowych tokenów binarnych. Ale ten idiom działa dla mnie.)

/*{<920>dup 1 4 3 roll put cvx exec}def/${//* 73
*}def[/T[48{}49{}43{A<88>$}45{A<6e88>$}70{R
0<85>$}91{<1e39>$[/.[<286827>$]cvx>><0d0d>$}93{.<9c6b1e39390d>$}>>/S{dup
B eq{T<0d3e>${<643f>$}<4939>$}{exch{<643e>$ 1 add S}73 *}85 * 1 sub}>><0d6b>$
0 S<a7>$

Binarnie częściowo komentowane.

/*{<920>dup 1 4 3 roll put cvx exec}def/${//* 73 *}def %73=forall
[/T[70{R 0<85>$}48{}49{} %<85>=rlineto
43{A<88>$}45{A<6e88>$} %<88>=rotate <6e>=neg
91{<1e39>$ %<1e>=currentdict <39>=end
    [/.[<286827>$]cvx>> %<28>=currentpoint <68>=matrix <27>=currentmatrix
        <0d0d>$} %<0d>=begin
93{.<9c6b1e39390d>$}>> %<9c>=setmatrix <6b>=moveto
/S{dup B eq{T<0d3e>${<643f>$}<4939>$} %<3e>=exch <64>=load <3f>=exec <49>=forall
{exch{<643e>$ 1 add S}73 *}85 * 1 sub}>>
<0d6b>$ 0 S<a7>$  % 85=ifelse <a7>=stroke

Un- „binarny”.

[/T[70{R 0 rlineto}48{}49{}43{A rotate}45{A neg rotate}91{currentdict
end[/.[currentpoint matrix currentmatrix]cvx>>begin begin}93{. setmatrix
moveto currentdict end end begin}>>/S{dup B eq{T begin exch{load exec}forall
end}{exch{load exch 1 add S}forall}ifelse 1 sub }>>begin moveto 0 S stroke

Wymaga zdefiniowania systemu L w słowniku na dyktafonie, z początkowym łańcuchem i pozycją początkową żółwia na stosie operandu (np. Dołączonym do źródła gs dragon.sys lsys.ps).

Dragon Curve.

%!
[                     %begin dictionary construction
    % productions are described by integer-key/string-value pairs
    48(0+1F) %0       %ascii code for '0' defined as the string "0+1F"
    49(F0-1) %1       %  "     "   "  '1'   "     "   "    "    "F0-1"
    43(+) %+          %  "     "   "  '+' defined as itself
    45(-) %-          %  "     "   "  '-'   "     "   "
    70(F) %F          %  "     "   "  'F'   "     "   "
    % parameters
    /A 90 %angle
    /R 2  %radius
    /B 10 %maximum recursion-level
>>begin  % L-system dictionary on top of dictstack
(F0)     % initial string on stack
300 400  % starting position on stack

Rozgałęzione Pędy.

[
    48(F[+0]-0) %0
    49(F0-1) %1
    43(+) %+
    45(-) %-
    70(FF) %F
    91([) %[
    93(]) %]
    /A 45 %angle
    /R 5  %radius
    /B 3 %recursion
>>begin
(++0)     % initial string
300 400  % starting position

Nie golfił i skomentował.

[                                 % begin dictionary construction
    /T[                           % /T is the Turtle dictionary containing
                                  % integer-key/procedure-value pairs
                                  % keyed to ascii values
        70{R 0 rlineto}        %F  
        48{}                   %0
        49{}                   %1  
        43{A rotate}           %+  
        45{A neg rotate}       %-  

          % For brackets, create a dictionary containing a single procedure '.' (dot)
          % which holds a saved matrix (orientation+size) and currentpoint.
          % Since this procedure is called while the Turtle dict is on top of the
          % dictstack, the temporary dictionary is placed just under the top.
        91{currentdict end[/.[currentpoint matrix currentmatrix]cvx>>begin begin} %[
          % Right bracket: reset position and orientation,
          % pop the dict just under the top.
        93{. setmatrix moveto currentdict end end begin}    %]  
    >>  
    /S{ % stack contains: string recursion-level
        dup B eq{ % hit recursion bound, interpret string as turtle commands
            T begin
                exch % level string
                %dup =
                {                      % iterate through string
                    load exec          % execute turtle command by integer code
                } forall % level       % string has been consumed
            end
            %(B)= pstack
        }{ % recurse
            %(A)= pstack
            exch % level string
            { % level char                   iterate through string
                load exch % string level   process production:load string by int code
                1 add S   % string level+1   increase level and call self
            } forall                       % string has been consumed
        }ifelse
        1 sub            % return level-1
        %(C)= pstack
    }
>>begin
moveto 0 S stroke

Aby go uruchomić, te 3 bloki można zapisać jako 3 pliki: dragon.ps, stems.ps, lsys.ps (dowolny z powyższych bloków programu będzie działał identycznie). Następnie uruchom z gs: gs dragon.ps lsys.pslub gs stems.ps lsys.ps. W razie potrzeby można je najpierw połączyć . cat dragon.ps lsys.ps | gs -Lub cat stems.ps lsys.ps | gs -.

Brak obrazu łodyg. Nie robi się już bardziej interesujący na wyższych głębokościach.

Mathematica 290

Ta implementacja od podstaw koncentruje się raczej na danych wyjściowych niż na przetwarzaniu. Nie używa reguł produkcji. Może to nie być odpowiednia odpowiedź na wyzwanie.

Rozgałęzione pędy dostosowane do pokazu Theo Graya .

Kod

f@{a_, b_} := {{a, #}, {b, #}} &[a + (b - a)/2 + {{0, 1/2}, {-1/2, 0}}.(b - a)]; w = Flatten;
h[s_, g_] :=Graphics[If[s == 0,Line /@ Nest[w[f /@ #, 1] &, {{{0, 0}, {1, 0}}}, g], 
 MapIndexed[Line@# &, NestList[w[Map[{{#[[2]], #[[2]] + m.(#[[2]] - #[[1]])}, {#[[2]], 
 #[[2]] + ({{1, -1}, {-1,1}} m).(#[[2]] - #[[1]])}} &, #], 1] &, {{{0, -1}, {0, 0}}}, g]]]]

Stosowanie

Pierwszy parametr określa, czy Smocza Krzywa, czy Pędy Gałęzi będą wyświetlane. Drugi termin odnosi się do generacji.

h[0, 5]
h[1, 5]

Więcej przykładów

GraphicsGrid@Partition[Flatten[Table[h[j, k], {j, 0, 1}, {k, 10}]], 5]