# 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).

This is code golf.

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

## Mathematica 200198188171 168

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

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

-
+1 A thing of beauty! –  David Carraher Jan 2 '13 at 14:23
Just modify `Graphics@k` by `Graphics@Flatten@k`if 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 very nice indeed ;) Could be a cool Demonstration. Do you submit those? –  Vitaliy Kaurov Apr 6 '13 at 2:32
@belisarius demonstrations.wolfram.com/GraphicalLSystems –  Vitaliy Kaurov Apr 6 '13 at 6:38

# Python, 369 294

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

``````from turtle import*
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==']':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.

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

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

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

# Postscript 264298295 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
/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
/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
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 -`.

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

-

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

More Examples

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

-
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
@dude I think it's because the graphics requirements aren't well suited for them –  belisarius Jan 3 '13 at 16:37
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