Bagaimana saya bisa menilai tantangan dengan ukuran masalah variabel?

21

Ada dukungan yang cukup kuat pada meta untuk pertanyaan-pertanyaan penulisan tantangan yang menjadi topik utama, asalkan pertanyaan-pertanyaan ini spesifik dan dapat dijawab. Namun, kami belum memiliki pertanyaan seperti itu, jadi saya pikir saya akan menguji air. Pertanyaan ini mungkin memasuki wilayah subyektif yang baik, wilayah subyektif yang buruk , tetapi saya pikir itulah kemungkinan pertanyaan penulisan tantangan. Untuk memastikan bahwa mereka masih menghasilkan konten berkualitas tinggi, jangan hanya memposting ide spekulatif liar di jawabannya. Jelaskan mengapa mereka menghindari masalah yang disebutkan di bawah ini, atau idealnya menunjuk tantangan yang ada yang telah berhasil menggunakan teknik yang disarankan di masa lalu.

Untuk tantangan pengoptimalan tertentu, parameter gratis dalam menetapkan tantangan adalah ukuran masalah yang akan dioptimalkan. Dengan "tantangan pengoptimalan", saya tidak bermaksud hal-hal seperti genre kami , di mana jawaban biasanya dituntut tepat / optimal, dan tantangan diberi skor baik pada ukuran masalah tetap atau pada ukuran masalah terbesar yang dapat ditangani dalam jumlah waktu yang tetap. Maksud saya secara khusus tantangan di mana solusi suboptimal untuk masalah yang mendasarinya diizinkan dan bahkan mungkin, dan tujuannya adalah untuk melakukan sebaik mungkin.

Demi kepastian, pertimbangkan tantangan berang-berang yang sibuk , meskipun pada prinsipnya ini berlaku untuk jenis tantangan lain tanpa solusi optimal yang diketahui juga (Saya hanya menggunakan berang-berang yang sibuk di sini karena mereka memperburuk masalah yang disebutkan di bawah). Katakanlah, saya ingin membuat tantangan tentang menemukan berang-berang Brainfuck tersibuk. Parameter gratis dalam masalah berang-berang yang sibuk adalah ukuran kode. Saya tidak dapat mengatur tantangan tanpa membuat referensi ke ukuran kode dalam beberapa cara. Di satu sisi, setiap nilai parameter ukuran masalah Nmemberikan tantangan yang terpisah (semakin sulit). Pertanyaan utama saya adalah bagaimana saya bisa membuat tantangan seperti itu berhasil tanpa mengalami masalah keseimbangan.

Solusi yang jelas adalah untuk memperbaiki N: "Temukan program Brainfuck penghentian dengan Nbyte kode sumber yang mencetak karakter sebanyak mungkin / berjalan untuk kutu sebanyak mungkin." Ini menyebabkan masalah balancing besar: jika saya memilih ukuran terlalu kecil, seseorang mungkin cepat menemukan yangberang-berang tersibuk dan tantangannya sudah berakhir. Jika saya memilih ukuran terlalu besar, solusi optimal akan mencetak sejumlah karakter astronomi sebelum mengakhiri, yang berarti bahwa itu mungkin sepele untuk menemukan program seperti itu dan tantangannya menjadi tugas / latihan dalam kesabaran - ini juga meninggalkan wilayah di mana berang-berang yang sibuk dapat ditemukan secara programatik, dan sebagai gantinya orang-orang perlu mulai membuktikan hasil mereka secara resmi yang mungkin dianggap tidak menyenangkan oleh banyak orang. Tentu saja, masalah ini lebih menonjol dalam tantangan berang-berang yang sibuk daripada jenis lainnya, karena pertumbuhan solusi yang optimal, tetapi itu berlaku untuk tantangan lain.

Pilihan selanjutnya adalah membiarkan Ntidak dibatasi dan menjadikannya bagian dari penilaian melalui beberapa fungsi. Bahkan untuk tantangan "normal" untuk menyeimbangkan skor gabungan dengan benar sangat sulit, tetapi dalam kasus berang-berang yang sibuk, pada dasarnya mustahil, karena solusi optimal tumbuh lebih cepat Ndaripada fungsi yang dapat dihitung. Itu berarti saya selalu bisa mengalahkan jawaban terbaik yang ada dengan pergi ke yang cukup besar di Nmana saya dapat dengan mudah menemukan program yang berjalan begitu lama sehingga saya bisa mendapatkan skor yang lebih baik tanpa banyak usaha.

