# Generate valid Fibonacci tilings

## 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. LLS
2. SL
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.

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

• Should that be LSLSL -> LL ? – user21677 Sep 30 '14 at 20:51
• @tolos Ah yes, good catch. I fixed that. FYI, this happened because I actually generated the string the other way round, starting from the bottom using similar decomposition rules, and those aren't exactly reversible when it comes to the boundaries of the fragment. – Martin Ender Sep 30 '14 at 21:06

# CJam, 7062 59 bytes

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


Reads from STDIN. Try it online.

$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. ";  ## 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 • @MartinBüttner, I normally would link to an online demo with golfscript.apphb.com, but it's running an old version with a bug around nested loops (fixed in the Dec 3, 2012 release) and can't correctly execute this program. – Peter Taylor Sep 30 '14 at 14:52 • @MartinBüttner Oops. Thanks guys for letting me know about the bug. I updated the website with the new GS version. Click this link for the demo. – Cristian Lupascu Sep 30 '14 at 15:58 • @w0lf, thanks for the update (and for the recent change to increase the time limit too). – Peter Taylor Sep 30 '14 at 16:05 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