Algorithms Fractals Math

Riddle of the Week – LStrings

So I wrote about lstrings. I intend to write about them again in a short while – I already finished the basic script a few days ago, but I’m waiting, until I will be satisfied with it.

In the meantime, here is a curious riddle (That I came up with):

Version 1 (not final)

Assume you are given some iteration of an lstring – S. How do you discover the original lstring used to create S?


Well, those who are quick to answer will first try to discover the length of the original string – it could be computed directly from S. At this point you should come to the conclusion that without being given the exact number of iterations – the riddle is not that interesting… Iterating on an lstring is an associative operation. If we denote the substitution of a string A into a string B as multiplication, when both are iterations on an original string T , we will get:

A*B =T^n * T^k = T^(n+k) = T^k* T^n

This will result in the obvious answer to the original riddle – “Why, the lstring S is the original string, with zero iterations!”. This answer is correct – and obviously useless :)

So, let us rephrase the riddle:

Version 2 (final)

Assume you are given some iteration of an lstring – S. How do you discover the minimum possible lstring that could be used to create S?

Discussion – But not a solution

This is the proper riddle – have at it! I will be glad to read your thoughts…

note: The acceptable solution should be either an algorithm, or a constructive mathematical proof. I don’t like reading only statements of existence :)

Fractals Programming Python

Fractals in 10 minutes No. 1 – LStrings

Lately it started to be quite fun to find some fun mathematical formula, and just code it in python, and plot the result. Fractals are such fun. LStrings is an example of that. For those who don’t know – lstrings are simple strings with three letters, ‘f’ for forward, ‘l’ for left, ‘r’ for right. An iteration of an lstring is replacing all occurrences of ‘f’ with the original string.

During high-school I recall long lessons when I would draw complicated iterations of some simple lstring just to see the result. Sometimes I still draw them. A few days ago I just wanted to see how long it would take me to program one. It actually was quite short. What really took me time is blogging about it ;)

The source and the results are available here.

This post is going to be the first in a series of posts about some fractals. I will continue to write other examples of simple code that (hopefully) generates beautiful results. Stay tuned for more.

Do you know any elegant\short\simple pieces of code that generate fractals?