Tulis sebuah program atau fungsi yang diberi n positif dan m menghitung jumlah domino berbeda tilings yang valid yang dapat Anda masukkan dalam persegi panjang n oleh m . Ini adalah urutan A099390 dalam Ensiklopedia Online Urutan Bilangan Bulat . Anda dapat mengambil input sebagai argumen fungsi, CLA atau pada stdin, dalam format apa pun yang masuk akal. Anda harus mengembalikan atau mencetak bilangan bulat tunggal sebagai output.
Setiap ubin tidak boleh meninggalkan celah, dan setiap ubin berbeda dihitung, termasuk rotasi, refleksi, dll. Misalnya, miring untuk 2x3 adalah:
|-- ||| --|
|-- ||| --|
Contoh input / output:
1, 9 -> 0
2, 2 -> 2
2, 3 -> 3
4, 4 -> 36
4, 6 -> 281
6, 6 -> 6728
7, 10 -> 53175517
Program Anda secara teoritis harus bekerja untuk setiap n dan m , tetapi jika program Anda membutuhkan terlalu banyak memori atau tipe data Anda meluap itu dikecualikan. Namun program Anda harus bekerja dengan benar untuk n, m <= 8.
Kode terpendek dalam byte menang.
Jawaban:
Pyth,
3029 byteCobalah online: Demonstration / Test Suite
Semua input contoh dijalankan di kompiler online. Yang terakhir membutuhkan beberapa detik.
Penjelasan:
Dalam kode saya, saya akan mendefinisikan fungsi rekursif
y
. Fungsi iniy
mengambil daftar koordinat 2D dan mengembalikan jumlah dominasi yang berbeda menggunakan koordinat ini. Misalnyay([[0,0], [0,1]]) = 1
(satu domino horisontal),y([[0,0], [1,1]]) = 0
(koordinat tidak berdekatan) dany([[0,0], [0,1], [1,0], [1,1]]) = 2
(baik dua domino horizontal atau dua). Setelah mendefinisikan fungsi saya akan memanggilnya dengan semua koordinat[x,y]
denganx in [0, 1, m-1], y in [0, 1, n-1]
.Bagaimana cara kerja fungsi rekursif? Sederhana saja. Jika daftar coords kosong, hanya ada satu ubin yang valid dan
y
kembali1
.Kalau tidak, saya mengambil koordinat pertama dalam daftar
b[0]
, dan mencari tetangga yang tersisa untuk tetangga. Jika tidak ada tetangga untukb[0]
, maka tidak ada ubin mungkin, maka saya kembali 0. Jika ada satu atau lebih tetangga, maka jumlah miring adalah (jumlah miring di mana saya terhubungb[0]
dengan tetangga pertama melalui domina, ditambah jumlah miring di mana saya terhubungb[0]
dengan tetangga kedua, ditambah ...) Jadi saya sebut fungsi secara rekursif untuk setiap tetangga dengan daftar singkat (dengan menghapus dua coordb[0]
dan tetangga). Setelah itu saya meringkas semua hasil dan mengembalikannya.Karena urutan koordinasi selalu hanya ada dua tetangga, satu di sisi kanan dan satu di bawah. Tetapi algoritma saya tidak peduli tentang itu.
sumber
Matlab, 292
Saya yakin ini bisa dipersingkat banyak hanya dengan porting ke bahasa lain.
Ide dasarnya adalah bruteforcing: Saya datang dengan semacam enumerasi dari semua cara bagaimana menempatkan
m*n/2
batu bata domino dim*n
papan tulis. Tetapi enumerasi ini juga mencakup banyak tilt yang tidak valid (batu bata yang tumpang tindih atau keluar dari papan.) Jadi program ini membangun semua tilings itu, dan hanya menghitung yang valid. Kompleksitas runtime adalah tentangO(2^(m*n/2) * m*n)
. Memori bukan masalah karena8x8
hanya membutuhkanO(m*n)
memori. Tetapi waktu yang dibutuhkan8x8
sekitar 20 hari.Di sini, versi yang sepenuhnya dikomentari yang menjelaskan apa yang sedang terjadi.
PS: Jika ada yang tahu cara membuat sintaks Matlab berfungsi, harap sertakan tag yang sesuai dalam jawaban ini!
Di sini yang sepenuhnya golf:
sumber
C89, 230 byte
Agar mudah dibaca, saya menulis jawaban ini dengan tangan - semua baris baru dapat dihapus dengan aman hingga mencapai 230 byte.
Menentukan fungsi
int g(int n, int m)
yang mengembalikan jumlah kemiringan. Ia menggunakan fungsi pembantuf
yang mengulangi semua tilings yang valid dengan menempatkan satu domino, berulang, dan kemudian menghapus domino pada papan bersama.sumber
Python 243
Saya memilih pendekatan brute force:
Jika semuanya cocok dan tidak ada spasi yang tersisa, kami memiliki entri yang valid.
Ini kodenya:
sumber