Baru-baru ini di Puzzling.SE yang baru dirilis , ada masalah tentang mata-mata melemparkan batu ke sungai yang sebenarnya cukup menantang:
Dua mata-mata harus saling melewati dua nomor rahasia (satu angka per mata-mata), tanpa disadari oleh musuh mereka. Mereka telah menyetujui metode untuk melakukan ini hanya dengan menggunakan 26 batu yang tidak bisa dibedakan sebelumnya.
Mereka bertemu di sungai, di mana ada tumpukan 26 batu. Dimulai dengan mata-mata pertama, mereka bergantian melemparkan sekelompok batu ke sungai: mata-mata pertama melempar sejumlah batu, lalu yang kedua, lalu yang pertama lagi ...
Setiap mata-mata harus melemparkan setidaknya satu batu pada gilirannya, sampai semua batu hilang.
Mereka mengamati semua lemparan dan berbeda ketika tidak ada lagi batu. Mereka diam sepanjang waktu dan tidak ada informasi yang dipertukarkan kecuali sejumlah batu yang dilemparkan pada setiap belokan.
Bagaimana mereka bisa menukar angka dengan sukses jika angka bisa dari 1 ke M?
Tugas Anda adalah membangun sepasang program, spy1
dan spy2
, yang dapat menyelesaikan masalah ini dengan setinggi mungkin M
.
Setiap program Anda akan mengambil nomor dari yang 1
Anda pilih M
sebagai masukan. Kemudian, spy1
akan menampilkan angka yang mewakili jumlah batu yang dilemparkannya ke sungai, yang akan menjadi input spy2
yang juga akan menampilkan angka yang akan dimasukkan spy1
, dan seterusnya hingga angka-angka yang dihasilkan bertambah 26
. Pada akhir lemparan, setiap program akan menampilkan nomor yang diyakini oleh program lain, yang harus cocok dengan angka yang sebenarnya diinput ke program lain.
Program Anda harus bekerja untuk semua pasangan angka yang mungkin dipesan di (i, j)
mana keduanya i
dan j
dapat bervariasi dari 1
hingga M
.
Program yang bekerja untuk yang terbesar M
akan menjadi pemenang, dengan jawaban pertama yang diposting melanggar dasi. Selain itu, saya akan memberikan hadiah +100 reputasi untuk solusi pertama yang terbukti berhasil M >= 2286
, dan +300 untuk solusi pertama yang terbukti berhasil M >= 2535
.
Jawaban:
C #, M = 2535
Ini mengimplementasikan * sistem yang saya uraikan secara matematis pada utas yang memicu kontes ini. Saya mengklaim bonus 300 rep. Tes mandiri program jika Anda menjalankannya tanpa argumen baris perintah atau dengan
--test
sebagai argumen baris perintah; untuk mata-mata 1, jalankan dengan--spy1
, dan untuk mata-mata 2 dengan--spy2
. Dalam setiap kasus dibutuhkan nomor yang saya harus berkomunikasi dari stdin, dan kemudian melakukan lemparan melalui stdin dan stdout.* Sebenarnya, saya telah menemukan optimasi yang membuat perbedaan besar (dari beberapa menit untuk menghasilkan pohon keputusan, hingga kurang dari satu detik); pohon yang dihasilkannya pada dasarnya sama, tetapi saya masih bekerja pada buktinya. Jika Anda menginginkan implementasi langsung dari sistem yang saya jelaskan di tempat lain, lihat revisi 2 , meskipun Anda mungkin ingin membuat cadangan dari logging tambahan
Main
dan lebih baik antar-thread dariTestSpyIO
.Jika Anda ingin test case yang selesai dalam waktu kurang dari satu menit, ubah
N
ke16
danM
ke87
.Instruksi untuk pengguna Linux
Anda harus
mono-csc
mengkompilasi (pada sistem berbasis Debian, ada dalammono-devel
paket) danmono
menjalankan (mono-runtime
paket). Maka mantra adalahdll.
sumber
yum install mono-core
(sebagai root). 2.dmcs Puzzle625.cs
3.mono Puzzle625.exe --test
Program Penguji Python
Saya pikir akan bermanfaat untuk memiliki program pengujian yang dapat memverifikasi bahwa implementasi Anda berfungsi. Kedua skrip di bawah ini berfungsi dengan Python 2 atau Python 3.
Program penguji (
tester.py
):Protokol: Dua program mata-mata yang ditentukan pada command-line akan dieksekusi. Mereka diharapkan berinteraksi hanya melalui stdin / stdout. Setiap program akan menerima nomor yang ditugaskan sebagai input pertama. Di setiap belokan, mata-mata 1 menghasilkan jumlah batu yang akan dilempar, mata-mata 2 membaca angka dari stdin (mewakili lemparan mata-mata 1), dan kemudian mereka mengulangi (dengan posisi terbalik). Ketika salah satu mata-mata menentukan bahwa 26 batu telah dilempar, mereka berhenti dan mengeluarkan tebakan mereka untuk nomor mata-mata lainnya.
Sesi contoh dengan spy1 yang kompatibel (
>
menunjukkan input ke spy)Jika Anda memilih M yang sangat besar, dan waktu terlalu lama untuk menjalankan, Anda dapat beralih
test(
untuktestrand(
di baris terakhir untuk menjalankan tes acak. Dalam kasus terakhir, biarkan program berjalan setidaknya untuk beberapa ribu percobaan untuk membangun kepercayaan.Contoh program (
spy.py
), untuk M = 42:Contoh penggunaan:
sumber
Java, M = 2535
OKE, ini implementasi saya. Pada setiap langkah satu mata-mata bergerak. Setiap langkah yang mungkin mewakili berbagai kode. Mata-mata memilih langkah yang cocok dengan kode rahasianya. Saat mereka melempar lebih banyak batu, kisaran kode yang mungkin berkurang hingga, pada akhirnya, untuk kedua mata-mata, hanya satu kode yang tetap mungkin sesuai dengan gerakan yang mereka lakukan.
Untuk memulihkan kode rahasia, Anda dapat memutar ulang semua gerakan dan menghitung rentang kode yang sesuai. Pada akhirnya, hanya satu kode yang tersisa untuk setiap mata-mata, yaitu kode rahasia yang ingin ia kirimkan.
Sayangnya, algoritma ini mengandalkan tabel prekomputasi besar dengan ratusan ribu bilangan bulat. Metode ini tidak dapat diterapkan secara mental dengan lebih dari 8-10 batu.
File pertama mengimplementasikan algoritma Spy. Bagian statis precomputes
codeCount
tabel yang kemudian digunakan untuk menghitung setiap gerakan. Bagian kedua menerapkan 2 prosedur, satu untuk memilih berapa banyak batu untuk dilempar, yang lain untuk memutar ulang langkah untuk membantu merekonstruksi kode rahasia.File kedua menguji kelas Spy secara ekstensif. Metode ini
simulate
mensimulasikan proses. Menggunakan kelas Spy untuk menghasilkan urutan lemparan dari kode rahasia dan kemudian merekonstruksi kode dari urutan.Spy.java
ThrowingStones.java
Untuk referensi, array codeCount yang dikomputasi mengandung nilai-nilai berikut:
Ini terkait langsung dengan perangkat Peter Taylor Tk. Kita punya:
sumber
range
bidang mereka . Tapi saya sangat tertarik dengan metode Anda menghitung tabel. Apakah Anda memiliki bukti kebenaran? Dan apakah Anda tertarik berkolaborasi dalam makalah yang membahas masalah dan menghitung solusinya?ksh / zsh, M = 126
Dalam sistem sederhana ini, setiap mata-mata melempar angka biner ke mata-mata lainnya. Dalam setiap lemparan, batu pertama diabaikan, batu berikutnya masing-masing bit 0, dan batu terakhir adalah bit 1. Misalnya, untuk melempar 20, seorang mata-mata akan melempar 4 batu (abaikan, 0, 2, tambahkan 4), lalu lempar 3 batu (abaikan, 8, tambah 16), karena 4 + 16 = 20.
Himpunan angka tidak berdekatan. 0 hingga 126 ada, tetapi 127 keluar. (Jika kedua mata-mata memiliki 127, mereka membutuhkan 28 batu, tetapi mereka memiliki 26 batu.) Kemudian 128 hingga 158 berada, 159 keluar, 160 hingga 174 masuk, 175 keluar, 176 hingga 182 masuk, 183 keluar, 184 hingga 186 ada di dalam, 187 ada di luar, dan seterusnya.
Jalankan swap otomatis dengan
ksh spy.sh 125 126
, atau jalankan mata-mata individual denganksh spy.sh spy1 125
danksh spy.sh spy2 126
. Di sini,ksh
bisa ksh93, pdksh atau zsh.EDIT 14 Jun 2014: Perbaiki masalah dengan beberapa proses bersama di zsh. Mereka akan menganggur selamanya dan gagal keluar, sampai pengguna membunuh mereka.
sumber