The Fibonacci tiling is a tiling of the (1D) line using two segments: a short one, S, and a long one, L (their length ratio is the golden ratio, but that's not relevant to this challenge). For a tiling using these two prototiles to actually be a Fibonacci tiling, the following conditions have to be fulfilled:
- The tiling must not contain the subsequence SS.
- The tiling must not contain the subsequence LLL.
- If a new tiling is composed by performing all of the following substitutions, the result must still be a Fibonacci tiling:
- LL → S
- S → L
- L → (empty string)
Let's look at some examples:
This looks like a valid tiling, because it doesn't contain two *S*s or three *L*s but let's perform the composition:
That still looks fine, but if we compose this again, we get
which is not a valid Fibonacci tiling. Therefore, the two previous sequences weren't valid tilings either.
On the other hand, if we start with
and repeatedly compose this to shorter sequences
LSLLSLLS LSLSL LL S
all results are valid Fibonacci tilings, because we never obtain SS or LLL anywhere inside those strings.
For further reading, there is a thesis which uses this tiling as a simple 1D analogy to Penrose tilings.
Write a program or function which, given a non-negative integer N, returns all valid Fibonacci tiling in the form of strings containing N characters (being
You may take input via function argument, STDIN or ARGV and return or print the result.
This is code golf, the shortest answer (in bytes) wins.
N Output 0 (an empty string) 1 S, L 2 SL, LS, LL 3 LSL, SLS, LLS, SLL 4 SLSL, SLLS, LSLS, LSLL, LLSL 5 LLSLL, LLSLS, LSLLS, LSLSL, SLLSL, SLSLL ... 8 LLSLLSLS, LLSLSLLS, LSLLSLLS, LSLLSLSL, LSLSLLSL, SLLSLLSL, SLLSLSLL, SLSLLSLL, SLSLLSLS