Temukan gerakan nim optimal

8

Permainan

Nim adalah permainan strategi matematika, di mana 2 pemain bergiliran mengambil item dari tumpukan yang berbeda. Pada gilirannya, Anda harus mengambil setidaknya satu item, dan Anda dapat mengambil sebanyak yang Anda inginkan, asalkan Anda hanya mengambil dari satu tumpukan. Pemain yang menerima item terakhir menang! Ini adalah permainan yang diselesaikan. Sebelum saya masuk ke strategi, Anda dapat mencoba bermain online di sini .

Strategi

Strategi kemenangan dijelaskan dengan sangat jelas dan sederhana di sini di tautan ini . Saya akan menjelaskannya menggunakan istilah teknis yang lebih sedikit. Cara untuk memenangkan permainan ini, adalah untuk selalu mengambil item sebanyak mungkin sehingga jumlah biner-digital selalu 0. Pertimbangkan papan berikut:

         *
       * *
     * * *
   * * * *
 * * * * *
 1 2 3 4 5

Untuk menemukan jumlah biner-digital-board ini, Anda harus:

  1. Ubah nomor di setiap baris menjadi biner. Jadi kita punya 001, 010, 011, 100 dan 101.

  2. Tambahkan semua angka, dan abaikan semua barang bawaan.

     001
 010
 011
 100
+101
----
 001

    Anda juga dapat bitwise-xor setiap nomor, dan ini akan mencapai hasil yang sama.

Sekarang, jika jumlah dalam konfigurasi saat ini adalah 001, maka ini bukan (belum) papan pemenang. Tapi Anda bisa menjadikannya papan pemenang! Jika kami mengambil satu item dari kolom 1, 3 atau 5, jumlahnya akan menjadi 0. Ini adalah papan kemenangan, yang berarti bahwa, asalkan Anda tidak melakukan kesalahan, pemain berikutnya yang akan bergerak akan kalah. Jadi, Anda harus selalu mengakhiri giliran Anda dengan papan kemenangan. Katakanlah Anda mengambil satu item dari kolom 5. Sekarang papan terlihat seperti ini:

       * *
     * * *
   * * * *
 * * * * *
 1 2 3 4 5

Selama Anda tidak mengacau, Anda dijamin menang. Tidak ada yang bisa dilakukan lawan Anda untuk menghentikan Anda. Katakanlah dia mengambil semua item dari kolom 5.

       *
     * *
   * * *
 * * * *
 1 2 3 4 5

Kemana kamu akan pergi selanjutnya? Jangan gulir ke bawah, dan coba cari tahu sendiri.

Saat ini, jumlahnya adalah 100. Langkah terbaik (dan hanya langkah menang) adalah mengambil semuanya dari kolom 4. Itu akan meninggalkan papan seperti ini:

     * 
   * * 
 * * * 
 1 2 3 4 5

dan jumlahnya seperti ini

 001
 010
+011
----
 000

itu berarti Anda berada di papan pemenang! Yay!

Tantangan

Anda harus menulis program atau fungsi yang, diberikan papan nim, akan mengembalikan langkah menang, atau nilai falsey jika tidak ada langkah menang.

Masukan Anda:

  • Akan menjadi format daftar asli bahasa Anda, di mana setiap item dalam daftar sesuai dengan jumlah item dalam kolom yang diberikan. Misalnya, input {4, 2, 1, 0, 3} sesuai dengan papan nim berikut:

    *
*           *
*  *        *
*  *  *     *
1, 2, 3, 4, 5

  • (opsional) Jumlah baris. (Untuk bahasa seperti C / C ++ yang tidak diketahui dari daftar itu sendiri.)

Output Anda:

  • Dapat pergi ke STDOUT atau dikembalikan dari fungsi

  • Harus terdiri dari dua angka, 1) kolom tempat kita menghapus (Ingat bahwa kolom diindeks 0) dan 2) jumlah item yang harus dihapus dari baris itu. Ini bisa berupa array 2-item, string dari dua angka, dll. Ingatlah bahwa jawabannya mungkin lebih dari 2 digit, jadi mengembalikan string "111" tidak valid karena tidak jelas apakah ini berarti "Hapus satu item dari kolom sebelas" atau "Hapus sebelas item dari kolom satu". "1,11" atau "11,1" akan diterima.

  • Jika tidak ada jawaban, kembalikan atau cetak nilai yang salah. Jika bahasa Anda hanya dapat mengembalikan satu jenis variabel (sekali lagi, seperti C / C ++), angka negatif untuk kolom, atau 0 atau kurang untuk nomor yang akan dihapus keduanya akan menjadi nilai falsey yang dapat diterima.

  • Jika nomor kolom atau nomor yang harus dihapus terlalu besar, ini dilihat sebagai output yang tidak valid.

