Tugas Anda adalah menulis program atau fungsi yang dapat mengisi persegi panjang yang diberikan dengan bilangan prima. The width
dan height
persegi panjang akan menjadi masukan. Output harus berupa daftar height
string yang terdiri dari width
digit dan spasi. Setiap urutan digit horizontal (kiri ke kanan) dan vertikal (atas ke bawah) (dibatasi oleh batas ruang atau persegi panjang) dengan panjang 2 atau lebih besar harus merupakan bilangan prima. Setiap bilangan prima hanya dapat digunakan satu kali. Angka nol di depan tidak diizinkan. Garis baru yang tertinggal adalah opsional pada output.
Contoh:
With input (5, 3) a valid output would be:
11 13
7 0
173
which scores 11, 13, 173, 17, 103 for a total of 5 points.
Skor:
Ukuran persegi panjang untuk penilaian akan 80, 60
. Setiap bilangan prima horisontal atau vertikal dengan panjang 2 atau lebih dalam segi empat mencetak satu poin. Jawaban dengan poin terbanyak menang. Dalam hal seri, jawaban paling awal akan menang.
Aturan:
- Celah standar dilarang.
- Program Anda tidak boleh dirancang untuk
80, 60
ukuran. Jika saya menduga jawaban dioptimalkan untuk ukuran ini, saya berhak mengubah ukuran persegi panjang hingga100, 100
. - Bilangan prima yang digunakan harus bilangan prima nyata (bukan probabilistik atau pseudoprimes). Program Anda dapat menghitung atau memeriksa angka pada saat dijalankan, atau meminta kode. Metode menemukan bilangan prima bukanlah bagian penting dari tantangan.
- Jawaban Anda harus mencakup teks keluaran dan kode Anda. Jika program Anda terlalu besar, Anda bisa memasukkan beberapa kode algoritma inti, dengan sedikit penjelasan.
Sunting: Mengklarifikasi bahwa bilangan prima nyata diperlukan. Menambahkan ukuran kotak maksimum.
Sunting 2: Mengklarifikasi kode apa yang perlu diposting.
sumber
Jawaban:
Clingo dengan Python,
160016891740 bilangan primaPendekatan
Saya menghasilkan masalah kepuasan kendala raksasa dan mengatasinya menggunakan pemecah kepuasan kekuatan industri. Banyak sihir telah digunakan untuk membuat pemecah kepuasan relatif cepat (meskipun masalahnya adalah NP-lengkap secara umum), tapi untungnya saya tidak perlu khawatir tentang bagian itu.
Secara khusus, saya memperbaiki posisi digit dalam pola yang dirancang untuk pengepakan dekat nomor 4 dan 5 digit, dengan sesekali angka 2 dan 3 digit pada batas, dan menambahkan batasan yang mengatakan bahwa setiap angka adalah prime yang berbeda. Kemasan saat ini menggunakan sebagian besar dari semua 4 digit bilangan prima (854 dari 1061).
Kode
Pemakaian
Peringatan: pada 80 × 60, ini membutuhkan waktu sekitar 8 menit dan menggunakan memori 3 GB. Anda mungkin ingin memulai dengan ukuran yang lebih kecil jika Anda hanya ingin melihatnya berjalan.
Output (80 × 60, 1740 primes):
sumber
Smalltalk, 1098 bilangan prima
Pertama, pertanyaan sulit yang bagus - sebagaimana dibuktikan oleh kurangnya tanggapan yang tidak sepele sejauh ini.
Saya punya solusi memasak di tempat kerja, tetapi harus menunggu akhir pekan yang panjang untuk punya waktu untuk membersihkannya sedikit. Meski begitu, ini cukup "berat", jadi maafkan panjangnya jawaban ini - untungnya ini bukan pertanyaan kode-golf. Ada banyak gotcha kecil di sepanjang jalan, tapi saya cukup yakin sekarang bebas bug, meskipun ada banyak ruang untuk perbaikan dan penyempurnaan.
Bahasa
Bahasa pilihan saya untuk hal semacam ini adalah Smalltalk - debugging yang unggul dan kemampuan untuk menguji as-you-code mengalahkan apa pun yang saya tahu. Plus, bahkan non-coders dapat membacanya dan memahami dasar-dasar apa yang terjadi. Saya telah membatasi kode di bawah ini pada bagian yang menarik, karena saya pikir pendekatan dan hasilnya akan lebih menarik daripada kode boilerplate, tetapi file-out dari kode lengkap ditempelkan di sini jika ada yang ingin mencobanya (simpan saja sebagai
*.st
dan file dari browser file di Pharo). Saya menggunakan Pharo 4.0, yang FOSS dan dapat diunduh dari pharo.org untuk Win / Mac / Linux. Senang juga menyisipkan kode lengkap di sini, tapi saya mengambil "harus menyertakan teks output dan kode Anda" sebagai saran - beri tahu saya jika saya salah.Pendekatan
Jadi, pemikiran saya adalah, bagaimana jika Anda bisa mulai di tengah, memasukkan sebanyak mungkin bilangan prima yang Anda bisa di dalam kotak, dan bekerja dengan cara Anda keluar dari sana? Mari kita mulai dengan
Box
objek, yang mengandungmatrix
karakter, dan kemudian gunakanStuffer
objek untuk mencoba mengisinya dengan menemukan yang terbaikInsertion
(objek lain) untuk setiap titik dalam matriks dan untuk setiap prime (dimulai dengan yang panjang). Pharo memiliki kelasMatrix
dan bagusPoint
dengan banyak metode yang berguna (meskipun cara matriks menggunakan notasi baris-utama versus menggunakan xy-koordinat poin bisa menjadi sedikit membingungkan jika Anda tidak hati-hati).Langkah-langkah dasar dari algoritma saya adalah:
Stuffer
contoh untuk dimensi yang diberikan.Dapat dikonfigurasi:
Untuk matriks di bawah ini, saya menggunakan 80x60, bilangan prima di bawah 20.000 (karena panjang gabungannya hanya di bawah 10.000 karakter, yaitu maksimum untuk boneka, meskipun tidak valid, kotak 100x100), dan, setelah beberapa percobaan, peringkat berikut untuk
each
penyisipan :di mana
accidentalPrimes
bilangan prima tegak lurus "tidak sengaja" dibuat ketika menyisipkan antara bilangan prima tetangga, dannumberOfOverlaps
berapa banyak karakter yang ditimpa (misalnya ketika menambahkan a3
di akhir11
untuk memasukkan113
). Pada awalnya saya memiliki bobot lebih ke arahaccidentalPrimes
, tetapi mendapat beberapa bilangan prima di kotak dengan melakukannya dengan cara ini - tidak sepenuhnya yakin mengapa (jangan ragu untuk menguji / tweak).Hasil
Matriks ini berisi 1098 bilangan prima, yang merupakan "beban" sekitar 70%.
Ini adalah bilangan prima (
box primesUsed asSortedCollection printString
):Seperti yang Anda lihat, beberapa bilangan prima "kebetulan" cukup lama ... 20 digit untuk bilangan terpanjang. :-)
Detail
Untuk memahami cara kerjanya, berikut adalah hasil dari melakukan beberapa langkah pertama - menyisipkan
19997
terlebih dahulu (jika Anda melihat di tengah matriks besar, Anda akan melihat di19997
sana juga), lalu turun daftar di mana ada ruang di 5x5 kotak (>
berarti menyisipkan ke kanan,v
berarti turun; apa pun yang{}
ada secara tidak sengaja ditambahkan bilangan prima:Dalam penyisipan tepat di atas, kotak menjadi 7x7, dan diisi dengan konten 5x5 sebelum penyisipan berikutnya terjadi. Saya juga menghitung ulang bilangan prima yang digunakan pada titik ini, karena beberapa "dibebaskan" karena menimpa (
11
dimasukkan, tetapi kemudian ditimpa oleh113
).Kode
Berikut adalah bagian kode yang paling relevan:
Kelas Stuffer
Sisi kelas
Sisi contoh
Kelas kotak
Sisi contoh
Koleksi
Oh, dan saya menambahkan satu metode ke sisi instance
Collection
, hanya untuk kenyamanan:Lari itu
Untuk menjalankan kode saya, yang perlu saya lakukan adalah memilih kode berikut di ruang kerja ("taman bermain" di Pharo) atau di panel teks apa pun, dan "lakukan itu" dari menu konteks:
Sisa kode ini relatif membosankan.
Seperti yang saya katakan, ruang untuk perbaikan, tetapi pada 80x60, setiap menjalankan membutuhkan waktu lebih dari 3 menit pada mesin saya. Jelas, kinerja bukan urusan saya, tetapi ada BANYAK bilangan prima terbang di sekitar. Ini tentu saja merupakan tantangan yang menarik. :-)
sumber
Javascript, skor 659
Hampir pasti suboptimal.
Hasil untuk 30x30:
Dan untuk kasus 60x60:
sumber