"Tut mir leid, junger Mann, aber es ist Turtles ganz unten!"

21

Führen Sie ein Lindenmayer-System aus

Ein Lindenmayer-System (oder L-System) ist mit Thue- und Post- Systemen verwandt und wird in der botanischen Modellierung und Fraktalerzeugung verwendet .

Ein L-System wird durch Umschreiben von Zeichenfolgen beschrieben , wobei ein Symbol aus dem Symbolalphabet auf eine Ersatzsequenz von Symbolen abgebildet wird . Eine Sammlung dieser Abbildungen bildet das eigentliche L-System.

Die von Prusinkiewicz entwickelte grafische Ausgabemethode interpretiert die resultierende Sequenz, nachdem die Zuordnungen für eine bestimmte Anzahl von Iterationen auf eine Anfangssequenz angewendet wurden , als Turtle-Drawing-Befehle: Vorwärts, Rückwärts, Links, Rechts, solche Dinge. Dies erfordert möglicherweise zusätzlichen Code, um den Maßstab der Zeichnung zu steuern, da unterschiedliche Iterationszahlen Bilder mit drastisch unterschiedlicher Größe erzeugen können.

Ihre Aufgabe ist es, ein L-System mit der geringsten Anzahl von Zeichen auszuführen. Ihr Programm muss in der Lage sein, sowohl die Drachenkurve als auch die Verzweigungsstämme von der Wikipedia-Seite zu rendern, indem Sie die entsprechende Eingabe (Datei, Befehlszeile, aber bitte außerhalb der Quelle) bereitstellen.

Verzweigungsstiele Drachenkurve

Das ist Code Golf.

Bearbeiten: Hier sind einige Beispiele, die ich in der Stadt gepostet habe. Antwort auf SO / Rotate-Nord { Wo ich zuerst das L-System entdeckt } , Antwort auf SO / wie-zu-Programm-a-Fraktal , Antwort auf SO / Rekursion-in-Nachsatz , comp.lang.postscript Diskussion / Erwägungsgrund , Postscript-L-System-Sammlung , Codegolf.SE/draw-a-sierpinski-triangle {Ursprung des Wettbewerbs zwischen mir und ThomasW} .

Luser Droog
quelle
Sandkasten übersprungen. Dies scheint relativ einfach zu sein und sollte Spaß machen.
Luser Droog
Übrigens, weiß jemand den Ursprung des obigen Zitats? Ich habe William James gehört, und ich habe Faraday gehört.
Luser Droog
1
Wikipedia sagt, die Herkunft sei umstritten, am besten Bertrand Russel.
Ugoren
ITYM Bertrand Russell .
Paul R
1
Gibt es irgendwelche Grenzen für die Größe des Alphabets, die Anzahl der Regeln, die Anzahl der Runden oder mögliche (Visualisierungs-) Regeln (zeichnen Sie eine gerade Linie, drücken Sie / Pop-Position / Winkel, drehen Sie wie viele Grad usw.), wenn wir nur zeichnen müssen diese beiden brauchen wir dann push & popping, zeichnen gerade linien und können 45 grad in beide richtungen drehen, nur zwei regeln und ein alphabet der größe 4.
shiona

Antworten:

31

Mathematica 200 198 188 171 168

Leerzeichen zur Verdeutlichung hinzugefügt:

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)

Woher:

i: Ausgangszustand;
b: Drehwinkel
h: Anfangswinkel
j: Anfangsposition
r: Produktionsregeln
n: Iterationen

Grammatik der Produktionsregeln:

2 = Links abbiegen (-);
4 = rechts abbiegen (+);
6 = Nach links drücken und drehen ("[");
8 = Pop and Turn Right ("]");
C [i] = Draw (Beliebige Anzahl von Symbolen)
Beliebiges anderes Symbol = Do Nothing, verwende es einfach, um den nächsten Zustand zu erzeugen (Beliebige Anzahl von Symbolen)

Die {2,4,6,8} -Sequenz ist da, weil ich I^n( I= imaginäre Einheit) verwende, um Runden zu machen.

Beispiele:

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

Mathematica-Grafiken

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]

Mathematica-Grafiken

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]

Mathematica-Grafiken

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]

Mathematica-Grafiken

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]

Mathematica-Grafiken

