Hasilkan miring Fibonacci yang valid

9

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:
    1. LLS
    2. SL
    3. 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 Satau 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
Martin Ender
sumber
Haruskah itu LSLSL-> LL?
@tolos Ah ya, tangkapan yang bagus. Saya memperbaikinya. FYI, ini terjadi karena saya benar-benar menghasilkan string sebaliknya, mulai dari bawah menggunakan aturan dekomposisi yang sama, dan itu tidak bisa dibalik ketika datang ke batas-batas fragmen.
Martin Ender

Jawaban:

4

CJam, 70 62 59 byte

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

Baca dari STDIN. Cobalah online.

Contoh dijalankan

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

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.

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.                                          ";
Dennis
sumber
3

GolfScript (86 byte)

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

Ini merupakan pendekatan inflasi: dimulai dengan Ldan Sdan memperluas mereka menggunakan aturan LL -> SLS, L -> S, S -> LL, dan memimpin atau trailing Sdapat memiliki Lditambahkan pada batas kata.

Demo online

Peter Taylor
sumber
@ MartinBüttner, saya biasanya akan ditautkan ke demo online dengan golfscript.apphb.com, tetapi menjalankan versi lama dengan bug di sekitar loop bersarang (diperbaiki pada rilis 3 Desember 2012 ) dan tidak dapat menjalankan program ini dengan benar.
Peter Taylor
3
@ MartinBüttner Ups. Terima kasih teman-teman karena memberi tahu saya tentang bug ini. Saya memperbarui situs web dengan versi GS baru. Klik tautan ini untuk demo.
Cristian Lupascu
@ w0lf, terima kasih atas pembaruannya (dan atas perubahan terbaru untuk menambah batas waktu juga).
Peter Taylor
1

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

Penjelasan:

Saya mendefinisikan 4 fungsi:

  • f mengambil bilangan bulat dan mengembalikan hasilnya

    replicateM n [L,S]membuat semua permutasi yang mungkin [L,S]dengan panjang n 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 Lakan menjadi daftar yang dimulai dengan Sdan sisanya berkurang

  • v 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 dihapus

  • s 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 slagi.
    Kalau tidak hasilnya adalahFalse

Johannes Kuhn
sumber