Tugas
Tulis sebuah program yang bertuliskan tiga bilangan bulat m , n baik dari STDIN atau sebagai argumen baris perintah, mencetak semua kemiringan yang mungkin dari segi empat dimensi m × n dengan domino 2 × 1 dan 1 × 2 dan akhirnya jumlah tilings yang valid.
Domino dari ubin individu harus diwakili oleh dua garis ( -
) untuk 2 × 1 dan dua batang vertikal ( |
) untuk 1 × 2 kartu domino . Setiap ubin (termasuk yang terakhir) harus diikuti oleh umpan baris.
Untuk tujuan penilaian, Anda juga harus menerima bendera dari STDIN atau sebagai argumen baris perintah yang membuat program Anda hanya mencetak jumlah tilings yang valid, tetapi bukan tilings itu sendiri.
Program Anda mungkin tidak lebih dari 1024 byte. Ini harus bekerja untuk semua input sehingga m × n ≤ 64 .
(Terinspirasi oleh Cetak semua domino miring dari persegi panjang 4x6 .)
Contoh
$ sdt 4 2
----
----
||--
||--
|--|
|--|
--||
--||
||||
||||
5
$ sdt 4 2 scoring
5
Mencetak gol
Skor Anda ditentukan oleh waktu pelaksanaan program Anda untuk input 8 8 dengan flag yang ditetapkan.
Untuk menjadikan ini kode tercepat daripada tantangan komputer tercepat , saya akan menjalankan semua pengiriman di komputer saya sendiri (Intel Core i7-3770, 16 GiB PC3-12800 RAM) untuk menentukan skor resmi.
Silakan tinggalkan instruksi rinci tentang cara menyusun dan / atau menjalankan kode Anda. Jika Anda memerlukan versi spesifik dari kompiler / juru bahasa Anda, buat pernyataan tentang hal itu.
Saya berhak untuk meninggalkan kiriman tanpa catatan jika:
Tidak ada kompiler / juru bahasa gratis (seperti dalam bir) untuk sistem operasi saya (Fedora 21, 64 bit).
Terlepas dari upaya kami, kode Anda tidak berfungsi dan / atau menghasilkan output yang salah di komputer saya.
Kompilasi atau eksekusi memakan waktu lebih dari satu jam.
Kode Anda atau satu-satunya kompiler / juru bahasa yang tersedia berisi panggilan sistem ke
rm -rf ~
atau sesuatu yang sama-sama mencurigakan.
Papan peringkat
Saya telah mencetak ulang semua kiriman, menjalankan kompilasi dan eksekusi dalam satu lingkaran dengan 10.000 iterasi untuk kompilasi dan antara 100 dan 10.000 iterasi untuk eksekusi (tergantung pada kecepatan kode) dan menghitung rata-rata.
Inilah hasilnya:
User Compiler Score Approach
jimmy23013 GCC (-O0) 46.11 ms = 1.46 ms + 44.65 ms O(m*n*2^n) algorithm.
steveverrill GCC (-O0) 51.76 ms = 5.09 ms + 46.67 ms Enumeration over 8 x 4.
jimmy23013 GCC (-O1) 208.99 ms = 150.18 ms + 58.81 ms Enumeration over 8 x 8.
Reto Koradi GCC (-O2) 271.38 ms = 214.85 ms + 56.53 ms Enumeration over 8 x 8.
sumber
--
. Jika vertikal, itu dua|
, satu di bawah yang lain.Jawaban:
C
Implementasi yang mudah ...
Versi curang
Penjelasan algoritma yang lebih cepat
Memindai dari kiri ke kanan, dan mempertahankan status
d[i][j]
, di mana:i
dalam[0,m)
, yang berarti kolom saat ini.j
adalah bit vektor ukurann
, di mana bit akan menjadi 1 jika posisi yang sesuai dalam kolomi
sudah ditempati sebelum mulai bekerja pada kolom ini. Yaitu ditempati oleh setengah kanan a--
.d[i][j]
adalah jumlah total tilings yang berbeda.Lalu ucapkan
e[i][j]
= jumlahd[i][k]
tempat Anda dapat meletakkan dasar kartu domino vertikalk
untuk membentuk aj
.e[i][j]
akan menjadi jumlah miring di mana setiap 1 bitj
ditempati oleh apa pun kecuali setengah dari a--
. Isi dengan--
dan Anda akan mendapatkand[i+1][~j]
=e[i][j]
.e[m-1][every bit being 1]
ataud[m][0]
jawaban terakhir.Implementasi naif akan memberi Anda kompleksitas waktu di suatu tempat dekat
g[n]=2*g[n-1]+g[n-2] = O((sqrt(2)+1)^n)
(sudah cukup cepat jika n = m = 8). Tetapi Anda dapat terlebih dahulu mengulang untuk setiap domino yang mungkin, dan mencoba menambahkannya ke setiap ubin yang dapat ditambahkan domino ini, dan menggabungkan hasilnya ke array aslid
(seperti algoritma untuk masalah Knapsack). Dan ini menjadi O (n * 2 ^ n). Dan yang lainnya adalah detail implementasi. Seluruh kode berjalan dalam O (m * n * 2 ^ n).sumber
-O1
tampaknya menjadi titik manis. Saya sudah mencoba semua level optimisasi.)C
Setelah putaran optimasi, dan diadaptasi untuk aturan yang dimodifikasi:
Saya mulai menabrak batas panjang 1024 karakter, jadi saya harus mengurangi keterbacaan. Nama variabel jauh lebih pendek, dll.
Membangun instruksi:
Jalankan dengan solusi yang diaktifkan:
Jalankan dengan hanya jumlah solusi:
Beberapa komentar:
-O2
kelihatannya bagus.Perhatikan juga bahwa kode masih menghasilkan solusi aktual, bahkan dalam mode "hitung saja". Setiap kali solusi ditemukan,
vM
bitmask berisi a1
untuk posisi yang memiliki bilah vertikal, dan a0
untuk posisi dengan bilah horizontal. Hanya konversi bitmask ini ke dalam format ASCII, dan output aktual, dilewati.sumber
-O2
harus baik.-O2
tampaknya menjadi sweet spot. Saya sudah mencoba semua level optimasi.)C
Konsepnya adalah untuk pertama-tama menemukan semua kemungkinan pengaturan domino horizontal dalam satu baris, menyimpannya
r[]
dan kemudian mengaturnya untuk memberikan semua kemungkinan pengaturan domino vertikal.Kode untuk memposisikan domino horisontal secara berturut-turut dimodifikasi dari jawaban saya: https://codegolf.stackexchange.com/a/37888/15599 . Ini lambat untuk grid yang lebih luas tapi itu bukan masalah untuk kasus 8x8.
Inovasi adalah cara baris dirakit. Jika papan memiliki jumlah baris ganjil, papan tersebut diputar hingga 90 derajat pada parsing input, sehingga sekarang memiliki jumlah baris genap. Sekarang saya menempatkan beberapa kartu domino vertikal di garis tengah. Karena simetri, jika ada
c
cara untuk mengatur domino yang tersisa di bagian bawah, juga harus adac
cara mengatur domino yang tersisa di bagian atas, yang berarti bahwa untuk pengaturan domino domino vertikal pada garis tengah, adac*c
solusi yang memungkinkan. . Oleh karena itu, hanya garis tengah ditambah setengah papan yang dianalisis ketika program diharuskan untuk mencetak hanya sejumlah solusi.f()
membangun tabel kemungkinan pengaturan domino horizontal, dan memindai melalui kemungkinan pengaturan domino vertikal di garis tengah. kemudian memanggil fungsi rekursifg()
yang mengisi baris. Jika diperlukan pencetakan, fungsih()
dipanggil untuk melakukan ini.g()
disebut dengan 3 parameter.y
adalah baris saat ini dand
merupakan arah (naik atau turun) di mana kita mengisi papan dari tengah ke luar.x
berisi bitmap menunjukkan domino vertikal yang tidak lengkap dari baris sebelumnya. Semua pengaturan domino yang mungkin secara berurutan dari r [] dicoba. Dalam array ini, 1 mewakili domino vertikal dan sepasang nol merupakan domino horizontal. Sebuah entri yang valid dalam array harus memiliki setidaknya cukup 1 untuk menyelesaikan setiap domino vertikal yang tidak lengkap dari baris terakhir:(x&r[j])==x
. Ini mungkin memiliki lebih dari 1 yang menunjukkan bahwa domino vertikal baru sedang dimulai. Untuk baris berikutnya, maka, kita hanya perlu domino baru sehingga kita memanggil prosedurnya lagix^r[j]
.Jika baris akhir telah tercapai dan tidak ada domino vertikal tidak lengkap yang tergantung di bagian atas atau bawah papan,
x^r[j]==0
maka separuh telah berhasil diselesaikan. Jika kita tidak mencetak, itu cukup untuk menyelesaikan setengah bagian bawah dan digunakanc*c
untuk menghitung jumlah total pengaturan. Jika kita mencetak, perlu juga untuk menyelesaikan setengah bagian atas dan kemudian memanggil fungsi pencetakanh()
.KODE
Perhatikan bahwa input dengan jumlah baris dan jumlah genap ganjil diputar 90 derajat pada fase parsing. Jika ini tidak dapat diterima, fungsi pencetakan
h()
dapat diubah untuk mengakomodasi itu. (EDIT: tidak wajib, lihat komentar.)EDIT: Fungsi baru
e()
telah digunakan untuk memeriksa paritasi
(yaitu jumlah domino yang mengangkang garis tengah). Paritasi
(jumlah setengah domino pada garis tengah yang menjorok ke setiap setengah papan) harus sama dengan keanehan dari jumlah total ruang di setiap setengah (diberikan olehn/2
) karena hanya dengan demikian domino dapat mengisi semua ruang yang tersedia. Hasil edit ini menghilangkan setengah nilai i dan karenanya membuat program saya kira-kira dua kali lebih cepat.sumber
-O0
adalah sweet spot untuk total. Opsi lain memperlambat kompilasi.)32 2 s
. Saya menghentikannya setelah sekitar 15 menit.2 32 s
berjalan hampir seketika. Pemindaian melalui semua kemungkinan domino vertikal sangat boros untukH=2
kasus ini, karena sebenarnya kita sudah memiliki semua informasi yang diperlukan dir[]
. Saya sangat senang dengan waktu resmi untuk8 8 s
Berikut adalah tambalan untuk kasus yang Anda sebutkan:if(H==2){C=p;if(!S)for(i=0;i<p;i++)q[0]=q[1]=r[i],h();}else for(i=0;i<=k;i++)c=0,g(H/2,1,i),C+=c*c;
Seperti yang Anda lihat, cuplikan ini akan berjalan langsungH=2
dengan set bendera. Keseluruhan runtime kemudian dibatasi oleh bangunanr[]
yang tentunya memiliki ruang untuk perbaikan.if(t)for(a=n;a--;a%H||puts(""))putchar(124-(q[a%H]>>a/H)%2*79);else for(a=n;a--;a%W||puts(""))putchar(45+(q[a/W]>>a%W)%2*79);
Panjang kode masih jauh di bawah 1000 byte dan dampak pada waktu kompilasi harus minimal. Saya tidak memasukkan patch ini tadi malam karena saya terlalu lelah.