Untuk gambar N demi N , temukan satu set piksel sehingga tidak ada jarak pemisahan yang muncul lebih dari satu kali. Yaitu, jika dua piksel dipisahkan oleh jarak d , maka mereka hanya dua piksel yang dipisahkan dengan tepat d (menggunakan jarak Euclidean ). Perhatikan bahwa d tidak perlu bilangan bulat.
Tantangannya adalah menemukan set yang lebih besar daripada orang lain.
Spesifikasi
Tidak diperlukan input - untuk kontes ini N akan diperbaiki pada 619.
(Karena orang terus bertanya - tidak ada yang istimewa tentang nomor 619. Dipilih menjadi cukup besar untuk membuat solusi optimal tidak mungkin, dan cukup kecil untuk membiarkan gambar N demi N ditampilkan tanpa Stack Exchange secara otomatis mengecilkannya. Gambar dapat ditampilkan ukuran penuh hingga 630 kali 630, dan saya memutuskan untuk menggunakan prime terbesar yang tidak melebihi itu.)
Outputnya adalah daftar integer yang dipisahkan oleh spasi.
Setiap bilangan bulat dalam output mewakili salah satu piksel, diberi nomor dalam urutan bacaan bahasa Inggris dari 0. Misalnya untuk N = 3, lokasi akan diberi nomor dalam urutan ini:
0 1 2
3 4 5
6 7 8
Anda dapat menampilkan informasi kemajuan selama menjalankan jika Anda inginkan, selama hasil penilaian akhir mudah tersedia. Anda dapat output ke STDOUT atau ke file atau apa pun yang paling mudah untuk menempel ke Hakim Potongan Stack di bawah ini.
Contoh
N = 3
Koordinat yang Dipilih:
(0,0)
(1,0)
(2,1)
Keluaran:
0 1 5
Kemenangan
Skor adalah jumlah lokasi dalam output. Dari jawaban yang valid yang memiliki skor tertinggi, yang paling awal untuk memposting output dengan skor yang menang.
Kode Anda tidak perlu deterministik. Anda dapat memposting output terbaik Anda.
Bidang terkait untuk penelitian
(Terima kasih kepada Abulafia untuk tautan Golomb)
Meskipun tidak satu pun dari keduanya yang sama dengan masalah ini, keduanya memiliki konsep yang sama dan dapat memberi Anda gagasan tentang cara mendekati ini:
- Penguasa Golomb : case 1 dimensional.
- Persegi panjang Golomb : perpanjangan 2 dimensi dari penguasa Golomb. Varian kasus NxN (kotak) yang dikenal sebagai array Costas diselesaikan untuk semua N.
Perhatikan bahwa poin yang diperlukan untuk pertanyaan ini tidak tunduk pada persyaratan yang sama dengan persegi panjang Golomb. Persegi panjang Golomb memanjang dari case 1 dimensi dengan mensyaratkan bahwa vektor dari setiap titik menjadi unik. Ini berarti bahwa ada dua titik yang dipisahkan oleh jarak 2 secara horizontal, dan juga dua titik dipisahkan oleh jarak 2 secara vertikal.
Untuk pertanyaan ini, jarak skalar yang harus unik, sehingga tidak boleh ada pemisahan horizontal dan vertikal 2. Setiap solusi untuk pertanyaan ini adalah persegi panjang Golomb, tetapi tidak setiap persegi panjang Golomb akan menjadi solusi yang valid untuk pertanyaan ini.
Batas atas
Dennis membantu menunjukkan dalam obrolan bahwa 487 adalah batas atas skor, dan memberikan bukti:
Menurut kode CJam saya (
619,2m*{2f#:+}%_&,
), ada 1.118.000 angka unik yang dapat ditulis sebagai jumlah kuadrat dari dua bilangan bulat antara 0 dan 618 (keduanya termasuk). n piksel memerlukan n (n-1) / 2 jarak unik antara satu sama lain. Untuk n = 488, itu memberi 118828.
Jadi ada 118.800 kemungkinan panjang berbeda antara semua piksel potensial dalam gambar, dan menempatkan 488 piksel hitam akan menghasilkan 118.828 panjang, yang membuat mustahil bagi mereka semua untuk menjadi unik.
Saya akan sangat tertarik untuk mendengar jika ada yang punya bukti batas atas yang lebih rendah dari ini.
Papan peringkat
(Jawaban terbaik oleh setiap pengguna)
Hakim Stack Snippet
sumber
Jawaban:
Python 3,
135136137Ditemukan menggunakan algoritma serakah yang, pada setiap tahap, memilih piksel yang valid yang set jaraknya ke piksel yang dipilih tumpang tindih paling sedikit dengan piksel lainnya.
Secara khusus, skornya adalah
dan piksel dengan skor terendah dipilih.
Pencarian dimulai dengan titik
10
(yaitu(0, 10)
). Bagian ini dapat disesuaikan, jadi mulai dengan piksel yang berbeda dapat menyebabkan hasil yang lebih baik atau lebih buruk.Algoritma ini cukup lambat, jadi saya mencoba menambahkan optimisasi / heuristik, dan mungkin beberapa langkah mundur. PyPy direkomendasikan untuk kecepatan.
Siapa pun yang mencoba membuat algoritme harus mencoba
N = 10
, yang saya dapatkan 9 (tetapi ini membutuhkan banyak penyesuaian dan mencoba titik awal yang berbeda):Kode
sumber
N=10
dan ada banyak tata letak yang berbeda dengan 9 poin tetapi itu yang terbaik yang bisa Anda lakukan.SWI-Prolog, skor 131
Hampir tidak lebih baik daripada jawaban awal, tapi saya kira ini akan membuat segalanya mulai lebih. Algoritma ini sama dengan jawaban Python kecuali fakta bahwa ia mencoba piksel dengan cara alternatif, dimulai dengan piksel kiri atas (piksel 0), kemudian piksel kanan bawah (piksel 383160), lalu piksel 1, kemudian piksel 383159 , dll.
Memasukkan:
a(A).
Keluaran:
Gambar dari Stack Snippet
sumber
Haskell—
115130131135136Inspirasi saya adalah Saringan Eratosthenes dan khususnya The Saringan Asli Eratosthenes , sebuah makalah oleh Melissa E. O'Neill dari Harvey Mudd College. Versi asli saya (yang dianggap sebagai poin dalam urutan indeks) menyaring poin dengan sangat cepat, untuk beberapa alasan saya tidak dapat mengingat saya memutuskan untuk mengacak poin sebelum "mengayak" mereka dalam versi ini (saya pikir semata-mata untuk membuat menghasilkan jawaban yang berbeda lebih mudah dengan menggunakan benih baru di generator acak). Karena poin tidak lagi dalam urutan apa pun, tidak ada penyaringan yang sebenarnya terjadi lagi, dan sebagai hasilnya diperlukan beberapa menit hanya untuk menghasilkan jawaban 115 poin tunggal ini. Sebuah KO
Vector
mungkin akan menjadi pilihan yang lebih baik sekarang.Jadi dengan versi ini sebagai pos pemeriksaan saya melihat dua cabang, kembali ke algoritma "Saringan Asli" dan memanfaatkan daftar monad untuk pilihan, atau mengganti
Set
operasi untuk padanan yang setaraVector
.Sunting: Jadi untuk versi dua bekerja saya beralih kembali ke algoritma ayakan, meningkatkan generasi "kelipatan" (mengetuk indeks dengan menemukan titik pada koordinat bilangan bulat pada lingkaran dengan jari-jari yang sama dengan jarak antara dua titik, mirip dengan menghasilkan kelipatan utama) ) dan membuat beberapa perbaikan waktu konstan dengan menghindari beberapa perhitungan ulang yang tidak perlu.
Untuk beberapa alasan saya tidak dapat mengkompilasi ulang dengan profil yang dihidupkan, tetapi saya percaya bahwa hambatan utama sekarang adalah kemunduran. Saya pikir mengeksplorasi sedikit paralelisme dan konkurensi akan menghasilkan peningkatan kecepatan linear, tetapi kehabisan memori mungkin akan membuat saya mengalami peningkatan 2x.
Sunting: Versi 3 sedikit berkelok-kelok, saya pertama kali bereksperimen dengan heuristik dalam mengambil indeks 𝐧 berikutnya (setelah menyaring dari pilihan sebelumnya) dan memilih yang menghasilkan set KO minimum berikutnya. Ini berakhir menjadi terlalu lambat, jadi saya kembali ke metode brute force seluruh-pencarian. Suatu ide untuk memesan titik-titik dengan jarak dari beberapa asal datang kepada saya, dan menyebabkan peningkatan dengan satu titik (pada saat kesabaran saya bertahan). Versi ini memilih indeks 0 sebagai asal, mungkin ada baiknya mencoba titik tengah pesawat.
Sunting: Saya mengambil 4 poin dengan memesan ulang ruang pencarian untuk memprioritaskan poin yang paling jauh dari pusat. Jika Anda menguji kode saya,
135136 sebenarnya adalah solusi ketigakedua yangditemukan. Edit cepat: Versi ini tampaknya paling mungkin tetap produktif jika dibiarkan berjalan. Saya kira saya mungkin mengikat pada 137, kemudian kehabisan kesabaran menunggu 138.Satu hal yang saya perhatikan (yang mungkin bisa membantu seseorang) adalah bahwa jika Anda mengatur titik pemesanan dari pusat pesawat (yaitu, menghapus
(d*d -)
darioriginDistance
) gambar yang terbentuk terlihat sedikit seperti spiral prima yang jarang.Keluaran
sumber
d
meminimalkan jumlah titik lain yang dikecualikan dari pertimbangan dengan menelusuri lingkaran jarid
- jari dengan pusat dari kedua titik yang dipilih, di mana perimeter hanya menyentuh tiga koordinat bilangan bulat lainnya (pada putaran 90, 180, dan 270 derajat sekitar lingkaran), dan garis membagi dua tegak lurus yang melintasi tidak ada koordinat bilangan bulat. Jadi setiap poin barun+1
akan mengecualikan6n
poin lain dari pertimbangan (dengan pilihan optimal).Python 3, skor 129
Ini adalah contoh jawaban untuk memulai sesuatu.
Hanya pendekatan naif melalui piksel secara berurutan dan memilih piksel pertama yang tidak menyebabkan jarak pemisahan duplikat, sampai piksel habis.
Kode
Keluaran
Gambar dari Stack Snippet
sumber
Python 3, 130
Sebagai perbandingan, berikut ini adalah implementasi backtracker rekursif:
Ia menemukan solusi 130 piksel berikut dengan cepat sebelum mulai tersedak:
Lebih penting lagi, saya menggunakannya untuk memeriksa solusi untuk kasus-kasus kecil. Untuk
N <= 8
, yang optimal adalah:Terdaftar dalam kurung adalah optimis leksikografis pertama.
Belum dikonfirmasi:
sumber
Scala, 132
Memindai dari kiri ke kanan dan dari atas ke bawah seperti solusi naif, tetapi coba mulai dari lokasi piksel yang berbeda.
Keluaran
sumber
Python, 134
132Inilah yang sederhana yang secara acak memilah beberapa ruang pencarian untuk mencakup area yang lebih luas. Itu iterates poin dalam jarak dari urutan asal. Itu melompati poin yang jaraknya sama dari asal, dan keluar awal jika tidak bisa meningkatkan yang terbaik. Ini berjalan tanpa batas.
Dengan cepat menemukan solusi dengan 134 poin:
3097 3098 2477 4333 3101 5576 1247 9 8666 8058 12381 1257 6209 15488 6837 21674 19212 26000 24783 1281 29728 33436 6863 37767 26665 14297 4402 43363 50144 52624 18651 9996 58840 42792 6495730730303030303073073030307303030303030303030303030303030303030303030303030303030303073030303030303030303030303030303030303030303030303030303030303030303030303030303030303030303030730303030303030303030303030303030303030 Dengan Penawaran Telepon 11.313. 249115 21544 95185 231226 54354 104483 280665 518 147181 318363 1793 248609 82260 52568 365227 361603 346849 331462 69310 90988 341446 229599 277828 382837 339014 323612 365040 269883 317
Bagi yang penasaran, berikut adalah beberapa N kecil paksa:
sumber
Fantom 96
Saya menggunakan algoritma evolusi, pada dasarnya menambahkan titik acak k pada suatu waktu, melakukannya untuk j set acak yang berbeda, lalu memilih yang terbaik dan ulangi. Jawaban yang cukup mengerikan saat ini, tetapi itu dijalankan dengan hanya 2 anak per generasi demi kecepatan, yang hampir hanya acak. Akan bermain dengan parameter sedikit untuk melihat bagaimana kelanjutannya, dan saya mungkin perlu fungsi penilaian yang lebih baik daripada jumlah tempat gratis yang tersisa.
Keluaran
sumber
Python 3, 119
Saya tidak lagi ingat mengapa saya menamai fungsi ini
mc_usp
, meskipun saya curiga ada hubungannya dengan rantai Markov. Di sini saya menerbitkan kode saya yang saya jalankan dengan PyPy selama sekitar 7 jam. Program ini mencoba untuk membangun 100 set piksel yang berbeda dengan memilih piksel secara acak hingga memeriksa setiap piksel dalam gambar, dan mengembalikan salah satu set terbaik.Pada catatan lain, pada titik tertentu, kita harus benar-benar berusaha untuk menemukan batas atas
N=619
yang lebih baik daripada 488, karena menilai dari jawaban di sini, angka itu terlalu tinggi. Komentar Rowan Blush tentang bagaimana setiap poin barun+1
berpotensi menghilangkan6*n
poin dengan pilihan optimal sepertinya ide yang bagus. Sayangnya, setelah memeriksa formulaa(1) = 1; a(n+1) = a(n) + 6*n + 1
, di manaa(n)
jumlah poin dihapus setelah menambahkann
poin ke set kami, ide ini mungkin tidak paling cocok. Memeriksa kapana(n)
lebih besar dariN**2
,a(200)
lebih besar dari yang619**2
tampaknya menjanjikan, tetapia(n)
lebih besar dari10**2
itua(7)
dan kami telah membuktikan bahwa 9 adalah batas atas aktual untukN=10
. Saya akan membuat Anda diposting karena saya mencoba untuk melihat batas atas yang lebih baik, tetapi ada saran dipersilahkan.Ke jawaban saya. Pertama, set 119 piksel saya.
Kedua, kode saya, yang secara acak mengambil titik awal dari oktan 619x619 persegi (karena titik awal dinyatakan sama di bawah rotasi dan refleksi) dan kemudian setiap titik lainnya dari sisa kotak.
sumber