Dr. belisarius
quelle
Ändern nur Graphics@kdurch , Graphics@Flatten@kwenn Sie vorhaben , viele Iterationen zu verwenden. Andernfalls wird ein Rekursionslimit Sie beißen und Ihre MMA-Sitzung wird abgebrochen.
Dr. Belisarius
Meine Makro-Expansionsmethode hatte ein ähnliches Problem mit höheren Iterationen. Die Saiten werden einfach riesig. Aber die Lösung bestand darin, nicht zu platt zu machen. :)
luser droog
2
+1 in der Tat sehr schön;) Könnte eine coole Demonstration sein. Reichen Sie diese ein?
Vitaliy Kaurov
@VitaliyKaurov Nein, aber zögern Sie nicht, es zu verwenden, wenn Sie denken, dass es die Mühe wert ist
Dr. belisarius
3
@belisarius demonstrations.wolfram.com/GraphicalLSystems
Vitaliy Kaurov
9

Python, 369 294

Kein Gewinner, aber ich werde trotzdem posten, was ich versucht habe.

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

Nicht gut im Golfen mit Python ...... Vielleicht kann es jemand anderes tun.

Eingang

Die Eingabe erfolgt aus einer externen Datei mit dem Namen "l" (keine Erweiterung) im folgenden Format:
Zeile 1 : Anfangszustand (Axiom)
Zeile 2 : Kommagetrennte Regeln

Symbole
f und F: Vorwärts zeichnen
+: 5 Grad nach rechts drehen: 5 Grad nach
-links drehen
[: Position und Überschrift speichern
]: Pop-Position und Überschrift
Andere Symbole werden von der Zeichenfunktion ignoriert.

Regeln
Eine Regel hat das Format "predecessor":"successor(s)"
Beachten Sie, dass einfache oder doppelte Anführungszeichen erforderlich sind.
predecessormuss ein einzelnes Zeichen sein.
Außerdem gibt es keine impliziten Konstanten: Sie müssen für diese explizit eine Änderungsregel angeben.

Beispiele

Verzweigungsstiele

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

Ausgabe

Beachten Sie, dass die Quelle so geändert wird, dass diese nur ausgegeben wird, um die Grafik auf den sichtbaren Bereich zu verkleinern. Die Konsole wird auch verwendet, um die "Schildkröte" zu verstecken.

Drachenkurve

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

Ausgabe

Wieder wird die Konsole verwendet, um die "Schildkröte" zu verbergen.

Sierpinski-Dreieck

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

Output

Generations hier auf 5 reduziert.

TwiNight
quelle
3
Sie können eine anständige Spar (ich es 32 Zeichen) , indem sie die Funktionen zu entfernen f, r, l; Hinzufügen eines Dummy-Parameters zu ound c; und dann den Pseudo-Schalter auf{'f':fd,'F':fd,'+':rt,'-':lt,'[':o,']':c}[k](5)
Peter Taylor
Sie können auch inline g, und ich denke, ound ces lohnt sich, mit Inline- ifAnweisungen zu beseitigen (billiger als die globalErklärung)
Peter Taylor
@ Peter Taylor gute Arbeit. Ich hatte die Intuition, dass einige dieser Funktionen integriert werden könnten, aber ich kannte nicht genug Python, um es artikuliert vorzuschlagen.
Luser Droog
1
@luserdroog, ich kenne Python auch nicht: Ich habe nur probeweise versucht, um zu sehen, was funktioniert - dh einige der Dinge, die ich ausprobiert habe (z. B. Lambdas für ound cdirekt im Pseudo-Switch), gaben Syntaxfehler, andere jedoch nicht. ' t.
Peter Taylor
Tipps für das weitere Golfen: 1. Eingabeformat ändern: Um die Regeln herum Klammern und Axiom von Regeln durch ein Leerzeichen trennen (kein Zeilenumbruch). 2. Lesen von stdin: s,R,*p=input().split(). 3. Generieren Sie den Endwert von sby exec('s="".join(map(eval(R).get,s));'*8). 4. Auslassen continue. 5. Nur 1 Leerzeichen einrücken. 6. Speichern Sie den Platz nach dem, ifindem Sie die Seiten für den Test wechseln. 7. Geben Sie k:intden dict(ersten Eintrag) ein und dann brauchen Sie nicht except: try:. (Ich erhalte 215 Zeichen.)
Setzen Sie Monica
7

Javascript (179 Bytes)

Dies ist nicht ganz sicher, da das Regelobjekt die gesamte Zeichnung ausführt.

Demo (Dragon, animiert):
- Erweitert: http://jsfiddle.net/SVkMR/9/show/light
- Mit Code: http://jsfiddle.net/SVkMR/9/

Minimiert:

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

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

Eingang:

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

Verwendung:

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
};
Shmiddty
quelle
Ich denke, die Animation gleicht Freiheiten mit den Regeln mehr als aus. Gut gemacht! +1
luser droog
:) Lustige Sachen! .
Shmiddty
5

Nachsatz 264 298 295 255

