Hintergrund

Die Fibonacci-Kachelung ist eine Kachelung der (1D) -Linie mit zwei Segmenten: einem kurzen, S , und einem langen, L (ihr Längenverhältnis ist das goldene Verhältnis, aber das ist für diese Herausforderung nicht relevant). Damit eine Kachelung mit diesen beiden Prototilen tatsächlich eine Fibonacci-Kachelung ist, müssen folgende Bedingungen erfüllt sein:

• Die Kachelung darf nicht die Teilsequenz SS enthalten .
• Die Kachelung darf nicht die Teilsequenz LLL enthalten .
• Wenn eine neue Kachelung durch Ausführen aller folgenden Ersetzungen erstellt wird, muss das Ergebnis immer noch eine Fibonacci-Kachelung sein:
  1. LL → S.
  2. S → L.
  3. L → (leere Zeichenfolge)

Schauen wir uns einige Beispiele an:

SLLSLLSLLSLS

Dies sieht aus wie eine gültige Kachelung, da sie keine zwei * S * s oder drei * L * s enthält, aber lassen Sie uns die Komposition ausführen:

LSLSLSLL

Das sieht immer noch gut aus, aber wenn wir das noch einmal komponieren, bekommen wir

LLLS

Dies ist keine gültige Fibonacci-Kachelung. Daher waren auch die beiden vorherigen Sequenzen keine gültigen Kacheln.

Auf der anderen Seite, wenn wir mit beginnen

LSLLSLSLLSLSLL

und komponiere dies wiederholt zu kürzeren Sequenzen

LSLLSLLS
LSLSL
LL
S

Alle Ergebnisse sind gültige Fibonacci-Kacheln, da wir innerhalb dieser Zeichenfolgen niemals SS oder LLL erhalten .

Zur weiteren Lektüre gibt es eine These, die diese Kacheln als einfache 1D-Analogie zu Penrose-Kacheln verwendet.

Die Herausforderung

Schreiben Sie ein Programm oder eine Funktion, die bei einer nicht negativen Ganzzahl N alle gültigen Fibonacci-Kacheln in Form von Zeichenfolgen mit N Zeichen (Sein Soder L) zurückgibt .

Sie können Eingaben über das Funktionsargument STDIN oder ARGV vornehmen und das Ergebnis zurückgeben oder drucken.

Dies ist Code Golf, die kürzeste Antwort (in Bytes) gewinnt.

Beispiele

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

Liest von STDIN. Probieren Sie es online aus.

Beispiellauf

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

Wie es funktioniert

Die Idee ist, alle Zeichenfolgen von L und S mit der richtigen Länge zu verschieben, die Transformation nacheinander auf jede anzuwenden, bis das Ergebnis eine leere Zeichenfolge ist, die Folgen von Zeichenfolgen zu verketten und nach den verbotenen Teilzeichenfolgen zu suchen.

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

Dies ist ein Inflations Ansatz: es beginnt mit Lund Sund erweitert sie die Regeln mit LL -> SLS, L -> S, S -> LL, und am Anfang oder Ende Skann eine hat Lan der Wortgrenze gegeben.

Online-Demo

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

Erklärung:

Ich definiere 4 Funktionen:

• f nimmt eine ganze Zahl und gibt das Ergebnis zurück

  replicateM n [L,S]Erstellt alle möglichen Permutationen [L,S]mit der Länge n filter s ..., filtert diese Liste (von Listen) mit der Funktions

• r reduziert eine gegebene Liste um 1 Stufe.

  Dies erfolgt einfach durch Mustervergleich. Eine Liste, die mit 2 beginnt, Lwird zu einer Liste, die mit beginnt Sund die verbleibende reduziert

• v validiert eine gegebene Liste nach den gegebenen Regeln (kein 3 kontinuierliches L, kein 2 kontinuierliches S)

  Wenn die Liste mit einer der beiden unzulässigen Sequenzen (L, L, L oder S, S) beginnt, ist das Ergebnis False, dass eine leere Liste gültig ist und eine nicht leere Liste erneut überprüft wird, wobei das erste Element entfernt wird

• s prüft, ob eine Liste und alle reduzierten Listen gültig sind.

  Nochmals: Eine leere Liste ist gültig (und kann nicht weiter reduziert werden).
  Wenn die als Argument angegebene Liste gültig ist, wird die Liste reduziert und serneut überprüft .
  Ansonsten ist das ErgebnisFalse