Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Execute a Lindenmayer System

A Lindenmayer System (or L-system) is related to Thue and Post systems, and is used in botanical modeling and fractal generation.

An L-system is described by string-rewriting where a symbol from the symbol-alphabet is mapped to a replacement sequence of symbols. A collection of these mappings constitutes the L-system proper.

The graphical output method as devised by Prusinkiewicz interprets the resulting sequence after the mappings have been applied to an initial sequence for a specified number of iterations, as Turtle-Drawing commands: forward, backward, left, right, that kind of stuff. This may require extra code to control the scale of the drawing as different iteration counts may produce drastically differently-sized images.

Your task is to execute an L-system in the fewest number of characters. Your program must be able to render both the Dragon Curve and the Branching Stems from the Wikipedia page by providing appropriate input (file, command-line, but external to the source, please).

Branching Stems Dragon Curve

This is code golf.

Edit: Here are some examples I've posted around town. answer to SO/rotate-to-north {Where I first discovered the L-system}, answer to SO/how-to-program-a-fractal, answer to SO/recursion-in-postscript, comp.lang.postscript discussion/recital, postscript l-system collection, codegolf.SE/draw-a-sierpinski-triangle {origin of the competition between myself and thomasW}.

share|improve this question
    
Skipped the sandbox. This seems relatively straightforward and should be fun. –  luser droog Dec 31 '12 at 11:32
    
BTW, anybody know the origin of the above quote? I've heard William James, and I've heard Faraday. –  luser droog Dec 31 '12 at 11:57
1  
Wikipedia says the origin is in dispute, best guess is Bertrand Russel. –  ugoren Dec 31 '12 at 13:09
    
ITYM Bertrand Russell. –  Paul R Dec 31 '12 at 16:06
1  
Are there any limits on the size of the alphabet, number of rules, number of rounds or possible (visualization) rules (draw a straight line, push/pop position/angle, turn how many degrees etc.) If we only need to draw those two then we would need pushing & popping, drawing straight lines and being able to turn 45 degrees in both directions, only two rules and an alphabet of size 4. –  shiona Dec 31 '12 at 16:54
show 4 more comments

5 Answers

up vote 22 down vote accepted

Mathematica 200 198 188 171 168

Spaces added for clarity:

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)

Where:

i : Initial state;
b : rotation angle
h : initial angle
j : initial position
r : production rules
n : iterations

Production rules grammar:

2 = Turn Left (-);
4 = Turn Right (+);
6 = Push and Turn Left ("[");
8 = Pop and Turn Right ("]");
C[i] = Draw (Any number of symbols)
Any other symbol = Do Nothing, just use it in producing next state (Any number of symbols)

The {2,4,6,8} sequence is there because I'm using I^n (I = imaginary unit) to make turns.

Examples:

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

Mathematica graphics

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 graphics

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 graphics

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 graphics

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 graphics

share|improve this answer
5  
+1 A thing of beauty! –  David Carraher Jan 2 '13 at 14:23
    
Just modify Graphics@k by Graphics@Flatten@kif you plan to use many iterations. Otherwise a Recursion Limit will bite you and your Mma session will abort. –  belisarius Jan 2 '13 at 21:03
    
My macro-expansion method had a similar issue with higher iterations. The strings just become enormous. But the solution there was not to flatten. :) –  luser droog Jan 3 '13 at 11:55
1  
+1 very nice indeed ;) Could be a cool Demonstration. Do you submit those? –  Vitaliy Kaurov Apr 6 '13 at 2:32
2  
@belisarius demonstrations.wolfram.com/GraphicalLSystems –  Vitaliy Kaurov Apr 6 '13 at 6:38
show 1 more comment

Python, 369 294

Not a winner but I'll post what I've tried anyway.

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

Not good at golfing Python...... Maybe someone else can do it.

Input

Input is from an external file named "l" (no extension), with the following format:
Line 1: Initial state (Axiom)
Line 2: Comma-separated rules

Symbols
f and F: Draw forward
+: Turn right 5 degrees
-: Turn left 5 degrees
[: Save position and heading
]: Pop position and heading
Other symbols are ignored by the drawing function.

Rules
A rule is in the format "predecessor":"successor(s)"
Note that the quotes are necessary, whether single or double.
predecessor must be a single character.
Also, there are no implicit constants: You must explicitly specify a no-change rule for those.

Examples

Branching stems

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

Output

Note that the source is modified to get this out put ONLY TO SCALE DOWN THE GRAPH TO THE VISIBLE AREA. The console is also used to hide the "turtle".

Dragon curve

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

Output

Again, the console is used to hide the "turtle".

Sierpinski Triangle

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

Output

Generations reduced to 5 here.

