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:
- LL → S
- S → L
- 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 S
lub 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
LSLSL
->LL
?Odpowiedzi:
CJam,
706259 bajtówCzyta ze STDIN. Wypróbuj online.
Przykładowy przebieg
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.
źródło
GolfScript (86 bajtów)
Jest to podejście inflacyjna: zaczyna się
L
iS
i rozszerza je za pomocą regułLL -> SLS
,L -> S
,S -> LL
, i prowadzące lub końcoweS
mogą miećL
dodany na granicy słowa.Demo online
źródło
Haskell, 217
Wyjaśnienie:
Definiuję 4 funkcje:
f
przyjmuje liczbę całkowitą i zwraca wynikreplicateM 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
L
stanie się listą rozpoczynającą się odS
i pozostała zmniejszonav
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 elementems
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
s
ponownie.W przeciwnym razie wynik jest
False
źródło