tło

Kafelkowanie Fibonacciego to kafelkowanie linii (1D) przy użyciu dwóch segmentów: krótkiego, S i długiego, L (ich stosunek długości jest złotym stosunkiem, ale to nie jest istotne dla tego wyzwania). Aby kafelkowanie z użyciem tych dwóch prototypów było faktycznie kafelkami Fibonacciego, muszą być spełnione następujące warunki:

• Zestawienie nie może zawierać podsekwencji SS .
• Zestawienie nie może zawierać podsekwencji LLL .
• Jeśli nowy kafelek składa się z wykonania wszystkich poniższych podstawień, wynikiem musi być nadal kafelek Fibonacciego:
  1. LL → S
  2. S → L
  3. L → (pusty ciąg)

Spójrzmy na kilka przykładów:

SLLSLLSLLSLS

Wygląda to na poprawne kafelkowanie, ponieważ nie zawiera dwóch * S * s lub trzech * L * s, ale wykonajmy kompozycję:

LSLSLSLL

To nadal wygląda dobrze, ale jeśli skomponujemy to ponownie, otrzymamy

LLLS

który nie jest prawidłowym kafelkiem Fibonacciego. Dlatego też dwie poprzednie sekwencje nie były poprawnymi pochyłościami.

Z drugiej strony, jeśli zaczniemy

LSLLSLSLLSLSLL

i wielokrotnie komponuj to do krótszych sekwencji

LSLLSLLS
LSLSL
LL
S

wszystkie wyniki są poprawnymi wartościami Fibonacciego, ponieważ nigdy nie uzyskujemy SS ani LLL nigdzie w tych ciągach.

Do dalszej lektury jest teza, która wykorzystuje to kafelkowanie jako prostą analogię 1D do kafelków Penrose'a.

Wyzwanie

Napisz program lub funkcję, która przy nieujemnej liczbie całkowitej N zwraca wszystkie poprawne kafelki Fibonacciego w postaci ciągów zawierających N znaków (istnienie Slub L).

Możesz pobrać dane wejściowe za pomocą argumentu funkcji, STDIN lub ARGV i zwrócić lub wydrukować wynik.

To jest kod golfowy, wygrywa najkrótsza odpowiedź (w bajtach).

Przykłady

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 bajtów

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

Czyta ze STDIN. Wypróbuj online.

Przykładowy przebieg

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

Jak to działa

Chodzi o to, aby popchnąć wszystkie ciągi L i S o odpowiedniej długości, sukcesywnie zastosować transformację do każdego z nich, aż wynikiem będzie pusty ciąg, połączyć sekwencje ciągów i poszukać zabronionych podciągów.

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 bajtów)

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

Jest to podejście inflacyjna: zaczyna się Li Si rozszerza je za pomocą reguł LL -> SLS, L -> S, S -> LL, i prowadzące lub końcowe Smogą mieć Ldodany na granicy słowa.

Demo online

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

Wyjaśnienie:

Definiuję 4 funkcje:

• f przyjmuje liczbę całkowitą i zwraca wynik

  replicateM n [L,S]tworzy wszystkie możliwe kombinacje [L,S]z długością n filter s ...filtruje tę listę (list) za pomocą funkcjis

• r zmniejsza daną listę o 1 poziom.

  Odbywa się to po prostu poprzez dopasowanie wzorca. Lista zaczynająca się od 2 Lstanie się listą rozpoczynającą się od Si pozostała zmniejszona

• v zatwierdza daną listę według podanych reguł (nr 3 ciągłe L, nr 2 ciągłe S)

  jeśli lista zaczyna się od jednej z 2 niedozwolonych sekwencji (L, L, L lub S, S), wynik jest taki False, że pusta lista jest ważna, a niepusta lista jest ponownie sprawdzana z usuniętym pierwszym elementem

• s sprawdza, czy lista i wszystkie listy zredukowane są prawidłowe.

  Ponownie: pusta lista jest ważna (i nie można jej dalej zmniejszać).
  Jeśli lista podana jako argument jest poprawna, lista jest zmniejszana i sprawdzana sponownie.
  W przeciwnym razie wynik jestFalse