# 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
• Is there any limit on the input N? like what is the max that N can be? – KrystosTheOverlord Sep 15 at 17:29

# 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. ";  # APL (Dyalog Unicode), 43 bytes (1+∘÷⍣=1){'LS'[∪2</⍺|(⍺×(⍳÷⊢)2*⍵)∘.+⍳⍵]}1∘+  Try it online! This uses the alternative formulation (actually the first one) shown in the linked paper: the closest integer staircase to the line $$\y = x/\phi\$$, where $$\\phi\$$ is the golden ratio $$\\frac{\sqrt5+1}{2}\$$. Given the initial vertical offset from the line $$\h\$$ (which can be positive or negative), the next term (one of LS) can be determined by the following rule: • If $$\h<0\$$ (below the line), $$\h←h+1\$$ and emit S. • Otherwise (over the line), $$\h←h-(\phi-1)\$$ and emit L. Since $$\h-(\phi-1) = h+1-\phi\$$, we can always increment and take modulo $$\\phi\$$ of it. Then the condition $$\h<0\$$ changes to $$\h<\phi-1\$$, but it doesn't affect the resulting sequence of terms. Then the problem becomes to sample enough values for initial $$\h\$$ so that we can get all possible sequences of SL for any given length $$\n\$$. I choose $$\2^{n+1}\$$ points uniformly spaced over the interval $$\[0,\phi)\$$, which works for small $$\n\$$, and the gap size reduces faster than that induced by the collection of lines $$\y=x/\phi+c\$$, each passing through some lattice point inside $$\0 \le x \le n\$$. Finally, I determine the actual SL terms by checking each consecutive pair: S if left < right, L otherwise, and take unique sequences. (1+∘÷⍣=1){'LS'[∪2</⍺|(⍺×(⍳÷⊢)2*⍵)∘.+⍳⍵]}1∘+ ⍝ Input: n (1+∘÷⍣=1){...}1∘+ ⍝ Pass n+1 and phi to the inner dfn... ⍳⍵ ⍝ Range 0..n ∘.+ ⍝ Outer product by addition... (⍺×(⍳÷⊢)2*⍵) ⍝ 2^(n+1) uniformly separated numbers in [0,phi) ⍺| ⍝ Modulo phi 2</ ⍝ Pairwise comparison in row direction ⍝ (1 if right is higher, 0 otherwise) ∪ ⍝ Take unique rows 'LS'[...] ⍝ Map 0, 1 to L, S  ## 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 # Brachylog, 69 bytes ~{Ėl|l.&ċ∈ᵛ"LS"&~c=ᵐ{¬{s₂tʰhᵗ=}&}cᵐ{"LL"∧"S"|"S"∧"L"|"L"∧""}ᵐcẹ↰∧}ᵘcᵐ  Try it online! ### How it works First define a predicate, that has a valid fibonacci tiling as input (as a list of "L" and "S"), and its length as output. Ėl|  It's either an empty list Ė, returning it's length l or … l.&ċ∈ᵛ"LS"  Something which length is the output and is a list which elements all are elements of "LS". (This part was rather annoying for how simple it should be; I couldn't generate strings up to length N consisting of "LS".) &~c=ᵐ  Also, the input splitted in groups where each group has only one unique element, e.g. [S, LL, S] or [S, L, L, S] or [LLLL] {¬{s₂tʰhᵗ=}&}  Has no two consecutive groups where the first group's last element and the second group's first element are the same – to filter out [S, L, L, S]. (Is there a way to drop {…&} here?) cᵐ{"LL"∧"S"|"S"∧"L"|"L"∧""}ᵐcẹ↰∧  Those groups are then replaced. If a group doesn't match one of the three rules, the whole partition of the string gets thrown out, i.e. [LLLL] isn't valid. The replaced groups then, converted to a list, must also fulfill this predicate. ~{…}ᵘcᵐ  We now find all unique fibonacci tilings that have the length of the input and convert the lists back to strings. 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