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