Tujuan Anda adalah menulis pemain yang sempurna untuk permainan Wythoff's Nim .
Aturan Wythoff's Nim
Wythoff's Nim adalah permainan dua pemain deterministik yang dimainkan dengan dua tumpukan counter identik. Pemain bergantian bergantian, di mana mereka melakukan salah satunya:
- Hapus satu atau lebih penghitung dari tumpukan pertama
- Hapus satu atau lebih penghitung dari tumpukan kedua
- Hapus jumlah penghitung yang sama (satu atau lebih), dari tumpukan pertama dan tumpukan kedua.
Tentu saja, tumpukan tidak bisa menjadi negatif, tetapi mereka bisa ke 0. Pemain mana saja yang menghapus counter terakhir secara keseluruhan memenangkan permainan.
Untuk yang lebih berpikiran geometris, berikut ini adalah rumusan setara game yang dapat Anda mainkan di applet ini . Seorang ratu tunggal mulai di atas papan catur berukuran seperempat tak terbatas yang sudutnya ada di kiri bawah. Pemain bergantian memindahkan sang ratu, yang bergerak seperti ratu catur tetapi terbatas pada tiga arah:
- Turun
- Kiri
- Diagonal ke bawah dan kiri
Siapa pun yang memindahkan ratu ke sudut akan menang.
Mengaitkan koordinat ratu (dengan sudut (0,0)
) dengan ukuran tumpukan masing-masing, mudah untuk melihat kedua permainan itu sama.
Bermain sempurna
(Anda dapat melewati ini jika terbiasa dengan gagasan bermain sempurna dan gerakan menang.)
Karena Wythoff's Nim adalah permainan yang terbatas dan deterministik, ia memiliki gagasan permainan yang sempurna . Seorang pemain yang sempurna adalah strategi yang akan selalu menang dari posisi yang dimenangkan secara teoritis, artinya posisi di mana ada strategi yang menjamin kemenangan.
Untuk menjadi strategi kemenangan, cukuplah bergerak untuk selalu pindah ke posisi kemenangan teoretis untuk pemain yang baru saja pindah, dan dengan demikian pemain tidak akan maju berikutnya. Posisi pemenang pertama (juga disebut posisi dingin ) adalah (0,0), (1,2), (2,1), (3,5), (5,3)
. Lihat artikel Wikipedia untuk penjelasan tentang algoritma untuk menemukan strategi kemenangan untuk Wythoff's Nim, serta formula untuk menghasilkan posisi menang.
Persyaratan program
Menulis suatu program atau fungsi mengambil posisi sebagai input dan menghasilkan langkah kemenangan dalam bentuk posisi setelah langkah itu. Bytes paling sedikit menang.
Jika tidak ada langkah yang menang, yaitu, posisi itu adalah kerugian teoritis, program Anda harus menunjukkan begitu dan kehilangan.
Program Anda harus berjalan dalam jumlah waktu yang wajar. Jadi, pencarian pohon game rekursif eksponensial tidak akan cukup. Jika Anda ingin melakukan precompute dan melakukan hard-code sebuah strategi, itu tidak masalah.
Memasukkan
Sepasang (i,j)
angka non-negatif yang mewakili ukuran tumpukan, masing-masing paling banyak 99
. Ini dapat berupa dua angka, tupel, daftar, atau wadah apa pun yang Anda inginkan.
Keluaran
Cetak atau keluarkan posisi setelah Anda bergerak, sekali lagi sebagai dua angka atau wadahnya. Ini harus menjadi langkah hukum ke posisi yang menang. Jika ada beberapa gerakan seperti itu, ada yang baik-baik saja, tetapi hanya satu.
Jika tidak ada langkah kemenangan, Anda harus menunjukkan ini di output. Setiap output seperti False
,, None
0, atau (-1,-1)
akan dilakukan, selama itu bukan posisi hukum, dan sama untuk setiap input yang hilang.
Contoh berjalan
f(5,0) = (0,0)
f(2,2) = (1,2) # Or (2,1) or (0,0)
f(1,2) = False
f(13,9) = (13,8) # Or (10,6)
f(10,6) = False
f(5,10) = (5,3)
f(25,30) = (8,13)
sumber
Jawaban:
Haskell,
167165 karakterAlgoritma ini tidak efisien, tetapi masih berjalan dalam hitungan detik (meskipun tidak di konsol interaktif) untuk input <100.
Penjelasan:
Daftar posisi dingin yang diberikan satu set posisi dingin sebelumnya adalah satu posisi dingin diikuti oleh daftar posisi dingin yang diberikan posisi ini dan yang sebelumnya (Ketidakefisienan: posisi ini dihasilkan dua kali)
Satu posisi dingin adalah pasangan pertama sehingga tidak ada posisi dingin yang dapat dicapai dari pasangan itu (Ketidakefisienan: kita harus mencari dari pasangan sebelumnya sebagai gantinya)
Posisi yang dapat dijangkau dari suatu pasangan adalah posisi sedemikian sehingga elemen pertama cocok, elemen kedua cocok, perbedaan selisih, atau tumpukan lebih kecil sebelum dilepas adalah tumpukan lebih besar setelah dilepas.
(metode utama) Jika tumpukan berada di urutan yang salah, tukar mereka. Lain, jika posisi dingin pertama yang dapat dicapai dari suatu posisi adalah posisi itu sendiri, menunjukkan kegagalan (idealnya, seseorang akan kembali
Maybe (Int,Int)
sebagai gantinya). Jika tidak, kembalikan posisi dingin itu (Ketidakefisienan: pasangan ini dilihat dua kali. Lebih buruk lagi, daftar posisi dingin dihasilkan dua kali)sumber
x@
x@(a,b)?p=...
GolfScript (
6357 byte)Mengharapkan input dari stdin dalam formulir
[a b]
, dan meninggalkan output pada stdout dalam bentuk itu atau0
jika itu posisi yang hilang. Demo onlineGambaran
menghitung daftar posisi dingin (termasuk versi membalik
[b a]
untuk setiap posisi dingin[a b]
) menggunakan properti urutan Beatty .Kemudian
?
mencari posisi dingin pertama memuaskan blok yang dibuat olehyang pada dasarnya cek bahwa posisi dicapai dari posisi masukan dengan menghitung perbedaan vektor dan kemudian memverifikasi bahwa itu baik
[0 x]
,[x 0]
atau[x x]
untuk beberapax > 0
. IMO tes yang adalah pintar bit:0|$
Pasukan setiap array dalam salah satu format ke dalam formulir[0 x]
sementara pemetaan[0 0]
untuk[0]
,[a b]
di mana tidaka
jugab
adalah0
untuk array tiga elemen, dan[-x 0]
atau[-x -x]
untuk[-x 0]
. Kemudian(!*,1=
periksa yang kita miliki[0 x]
.Akhirnya
0]0=`
apakah kasus mundur dan format untuk output.sumber
Pyth 57
58 61 62Cobalah online.
Cukup mirip dengan jawaban lain, tetapi halaman wikipedia itu tidak memberikan banyak hal lain untuk dilanjutkan;) Angka ajaib
39
adalah jumlah posisi dingin dengan nilai <99
.Menentukan fungsi
g
yang dapat Anda panggilg 30 25
. Pengembalian[]
untuk kegagalan,[(13,8)]
pada kesuksesan.Penjelasan
sumber
s
digunakan untuk menyimpan beberapa karakter/____1
.rZ39
dapat diganti denganU39
, menggunakan rentang unary. Demikian juga, Anda dapat menggantinyar99)
denganU99
.U
. Saya benar-benar harus memperbarui penjelasan: P@
melakukan persimpangan set jika argumen kedua adalah daftar sekarang. Ini agak canggung ditinggalkan sejaka
diubah: PJavascript ES6 - 280 byte
Diperkecil
Diperluas
Algoritma bagus dan cepat. Berjalan di O (n), tetapi akan berjalan dalam waktu yang konstan jika tidak untuk loop byte-saving. Loop diimplementasikan sebagai incrementer rekursif, karenanya skrip pada akhirnya akan gagal dengan kesalahan rekursi untuk n dalam ratusan atau ribuan. Menggunakan properti urutan Beatty yang sama dengan yang disebutkan Mr. Taylor, tetapi alih-alih menghitung urutannya, ia hanya melangkah ke istilah yang benar.
Berjalan dengan baik pada semua input tes dan banyak lusinan selain itu saya diuji.
Fungsi untuk memanggil adalah
f
. Ini mengembalikan array pada kesuksesan dan0
menyerah.sumber
Perl 5 - 109 (dengan 2 bendera)
Pemakaian:
Cukup hitung solusi untuk setiap input yang mungkin, lalu lakukan pencarian tunggal.
sumber