Latar Belakang
Ubin Fibonacci adalah ubin garis (1D) menggunakan dua segmen: pendek, S , dan panjang, L (rasio panjangnya adalah rasio emas, tetapi itu tidak relevan dengan tantangan ini). Untuk ubin yang menggunakan dua prototipe ini untuk benar-benar menjadi ubin Fibonacci, kondisi berikut harus dipenuhi:
- Ubin tidak boleh mengandung SS berikutnya .
- Ubin tidak boleh mengandung LLL berikutnya .
- Jika ubin baru dikomposisikan dengan melakukan semua pergantian berikut, hasilnya tetap harus ubin Fibonacci:
- LL → S
- S → L
- L → (string kosong)
Mari kita lihat beberapa contoh:
SLLSLLSLLSLS
Ini terlihat seperti ubin yang valid, karena tidak mengandung dua * S * atau tiga * L * tetapi mari kita lakukan komposisi:
LSLSLSLL
Itu masih terlihat baik-baik saja, tetapi jika kita menyusun ini lagi, kita dapatkan
LLLS
yang bukan merupakan ubin Fibonacci yang valid. Oleh karena itu, dua urutan sebelumnya juga tidak berlaku.
Di sisi lain, jika kita mulai dengan
LSLLSLSLLSLSLL
dan berulang kali menyusun ini ke urutan yang lebih pendek
LSLLSLLS
LSLSL
LL
S
semua hasil adalah Fibonacci yang valid, karena kami tidak pernah mendapatkan SS atau LLL di mana pun di dalam string itu.
Untuk bacaan lebih lanjut, ada tesis yang menggunakan ubin ini sebagai analogi 1D sederhana untuk ubin Penrose.
Tantangan
Menulis sebuah program atau fungsi yang, diberi non-negatif bilangan bulat N , mengembalikan semua Fibonacci berlaku ubin dalam bentuk string yang mengandung N karakter (menjadi S
atau L
).
Anda dapat mengambil input melalui argumen fungsi, STDIN atau ARGV dan mengembalikan atau mencetak hasilnya.
Ini adalah kode golf, jawaban terpendek (dalam byte) menang.
Contohnya
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
?Jawaban:
CJam,
706259 byteBaca dari STDIN. Cobalah online.
Contoh dijalankan
Bagaimana itu bekerja
Idenya adalah untuk mendorong semua string L dan S dengan panjang yang sesuai, berturut-turut menerapkan transformasi untuk masing-masing sampai hasilnya adalah string kosong, menyatukan urutan string dan mencari substring terlarang.
sumber
GolfScript (86 byte)
Ini merupakan pendekatan inflasi: dimulai dengan
L
danS
dan memperluas mereka menggunakan aturanLL -> SLS
,L -> S
,S -> LL
, dan memimpin atau trailingS
dapat memilikiL
ditambahkan pada batas kata.Demo online
sumber
Haskell, 217
Penjelasan:
Saya mendefinisikan 4 fungsi:
f
mengambil bilangan bulat dan mengembalikan hasilnyareplicateM n [L,S]
membuat semua permutasi yang mungkin[L,S]
dengan panjangn
filter s ...
akan memfilter daftar ini (daftar) dengan fungsis
r
mengurangi daftar yang diberikan oleh 1 level.Ini hanya dilakukan dengan pencocokan pola. Daftar yang dimulai dengan 2
L
akan menjadi daftar yang dimulai denganS
dan sisanya berkurangv
memvalidasi daftar yang diberikan oleh aturan yang diberikan (no 3 continuous L, no 2 continous S)jika daftar dimulai dengan salah satu dari 2 urutan ilegal (L, L, L atau S, S) hasilnya adalah
False
, daftar kosong valid, dan daftar non-kosong diperiksa lagi dengan elemen pertama dihapuss
memeriksa apakah daftar dan semua daftar yang dikurangi valid.Sekali lagi: daftar kosong valid (dan tidak dapat direduksi lebih jauh).
Jika daftar yang diberikan sebagai argumen valid maka daftar tersebut dikurangi iklannya diperiksa
s
lagi.Kalau tidak hasilnya adalah
False
sumber