{"id":380,"date":"2013-03-24T16:15:33","date_gmt":"2013-03-24T16:15:33","guid":{"rendered":"http:\/\/opisthokonta.net\/?p=380"},"modified":"2013-05-27T22:04:13","modified_gmt":"2013-05-27T22:04:13","slug":"l-system-in-python","status":"publish","type":"post","link":"https:\/\/opisthokonta.net\/?p=380","title":{"rendered":"L-system in Python"},"content":{"rendered":"

The other day I was skimming trough articles on different subjects on Wikipedia. After a while I stumbled across the article on L-systems<\/a>. 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<\/em> in L-system terminology) in that string you apply a set of rules<\/em> that change that character into a set of new characters. Then you repeat n<\/em> times. The resulting string is then a recipe for a graph or geometric structure. See the Wikipedia article for more details and examples.<\/p>\n

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<\/em>, and constants<\/em> are defined implicitly by the production rules. <\/p>\n

Here are two example from the Wikipedia article:<\/p>\n

\r\n\r\n#Algae example\r\nalgaeRules = { "A" : "AB",\r\n\t\t"B" : "A",}\r\n\t\t\r\nalgaeExample = lsystem("A", 7, algaeRules)\r\nprint(algaeExample)\r\n\r\n#ABAABABAABAABABAABABAABAABABAABAAB\r\n<\/pre>\n
\r\n#Sierpinski triangle example\r\nsierpinskiRules = {"A": "B-A-B",\r\n\t\t\t\t\t"B": "A+B+A"}\r\n\r\nsierpinskiExample = lsystem("A", 3, sierpinskiRules)\r\nprint(sierpinskiExample)\r\n#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\r\n<\/pre>\n
Here is the code for the lsystem() function, including the function that does not use recursion. <\/p>\n
\r\ndef _applyRules(letter, rules):\r\n\t"""Internal function for applying production rules on a single character."""\r\n\ttry:\r\n\t\treturn rules[letter]\r\n\texcept:\r\n\t\treturn letter\r\n\r\ndef lsystem(init, n, rulesDict):\r\n\t"""Return the n-th iteration of a L-system (generated recursively)."""\r\n\t\r\n\tif n <= 0:\r\n\t\treturn init\r\n\tif n == 1:\r\n\t\treturn "".join([_applyRules(i, rulesDict) for i in init])\r\n\telse:\r\n\t\tnewCond = "".join([_applyRules(i, rulesDict) for i in init])\r\n\t\treturn lsystem(newCond, n-1, rulesDict)\r\n\t\r\n\t\r\n\r\ndef lsystemNonRecursive(init, n, rulesDict):\r\n\t"""Return the n-th iteration of a L-system."""\r\n\t\r\n\tif n <= 0:\r\n\t\treturn init\r\n\telse:\r\n\t\tcurrentCond = init\r\n\t\twhile True:\r\n\t\t\tcurrentCond = "".join([_applyRules(i, rulesDict) for i in currentCond])\r\n\t\t\tn -= 1\r\n\t\t\tif n == 0:\r\n\t\t\t\treturn currentCond\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
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 … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[],"class_list":["post-380","post","type-post","status-publish","format-standard","hentry","category-python"],"_links":{"self":[{"href":"https:\/\/opisthokonta.net\/index.php?rest_route=\/wp\/v2\/posts\/380","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/opisthokonta.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/opisthokonta.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/opisthokonta.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/opisthokonta.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=380"}],"version-history":[{"count":23,"href":"https:\/\/opisthokonta.net\/index.php?rest_route=\/wp\/v2\/posts\/380\/revisions"}],"predecessor-version":[{"id":472,"href":"https:\/\/opisthokonta.net\/index.php?rest_route=\/wp\/v2\/posts\/380\/revisions\/472"}],"wp:attachment":[{"href":"https:\/\/opisthokonta.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=380"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/opisthokonta.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=380"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/opisthokonta.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=380"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}