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

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

Answer 2

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 3

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 4

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.

Answer 5

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