16
\$\begingroup\$

Background

An L-system (or Lindenmayer system) is a parallel rewriting system that, among other things, can be easily used to model fractals. This question concerns deterministic, context-free L-systems. These consists of an alphabet of symbols, an initial axiom string and a set of rewrite rules mapping each alphabet symbol to a new string. The rules are applied to the axiom in parallel, generating a new string. This process is then repeated.

For example, the system with the axiom "A" and the rules A=ABA;B=BBB generates the sequence of strings "ABA", "ABABBBABA", "ABABBBABABBBBBBBBBABABBBABA", etc. For conciseness, we don't explicitly mention the alphabet when defining the L-system. Furthermore, any symbol without an explicit rewrite rule is assumed to be unchanged (i.e. the default rule for a symbol A is A=A).

L-systems can be visualised using a form of turtle graphics. By convention, the turtle starts facing to the right. A string is then drawn by iterating over its symbols: an F means "draw forward one unit", a G means "move forward one unit", a + means "turn left one angle unit" and a - means "turn right one angle unit". All other symbols in the string are ignored. For the purpose of this question, the angle units are assumed to always be 90°.

Task

Given a specification of any L-system and a number of iterations, your program should output an ASCII rendering of the resulting string (as described above) using box-drawing characters.

  • The parameters are passed in as a space-separated string comprising the axiom, rewrite rules (as a ;-separated list of equations) and number of rewrite iterations. For example, the input "F F=FGF;G=GGG 2" generates the string "FGFGGGFGF" and hence draws four lines with appropriate gaps.
  • The symbols used by the L-system can be any ASCII character apart from space and semicolon. There is at most one explicit rule specified per symbol (with the default rewrite rule being the identity mapping as described above).
  • You can assume that the output will always contain at least one F.
  • The output should use the following UNICODE box-drawing characters to represent the visualization: ─ (U+2500), │ (U+2502), ┌ (U+250C), ┐ (U+2510), └ (U+2514), ┘ (U+2518), ├ (U+251C), ┤ (U+2524), ┬ (U+252C), ┴ (U+2534), ┼ (U+253C), ╴ (U+2574), ╵ (U+2575), ╶ (U+2576) and ╷ (U+2577). See below for examples.
  • The output should not contain empty lines above the topmost box character or below the bottommost one. It should also not contain any spaces to the left of the leftmost box characer or to the right of the rightmost one. Lines with trailing spaces that don't extend beyond the rightmost box character are allowed.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument. Results should be printed to STDOUT (or closest alternative), saved to a file or returned as a string.

Examples

# Cantor dust
>> "F F=FGF;G=GGG 0"
╶╴
>> "F F=FGF;G=GGG 1"
╶╴╶╴
>> "F F=FGF;G=GGG 2"
╶╴╶╴  ╶╴╶╴
>> "F F=FGF;G=GGG 3"
╶╴╶╴  ╶╴╶╴        ╶╴╶╴  ╶╴╶╴

# Koch curve
>> "F F=F+F−F−F+F 1"
 ┌┐
╶┘└╴
>> "F F=F+F-F-F+F 2"
    ┌┐
   ┌┘└┐
  ┌┘  └┐
 ┌┼┐  ┌┼┐
╶┘└┘  └┘└╴

Other examples to test your program with include:

# Dragon curve
>> "FX X=X+YF+;Y=-FX-Y n"

# Hilbert curve
>> "A A=-BF+AFA+FB-;B=+AF-BFB-FA+ n"

# Sierpinski carpet
>> "F F=F+F-F-F-G+F+F+F-F;G=GGG n"

