Antecedentes

El mosaico de Fibonacci es un mosaico de la línea (1D) que utiliza dos segmentos: uno corto, S y uno largo, L (su relación de longitud es la relación de oro, pero eso no es relevante para este desafío). Para que un mosaico que utiliza estos dos prototipos sea realmente un mosaico de Fibonacci, se deben cumplir las siguientes condiciones:

• El mosaico no debe contener la subsecuencia SS .
• El mosaico no debe contener la subsecuencia LLL .
• Si un nuevo mosaico se compone realizando todas las sustituciones siguientes, el resultado debe ser un mosaico de Fibonacci:
  1. LL → S
  2. S → L
  3. L → (cadena vacía)

Veamos algunos ejemplos:

SLLSLLSLLSLS

Esto parece un mosaico válido, porque no contiene dos * S * so tres * L * s, pero realicemos la composición:

LSLSLSLL

Eso todavía se ve bien, pero si volvemos a componer esto, obtenemos

LLLS

que no es un mosaico válido de Fibonacci. Por lo tanto, las dos secuencias anteriores tampoco eran válidas.

Por otro lado, si comenzamos con

LSLLSLSLLSLSLL

y componer esto repetidamente en secuencias más cortas

LSLLSLLS
LSLSL
LL
S

todos los resultados son inclinaciones de Fibonacci válidas, porque nunca obtenemos SS o LLL en ningún lugar dentro de esas cadenas.

Para leer más, hay una tesis que usa este mosaico como una simple analogía 1D a las inclinaciones de Penrose.

El reto

Escriba un programa o función que, dado un número entero no negativo N , devuelva todos los mosaicos de Fibonacci válidos en forma de cadenas que contienen N caracteres (being So L).

Puede tomar la entrada a través del argumento de función, STDIN o ARGV y devolver o imprimir el resultado.

Este es el código golf, gana la respuesta más corta (en bytes).

Ejemplos

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

CJam, 70 62 59 bytes

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

Lecturas de STDIN. Pruébalo en línea.

Ejecución de ejemplo

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

Cómo funciona

La idea es empujar todas las cadenas de L y S de la longitud adecuada, aplicar sucesivamente la transformación a cada una hasta que el resultado sea una cadena vacía, concatenar las secuencias de cadenas y buscar las subcadenas prohibidas.

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

Este es un enfoque inflacionario: comienza con Ly S, y los amplía el uso de las reglas LL -> SLS, L -> S, S -> LL, y el principio o al final Spuede tener un Lañadido en el límite de palabra.

Demostración en línea

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

Explicación:

Defino 4 funciones:

• f toma un entero y devuelve el resultado

  replicateM n [L,S]crea todas las permutaciones posibles [L,S]con la longitud n filter s ...filtrará esta lista (de listas) con la funcións

• r reduce una lista dada en 1 nivel.

  Esto se hace simplemente por coincidencia de patrones. Una lista que comienza con 2 Lse convertirá en una lista que comience con Sel resto

• v valida una lista dada por las reglas dadas (no 3 continuas L, no 2 continuas S)

  si la lista comienza con una de las 2 secuencias ilegales (L, L, L o S, S), el resultado es que Falseuna lista vacía es válida y una lista no vacía se verifica nuevamente con el primer elemento eliminado

• s comprueba si una lista y todas las listas reducidas son válidas.

  Nuevamente: una lista vacía es válida (y no se puede reducir más).
  Si la lista dada como argumento es válida, la lista se reduce y se svuelve a verificar .
  De lo contrario, el resultado esFalse