J and L-systems

Question

I'm going to create a program that can generate strings from L-system grammars.

Astrid Lindenmayer's original L-System for modelling the growth of algae is:

variables : A B  
constants : none  
axiom     : A  
rules     : (A → AB), (B → A)

which produces:

iteration | resulting model
        0 | A
        1 | AB
        2 | ABA
        3 | ABAAB
        4 | ABAABABA
        5 | ABAABABAABAAB

that is naively implemented by myself in J like this:

   algae =: 1&algae : (([: ; (('AB'"0)`('A'"0) @. ('AB' i. ]))&.>"0)^:[) "1 0 1
   (i.6) ([;algae)"1 0 1 'A'
┌─┬─────────────┐
│0│A            │
├─┼─────────────┤
│1│AB           │
├─┼─────────────┤
│2│ABA          │
├─┼─────────────┤
│3│ABAAB        │
├─┼─────────────┤
│4│ABAABABA     │
├─┼─────────────┤
│5│ABAABABAABAAB│
└─┴─────────────┘

Step-by-step illustration:

   ('AB' i. ]) 'ABAAB' NB. determine indices of productions for each variable
0 1 0 0 1
   'AB'"0`('A'"0)@.('AB' i. ])"0 'ABAAB' NB. apply corresponding productions 
AB
A 
AB
AB
A
   'AB'"0`('A'"0)@.('AB' i. ])&.>"0 'ABAAB' NB. the same &.> to avoid filling
┌──┬─┬──┬──┬─┐
│AB│A│AB│AB│A│
└──┴─┴──┴──┴─┘
   NB. finally ; and use ^: to iterate

By analogy, here is a result of the 4th iteration of L-system that generates Thue–Morse sequence

   4 (([: ; (0 1"0)`(1 0"0)@.(0 1 i. ])&.>"0)^:[) 0
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

That is the best that I can do so far. I believe that boxing-unboxing method is insufficient here. This is the first time I've missed linked-lists in J - it's much harder to code grammars without them.

What I'm really thinking about is:
a) constructing a list of gerunds of those functions that build final string (in my examples those functions are constants like 'AB'"0 but in case of tree modeling functions are turtle graphics commands) and evoking (`:6) it,
or something that I am able to code:
b) constructing a string of legal J sentence that build final string and doing (".) it.
But I'm not sure if these programs are efficient.

• Can you show me a better approach please?

Any hints as well as comments about a) and b) are highly appreciated!

Kp

Answer 1

The following will pad the rectangular array with spaces:

   L=: rplc&('A';'AB';'B';'A')
   L^:(<6) 'A'
A            
AB           
ABA          
ABAAB        
ABAABABA     
ABAABABAABAAB

Or if you don't want padding:

   L&.>^:(<6) <'A'
┌─┬──┬───┬─────┬────────┬─────────────┐
│A│AB│ABA│ABAAB│ABAABABA│ABAABABAABAAB│
└─┴──┴───┴─────┴────────┴─────────────┘

Obviously you'll want to inspect rplc / stringreplace to see what is happening under the covers.

Pandanus

Unless performance is an issue, rplc is the most straightforward approach. – Poultry

Answer 2

You can use complex values in the left argument of # to expand an array without boxing.

For this particular L-system, I'd probably skip the gerunds and use a temporary substitution:

to  =: 2 : 'n (I.m=y) } y'        NB. replace n with m in y
ins =: 2 : '(1 j. m=y) #!.n y'    NB. insert n after each m in y
L =:  [: 'c'to'A' [: 'A'ins'B' [: 'B'to'c' ]

Then:

    L^:(<6) 'A'
A
AB
ABA
ABAAB
ABAABABA
ABAABABAABAAB

Here's a more general approach that simplifies the code by using numbers and a gerund composed of constant functions:

   'x'-.~"1 'xAB'{~([:,(0:`(1:,2:)`1:)@.]"0)^:(<6) 1
A
AB
ABA
ABAAB
ABAABABA
ABAABABAABAAB

The AB are filled in at the end for display. There's no boxing here because I use 0 as a null value. These get scattered around quite a bit but the -.~"1 removes them. It does pad all the resulting strings with nulls on the right. If you don't want that, you can use <@-.~"1 to box the results instead:

   'x'<@-.~"1 'xAB'{~([:,(0:`(1:,2:)`1:)@.]"0)^:(<6) 1
┌─┬──┬───┬─────┬────────┬─────────────┐
│A│AB│ABA│ABAAB│ABAABABA│ABAABABAABAAB│
└─┴──┴───┴─────┴────────┴─────────────┘

Ygerne

Than you, your answer is useful for me, however the answer of Tikkanz appeared to be more efficient both in time and space. And thanks for pointing the ^:(<n) construct - I didn't know it. – Kp