Untuk informasi lebih lanjut, tonton video ini , dan buka A276523 untuk urutan yang terkait.
Puzzle Mondrian (untuk bilangan bulat n
) adalah sebagai berikut:
Pasangkan persegi panjang yang tidak kongruen ke dalam n*n
kotak persegi. Apa perbedaan terkecil yang mungkin antara persegi panjang terbesar dan terkecil?
Sebab 6
, perbedaan optimal untuk M(6)
adalah 5
, dan dapat ditunjukkan seperti:
___________
| |S|_______|
| | | L |
| |_|_______|
| | | |
| |_____|___|
|_|_________| (fig. I)
Kotak terbesar (L) memiliki luas 2 * 4 = 8
, dan kotak terkecil (S) memiliki luas 1 * 3 = 3
. Karena itu, perbedaannya adalah 8 - 3 = 5
.
Perlu diingat bahwa saat ini, tidak ada solusi optimal untuk n > 44
telah ditemukan.
Tugas Anda adalah membuat program yang menghasilkan kisi Mondrian yang berisi solusi (tidak optimal), diberi bilangan bulat n
.
Anda akan diuji pada angka dari 100 hingga 150. Skor Anda untuk setiap tes akan menjadi perbedaan antara persegi panjang terbesar dan terkecil. Skor total Anda adalah jumlah skor Anda untuk semua tes dari 100 hingga 150.
Anda harus menyajikan output Anda seperti ini:
{number}
{grid}
Di mana number
skor (perbedaan antara terbesar dan terkecil), dan grid
adalah:
- String multi-baris, atau
- Daftar dua dimensi.
Grid HARUS dengan jelas menunjukkan di mana persegi panjang dimulai dan berakhir.
Aturan:
- Program Anda harus sesuai dengan jawaban Anda.
- Program Anda harus menampilkan nilai untuk angka antara 100 dan 150 dalam 1 jam pada laptop modern.
- Program Anda harus menghasilkan solusi yang sama untuk integer
n
setiap kali program dijalankan. - Anda harus memberikan tautan ke output dari semua 51 solusi (menggunakan Pastebin, Github Gist ... apa saja, sungguh).
- Anda harus memiliki setidaknya dua persegi panjang di kotak persegi untuk solusi Anda.
sumber
Jawaban:
Piet, 9625
(Akhirnya berhasil!)
Orang-orang menuntutnya, jadi ini dia. Ini adalah solusi yang sangat naif (pada dasarnya sama dengan batas atas yang longgar pada halaman OEIS): solusi ini membagi setiap kotak menjadi hanya dua persegi panjang.
Intisari ini berisi detail dalam dua file:
?
adalah input prompt, segera diikuti oleh skor output, kemudian grid.Penjelasan
Program ini mengambil satu nomor
N
sebagai input. Jika angkanya ganjil, skornya adalah angkanya; jika genap, angkanya dua kali angka.Setelah mengeluarkan skor, sisa sisi kiri program dihabiskan untuk mengisi tumpukan dengan lima lot informasi berikut:
N
)_
spasi)|
)Sisi kanan program mengambil setiap set empat nilai dan mencetak bagian dari grid.
sumber
C 6108
Ini menggunakan versi minimal solusi rekursif (benar-benar iteratif). Alih-alih membagi persegi menjadi dua persegi panjang di mana seseorang sedikit lebih besar dari setengah luasnya, ia membaginya menjadi N persegi panjang. Jadi persegi panjang pertama sedikit lebih besar dari
1/N
luas total. Kemudian mengambil sisanya, program memecah persegi panjang sedikit lebih besar1/(N-1)
dari sisanya dan seterusnya sampai hanya mengambil sisanya sebagai persegi panjang terakhir. Segi empat terpotong dari sisanya dalam spiral searah jarum jam, jadi pertama di atas, lalu di kanan, dll.Karena ini adalah metode yang sangat langsung alih-alih pencarian ruang yang luas, ini berjalan cepat - membutuhkan waktu sekitar 25 detik (pada Raspberry Pi) untuk melihat 74 solusi masing-masing untuk set masalah yang diberikan.
Maksud saya adalah menggunakan hasil ini untuk menginformasikan algoritma pencarian dengan lebih baik untuk pendekatan yang lebih canggih.
Outputnya memberikan skor dan gambar (ascii) dan koordinat untuk simpul persegi panjang. Verteks berada dalam urutan searah jarum jam, mulai dari sudut kiri atas dari persegi panjang yang bersangkutan.
Dikembangkan menggunakan gcc 4.9.2-10.
Hasil di https://github.com/JaySpencerAnderson/mondrian
Kode:
sumber
C - 2982
Program ini mengimplementasikan pencarian melalui set hasil yang luas. Bagian penting dari membuat pencarian ini praktis adalah gagal lebih awal dan / atau tidak turun jalur yang buruk.
Ini menghasilkan seperangkat persegi panjang untuk dipertimbangkan untuk solusi. Himpunan persegi panjang yang dihasilkan menghindari mereka dengan dimensi yang tidak akan berguna. Misalnya, jika program mencoba menemukan solusi untuk 128x128 persegi, dibagi menjadi 8 persegi panjang, itu akan menghasilkan persegi panjang yaitu 128x16. Itu tidak akan menghasilkan yang satu adalah 120x17 karena tidak ada prospek menghasilkan persegi panjang yang lebar 8 untuk mengisi celah di akhir 120.
Strategi awal untuk menempatkan persegi panjang adalah menempatkannya di bagian dalam perimeter persegi (fungsi buildedge). Dengan cara itu, algoritma mendapatkan umpan balik yang cukup cepat di setiap sudut, apakah ada masalah dengan urutan yang dipilih. Sambil menempatkan persegi panjang, logika terus mengawasi untuk melihat apakah ada celah ruang yang terlalu sempit untuk persegi panjang. Setelah perimeter berhasil diisi, strategi berubah menjadi mencoba mencocokkan ruang yang tersisa dengan persegi panjang yang tersisa (fungsi pertandingan).
Satu hal lain yang mungkin menarik adalah bahwa ini mengimplementasikan transaksi dengan rollback untuk tumpukan persegi panjang.
Program ini tidak mencoba menemukan yang paling cocok. Itu diberikan anggaran (64) dan berhenti ketika menemukan solusi pertama. Jika tidak pernah menemukan solusi, kami menambah anggaran (sebesar 16) dan mencoba lagi. Waktu yang diperlukan (pada laptop Dell dengan prosesor I7) berkisar dari jauh di bawah satu menit hingga 48 menit selama 150 pada satu sisi (149 pada satu sisi membutuhkan waktu kurang dari 2 menit). Semua 51 solusi menggunakan 11 persegi panjang. Skor dari 51 solusi berkisar 41-78. Alasan saya menggunakan 11 persegi panjang adalah bahwa skor lebih rendah daripada dengan lebih sedikit persegi panjang dan sepertinya 12 persegi panjang akan membutuhkan lebih banyak daripada waktu yang diberikan.
Solusi dan kode dapat ditemukan di https://github.com/JaySpencerAnderson/mondrian . Mereka adalah dua file my4 *.
BTW, jika Anda mengkompilasi ini ke "my4" dan menjalankannya sebagai berikut: "./my4 -h", itu akan memberi Anda penggunaan. Jika Anda ingin melihatnya bekerja, coba sesuatu seperti "./my4 -l 50 -n 8". Jika Anda mengubah yang "# jika 0" menjadi "# jika 1" itu akan membuat ruang yang tersisa di layar. Jika Anda ingin mengubah ini untuk merender persegi panjang, cari satu tempat di mana kode mengeksekusi "grafik (spasi, samping)" dan ubah itu menjadi "grafik (panggil, sisi)" sebagai gantinya. Saya juga menyarankan mengubah anggaran awal dari 64 menjadi 32 jika Anda ingin bermain-main dengan solusi untuk kotak yang sekitar 50 lebar. Solusi untuk kotak yang lebih kecil akan memiliki skor yang lebih baik dengan anggaran yang lebih kecil.
Program di bawah ini fungsional. Periksa github untuk kode lengkap (dengan penggunaan, komentar, dll).
sumber