11

Ada hasil kombinasi klasik bahwa jumlah cara untuk memasang 2*nstrip oleh 1*2domino adalah angka Fibonacci ^ke- n . Tujuan Anda adalah untuk mencetak semua kemiringan untuk yang diberikan n, digambar dengan garis dan garis vertikal seperti ini 8 kemiringan untuk n=5:

|————
|————

——|——
——|——

|||——
|||——

————|
————|

||——|
||——|

|——||
|——||

——|||
——|||

|||||
|||||

Anda harus menyediakan program atau fungsi bernama yang mengambil ninput dan mencetak output yang diperlukan. Bytes paling sedikit menang.

Memasukkan

Sejumlah nantara 1dan 10inklusif melalui STDIN atau input fungsi.

Keluaran

Cetak setiap kemungkinan dominasi 2*nstrip, yang digambar secara horizontal. Miring mungkin dalam urutan apa pun, tetapi masing-masing harus muncul tepat satu kali. Mereka harus dipisahkan oleh garis kosong.

Domino vertikal terbuat dari dua batang vertikal ( |) dan domino horizontal dibuat dari dua garis putus-putus ( —). Anda dapat menggunakan tanda hubung ( -) sebagai ganti tanda hubung untuk tetap di ASCII.

Anda dapat melakukan apa saja dengan spasi putih selama hasil cetak terlihat sama.

code-golf math ascii-art combinatorics tiling Tidak
sumber

Apakah pemberian makan tambahan setelah ubin terakhir jatuh di bawah sesuatu dengan spasi putih ?

Dennis

@ Dennis Ya, garis kosong ekstra baik-baik saja.

xnor

Saya benar-benar terkejut melihat begitu banyak pendekatan berbeda untuk menyelesaikan masalah yang sama. Apakah Anda mengharapkan itu?

Level River St