Saya juga telah mempertimbangkan menetapkan fix Ndan memungkinkan orang untuk juga mengirimkan berang-berang untuk yang lebih besar Nyang akan digunakan sebagai pemutus dasi berturut-turut. Ini memiliki masalah yang sama, di mana seseorang dapat "kebetulan menemukan berang-berang yang sama-sama baik" untuk sebuah N, sehingga menciptakan dasi dan kemudian hanya mengirimkan apa saja untuk selanjutnya di Nmana menemukan skor besar lebih mudah (bahkan jika menemukan skor optimal semakin sulit). Dalam kasus ini, bagaimana Anda akan berurusan dengan banyak orang menggunakan solusi yang sama? Melarang itu juga akan aneh kalau-kalau itu optimal.

Mungkin orang bisa menemukan jalan tengah, dengan membuat tebakan yang berpendidikan dengan wajar Ndan kemudian meminta berang-berang yang sibuk untuk semua ukuran dalam (katakanlah) 5 byte N, sehingga ada beberapa kelonggaran di kedua arah (dan kemudian Anda kombinasikan skor ~ 10) menjadi satu per satu teknik atau lainnya). Ini tidak terasa cukup memuaskan juga karena tebakan awal saya Nmasih bisa jauh dari jangkauan yang membuat tantangan menarik.

TL; DR: dalam kasus di mana tantangannya adalah (memecahkan secara optimal dan) mengoptimalkan masalah yang ukurannya variabel, bagaimana cara saya memasukkan ukuran ke dalam tantangan? Idealnya saya ingin orang dapat bekerja dengan nilai Nyang dekat dengan ujung atas kisaran ukuran traktat. Tapi kalau-kalau ternyata solusi optimal adalah mungkin untuk itu N, akan lebih bagus jika solusi untuk sedikit lebih besar Nakan mulai membebani, sehingga tantangan bisa berlanjut dengan ukuran masalah yang lebih menarik.

Martin Ender
sumber
6
Saya suka ini sebagai model untuk pertanyaan penulisan tantangan karena tidak spesifik untuk PPCG. Itu bukan "Bagaimana kita harus melakukan ini?" tetapi "Apa cara yang baik untuk melakukan ini?". Saya bisa membayangkan tantangan seperti itu dijalankan di situs hobi pemrograman atau di kompetisi langsung.
xnor
Letakkan tldr di atas!
Majora320
1
@ Majora320 ... tapi kemudian ubah d ke w :-)
Luis Mendo

Jawaban:

3

Temukan N berikutnya

Tantangan akan mengindikasikan Nbahwa pengiriman harus dimulai.

Kemudian, orang akan mengirimkan jawaban saat ini N. Jika pengiriman yang diberikan terbukti optimal, maka Nditambah 1, dan prosesnya berulang.

Ada beberapa cara untuk menilai ini:

  1. Skor pengajuan terbaik saat ini N
  2. Berikan poin untuk pengajuan terbaik saat ini N, ditambah satu poin untuk setiap solusi optimal
  3. Sama seperti # 2, tetapi juga memberikan poin kepada orang yang membuktikan bahwa pengiriman yang diberikan adalah optimal.
Nathan Merrill
sumber
1

Berikan poin untuk solusi dalam N terbatas

Izinkan Nberada dalam batas tetap. Batas bawah harus mengecualikan jawaban yang jelas sepele, dan bahwa batas atas tidak boleh terlalu jauh dari batas bawah.

Lalu, beri 1 poin untuk setiap orang yang memiliki solusi terbaik untuk masing-masing Ndalam batas. Jika lebih tinggi Nberarti bahwa solusinya lebih sulit, maka berikan N poin kepada mereka. (atau rumus berdasarkan N).

Metode ini mirip dengan bagaimana AZsPC melakukannya, tetapi sebagian poin tidak diberikan.

Nathan Merrill
sumber