share|improve this answer
3  
You can get a decent saving (I make it 32 chars) by removing the functions f, r, l; adding a dummy parameter to o and c; and then changing the pseudo-switch to {'f':fd,'F':fd,'+':rt,'-':lt,'[':o,']':c}[k](5) –  Peter Taylor Jan 2 '13 at 13:13
    
You can also inline g, and I think o and c are worth eliminating with inline if statements (cheaper than the global declaration) –  Peter Taylor Jan 2 '13 at 13:36
    
Thanks!! Saved quite some chars. –  TwiNight Jan 2 '13 at 17:17
    
@PeterTaylor good work. I had an intuition that some of those functions could be inlined, but didn't know enough Python to suggest it articulately. –  luser droog Jan 3 '13 at 11:57
1  
@luserdroog, I don't know Python either: I just did trial and error to see what worked - i.e. some of the things I tried (e.g. using lambdas for o and c directly in the pseudo-switch) gave syntax errors, but others didn't. –  Peter Taylor Jan 3 '13 at 12:24
show 1 more comment

Javascript (179 bytes)

Not completely sure this qualifies, as the rules object does all of the actual drawing.

Demo (Dragon, animated):
-- Expanded: http://jsfiddle.net/SVkMR/9/show/light
-- With Code: http://jsfiddle.net/SVkMR/9/

Minified:

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

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

Input:

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
};
share|improve this answer
    
I think the animation more than compensates for any liberties with the rules. Good job! +1 –  luser droog Jan 30 '13 at 21:49
    
:) Fun stuff! . –  Shmiddty Jan 30 '13 at 21:57
add comment

Postscript 264 298 295 255

Here's my attempt to do it differently. Rather than the macro-expansion that I usually use, this one checks the size of the execution stack to bound the recursion. If the bound is exceeded, it stops recursively examining the procedure and tries to interpret turtle commands (and discards pop pop otherwise). An advantage of this method is that it does not require enormous amounts of memory. A disadvantage is the recursion control is rather clumsy, as the stack size grows by more than just 1 from one recursion level to the next.

Edit: +34 chars for branching.
Edit: -3 chars. Redesigned to use the operand stack for recursion control. This makes the basic system much simpler. But brackets need an independent stack, so I put the saved position in the dictionary stack, and almost paid back all the savings.

Also, redesigned to use strings and integers instead of arrays and names.

Edit: -40 chars. Added two procedures for calling system names by number (I can't seem to get raw binary tokens to work. But this idiom works for me.)

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

Semi-commented binary.

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

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

It requires the L-system to be defined in a dictionary on the dictstack, with the initial string and the starting position of the turtle on the operand stack (prepended to the source, eg. 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

Branching Stems.

[
    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 and commented.

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

To run it, these 3 blocks can be saved as 3 files: dragon.ps, stems.ps, lsys.ps (any of the above program blocks will work identically). Then run with gs: gs dragon.ps lsys.ps or gs stems.ps lsys.ps. They can also be concatenated first, if desired: cat dragon.ps lsys.ps | gs - or cat stems.ps lsys.ps | gs -.

dragon curve

No stems picture. It doesn't get any more interesting at higher depths.

share|improve this answer
add comment

Mathematica 290

This bare-bones implementation focuses on the output rather than the processing. It does not use production rules. So it may not be a suitable response to the challenge.

Branching stems adapted from Theo Gray's demonstration.

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

The first parameter determines whether the Dragon Curve or Branch Stems will be displayed. The second term refers to the generation.

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

second pic


More Examples

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

fractal3

share|improve this answer
1  
Very pretty. But wouldn't it save some bytes to pass the rule in as an argument? –  luser droog Dec 31 '12 at 21:38
    
If this were a general solution, perhaps one could pass a rule rather than parameters. I would have to be more knowledgeable about Lindenmayer Systems than I presently am. –  David Carraher Dec 31 '12 at 21:46
    
I don't read mathematica. I should go learn some. (add it to the stack :) But you can interpret that to mean "whatever constitutes the description of the image, as distinct from the engine that drives it" can be factored out. If you can then modify the data to control some feature of the image, independently from touching the engine proper; I'd consider that to be "functionally equivalent" to an L-system. [That should give you lots of loopholes to work with ;)]. +1 anyway 'cause it's so pretty. –  luser droog Jan 1 '13 at 3:45
1  
@dude I think it's because the graphics requirements aren't well suited for them –  belisarius Jan 3 '13 at 16:37
1  
Finally figured out the l-system for your tree: A->F[+A][-A] where F is move, + is rotate left 30, - is rotate right 30, and [/] are push/pop –  Shmiddty Jan 31 '13 at 22:25
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.