@steveverrill Tidak, saya benar-benar tidak, dan saya senang melihat variasi! Dan milikmu mengambil kue untuk tak terduga. Saya sebagian besar ada dalam pikiran rekursi gaya Fibonacci, karena sebagian besar solusi yang digunakan saya gunakan. Saya tidak berharap penyaringan menjadi efektif, dan sejauh yang saya lakukan, saya pikir itu akan menyaring string ——dan |panjangnya seperti milik Dennis, bukan nstring —dan |disaring dengan —muncul berpasangan. Dan untuk yang terakhir, saya mengharapkannya melalui regex atau operasi string pada string yang dihasilkan, seperti s.split('——) `, bukan dengan pendekatan aritmatika seperti milik Anda.

xnor

Saya pikir "domino 1x2" berlebihan.

SuperJedi224

5

C, 106

Versi golf

f(n){
  for(int i,h=n*2<<n;h--;(i/3|i/3*2)-i||(putchar(i>>h%n&1?45:124),h%n||puts(h%(n*2)?"":"\n")))
    i=h/2/n;
}

Versi asli

i,j,n;
main(){
  scanf("%d",&n);
  for(i=1<<n;i--;)if((i/3|i/3*2)==i){
    for(j=1<<n;j/=2;)printf("%c",i&j?'-':'|');puts("");
    for(j=1<<n;j/=2;)printf("%c",i&j?'-':'|');puts("\n");
  }
}

Bagaimana itu bekerja

Variabel iberjalan dari 1<<n-1bawah hingga 0, menghasilkan semua angka biner yang mungkin dengan ndigit. 0 encode untuk |dan 1 encode untuk -. Kami tertarik pada angka yang berisi 1 berpasangan. Jelas angka seperti itu dapat dibagi 3.

Ketika suatu angka dibagi dengan 3, angka asli dapat dipulihkan dengan mengalikan hasilnya dengan 2 dan menambahkannya ke dirinya sendiri (secara efektif saling-campur dengan 3.) Sebagian besar angka akan membutuhkan carry, tetapi ketika proses dilakukan pada jumlah menarik, tidak perlu membawa, jadi dalam kasus ini saja, ATAU dapat digunakan sebagai pengganti. Ini digunakan untuk menguji jumlah bunga, karena mereka adalah satu-satunya di mana ekspresi i/3|i/3*2mengembalikan nilai asli i. Lihat contoh di bawah ini.

1111= 15 ---> 0101= 5 ---> 1111= 15 (valid, 0101|1010== 0101+1010)

1001= 9 ---> 0011= 3 ---> 0111= 7 (tidak valid,! 0011|0110= 0011+0110)

Nilai tes selalu sama atau kurang dari nilai aslinya. Karena angka-angka yang bukan kelipatan 3 juga menghasilkan angka kurang dari aslinya ketika dibagi dengan 3 kemudian dikalikan dengan 3, tes memberikan FALSE yang diinginkan pada angka-angka ini juga.

Dalam versi asli, beberapa loop jdigunakan untuk memindai bit idan menghasilkan output. Dalam versi golf, satu forloop digunakan, di mana hberjalan melalui semua angka dari (n*2)*(1<<n)-1bawah hingga 0. Nilai idihasilkan oleh h/2/n. Variabel jtidak lagi digunakan, karena kuantitas yang setara diperoleh dari h%n. Penggunaan n*2memungkinkan kedua garis untuk dicetak dari loop yang sama, dengan beberapa multiplexing yang bagus dalam putspernyataan untuk mencetak satu atau dua baris baru di akhir baris.

Perhatikan bahwa daging ini berada di posisi kenaikan dari for()braket dan karena itu dijalankan setelah itu i=h/2/h.

Output sampel n = 6:

$ ./a
6
------
------

----||
----||

--|--|
--|--|

--||--
--||--

--||||
--||||

|----|
|----|

|--|--
|--|--

|--|||
|--|||

||----
||----

||--||
||--||

|||--|
|||--|

||||--
||||--

||||||
||||||

Level River St
sumber

The i/3|i/3*2Caranya adalah cerdik! Saya tidak mengharapkan ekspresi aritmatika untuk tata bahasa.

xnor

3

CJam, 33 27 byte

LN{_'|f+@"——"f++}ri*\;{_N}/

Terima kasih kepada @ jimmy23013 untuk bermain golf 6 byte!

Cobalah online!

Latar Belakang

Ini adalah implementasi berulang dari algoritma rekursif:

Kemungkinan tilings untuk n dapat diperoleh dengan menambahkan domino vertikal ke kemungkinan tilings untuk n - 1 dan dua domino horizontal ke kemungkinan tilings untuk n - 2 .

Dengan cara ini, jumlah tilings untuk n adalah jumlah dari jumlah tilings untuk n - 1 dan n - 2 , yaitu, n ^th nomor Fibonacci.

Bagaimana itu bekerja

LN                                " A:= [''] B:= ['\n']                         ";
  {             }ri*              " Repeat int(input()) times:                  ";
   _'|f+                          "   C = copy(B); for T ∊ C: T += '|'          ";
              @                   "   Swap A and B.                             ";
               "——"f+             "   for T ∊ B: T += "——"                      ";
                     +            "   B = C + B                                 ";
                        \;        " Discard A.                                  ";
                          {_N}/   " for T ∊ B: print T, T + '\n'                ";

Contoh dijalankan

$ alias cjam='java -jar cjam-0.6.2.jar'

$ cjam domino.cjam <<< 3
|||
|||

——|
——|

|——
|——

$ for i in {1..10}; do echo $[$(cjam domino.cjam <<< $i | wc -l) / 3]; done1
2
3
5
8
13
21
34
55
89

Dennis
sumber

LNli{_'|f\@"——"f\+2/}*\;{_N}/.

jimmy23013

f\belum diimplementasikan pada 0.6.2, tapi saya bisa menggabungkan pendekatan kami. Terima kasih!

Dennis

2

Haskell, 89 byte

f(-1)=[]
f 0=[""]
f n=map('|':)(f$n-1)++map("--"++)(f$n-2)
g=unlines.(>>= \x->[x,x,""]).f

fadalah fungsi yang diberikan nomor mengembalikan daftar satu baris dari semua kemungkinan Fibonacci tilings panjang n mungkin. tidak masalah bahwa ia mengembalikan satu baris, karena kedua baris dari semua tilings adalah sama.

fbekerja dengan memanggil secara berulang n-1dan n-2dan menambahkan "|"dan "--"(masing-masing) ke string.

gadalah fungsi yang menjawab pertanyaan. pada dasarnya memanggil finput, menggandakan setiap string sehingga akan menampilkan dua baris dan menggabungkan mereka semua dengan baris baru.

contoh output:

*Main> putStrLn $ g 5
|||||
|||||

|||--
|||--

||--|
||--|

|--||
|--||

|----
|----

--|||
--|||

--|--
--|--

----|
----|

haskeller bangga
sumber

2

CJam, 42 37 byte

3li:L#,{3b"——|"2/f=s}%{,L=},_&{N+_N}/

Saya telah menghitung tanda hubung sebagai satu byte masing-masing karena pertanyaan memungkinkan untuk menggantinya dengan tanda hubung ASCII.

Cobalah online.

Bagaimana itu bekerja

Untuk mendapatkan semua kemiringan 2 × L , kami mengulangi semua bilangan bulat non-negatif I <3 ^L , membuat angka genap pada basis 3 sesuai dengan domino horizontal dan angka ganjil ke yang vertikal.

Karena setiap saya memiliki L atau kurang digit dalam basis 3, ini menghasilkan semua cara yang mungkin dari meliputi 2 × L Strip. Yang tersisa adalah menyaring penutup yang lebih besar atau lebih kecil dari 2 × L dan mencetak penutup yang tersisa.

3li:L#,      " Read an integer L from STDIN and push A := [ 0 1 ... (3 ** N - 1) ].       ";
{            " For each integer I in A:                                                   ";
  3b         " Push B, the array of I's base 3 digits.                                    ";
  "——|"2/    " Push S := [ '——' '|' ].                                                    ";
  f=         " Replace each D in B with S[D % 2] (the modulus is implicit).               ";
  s          " Flatten B.                                                                 ";
}%           " Collect the result in an array R.                                          ";
{,L=},       " Filter R so it contains only strings of length L.                          ";
_&           " Intersect R with itself to remove duplicates.                              ";
{N+_N}/      " For each string T in B, push (T . '\n') twice, followed by '\n'.           ";

Contoh dijalankan

$ cjam domino.cjam <<< 3
|——
|——

——|
——|

|||
|||

$ for i in {1..10}; do echo $[$(cjam domino.cjam <<< $i | wc -l) / 3]; done
1
2
3
5
8
13
21
34
55
89

Dennis
sumber

Keren. Saya hanya ingin tahu mengapa Anda tidak menggunakan basis 2 seperti edc65 bukannya basis 3. Itu akan menyelamatkan Anda dari duplikat. Saya berasumsi itu karena memimpin nol mungkin terpotong pada langkah 3b. Apakah itu benar?

Level River St

1

@steveverrill: Ya, itulah alasannya. Karena itu, angka nol di depan sama dengan tidak ada domino sama sekali. Tetapi tidak memiliki duplikat akan memungkinkan saya untuk mengganti tiga blok dengan satu blok. Saya harus memikirkan ini lagi.

Dennis

@steveverrill: Saya tidak berhasil membuat basis 2 bekerja, tetapi pendekatan rekursif tampaknya bahkan lebih pendek.

Dennis

2

JavaScript (E6) 102

Hasilkan konfigurasi dari urutan bit, 0 -> '-' dan 1 -> '|'.

F=n=>{
  for(i=0;(j=++i)<2<<n;s.length==1+n&&console.log('\n'+s+s))
    for(s='\n';j>1;j>>=1)s+=j&1?'|':'--';
}

Uji di konsol firefox / firebug

F(5)

Keluaran

|----
|----

--|--
--|--

----|
----|

|||--
|||--

||--|
||--|

|--||
|--||

--|||
--|||

|||||
|||||

edc65
sumber

1

Haskell: 109 byte

Ini adalah terjemahan dari Haskell one-liner yang terkenal untuk dengan malas menghitung urutan angka Fibonacci:

b=map.map.(++)
w=zipWith
z=w(++)
s=["\n"]:["|\n"]:z(b"--"s)(b"|"$tail s)
f=sequence_.map putStrLn.(w z s s!!)

Urutan utama dari string ubin, tidak diserang:

dominos = [""] : ["|"] : zipWith (++) ("--" `before` dominos) ("|" `before` tail dominos)
    where before = map . map . (++)

Dan Fibonacci one-liner untuk perbandingan:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Contoh penggunaan:

$ ghci fibtile
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( fibtile.hs, interpreted )
Ok, modules loaded: Main.
*Main> f 5
----|
----|

--|--
--|--

--|||
--|||

|----
|----

|--||
|--||

||--|
||--|

|||--
|||--

|||||
|||||

*Main>

Matt Noonan
sumber

1

Cobra - 176

Tidak bisa menunggu sampai saya menyelesaikan paket golf Cobra.

def m(n)
    for t in.f(n),print t+t
def f(n,x='')as String*
    if x.length<n,for i in.f(n,x+'-').toList+.f(n,x+'|').toList,yield i
    else if not'-'in x.replace('--',''),yield x+'\n'

Suram
sumber

1

J - 54 char

Berfungsi nsebagai argumen di sebelah kanan.

0{::(];'--'&,"1@[,'|',"1])&>/@[&0&((1 2$,:)&.>'';,'|')

Akar utama golf ini adalah (];'--'&,"1@[,'|',"1])&>/. Ini mengambil daftar tilings of length (N-2) dan (N-1), dan mengembalikan daftar tilings of length (N-1) dan N. Ini adalah pengulangan Fibonacci standar, à la aljabar linier. ];mengembalikan daftar kanan sebagai kiri baru (karena tidak ada perubahan). '--'&,"1@[menambahkan --ubin ke daftar kiri, sementara '|',"1]menambahkan |ubin ke daftar kanan, dan mereka bersama-sama adalah daftar kanan baru.