Input / Output Sampel

[1, 2, 3, 4, 5]---> [0, 1]atau [4, 1]atau[2, 1]

[1, 3, 5, 6]---> [0, 1]atau [1, 1]atau[2, 1]

[1, 2, 0, 0, 5] ---> [4, 2]

[1, 2, 3] ---> ERROR

Jika Anda memilih untuk melakukan fungsi alih-alih program penuh, maka Anda harus menulis program lengkap untuk menunjukkan fungsi tersebut dalam tindakan. Ini tidak akan dihitung untuk skor penuh Anda. Selain itu, program diharapkan berjalan dalam jumlah waktu yang wajar. Saya tidak berencana untuk memasukkan input yang terlalu besar, jadi selama program Anda tidak melakukan pencarian kasar di seluruh pohon permainan, Anda harus baik-baik saja.

Seperti biasa, ini adalah kode-golf, jadi lubang loop standar berlaku , dan jawaban dihitung dalam byte.

Papan peringkat

Berikut ini adalah Stack Snippet untuk menghasilkan leaderboard biasa dan gambaran umum pemenang berdasarkan bahasa.

Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:

# Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Contohnya:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Tampilkan cuplikan kode

code-golf game James
sumber
Bisakah kita berasumsi, bahwa daftar input mengandung setidaknya satu angka positif?
Jakube
@ Yakub ya, Anda bisa.
James
Terkait -ish?
FryAmTheEggman

Jawaban:

3

Pyth, 33 22 21 20 19 byte

eS.e*<JxxFQbb,k-bJQ

Anda dapat mencobanya di kompiler online di sini.

Terima kasih kepada Jakube karena menghapus 12 byte dan Maltysen karena menghapus byte tambahan!

Ini mencetak langkah kemenangan dari posisi saat ini. Jika tidak ada gerakan menang, itu tidak mencetak apa pun.

Saya menggunakan algoritma di wikipedia . Berikut ini rinciannya:

  .e              Q    While enumerating every element in the input:
      J                    Assign variable J to:
        xFQ                 Every element of the input bitwise xor'ed together,
       x   b                bitwise xor'ed with the current element of the input
             ,             Create a tuple containing:
              k             The index of the current element, and
               -bJ          the difference between the current element and J
    *<J     b              Put that tuple into a list if J < b, otherwise put an empty tuple
 S                     Sort the list
e                      Print the last element of the list
Mike Bufardeci
sumber
3

Pyth, 23 byte

eSs.em*,kd!xxxFQb-bdSbQ

Cobalah online: Peragaan

Ini beralih pada semua kemungkinan gerakan dan bahkan penyortiran. Oleh karena itu ia memiliki kompleksitas waktu O(N*log(N))dan kompleksitas memori O(N), di mana Njumlah dari daftar input atau jumlah item.

Karena kompleksitas waktu yang buruk, ini mungkin bukan jawaban yang valid. Meskipun itu memecahkan semua game, bahwa Anda dapat bermain dalam kehidupan nyata dengan benda nyata, secara instan.

Penjelasan:

                          implicit: Q = input list
   .e                 Q   map each (index k, item b) of Q to:
     m              Sb      map each d of [1, 2, ..., b] to:
       ,kd                      the pair (k, d)
      *                       multiplied by
             xFQ                xor of all numbers in Q
            x   b               xor with b
           x     -bd            xor with b-d
          !                     not (1 if xor==0 else 0)

So the input [1, 2, 0, 0, 5] gives [[[]], [[], []], [], [], [[], [4, 2], [], [], []]]

  s                       add all lists to one big list
 S                        sort

Now it looks like this: [[], [], [], [], [], [], [], [4, 2]]

e                         pick the last element and print
Jakube
sumber
3

CJam, 21 20 byte

Menyimpan byte dibandingkan dengan versi asli, dan penanganan kesalahan juga berfungsi sekarang:

l~__:^f^.-_:g1#_@=S\

Cobalah online

Input adalah array CJam, misalnya:

[1 2 3 4 5]

