Jalankan Sistem Lindenmayer

Sebuah Lindenmayer Sistem (atau L-system) terkait dengan Thue dan Pos sistem, dan digunakan dalam pemodelan botani dan generasi fraktal .

Sistem-L dijelaskan dengan penulisan ulang string di mana simbol dari simbol-alfabet dipetakan ke urutan penggantian simbol. Kumpulan pemetaan ini merupakan sistem L yang tepat.

Metode output grafis seperti yang dirancang oleh Prusinkiewicz menginterpretasikan urutan yang dihasilkan setelah pemetaan diterapkan pada urutan awal untuk jumlah iterasi tertentu , seperti perintah Turtle-Drawing: maju, mundur, kiri, kanan, hal-hal semacam itu. Ini mungkin memerlukan kode tambahan untuk mengontrol skala gambar karena jumlah iterasi yang berbeda dapat menghasilkan gambar dengan ukuran yang berbeda secara drastis.

Tugas Anda adalah menjalankan sistem-L dalam jumlah karakter paling sedikit. Program Anda harus dapat me-render Kurva Naga dan Batang Bercabang dari halaman Wikipedia dengan memberikan input yang sesuai (file, baris perintah, tetapi eksternal ke sumbernya, silakan).

Ini kode golf.

Sunting: Berikut adalah beberapa contoh yang telah saya posting di sekitar kota. jawaban untuk SO / rotate-to-north { Di mana saya pertama kali menemukan sistem-L } , jawaban untuk SO / bagaimana-program-a-fraktal , jawaban untuk SO / rekursi-dalam-postscript , diskusi comp.lang.postscript / resital , koleksi sistem-l postscript , codegolf.SE/draw-a-sierpinski-triangle {asal kompetisi antara saya dan thomasW} .

Mathematica 200 198 188 171 168

Spaces ditambahkan untuk kejelasan:

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)

Dimana:

i: Keadaan awal;
b: sudut rotasi
h: sudut awal
j: posisi awal
r: aturan produksi
n: iterasi

Tata bahasa aturan produksi:

2 = Belok Kiri (-);
4 = Belok Kanan (+);
6 = Dorong dan Belok Kiri ("[");
8 = Pop dan Belok Kanan ("]");
C [i] = Menggambar (Sejumlah simbol)
Simbol lain = Tidak Melakukan apa-apa, cukup gunakan untuk menghasilkan status berikutnya (Sejumlah simbol)

Urutan {2,4,6,8} ada di sana karena saya menggunakan I^n( I= unit imajiner) untuk berbelok.

Contoh:

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

Bukan pemenang, tetapi saya akan tetap memposting apa yang saya coba.

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

Tidak pandai bermain golf Python ...... Mungkin orang lain bisa melakukannya.

Memasukkan

Input berasal dari file eksternal bernama "l" (tanpa ekstensi), dengan format berikut:
Baris 1 : Status awal (Aksioma)
Baris 2 : Aturan yang dipisahkan koma

Simbol
f dan F: Menggambar ke depan
+: Belok kanan 5 derajat
-: Belok kiri 5 derajat
[: Simpan posisi dan tajuk
]: Posisi pop dan tajuk
Simbol lainnya diabaikan oleh fungsi menggambar.

Aturan
Aturan ada dalam format. "predecessor":"successor(s)"
Perhatikan bahwa tanda kutip diperlukan, baik tunggal atau ganda.
predecessorharus berupa karakter tunggal.
Juga, tidak ada konstanta implisit: Anda harus secara eksplisit menetapkan aturan tidak ada perubahan untuk itu.

Contohnya

Batang percabangan

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

Keluaran

Perhatikan bahwa sumber dimodifikasi untuk mengeluarkan ini HANYA UNTUK MENURUNKAN GRAFIK KE DAERAH YANG TAMPAK. Konsol juga digunakan untuk menyembunyikan "kura-kura".

Kurva naga

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

Keluaran

Lagi, konsol digunakan untuk menyembunyikan "kura-kura".

Segitiga Sierpinski

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

Generasi Keluaran dikurangi menjadi 5 di sini.

Javascript (179 byte)

Tidak sepenuhnya yakin ini memenuhi syarat, karena objek aturan melakukan semua gambar yang sebenarnya.

Demo (Naga, animasi):
- Diperluas: http://jsfiddle.net/SVkMR/9/show/light
- Dengan Kode: http://jsfiddle.net/SVkMR/9/

Diperkecil:

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

Dapat dibaca (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)
}

Memasukkan:

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

Pemakaian:

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

Nota bene 264 298 295 255

Inilah usaha saya untuk melakukannya secara berbeda. Daripada ekspansi makro yang biasanya saya gunakan, yang ini memeriksa ukuran tumpukan eksekusi untuk mengikat rekursi. Jika batas terlampaui, ia berhenti memeriksa prosedur secara rekursif dan mencoba menafsirkan perintah kura-kura (dan membuang yang pop poplain). Keuntungan dari metode ini adalah tidak memerlukan memori yang sangat besar. Kerugiannya adalah kontrol rekursi agak canggung, karena ukuran tumpukan tumbuh lebih dari hanya 1 dari satu tingkat rekursi ke yang berikutnya.

Sunting: +34 karakter untuk bercabang.
Edit: -3 karakter. Didesain ulang untuk menggunakan tumpukan operan untuk kontrol rekursi. Ini membuat sistem dasar lebih sederhana. Tapi kurung memerlukan tumpukan independen, jadi saya meletakkan posisi yang disimpan dalam tumpukan kamus, dan hampir membayar semua tabungan.

Juga, didesain ulang untuk menggunakan string dan integer, bukan array dan nama.

Edit: -40 karakter. Menambahkan dua prosedur untuk memanggil nama sistem dengan nomor (Sepertinya saya tidak bisa mendapatkan token biner mentah untuk bekerja. Tapi idiom ini bekerja untuk saya.)

/*{<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>$

Biner semi-komentar.

/*{<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

Hapus "biner".

[/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

Ini membutuhkan sistem-L untuk didefinisikan dalam kamus pada dictstack, dengan string awal dan posisi awal kura-kura pada tumpukan operan (digantungkan pada sumbernya, mis. gs dragon.sys lsys.ps).

Kurva Naga.

%!
[                     %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

Batang Percabangan.

[
    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

Tidak diikat dan dikomentari.

[                                 % 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

Untuk menjalankannya, 3 blok ini dapat disimpan sebagai 3 file: dragon.ps, stems.ps, lsys.ps (salah satu dari blok program di atas akan bekerja secara identik). Kemudian jalankan dengan gs: gs dragon.ps lsys.psor gs stems.ps lsys.ps. Mereka juga dapat digabungkan terlebih dahulu, jika diinginkan: cat dragon.ps lsys.ps | gs -atau cat stems.ps lsys.ps | gs -.

Tidak ada gambar batang. Tidak ada yang lebih menarik di kedalaman yang lebih tinggi.

Mathematica 290

Implementasi telanjang-tulang ini berfokus pada output daripada pemrosesan. Itu tidak menggunakan aturan produksi. Jadi itu mungkin bukan jawaban yang cocok untuk tantangan.

Batang percabangan diadaptasi dari demonstrasi Theo Gray .

Kode

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

Pemakaian

Parameter pertama menentukan apakah Kurva Naga atau Batang Cabang akan ditampilkan. Istilah kedua mengacu pada generasi.

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

Lebih banyak contoh

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