Papan angka
Berikut adalah skor mentah (yaitu jumlah domino) untuk pengiriman VisualMelon. Saya akan mengubahnya menjadi skor yang dinormalisasi yang dijelaskan di bawah ini, ketika lebih banyak jawaban masuk. Solusi yang ada sekarang dapat menyelesaikan semua sirkuit di benchmark:
Author Circuit: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
VisualMelon 39 45 75 61 307 337 56 106 76 62 64 62 182 64 141 277 115 141 92 164 223 78 148 371 1482 232 107 782 4789 5035 1314 3213 200 172 1303 3732 97596 156889 857
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Legend:
I - invalid circuit
B - circuit too big
W - circuit computes wrong function
T - exceeded time limit
Tantangan
Hal ini dimungkinkan untuk membangun gerbang logika sederhana dari domino. Oleh karena itu, dengan menggabungkan ini atau sebaliknya, fungsi biner sewenang-wenang dapat dihitung dengan kartu domino.
Tapi tentu saja, semua orang yang telah bermain dengan kartu domino (kecuali Robin Paul Weijers) telah mengalami kekecewaan ketika kehabisan mereka. Oleh karena itu, kami ingin menggunakan kartu domino kami seefisien mungkin, sehingga kami dapat melakukan beberapa perhitungan yang sangat menarik dengan bahan yang kami miliki.
Perhatikan, bahwa Anda tidak dapat menghasilkan output non-nol dari input nol per se, jadi kami perlu menambahkan "saluran listrik", yang jatuh di sepanjang pengaturan Anda, dan yang dapat Anda tarik 1
kapan saja.
Tugas Anda
Diberikan fungsi boolean dengan M
input dan N
output ( f: {0,1}^M --> {0,1}^N
untuk kemiringan matematis), menghasilkan sirkuit domino dengan sesedikit mungkin domino yang menghitung fungsi itu. Anda akan menggunakan simbol-simbol |
, -
, /
, \
untuk mewakili domino di berbagai orientasi.
Memasukkan
Anda akan diberikan masukan melalui argumen baris perintah:
[command for your solver] M N f
di mana M
dan N
bilangan bulat positif dan f
merupakan tabel kebenaran yang dipisahkan koma dalam urutan kanonik. Artinya, f
akan mengandung 2^M
nilai panjang N
. Misal jika M = N = 2
dan bit pertama dalam output adalah fungsi AND sedangkan bit kedua adalah fungsi OR, f
akan dibaca
00,01,01,11
Keluaran
Menulis ke STDOUT kisi ASCII yang mewakili pengaturan domino. Pengaturan Anda harus sesuai dengan kerangka kerja berikut
/////.../////
????...????
I????...????O
I????...????O
.............
.............
I????...????O
I????...????O
I????...????O
- Baris teratas seluruhnya terdiri dari
/
, dan domino paling kiri dijamin akan terguling di awal - ini adalah saluran listrik Anda. - Kolom paling kiri terdiri dari input Anda. Masing
I
- masing bisa berupa spasi atau|
, sedemikian rupa sehingga ada persisM
|
s. - Kolom paling kanan terdiri dari output Anda. Masing
O
- masing bisa berupa spasi atau|
, sedemikian rupa sehingga ada persisN
|
s. - Perhatikan bahwa setidaknya ada satu yang kosong sebelum yang pertama
|
di input atau output. - The
.
menunjukkan bahwa grid dapat sewenang-wenang besar. - Anda dapat mengisi
?
dengan cara apa pun yang Anda inginkan.
Perhatikan bahwa input bawah adalah yang paling beragam saat Anda menelusuri tabel kebenaran, sedangkan input atas adalah 0
untuk bagian pertama dari output dan 1
untuk bagian kedua.
Aturan
Domino menyebar seperti yang ditentukan dalam Golfing untuk Domino Day . Singkatnya, jika kita mewakili arah jatuh sebagai huruf
Q W E
A D
Z X C
maka ini semua kombinasi unik yang dapat diperbanyak (serta rotasi dan pantulannya):
D| -> DD D\ -> DE D/ -> DC
C| -> CD C/ -> CC
C -> C C -> C C -> C
| D - X / C
Semua aturan di atas diterapkan secara bersamaan pada setiap langkah waktu. Jika dua orang dari aturan-aturan yang bertentangan (ubin yaitu didorong ke dua valid arah berlawanan pada waktu yang sama), ubin yang terkena akan tidak jatuh, dan akan efektif dikunci ke posisi untuk sisa simulasi.
Batasan
M
danN
tidak akan pernah melebihi 6.- Pemecah Anda harus menghasilkan sirkuit dalam N * 2 M detik .
- Solver Anda tidak boleh menggunakan memori lebih dari 1 GB . Ini adalah batas lunak, karena saya akan memonitor ini secara manual dan membunuh proses Anda jika secara signifikan / terus menerus melebihi batas ini.
- Tidak ada sirkuit yang diizinkan mengandung lebih dari 8.000.000 sel atau 1.000.000 kartu domino .
- Kiriman Anda harus bersifat deterministik . Anda diizinkan untuk menggunakan generator angka pseudo-acak, tetapi mereka harus menggunakan seed hardcoded (yang Anda bebas untuk mengoptimalkan sebanyak yang Anda mau).
Mencetak gol
Untuk setiap sirkuit, biarlah D
jumlah total kartu domino di sirkuit Anda dan B
jumlah kartu domino terendah yang pernah diselesaikan oleh sirkuit ini (oleh Anda atau peserta lain). Kemudian skor Anda untuk sirkuit ini diberikan dengan 10,000 * B / D
dibulatkan ke bawah. Jika Anda gagal menyelesaikan sirkuit, skor Anda adalah 0. Skor keseluruhan Anda akan menjadi jumlah atas serangkaian kasus uji patokan. Sirkuit yang belum diselesaikan oleh siapa pun tidak akan dimasukkan dalam skor total.
Setiap peserta dapat menambahkan satu test case ke benchmark (dan semua pengiriman lainnya akan dievaluasi ulang termasuk case test yang baru).
File benchmark dapat ditemukan di GitHub .
Contohnya
Berikut adalah beberapa contoh yang tidak diselesaikan secara optimal.
Konstan 1
1 1
1,1
///////
/
| |||
Hitungan domino: 12
ATAU gerbang
2 1
0,1,1,1
///////////
|||||/
|||||
|||||\
Hitungan domino: 28
DAN gerbang
2 1
0,0,0,1
///////////////////
\-/
- -
|||||/|\ /|||/
/ -
- \-
\- \ -
|||||\ / \ /
|\ |||||
Jumlah domino: 62
Ganti jalur
2 2
00,10,01,11
////////////
||||/ \||||
/\
\/
||||\ /||||
Hitungan domino: 36
catatan tambahan
Aturan propagasi sedemikian rupa, sehingga jalur diagonal dapat menyeberang menggunakan bentuk berlian (lihat contoh terakhir) meskipun satu jatuh sebelum yang lain (tidak seperti dengan domino nyata).
Sebagai titik awal, Anda dapat menggunakan gerbang logis (tidak diminimalkan) dalam inti ini dan mencoba menggabungkan sesedikit mungkin dari ini. Untuk cara sederhana (tidak optimal) untuk membangun fungsi boolean yang sewenang-wenang dari gerbang AND, ATAU dan BUKAN, lihatlah Bentuk Normal Konjungtif dan Disjungtif .
Ada verifikasi tempat penyimpanan GitHub ini untuk menguji kode Anda, yang juga akan digunakan untuk menilai semua pengiriman. Ini menghasilkan skor mentah (jumlah domino) dan menyimpannya ke file untuk diproses oleh pencetak skor terpisah (juga dalam repositori itu) untuk mendapatkan skor akhir.
Dokumentasi umum dapat ditemukan dalam dua file Ruby, tetapi controller.rb
dibutuhkan dua switch baris perintah sebelum file benchmark:
-v
memberi Anda lebih banyak output, termasuk sirkuit aktual yang dihasilkan oleh pemecah Anda.-c
memungkinkan Anda memilih subset benchmark yang ingin Anda uji. Berikan sirkuit yang diinginkan sebagai daftar indeks berbasis 1 yang dipisahkan koma. Anda juga dapat menggunakan rentang Ruby, sehingga Anda dapat melakukan sesuatu seperti-c 1..5,10,15..20
.
Harap sertakan dalam jawaban Anda:
- Kode Anda
- Perintah untuk (kompilasi dan) menjalankan kode Anda. Saya akan bertanya kepada Anda di mana mendapatkan kompiler / juru bahasa yang diperlukan jika saya tidak memilikinya.
- Tabel kebenaran tambahan dengan nama, akan ditambahkan sebagai kasus uji untuk benchmark. (Ini opsional, tetapi sangat dianjurkan.)
Saya akan menguji semua pengiriman pada Windows 8.
sumber
Jawaban:
C # - Solusi masif, Lambat, dan tidak efisien
Pengakuan: menulis solusi ini beberapa waktu lalu ketika pertanyaannya masih di kotak pasir, tapi itu tidak terlalu baik: Anda bisa melakukan yang lebih baik!
Sunting: mengganti penyelesaian yang membosankan dengan metode yang kurang membosankan, lebih fleksibel, dan umumnya lebih baik
Anda menjalankan program dengan kompilasi dengan
csc dominoPrinter.cs
dan kemudian meneruskan argumen ke executable, misalnya (pemeriksa utama 4-bit):Penjelasan:
"Domino Printer" adalah program 3 tahap:
Tahap 1 : "pemecah" menghasilkan pohon ekspresi "ifnot" dan "atau" operasi biner dengan input yang diberikan, dan "1" dari kabel listrik, ada 2 cara ini dilakukan, tergantung pada jumlah input:
Jika terdapat kurang dari 4 input, program akan menghasilkan solusi dari jumlah operasi yang paling sedikit
Jika ada 4 atau lebih input, program akan melakukan brute setiap 8 bit output dan kemudian menggabungkan hasilnya untuk memberikan output yang diinginkan. Bit yang dirusak jika fleksibel: bit yang lebih kasar, semakin kecil solusinya, tetapi semakin lama waktu proses.
"Pemecah masalah" adalah yang membutuhkan waktu lama (atau paling tidak seperti dulu), dan juga sebagian besar kode. Saya percaya ada solusi yang terdokumentasi dengan baik, cepat, tidak begitu memori, dan mungkin solusi optimal untuk masalah ini, tetapi di mana kesenangan berada dalam mencari itu?
Pohon ekspresi (brute) untuk pemeriksa utama 4-bit adalah
di mana angka-angka adalah indeks input.
Tahap 2 : "Penyelenggara" mengambil pohon ekspresi sebagai input dan merakit tata letak "kerangka", yang secara tepat menggambarkan tata letak domino yang dibuat dari beberapa set sel 4x5 yang tumpang tindih. Di bawah ini adalah kerangka untuk pemeriksa prima 4-bit yang dibasahi (Anda harus mengubah
bruteBase
variabel integer pada baris 473 ke 4 (atau lebih besar) untuk mendapatkan hasil ini).Output ini secara efektif dibuat hingga dua bagian, "evaluator" di sebelah kanan, yang dibuat dari pohon ekspresi dari tahap 1, dan "switchboard" di sebelah kiri, yang menukar dan membagi input sehingga mereka tiba di tempat yang tepat untuk ditangani oleh "evaluator".
Ada ruang yang cukup besar untuk memadatkan tata letak pada titik ini, tetapi program saat ini tidak begitu berfungsi. Kode untuk tahap ini mengerikan, tetapi cukup sederhana di bawahnya (lihat metode "orifnot"). Output dilewatkan ke tahap 3.
Tahap 3 : "Printer" mengambil output dari "organizer" dan mencetak "sel" 4x5 yang sesuai bersama dengan saluran listrik. Di bawah ini adalah animasi dari pemeriksa prime 4-bit yang diperiksa memeriksa apakah 5 adalah prima.
Kode kurangnya indentasi adalah untuk menghindari melampaui batas karakter SE 30k yang seharusnya :
Kasing uji tambahan:
Ini memeriksa apakah dua bit yang berdekatan (non-pembungkus) keduanya 1s (mis. True untuk 0110, tetapi false untuk 0101 dan 1001)
sumber
I
dan yang hasilnya menentukan tata letak domino baru