Jika tidak ada solusi yang ditemukan, ia mencetak -1 0, yang memenuhi pemahaman saya tentang persyaratan output.

Penjelasan:

l~      Get input.
__      Make two copies for following operations.
:^      Reduce with xor operator, producing xor of all columns.
f^      xor all input values with the result. For each column, this calculates
        the value that the column would have to change to make the overall
        xor zero. Consider this the "target values".
.-      Subtract the target values from the input values.
_:g     Per element signum of difference between target value and input value.
1#      Find index with value 1, which is the first positive value.
_@=     Get the value at the index.
S\      Put a space between index and value.
Reto Koradi
sumber
1

Ruby, 95

->(a){r=[false,c=0]
a.each{|e|c^=e}
a.each_index{|i|(n=a[i]-(c^a[i]))>0&&n>r[1]?(r=[i,n]):0}
r}

Saya menulis 2 fungsi anonim yang terpisah. Yang pertama, yang ditetapkan fdalam program di bawah ini, mencetak semua solusi, dan yang kedua g(sesuai dengan skor di atas, karena keduanya lebih pendek dan lebih sesuai dengan spesifikasi) hanya mengembalikan solusi yang membutuhkan penghapusan jumlah terbesar.

dalam kedua kasus, jumlah digit dijumlahkan dalam c. Kemudian array di-looped dan ekspresi n=a[i]-(c^a[i])digunakan untuk menghitung jumlah counter yang akan dihapus (jelas ini hanya dapat dilakukan jika melebihi nol).

dalam f, semua solusi yang mungkin dicetak (jika cditemukan 0, errordicetak tanpa perulangan.) Saya terkejut melihat bahwa tumpukan yang berbeda dapat membutuhkan jumlah penghitung yang sangat berbeda untuk dihilangkan.

dalam garray keluaran rhanya diperbarui jika jumlah counter yang akan dihapus melebihi angka sebelumnya. array r = [pile index, number to be removed]dikembalikan. Jika tidak ada solusi, jumlah penghitung yang akan dihapus selalu nol, rtetap tidak berubah, dan nilai awal r = [false,0]dikembalikan.

Penghematan kecil dimungkinkan jika falsedapat diubah ke misalnya "!"dan jika ada solusi yang valid daripada yang terbesar dapat dikembalikan (dengan menghapus &&n>r[1].)

Diformat dalam program uji

f=->(a){
  c=0
  a.each{|e|c^=e}
  c<1?(p "error"):(a.each_index{
     |i|(n=a[i]-(c^a[i]))>0?(p"#{i},#{n}"):0
   })
}

g=->(a){
  r=[false,c=0]
  a.each{|e|c^=e}
  a.each_index{
     |i|(n=a[i]-(c^a[i]))>0&&n>r[1]?(r=[i,n]):0
  }
  r
}

#Change the following two lines according to the number of values youj want to use for testing.
t=[rand(15),rand(15),rand(15),rand(15)] #Generate some random numbers for testing.
t=[gets.to_i,gets.to_i,gets.to_i]       #User input. Delete this line if you want to test with random numbers.
print t,"\n"

f.call(t)
puts g.call(t)
Level River St
sumber
Sebenarnya, karena r[1]selalu paling tidak nol, saya pikir >0&&n>r[1]bisa disingkat>r[1]
Level River St
0

Mathematica, 73 byte

{f=BitXor;p=Position[#,x_/;BitAnd[x,a=f@@#]==a][[1,1]],(n=#[[p]])-n~f~a}&
pengguna202729
sumber
1
Apa. Mathematica tidak memiliki builtin untuk ini?
Draco18s tidak lagi mempercayai SE
0

JavaScript (ES6), 54 byte

Mengembalikan pasangan [column, number]atau salah

a=>a.some((n,i)=>r=(n-=n^eval(a.join`^`))>0&&[i,n])&&r

Cobalah online!

Berkomentar

a =>                        // a[] = input array
  a.some((n, i) =>          // for each value n at position i in a[]:
    r = (                   //   save the result of the iteration in r
      n -=                  //   subtract from n:
        n ^ eval(a.join`^`) //     n XOR (all values in a[] XOR'ed together)
    ) > 0                   //   if the above value is positive:
    && [i, n]               //     yield the solution [i, n] and exit the some() loop
                            //   (otherwise: yield false and go on with the next value)
  ) && r                    // end of some(); return r
Arnauld
sumber