Generate valid Fibonacci tilings

Question

Background

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:
  1. LL → S
  2. S → L
  3. L → (empty string)

Let's look at some examples:

SLLSLLSLLSLS

This looks like a valid tiling, because it doesn't contain two *S*s or three *L*s but let's perform the composition:

LSLSLSLL

That still looks fine, but if we compose this again, we get

LLLS

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

LSLLSLSLLSLSLL

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.

The Challenge

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 S or L).

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.

Examples

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

Answer 1

CJam, 70 62 59 bytes

Qali{_'L:Xf+\'S:Yf++}*{{_X2*/Xf-Yf/Xf*Y*}h]N*_X3*#\Y2*#=},p

Reads from STDIN. Try it online.

Example run

$ cjam tilings.cjam <<< 5
["LLSLL" "SLSLL" "SLLSL" "LSLSL" "LSLLS" "LLSLS"]

How it works

The idea is to push all strings of L's and S's of the proper length, successively apply the transformation to each until the result is an empty string, concatenate the sequences of strings and search for the forbidden substrings.

Qa         " Push R := [ '' ].                                                            ";
li{        " Do the following int(input()) times:                                         ";
  _'L:Xf+  " Append (X := 'L') to a copy of all strings in R.                             ";
  \'S:Yf+  " Append (Y := 'S') to all original strings in R.                              ";
  +        " Concatenate the arrays into R.                                               ";
}*         " R now contains all strings of L's and S's of length int(input()).            ";
{          " For each S ∊ R:                                                              ";
  {        "                                                                              ";
    _      " Push a copy of S.                                                            ";
    X2*/   " Split S at 'LL'.                                                             ";
    Xf-    " Remove 'L' from the chunks.                                                  ";
    Yf/    " Split the chunks at 'S'.                                                     ";
    Xf*    " Join the chunks, separating by 'L'.                                          ";
    Y*     " Join, separating by 'S'.                                                     ";
  }h       " If the resulting string is non-empty, repeat.                                ";
  ]N*      " Join the array of resulting strings from S to '', separating by linefeeds.   ";
  _X3*#    " Push the index of 'LLL' a copy in the resulting string (-1 if not present).  ";
  \Y2*#    " Push the index of 'SS' in the original string (-1 if not present).           ";
  =        " Check if the indexes are equal; this happens if and only if both are -1.     ";
},         " Filter: Keep S in R if and only if = pushed 1.                               ";
p          " Print a string representation of R.                                          ";

Answer 2

GolfScript (86 bytes)

~:|'LS'1/\{{.{1&!'LLS'2/=}%'SS'/'SLS'*[.(1&{'LS'\+}*]{.)1&{'SL'+}*}/}%.&}*['']+{,|=},p

This is an inflationary approach: it starts with L and S and expands them using the rules LL -> SLS, L -> S, S -> LL, and leading or trailing S can have an L added at the word boundary.

Online demo

Answer 3

Haskell, 217

import Control.Monad
data F=L|S deriving (Eq)
f n=filter s$replicateM n [L,S]
r (L:L:m)=S:r m
r (S:m)=L:r m
r (L:m)=r m
r []=[]
s []=True
s m|v m=s$r m
s _=False
v (L:L:L:_)=False
v (S:S:_)=False
v (_:m)=v m
v []=True

Explaination:

I define 4 functions:

• f takes an integer and returns the result

  replicateM n [L,S] creates all possible permutations of [L,S] with the length n filter s ... will filter this list (of lists) with the function s

• r reduces a a given list by 1 level.

  This is simply done by pattern matching. A list starting with 2 L will become a list starting with S and the reduced remaining

• v validates a given list by the rules given (no 3 continuous L, no 2 continous S)

  if the list starts with one of the 2 illegal sequences (L,L,L or S,S) the result is False, an empty list is valid, and an non-empty list is checked again with the first element removed

• s checks if a list and all reduced lists are valid.

  Again: an empty list is valid (and can't be reduced further).
  If the list given as argument is valid then the list is reduced ad checked with s again.
  Otherwise the result is False