The first two of which look as follows (produced using @edc65's answer):

enter image description here enter image description here

You can test out any of the systems at this page.

Scoring

Shortest code (in bytes) wins. Standard rules apply.

Miscellania

This challenge was inspired by Draw a Random Walk with Slashes. In fact, it's possible to represent a random walk as an L-system if we extend the system to allow multiple rules per symbol, with the expansion chosen non-determistically during rewriting. One formulation is:

"F F=FF;F=F+F;F=F++F;F=F+++F"

Another common extension, often used when modeling plants, is to interpret the [ and ] characters as pushing and popping the current position and angle. Most plants use angles smaller than 90°, but here is one example that doesn't:

"FAX X=[-FAX][FAX][+FAX];A=AFB;B=A"

Neither of these examples need to be supported in this challenge.

This challenge is also similar to "Sorry, young man, but it's Turtles all the way down!". However, that challenge used line rendering rather than ASCII and allowed a more flexible syntax.

\$\endgroup\$
7
\$\begingroup\$

JavaScript (ES6), 440 bytes (410 chars)

F=p=>([a,r,n]=p.split(' '),t=>{r.split(';').map(x=>r[x[0]]=x.slice(2),r={});for(;n--;)a=[...a].map(c=>r[c]||c).join('');u=x=y=0,g=[];for(c of a)c=='+'?[t,u]=[u,-t]:c=='-'?[u,t]=[t,-u]:c<'F'|c>'G'?0:((y+=u)<0?(g=[[],...g],++y):g[y]=g[y]||[],(x+=t)<0?(g=g.map(r=>[,...r]),++x):0,c>'F'?0:g[g[f=t?0.5:2,y][x]|=(3+t-u)*f,y-u][x-t]|=(3+u-t)*f)})(1)||g.map(r=>[for(c of r)' ╶╴─╵└┘┴╷┌┐┬│├┤┼'[~~c]].join('')).join('\n')

Less golfed

F=p=>{
  [a,r,n]=p.split(' '),
  r.split(';').map(x=>r[x[0]]=x.slice(2),r={}); // set rules
  for(;n--;)a=[...a].map(c=>r[c]||c).join(''); // build string
  t=1,u=x=y=0, // start pos 0,0 start direction 1,0
  g=[[]]; // rendering in bitmap g
  for(c of a)
    c=='+'?[t,u]=[u,-t] // left turn
    :c=='-'?[u,t]=[t,-u] // right turn
    :c=='F'|c=='G'?(     // move or draw
      (y+=u)<0?(g=[[],...g],++y):g[y]=g[y]||[], // move vertical, enlarge grid if needed
      (x+=t)<0?(g=g.map(r=>[,...r]),++x):0, // move horizontal, enlarge grid if needed
      c=='F'&&( // draw: set bits
        f=t?0.5:2,
        g[y][x]|=(3+t-u)*f,
        g[y-u][x-t]|=(3+u-t)*f
      )
    ):0;
  // render bits as box characters
  return g.map(r=>[' ╶╴─╵└┘┴╷┌┐┬│├┤┼'[~~c]for(c of r)].join('')).join('\n')
}

Test Code snippet to test (in Firefox)

F=p=>([a,r,n]=p.split(' '),t=>{r.split(';').map(x=>r[x[0]]=x.slice(2),r={});for(;n--;)a=[...a].map(c=>r[c]||c).join('');u=x=y=0,g=[];for(c of a)c=='+'?[t,u]=[u,-t]:c=='-'?[u,t]=[t,-u]:c<'F'|c>'G'?0:((y+=u)<0?(g=[[],...g],++y):g[y]=g[y]||[],(x+=t)<0?(g=g.map(r=>[,...r]),++x):0,c>'F'?0:g[g[f=t?0.5:2,y][x]|=(3+t-u)*f,y-u][x-t]|=(3+u-t)*f)})(1)||g.map(r=>[for(c of r)' ╶╴─╵└┘┴╷┌┐┬│├┤┼'[~~c]].join('')).join('\n')

fs=18;(Z=d=>(Result.style.fontSize=(fs+=d)+'px',Result.style.lineHeight=fs+'px'))(0)
#Result { font-size: 10px }
#Param { width: 400px }
Param: <input type=text id=Param />
<button onclick="Result.innerHTML=F(Param.value)">Start</button><br>
Output <button onclick="Z(-2)">Z-</button> <button onclick="Z(2)">Z+</button>
<br>
<pre id=Result></pre>

\$\endgroup\$
  • \$\begingroup\$ Great (and quick!) answer. I've added screenshots of the dragon and hilbert curve outputs to the question. \$\endgroup\$ – Uri Zarfaty Apr 10 '15 at 16:04
6
\$\begingroup\$

Haskell, 568 bytes

import Data.List.Split
p=splitOn
l=lookup
m=maximum
n=minimum
o[h,x]=(h,x)
Just x#_=x
_#x=x
g[s,r,i]=iterate((\c->lookup[c](map(o.p"=")(p";"r))#[c])=<<)s!!read i
u v@(a,x,y,d,e)c|c=='+'=(a,x,y,-e,d)|c=='-'=(a,x,y,e,-d)|c=='G'=(a,x+d,y+e,d,e)|c=='F'=(s(x,y)(d%e)a:s(x+d,y+e)(d?e)a:a,x+d,y+e,d,e)|1<2=v
s p n a=(p,n+(l p a)#0)
1%0=2;0%1=8;-1%0=1;0%(-1)=4
1?0=1;0?1=4;-1?0=2;0?(-1)=8
f z=unlines[[" ╴╶─╷┐┌┬╵┘└┴│┤├┼"!!(l(x,y)q#0)|x<-[n a..m a]]|y<-[m b,m b-1..n b]]where a=map(fst.fst)q;b=map(snd.fst)q;(q,_,_,_,_)=foldl u([],0,0,1,0)$g$p" "z

Test run:

*Main> putStr $ f "F F=F-F+F+F-F 3"
╶┐┌┐  ┌┐┌┐        ┌┐┌┐  ┌┐┌╴
 └┼┘  └┼┼┘        └┼┼┘  └┼┘
  └┐  ┌┼┼┐        ┌┼┼┐  ┌┘
   └┐┌┼┘└┘        └┘└┼┐┌┘
    └┼┘              └┼┘   
     └┐              ┌┘
      └┐┌┐        ┌┐┌┘
       └┼┘        └┼┘
        └┐        ┌┘
         └┐┌┐  ┌┐┌┘
          └┼┘  └┼┘
           └┐  ┌┘
            └┐┌┘
             └┘

How it works:

  • rewriting (function g): I parse the rules into an association list (letter -> replacement string) and repeatedly map it over the axiom.
  • creating the path (function u for a single step): I do not store the path in a matrix but in another association list with (x,y) positions as the keys and bit patterns of the 4 basic blocks (,, and ) as values. Along the way I keep track of the current position and direction.
  • drawing the path (function f): first I calculate the max/min dimensions from the path list and then I iterate over [max y -> min y] and [min x -> max x] and lookup the blocks to draw.
\$\endgroup\$
0
\$\begingroup\$

ES7, 394 chars, 424 bytes

F=p=>([a,r,n]=p.split` `,t=>{r.split`;`.map(x=>r[x[0]]=x.slice(2),r={});for(;n--;)a=[...a].map(c=>r[c]||c).join``;u=x=y=0,g=[];for(c of a)c=='+'||c=='-'?[t,u]=[u,-t]:c<'F'|c>'G'?0:((y+=u)<0?(g=[[],...g],++y):g[y]=g[y]||[],(x+=t)<0?(g=g.map(r=>[,...r]),++x):0,c>'F'?0:g[g[f=t?0.5:2,y][x]|=(3+t-u)*f,y-u][x-t]|=(3+u-t)*f)})(1)||g.map(r=>[for(c of r)'╶╴─╵└┘┴╷┌┐┬│├┤┼'[~~c]].join``).join`
`
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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