Contexte

Le pavage Fibonacci est un pavage de la ligne (1D) utilisant deux segments: un court, S et un long, L (leur rapport de longueur est le nombre d'or, mais ce n'est pas pertinent pour ce défi). Pour qu'un carrelage utilisant ces deux prototiles soit réellement un carrelage de Fibonacci, les conditions suivantes doivent être remplies:

• Le pavage ne doit pas contenir la sous-séquence SS .
• Le pavage ne doit pas contenir la sous-séquence LLL .
• Si un nouveau pavage est composé en effectuant toutes les substitutions suivantes, le résultat doit toujours être un pavage de Fibonacci:
  1. LL → S
  2. S → L
  3. L → (chaîne vide)

Regardons quelques exemples:

SLLSLLSLLSLS

Cela ressemble à un pavage valide, car il ne contient pas deux * S * ou trois * L * mais effectuons la composition:

LSLSLSLL

Cela semble toujours bien, mais si nous composons à nouveau cela, nous obtenons

LLLS

qui n'est pas un pavage Fibonacci valide. Par conséquent, les deux séquences précédentes n'étaient pas non plus des pavages valides.

D'un autre côté, si nous commençons par

LSLLSLSLLSLSLL

et composer à plusieurs reprises cela en séquences plus courtes

LSLLSLLS
LSLSL
LL
S

tous les résultats sont des pavages de Fibonacci valides, car nous n'obtenons jamais SS ou LLL n'importe où à l'intérieur de ces chaînes.

Pour une lecture plus approfondie, il existe une thèse qui utilise ce pavage comme une simple analogie 1D aux pavages Penrose.

Le défi

Écrivez un programme ou une fonction qui, étant donné un entier non négatif N , retourne tous les pavages de Fibonacci valides sous la forme de chaînes contenant N caractères (étant Sou L).

Vous pouvez saisir des données via l'argument de fonction, STDIN ou ARGV et retourner ou imprimer le résultat.

C'est le golf de code, la réponse la plus courte (en octets) l'emporte.

Exemples

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 octets

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

Lit à partir de STDIN. Essayez-le en ligne.

Exemple d'exécution

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

Comment ça fonctionne

L'idée est de pousser toutes les chaînes de L et de S de la bonne longueur, d'appliquer successivement la transformation à chacune jusqu'à ce que le résultat soit une chaîne vide, de concaténer les séquences de chaînes et de rechercher les sous-chaînes interdites.

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 octets)

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

Ceci est une approche inflationniste: elle commence par Let Set les développe en utilisant les règles LL -> SLS, L -> S, S -> LLet avant ou arrière Speut avoir un Lajouté à la limite de mot.

Démo en ligne

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

Explication:

Je définis 4 fonctions:

• f prend un entier et retourne le résultat

  replicateM n [L,S]crée toutes les permutations possibles de [L,S]la longueur n filter s ...filtrera cette liste (des listes) avec la fonctions

• r réduit une liste donnée d'un niveau.

  Cela se fait simplement par correspondance de motifs. Une liste commençant par 2 Ldeviendra une liste commençant par Set la réduction restante

• v valide une liste donnée par les règles données (pas 3 L continus, pas 2 S continus)

  si la liste commence par l'une des 2 séquences illégales (L, L, L ou S, S) le résultat est False, une liste vide est valide et une liste non vide est vérifiée à nouveau avec le premier élément supprimé

• s vérifie si une liste et toutes les listes réduites sont valides.

  Encore une fois: une liste vide est valide (et ne peut pas être réduite davantage).
  Si la liste donnée en argument est valide, la liste est réduite et vérifiée à snouveau.
  Sinon, le résultat estFalse