Hier ist mein Versuch, es anders zu machen. Anstelle der Makro-Erweiterung, die ich normalerweise verwende, überprüft diese die Größe des Ausführungsstapels, um die Rekursion zu begrenzen. Wenn die Grenze überschritten wird, wird die Prozedur nicht mehr rekursiv überprüft und es wird versucht, Turtle-Befehle zu interpretieren (und pop popansonsten verworfen ). Ein Vorteil dieser Methode ist, dass sie keinen enormen Speicherbedarf hat. Ein Nachteil ist, dass die Rekursionssteuerung ziemlich umständlich ist, da die Stapelgröße von einer Rekursionsstufe zur nächsten um mehr als nur 1 zunimmt.

Bearbeiten: +34 Zeichen zum Verzweigen.
Bearbeiten: -3 Zeichen. Überarbeitet, um den Operandenstapel für die Rekursionssteuerung zu verwenden. Dies macht das Basissystem viel einfacher. Aber Klammern brauchen einen unabhängigen Stapel, also habe ich die gespeicherte Position in den Wörterbuchstapel eingefügt und fast alle Einsparungen zurückgezahlt.

Neu gestaltet, um Zeichenfolgen und Ganzzahlen anstelle von Arrays und Namen zu verwenden.

Bearbeiten: -40 Zeichen. Es wurden zwei Prozeduren zum Aufrufen von Systemnamen nach Nummer hinzugefügt (Ich kann nicht scheinen, dass rohe Binärtoken funktionieren. Aber diese Redewendung funktioniert für mich.)

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

Semikommentierte Binärdatei.

/*{<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- "binär".

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

Dazu muss das L-System in einem Wörterbuch auf dem Dictstack definiert sein, mit der Anfangszeichenfolge und der Startposition der Schildkröte auf dem Operandenstapel (vor der Quelle, z. B. gs dragon.sys lsys.ps).

Drachenkurve.

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

Verzweigungsstiele.

[
    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

Ungolfed und kommentiert.

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

Um es auszuführen, können diese 3 Blöcke als 3 Dateien gespeichert werden: dragon.ps, stems.ps, lsys.ps (jeder der obigen Programmblöcke funktioniert identisch). Dann laufe mit gs: gs dragon.ps lsys.psoder gs stems.ps lsys.ps. Bei Bedarf können sie auch zuerst verkettet werden: cat dragon.ps lsys.ps | gs -oder cat stems.ps lsys.ps | gs -.

Drachenkurve

Kein Stängelbild. In höheren Tiefen wird es nicht interessanter.

Luser Droog
quelle
4

Mathematica 290

Diese Bare-Bones-Implementierung konzentriert sich eher auf die Ausgabe als auf die Verarbeitung. Es werden keine Produktionsregeln verwendet. Daher ist dies möglicherweise keine geeignete Antwort auf die Herausforderung.

Verzweigungsstiele nach Theo Grays Vorführung .

Code

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

Verwendung

Der erste Parameter bestimmt, ob die Drachenkurve oder die Zweigstämme angezeigt werden. Der zweite Begriff bezieht sich auf die Generation.

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

zweites Bild


Mehr Beispiele

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

fractal3

DavidC
quelle
1
Sehr hübsch. Aber würde es nicht ein paar Bytes sparen, um die Regel als Argument weiterzugeben?
Luser Droog
Wenn dies eine allgemeine Lösung wäre, könnte man vielleicht eher eine Regel als Parameter übergeben. Ich müsste mich mit Lindenmayer-Systemen besser auskennen als ich es derzeit bin.
DavidC
Ich lese kein Mathematica. Ich sollte etwas lernen. (Füge es dem Stapel hinzu :) Aber du kannst das so interpretieren, dass "was auch immer die Beschreibung des Bildes ausmacht, im Unterschied zu der Engine, die es antreibt", herausgerechnet werden kann. Wenn Sie dann die Daten ändern können, um einige Funktionen des Bildes zu steuern, unabhängig davon, ob Sie den richtigen Motor berühren . Ich würde das als "funktional äquivalent" zu einem L-System ansehen. [ Das sollte dir viele Lücken geben, mit denen du arbeiten kannst;) ]. Trotzdem +1, weil es so hübsch ist.
Luser Droog
1
@Dude Ich denke, es ist, weil die Grafik-Anforderungen für sie nicht gut geeignet sind
Dr. Belisarius
1
Schließlich herausgefunden, das L-System für Ihren Baum: A->F[+A][-A]Wo Fist bewegen, +ist links drehen 30, -ist rechts drehen 30, und [/ ]sind Push / Pop
Shmiddty