Kami mengulanginya berulang nkali (itu adalah @[&0) dan mulai dengan ubin kosong dan satu ubin panjang 1. Lalu kita kembalikan pasangan pertama dengan 0{::. Artinya, jika kita menjalankannya nol kali, kita hanya mengembalikan yang pertama yaitu ubin kosong. Jika kami menjalankannya nkali, kami menghitung hingga ndan ( n+1) pasangan, tetapi membuang yang terakhir. Ini pekerjaan ekstra tetapi lebih sedikit karakter.

Ini (1 2$,:)adalah sesuatu yang harus dilakukan J agar tilings dalam daftar mudah diperpanjang. Kami membuat daftar awal kiri menjadi daftar 1-item dari matriks 2-baris karakter, setiap baris memiliki panjang 0. Daftar awal kanan adalah sama, tetapi memiliki baris dengan panjang 1, diisi |. Kemudian, kami menambahkan ubin baru ke setiap baris, dan menambahkan daftar matriks saat kami menggabungkan dua set ubin bersama. Ini adalah aplikasi sederhana dari sebuah konsep yang disebut peringkat J: pada dasarnya memanipulasi dimensi argumennya, dan secara implisit mengulang jika perlu.

   0{::(];'--'&,"1@[,'|',"1])&>/@[&0&((1 2$,:)&.>'';,'|')5
----|
----|

--|--
--|--

--|||
--|||

|----
|----

|--||
|--||

||--|
||--|

|||--
|||--

|||||
|||||

Cobalah sendiri di tryj.tk .

algoritme hiu
sumber

1

Python 3: 70 byte

f=lambda n,s="\n":n>0and f(n-1,"|"+s)==f(n-2,"--"+s)or n or print(s*2)

Secara rekursif membangun semua string yang mungkin smewakili satu baris domino, yang digandakan dan dicetak. Mulai ssebagai karakter baris baru membuat garis kosong terjadi secara otomatis.

The ==antara dua panggilan untuk fhanya untuk melakukan kedua fungsi panggilan. Ini biasanya kembali Nonekarena mereka baru saja mencetak, dan ==merupakan salah satu dari sedikit operator yang ditentukan None.

The ands dan ors adalah untuk menghasilkan perilaku hubungan arus pendek hak untuk mereproduksi ifdan elses kode ungolfed.

Tidak Disatukan:

def f(n,s="\n"):
 if n==-1:pass
 elif n==0: print(s*2)
 else: f(n-1,"|"+s);f(n-2,"--"+s)

Tidak
sumber

1

Retina , 44 byte

Catatan: Retina lebih muda dari tantangan ini.

+`([-|]*)11(1*#)
$1|1$2$1--$2
1
|
.*?#
$0$0#

Mengambil input di unary dengan baris baru tambahan.

Setiap baris harus menuju ke file sendiri dan #harus diubah ke baris baru di file. Ini tidak praktis tetapi Anda dapat menjalankan kode seperti halnya satu file dengan -sflag, menjaga #markers (dan mengubah baris baru ke #dalam input juga). Anda dapat mengubah #kembali ke baris baru di output agar mudah dibaca jika diinginkan. Misalnya:

> echo 1111# | retina -s fib_tile | tr # '\n'
||||
||||

||--
||--

|--|
|--|

--||
--||

----
----

Metode:

Mulai dari input kami menukar setiap baris dengan dua lainnya: satu dengan 1perubahan pertama ke |dan satu dengan dua yang pertama 1diubah ke --. Kami melakukan ini sampai kami memiliki garis dengan setidaknya dua 1.
Ketika hanya ada satu yang 1tersisa, kami mengubahnya menjadi |.
Kami menggandakan setiap baris dan menambahkan baris baru ekstra untuknya dan kami mendapatkan hasil yang diinginkan.

randomra
sumber

Mengejar baris baru baik-baik saja.

xnor

Ubin domino Fibonacci

Jawaban:

C, 106

CJam, 33 27 byte

Latar Belakang

Bagaimana itu bekerja

Contoh dijalankan

Haskell, 89 byte

CJam, 42 37 byte

Bagaimana itu bekerja

Contoh dijalankan

JavaScript (E6) 102

Haskell: 109 byte

Cobra - 176

J - 54 char

Python 3: 70 byte

Retina , 44 byte