# L-system in Python

The other day I was skimming trough articles on different subjects on Wikipedia. After a while I stumbled across the article on L-systems. In short, L-systems is method for generating fractals using simple string manipulations. You start out with an initial string, and for each character (called variable in L-system terminology) in that string you apply a set of rules that change that character into a set of new characters. Then you repeat n times. The resulting string is then a recipe for a graph or geometric structure. See the Wikipedia article for more details and examples.

I decided to try to implement this in Python. I only implemented the string manipulation engine and not a graphing tool. It was fairly easy, and the first method I came up with takes only about 15 lines of code and relies on recursion. A method without recursion is a couple of lines more, but probably more efficient. The user have to supply their own substitution rules by using a Python dictionary. Each key in the dictionary corresponds to a variable, and constants are defined implicitly by the production rules.

Here are two example from the Wikipedia article:

```
#Algae example
algaeRules = { "A" : "AB",
"B" : "A",}

algaeExample = lsystem("A", 7, algaeRules)
print(algaeExample)

#ABAABABAABAABABAABABAABAABABAABAAB
```
```#Sierpinski triangle example
sierpinskiRules = {"A": "B-A-B",
"B": "A+B+A"}

sierpinskiExample = lsystem("A", 3, sierpinskiRules)
print(sierpinskiExample)
#B-A-B+A+B+A+B-A-B-A+B+A-B-A-B-A+B+A-B-A-B+A+B+A+B-A-B
```

Here is the code for the lsystem() function, including the function that does not use recursion.

```def _applyRules(letter, rules):
"""Internal function for applying production rules on a single character."""
try:
return rules[letter]
except:
return letter

def lsystem(init, n, rulesDict):
"""Return the n-th iteration of a L-system (generated recursively)."""

if n <= 0:
return init
if n == 1:
return "".join([_applyRules(i, rulesDict) for i in init])
else:
newCond = "".join([_applyRules(i, rulesDict) for i in init])
return lsystem(newCond, n-1, rulesDict)

def lsystemNonRecursive(init, n, rulesDict):
"""Return the n-th iteration of a L-system."""

if n <= 0:
return init
else:
currentCond = init
while True:
currentCond = "".join([_applyRules(i, rulesDict) for i in currentCond])
n -= 1
if n == 0:
return currentCond
```

## 2 thoughts on “L-system in Python”

1. Jeg forsøkte meg på min egen variant, før jeg leste denne posten, og det ble stort sett ganske likt. Jeg hadde ikke tenkt på try-except-varianten for å fylle ut dicten. Jeg håper det blir riktig formatert:

```def fyllfunksjon(f,start=''):
""" Tar f som dict og fyller ut potensielt manglende verdier."""
alfa = ''.join((f.values())) + start # det effektive alfabetet til L-systemet.
newf = dict([(i,i) for i in alfa])
newf.update(f)
return newf

def lsys(f,start='',n=10):
""" Beregner n iterasjoner av lsys."""
f = fyllfunksjon(f,start)
for i in xrange(1,n+1):
start = ''.join(([f[x] for x in start]))
return start
```

Jeg er ikke helt fornøyd med fyllfunksjonfunksjonen min, den ser litt uelegant ut, men jeg er ikke fornøyd med den mer elegante try-except varianten heller, for den skaper unødvendig mange function calls, som koster mer enn å looke up i en dictionary, regner jeg med?

Tenkt på å lage en variant for stokastiske L-systemer? Det letteste blir kanskje forandre inputet til en liste av 3-tupler (som (“A”,0.3,”AB”),(“A”,0.7,”BA”)), sjekke at sannsynlighetene summerer seg til en, og kjøre en uniform fordeling for å velge riktig variant.

• Synes ideen om å fylle opp dict-en med de manglende verdiene var smart. Det hadde jeg ikke tenkt på. Det er sikkert litt raskere enn min løsning. Jeg vet ikke hvor mye ett funksjonskall koster, men try/except koster ihvertfall litt mer enn en en enkel if/else.

Jeg har tenkt så mye på hvordan jeg ville gjort det med stokastiske regler. Hvis jeg skulle fortsatt med et dict-basert system ville jeg kanskje prøvd å ha en 2-tuppel, med ett av elementene en liste over sannsynlighetene og det andre elementet en liste over tilsvarende outputs.