Exécuter un système Lindenmayer

Un système Lindenmayer (ou système L) est lié aux systèmes Thue et Post , et est utilisé dans la modélisation botanique et la génération fractale .

Un système L est décrit par réécriture de chaînes où un symbole de l'alphabet de symboles est mappé à une séquence de remplacement de symboles. Une collection de ces mappages constitue le système L proprement dit.

La méthode de sortie graphique conçue par Prusinkiewicz interprète la séquence résultante après que les mappages ont été appliqués à une séquence initiale pour un nombre spécifié d' itérations , en tant que commandes Turtle-Drawing: avant, arrière, gauche, droite, ce genre de choses. Cela peut nécessiter un code supplémentaire pour contrôler l'échelle du dessin, car différents nombres d'itérations peuvent produire des images de tailles radicalement différentes.

Votre tâche consiste à exécuter un système L avec le moins de caractères. Votre programme doit être capable de rendre à la fois la courbe de dragon et les tiges de branchement à partir de la page Wikipedia en fournissant une entrée appropriée (fichier, ligne de commande, mais externe à la source, s'il vous plaît).

C'est le golf de code.

Edit: Voici quelques exemples que j'ai publiés dans la ville. réponse à SO / rotation vers le nord { où j'ai découvert le système L pour la première fois } , réponse à SO / comment-programmer-une-fractale , réponse à SO / récursion-en-postscript , discussion comp.lang.postscript / considérant , collection postscript l-system , codegolf.SE/draw-a-sierpinski-triangle {origine de la compétition entre moi et thomasW} .

Mathematica 200 198 188 171 168 168

Espaces ajoutés pour plus de clarté:

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)

Où:

i: état initial;
b: angle de rotation
h: angle initial
j: position initiale
r: règles de production
n: itérations

Grammaire des règles de production:

2 = tourner à gauche (-);
4 = tourner à droite (+);
6 = Poussez et tournez à gauche ("[");
8 = Pop et tourner à droite ("]");
C [i] = Dessiner (N'importe quel nombre de symboles)
N'importe quel autre symbole = Ne rien faire, il suffit de l'utiliser pour produire l'état suivant (N'importe quel nombre de symboles)

La séquence {2,4,6,8} est là parce que j'utilise I^n( I= unité imaginaire) pour faire des tours.

Exemples:

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

Pas un gagnant mais je publierai ce que j'ai essayé de toute façon.

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

Pas bon au golf Python ...... Peut-être que quelqu'un d'autre peut le faire.

Contribution

L'entrée provient d'un fichier externe nommé "l" (sans extension), au format suivant:
Ligne 1 : état initial (Axiom)
Ligne 2 : règles séparées par des virgules

Symboles
f et F: Dessin en avant
+: Tournez à droite de 5 degrés
-: Tournez à gauche de 5 degrés
[: Enregistrez la position et le cap
]: Position pop et cap
D'autres symboles sont ignorés par la fonction de dessin.

Règles
Une règle est au format "predecessor":"successor(s)"
Notez que les guillemets sont nécessaires, qu'ils soient simples ou doubles.
predecessordoit être un seul caractère.
De plus, il n'y a pas de constantes implicites: vous devez explicitement spécifier une règle de non-modification pour celles-ci.

Exemples

Tiges ramifiées

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

Sortie

Notez que la source est modifiée pour obtenir ce résultat, UNIQUEMENT POUR ÉCHANGER LE GRAPHIQUE DANS LA ZONE VISIBLE. La console sert également à masquer la "tortue".

Courbe de dragon

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

Sortie

Encore une fois, la console est utilisée pour masquer la "tortue".

Triangle de Sierpinski

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

Générations de sortie réduites à 5 ici.

Javascript (179 octets)

Pas complètement sûr que cela se qualifie, car l'objet de règles effectue tout le dessin réel.

Démo (Dragon, animé):
- Développé: http://jsfiddle.net/SVkMR/9/show/light
- Avec code: http://jsfiddle.net/SVkMR/9/

Minifié:

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

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

Contribution:

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

Usage:

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

Postscript 264 298 295 255

Voici ma tentative de le faire différemment. Plutôt que la macro-expansion que j'utilise habituellement, celle-ci vérifie la taille de la pile d'exécution pour délimiter la récursivité. Si la limite est dépassée, il arrête d'examiner récursivement la procédure et essaie d'interpréter les commandes de tortue (et les rejette pop popsinon). Un avantage de cette méthode est qu'elle ne nécessite pas d'énormes quantités de mémoire. Un inconvénient est que le contrôle de récursivité est plutôt maladroit, car la taille de la pile augmente de plus de 1 d'un niveau de récursivité au suivant.

Edit: +34 caractères pour la ramification.
Edit: -3 caractères. Reconçu pour utiliser la pile d'opérandes pour le contrôle de la récursivité. Cela rend le système de base beaucoup plus simple. Mais les supports ont besoin d'une pile indépendante, j'ai donc mis la position enregistrée dans la pile de dictionnaires et j'ai presque remboursé toutes les économies.

Aussi, repensé pour utiliser des chaînes et des entiers au lieu des tableaux et des noms.

Modifier: -40 caractères. Ajout de deux procédures pour appeler les noms de système par numéro (je n'arrive pas à faire fonctionner les jetons binaires bruts . Mais cet idiome fonctionne pour moi.)

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

Binaire semi-commenté.

/*{<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- "binaire".

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

Il nécessite que le système L soit défini dans un dictionnaire sur la pile de dictées, avec la chaîne initiale et la position de départ de la tortue sur la pile d'opérandes (ajoutée à la source, par exemple gs dragon.sys lsys.ps).

Courbe du dragon.

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

Tiges de ramification.

[
    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

Non golfé et commenté.

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

Pour l'exécuter, ces 3 blocs peuvent être enregistrés sous 3 fichiers: dragon.ps, stems.ps, lsys.ps (n'importe lequel des blocs de programme ci-dessus fonctionnera de manière identique). Ensuite, exécutez avec gs: gs dragon.ps lsys.psou gs stems.ps lsys.ps. Ils peuvent également être concaténés en premier, si vous le souhaitez: cat dragon.ps lsys.ps | gs -ou cat stems.ps lsys.ps | gs -.

Aucune image de tiges. Cela ne devient plus intéressant à des profondeurs plus élevées.

Mathematica 290

Cette implémentation simple met l'accent sur la sortie plutôt que sur le traitement. Il n'utilise pas de règles de production. Ce n'est donc peut-être pas une réponse appropriée au défi.

Tiges ramifiées adaptées de la démonstration de Theo Gray .

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

Usage

Le premier paramètre détermine si la courbe du dragon ou les tiges de branche seront affichées. Le deuxième terme fait référence à la génération.

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

Plus d'exemples

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