Strategi optimal untuk permainan abstrak

12

Saya telah diberi masalah berikut dalam sebuah wawancara (yang telah saya gagal pecahkan, tidak mencoba menipu jalan saya sebelumnya): Permainan dimulai dengan bilangan bulat positif . (Mis. A 0 = 1234. ) Angka ini dikonversi ke representasi biner, dan N adalah jumlah bit yang ditetapkan ke 1 . (Mis. A 0 = b 100 1101 0010 , N = 5. )A0A0=1234N1A0=b100 1101 0010N=5.

Pemain 1 memilih nomor lebih kecil dari A 0 . B 0 harus hanya memiliki satu bit yang diatur ke 1. (Misalnya B 0 = b 10 0000 0000 = 512. ) Misalkan A 1 = A 0 - B 0 . (Mis. A 1 = 1234 - 512 = 722 = b 10 1101 0010. ) Suatu perpindahan valid jika B 0B0A0B0B0=b10 0000 0000=512A1=A0B0A1=1234512=722=b1011010010B0memenuhi kendala sebelumnya, dan jika jumlah bit di dalam masih sama dengan N .A1

Pemain 2 melanjutkan dari dengan memilih B 1 yang valid , kemudian pemain 1 melanjutkan dari A 2 , dan seterusnya. Seorang pemain kalah jika mereka tidak memiliki gerakan sah yang tersisa.A1B1A2

Dengan asumsi kedua pemain bermain secara optimal, tentukan pemain yang menang menggunakan metode yang cukup efisien. (Dalam definisi masalah saya, kendala pada hal ini adalah bahwa program harus dapat memberikan solusi untuk beberapa juta angka input yang masuk ke dalam bilangan bulat 32-bit yang sudah ditandatangani). Artinya, solusi tidak perlu sepenuhnya analitis.


Minat pribadi saya di sini adalah mencari tahu apakah harapan saya untuk menemukan dan menerapkan solusi yang benar tanpa umpan balik tentang kebenaran dalam 120 menit yang saya berikan adalah masuk akal; atau apakah ini salah satu dari pertanyaan "mari kita lihat apakah mereka pernah melihat puzzle ini sebelumnya".

Saya gagal karena saya memilih untuk menerapkan apa yang tampak seperti strategi yang masuk akal, yang memberi saya hasil yang benar untuk beberapa kasus uji yang telah saya berikan di muka, membuang-buang terlalu banyak waktu untuk menjalankan ini dengan cepat, dan akhirnya menyerahkan salah output penuh saat waktu saya habis.

Dalam retrospeksi saya harus menerapkan pencarian parsial dan hafal solusi parsial untuk angka awal yang kecil, tetapi melihat ke belakang selalu 20/20. Namun saya ingin tahu apakah ada pendekatan umum yang berbeda yang menghindari saya sebagai flunkee.

millimoose
sumber
Dari uraian saya tidak memahami bahwa gerakan yang dipilih harus memiliki set bit tunggal ke 1 (saya pikir itu hanya bagian dari contoh).
jjmontes
@ jjmontes - Dinyatakan sebagai aturan pertama untuk memilih nomor B - semua contoh diindikasikan demikian, semua yang ada di luar tanda kurung bersifat umum. Apakah Anda punya saran bagaimana bisa lebih jelas?
millimoose
1
B0A0
@Veedrac - Sobat, seandainya saya tahu itu, semua usaha saya untuk membuat bitcount berjalan cukup cepat tidak akan sia-sia. Sebuah jawaban yang menjelaskan mengapa ini bekerja akan sangat baik.
millimoose
@millimoose Bitcount ada di perangkat keras untuk sebagian besar CPU modern!
Veedrac

Jawaban:

21

011001

1001

Jadi satu-satunya faktor penentu dalam permainan adalah berapa banyak swap yang diperlukan untuk sampai ke keadaan di mana semua yang ada di sebelah kanan, dan tidak ada strategi menang atau kalah. Paritas dari jumlah swap yang diperlukan adalah satu-satunya faktor penentu.

1

i1101kki

i = 0
k = 0
total = 0
while n > 0:
    if n & 1:
       total += k - i
       i += 1
    n >>= 1
    k += 1

totalO(logn)

orlp
sumber
Sepertinya ini benar, saya telah menemukan sedikit demi sedikit pendekatan ini setelah hand-in. Kira saya sudah selesai dengan melompat pistol pada memulai coding dan terjebak dalam pengejaran angsa liar yang dihasilkan.
millimoose
Memikirkan hal ini, fakta strategi itu tidak masalah berarti saya memiliki bug yang agak tidak jelas dalam implementasi saya, atau seharusnya menghasilkan hasil yang sama seperti implementasi lainnya yang memainkan permainan dengan benar ...
millimoose
5

Salah satu cara untuk memecahkan masalah tersebut adalah sebagai berikut:

  • Temukan solusi untuk beberapa nilai sederhana menggunakan pendekatan "memoized brute-force" yang Anda sarankan.

  • Tebak jawabannya (posisi mana yang menang dan yang kalah).

  • Cobalah buktikan jawaban Anda. Jika Anda berhasil, bagus. Jika tidak, coba temukan contoh tandingan, dan gunakan untuk menebak jawaban lain. Di sini bisa bermanfaat untuk menyelesaikan beberapa kasus lagi.

Sangat sulit untuk mengatakan berapa banyak waktu yang diperlukan. Namun, dalam wawancara Anda tidak perlu menemukan solusinya. Sebaliknya, pewawancara ingin tahu bagaimana Anda mendekati memecahkan masalah, dan kemajuan apa yang berhasil Anda buat.

Yuval Filmus
sumber
Ya tidak, mereka menolak saya karena hasil saya salah dan saya kehabisan waktu.
millimoose
Pendekatan brute force memoized akan benar, karena tidak memerlukan jalan pintas mengenai strategi. Namun, itu juga - saya pikir - menjadi lambat, dan memoisasi mungkin terlalu banyak bekerja di atas untuk mungkin tidak banyak membantu tanpa menggunakan jumlah memori konyol. Atau mungkin tidak, saya akan coba nanti hanya untuk menghapus ini dari sistem saya.
millimoose
5

Catat dari jawaban orlp @ bahwa kita menginginkan paritas jumlah perpindahan dari posisi awal ke posisi akhir. Mari kita beri catatan:

       9876543210
       9 76 4  1    (positions at start)
start: 1011010010
end:   0000011111
            43210   (positions at end)

Jadi kami mau

  ((1 - 0) + (4 - 1) + (6 - 2) + (7 - 3) + (9 - 4)) & 1
= ((1 + 4 + 6 + 7 + 9) - (0 + 1 + 2 + 3 + 4)) & 1
= ((1 + 0 + 0 + 1 + 1) - (0 + 1 + 0 + 1 + 0)) & 1

Bagian pertama adalah paritas dari jumlah bit dalam posisi ganjil. Anda bisa menutupi itu dengan mengambil bilangan bulat unsigned maksimum, membaginya dengan 0b11 dan meniadakan.

= (bitcount(x & ~(UINT_MAX / 0b11)) ^ (0 + 1 + 0 + 1 + 0)) & 1

Bagian kedua adalah paritas dari setengah jumlah bit dalam x.

= (bitcount(x & ~(UINT_MAX / 0b11)) ^ (bitcount(x) >> 1)) & 1

bitcountdapat menggunakan popcntinstruksi perangkat keras , atau dapat diimplementasikan secara manual dengan memanfaatkan hanya bit terakhir atau kedua-ke-terakhir yang diperlukan, dengan pengurangan cepat seperti ini .

Veedrac
sumber