Saya sedang menelusuri Stackoverflow dan melihat pertanyaan ini tentang memasang persegi panjang MxN, dan saya pikir itu akan bagus untuk bermain golf. Inilah tugasnya.
Dengan dimensi M dan N, tulislah sebuah program yang menampilkan berapa banyak cara unik sebuah persegi panjang MxN (N adalah jumlah baris, bukan kolom. Bukan berarti itu benar-benar penting) dapat dibuat berdasarkan batasan-batasan ini.
- Semua ubin berukuran 2x1 atau 3x1
- Semua ubin tetap dalam baris mereka (yaitu semuanya horisontal)
- Di antara setiap dua baris yang berdekatan, ubin tidak boleh disejajarkan, kecuali pada kedua ujungnya
- M dan N dijamin setidaknya 1
Misalnya, ubin yang valid dari matriks 8x3 adalah
2 3 3
| | |
v v v
_______________
|___|_____|_____|
|_____|_____|___|
|___|_____|_____|
Tetapi yang berikut ini tidak valid, karena baris-barisnya sejajar
2 3 3
| | |
v v v
_______________
|___|_____|_____|
|_____|___|_____|
|_____|_____|___|
Kasus uji:
8x3: 4
3x1: 1
1x1: 0
9x4: 10
Golf kode, jadi jawaban terpendek menang.
2x1
atau3x1
? Juga apakah output untuk4x1
nol?|
s tidak berkontribusi pada panjang baris, dengan menggunakan representasi seperti ini (di mana, jika tidak ada pipa (|
), ada spasi).Jawaban:
Jelly , 20 byte
Cobalah online!
sumber
JavaScript (ES6),
119 110 106 9691 byteMengambil input sebagai( N, M.) .
Cobalah online!
Berkomentar
NB: Kode ini menggunakan 3 fungsi berbeda yang saling memanggil. Ini membuatnya agak sulit untuk melacak ruang lingkup variabel. Ingat itug didefinisikan dalam ruang lingkup f dan h didefinisikan dalam ruang lingkup g .
sumber
R ,
243231 byteCobalah online!
Versi dengan jeda baris:
Perhatikan tidak ada rekursi, dan menangani nilai m dan n yang cukup besar (mis. 24x20 -> 3.3e19)
Berikut jawaban yang dikomentari yang berfungsi kurang lebih sama dengan yang di atas, tetapi saya belum menguji semua fungsi sehingga sebenarnya dapat dibaca:
Metode untuk mengambil matriks dan berulang kali mengalikannya dengan sendirinya adalah dari pertanyaan tentang stackoverflow . Pendekatan ini bekerja di sini karena secara efektif menghitung jumlah cabang kumulatif melalui barisan bata yang berbeda.
Jika paket eksternal diizinkan, saya bisa mendapatkannya ke 192:
sumber
Jelly , 26 byte
Cobalah online!
Rusak:
Hasilkan daftar dinding yang mungkin sebagai jumlah kumulatif dengan ujungnya dihapus:
Temukan tabel terluar dari semua dinding yang mungkin saling berhadapan yang tidak memiliki persimpangan:
Ambil matriks ini dengan kekuatan (N-1) dan kemudian jumlahkan semuanya:
Menggunakan bit pertama dari jawaban @ EriktheOutgolfer untuk menghasilkan daftar dinding yang mungkin, dan kemudian menggunakan persimpangan matriks dan pendekatan matriks eksponensial dari jawaban R saya. Dengan demikian, ini bekerja dengan baik bahkan dengan N. besar. Ini adalah jawaban Jelly pertama saya, dan saya kira itu bisa bermain golf lebih. Saya juga idealnya ingin mengubah bagian pertama sehingga persyaratan waktu dan memori tidak skala secara eksponensial dengan M.
sumber
05AB1E , 42 byte
Saya hampir terlalu malu untuk memposting ini, dan itu pasti bisa dipagari oleh BANYAK dengan pendekatan yang berbeda, tetapi karena butuh beberapa saat untuk menyelesaikannya saya tetap memutuskan untuk mempostingnya dan menurunkannya dari sini. Tantangannya terlihat lebih mudah daripada imo, tapi saya pasti menggunakan pendekatan yang salah di sini dan saya merasa 05AB1E bisa melakukan sekitar 25 byte ..
Cobalah online. CATATAN: Tidak hanya panjang, tetapi juga tidak efisien, karena
9x4
kasus uji beroperasi dalam waktu sekitar 40 detik pada TIO ..Penjelasan:
sumber
Arang , 89 byte
Cobalah online! Tautan adalah untuk mengucapkan versi kode. Bekerja untuk persegi panjang ukuran hingga sekitar 12 pada TIO, tetapi dapat dibuat sekitar tiga kali lebih cepat dengan biaya 2 byte dengan menggunakan sedikit memutar-mutar bukannya persimpangan daftar. Penjelasan:
Masukkan lebar.
Mulai dengan baris tanpa batu bata.
Mulai tanpa baris yang selesai.
Lingkari baris.
Lewati batu bata.
Tambahkan lebar bata ke lebar baris saat ini.
Jika ini menghasilkan lebar input maka tambahkan baris ini ke daftar baris yang sudah selesai.
Kalau tidak, jika ini masih kurang dari lebar input maka tambahkan baris baru ke daftar baris, sehingga menyebabkannya diambil oleh iterasi kemudian.
Buatlah daftar dinding satu baris.
Lingkari satu kurang dari ketinggian.
Simpan daftar dinding.
Kosongkan daftar dinding.
Ulangi daftar dinding yang disimpan.
Lingkari baris yang sudah selesai.
Jika baris dapat ditambahkan ke dinding ini maka tambahkan itu ke daftar dinding.
Keluarkan panjang daftar dinding terakhir.
sumber