Latar Belakang

Jika Anda melakukan banyak kode golf, kemungkinan Anda mengetahui operasi XOR bitwise . Diberikan dua bilangan bulat, ini memberikan bilangan bulat lain dengan 1s dalam bit di mana dua input berbeda. Jadi, misalnya 1010 XOR 0011 = 1001,.

Ternyata sangat berguna dalam teori permainan, di mana itu lebih dikenal sebagai "nim sum". Jika Anda memiliki jumlah dari dua game (yaitu, Anda bergerak dalam satu game pada satu waktu), nilai dari posisi adalah jumlah nim dari nilai-nilai posisi dalam setiap game individu.

Tapi kita bisa mengambil langkah ini lebih jauh. Dengan penambahan nim dan definisi yang sesuai untuk perkalian nim , kita dapat membentuk bidang dari bilangan bulat non-negatif. Jadi tantangannya adalah multiplikasi golf nim.

Definisi

Perkalian
nim mematuhi aturan berikut: Produk nim dari Fermat 2-power n = (2 ^ (2 ^ k)) dengan jumlah yang lebih kecil adalah produk biasa.
Produk nim dari Fermat 2-power n dengan sendirinya adalah 3n / 2.
Perkalian nim mendistribusikan lebih dari penambahan nim.
Perkalian nim bersifat komutatif dan asosiatif (seperti halnya penambahan nim).
Identitas multiplikatif adalah 1 (dan identitas aditif adalah 0).

Setiap integer nonnegatif dapat ditulis sebagai nim sum dari kekuatan yang berbeda dari dua, dan kekuatan apa pun dari dua dapat ditulis sebagai produk dari nomor Fermat yang berbeda, jadi ini cukup untuk mendefinisikan perkalian nim untuk semua bilangan bulat nonnegatif.

Contoh

Itu semua sangat abstrak, jadi mari kita bekerja melalui contoh. Saya akan gunakan +untuk menunjukkan penambahan nim (XOR) dan *untuk perkalian nim.

6 * 13
= (4 + 2) * (8 + 4 + 1)
= (4 + 2) * ((4 * 2) + 4 + 1)
= (4 * 4 * 2) + (4 * 2 * 2) + (4 * 4) + (4 * 2) + (4 * 1) + (2 * 1)
= (6 * 2) + (4 * 3) + 6 + 8 + 4 + 2
= ((4 + 2) * 2) + 12 + 6 + 8 + 4 + 2
= (4 * 2) + (2 * 2) + 12 + 6 + 8 + 4 + 2
= 8 + 3 + 12 + 6 + 8 + 4 + 2
= 15

Kasus Uji Tambahan

4, 4 -> 6
4, 3 -> 12
4, 7 -> 10
2, 4 -> 8
2, 3 -> 1
1, 42 -> 42

Tantangan

Tulis program atau fungsi yang, mengingat dua bilangan bulat negatif dalam bentuk apa pun, menghitung produk nim mereka.

Ini adalah kode-golf , jadi pengiriman terpendek menang.

Nim , 120 byte

proc f(a,b:int):int=
 var s={0..a*b}
 for i in 0..<a*b:s=s-{f(i%%a,i/%a)xor f(a,i/%a)xor f(i%%a,b)}
 for i in s:return i

Cobalah online!

OK, ini mungkin gila, tetapi seseorang harus melakukan perkalian Nim di Nim ...

Ini adalah algoritma standar dari Wikipedia. Masalahnya adalah saya tidak tahu bahasa, jadi harus mempelajari dasar-dasarnya dengan cepat. Secara khusus, saya terkejut -=dan mintidak bekerja untuk set, dan cara terbaik saya berhasil menemukan untuk mengekstraksi minimum adalah dengan menggunakan iterator dan mengembalikan nilai pertama. Semoga para ahli Nim akan membantu saya untuk meningkatkan ini.

Python 2 , 85 byte

f=lambda x,y:min(set(range(x*y+1))-{f(i%x,i/x)^f(x,i/x)^f(i%x,y)for i in range(x*y)})

Cobalah online!

Lambat seperti sih. Menghitung mex ({α ′ β ⊕ α β ′ ⊕ α 'β ′: α ′ <α, β ′ <β}) secara rekursif.

Jelly , 16 byte

p’ß/;ß"^/ʋ€ṭ‘ḟ$Ṃ

Menggunakan rumus rekursif xy = mex ({ay ⊕ xb ⊕ ab: a <x, b <y}) untuk perkalian nimber .

Cobalah online!

Bagaimana itu bekerja

p’ß/;ß"^/ʋ€ṭ‘ḟ$Ṃ  Main link. Left argument: x. Right argument: y.

p                 Cartesian product; yield the array of all pairs [a, b] such that
                  0 < a ≤ x and 0 < b ≤ y.
 ’                Decrement, changing the conditions to 0 ≤ a < x and 0 ≤ b < y.
          ṭ       Tack; yield [y, x].
        ʋ€        Combine the four links to the left into a dyadic chain. Call it
                  with right argument [y, x] and each of the [a, b] as left one.
  ß/                  Reduce [a, b] by the main link, computing the product ab.
     ß"               Zip [a, b] with [y, x] using the main link, computing the
                      array of products [ay, xb].
    ;                 Concatenate, yielding [ab, ay, xb].
       ^/             Reduce by bitwise XOR, yielding ab ⊕ ay ⊕ xb.
                  All that's left is to compute the minimum excluded (mex) non-
                  negative integer.
             $    Combine the two links to the left into a monadic chain.
           ‘          Increment the XOR sums.
            ḟ         Filterfalse; remove all incremented sums that appear in the
                      original sums.
              Ṃ  Take the minimum if the resulting array is non-empty or yield 0.
                 If x = 0 or y = 0, the array of sums is empty and Ṃ yields 0.
                 If x > 0 and y > 0, since 0 is among the sums, this finds the
                 smallest non-sum n+1 such that n ≥ 0 is a sum.
                 In either case, Ṃ yields xy.

CGSuite ,52 39 22 byte

(a,b)->a.NimProduct(b)

Tidak menyadari bahwa ia memiliki "prosedur" bawaan ini, dan anonim.

Versi asli, 36 byte:

(a,b)->*a.ConwayProduct(*b).NimValue

Atau 25 byte jika input / output bisa berupa nimbers:

(a,b)->a.ConwayProduct(b)

Yah, aku berharap *a**b/ a*bbekerja, tetapi ternyata tidak.

Pyth , 21 byte

Mf-TsmmxxgkdgkHgGdGH0

Demonstrasi

Menggunakan formulasi elemen minimum yang dikecualikan dari perkalian nim, seperti yang diberikan di sini .

Dua peta bersarang digunakan untuk beralih pada semua nilai yang lebih kecil ( mm ... GH), kemudian hasilnya diratakan ( s). Bagian pintar datang dengan f-T ... 0, di mana kita beralih bilangan bulat ke atas dari 0 untuk menemukan yang pertama tidak terkandung dalam set yang disebutkan di atas. Dengan melakukannya dengan cara ini, kita tidak perlu menghitung iterasi batas atas, menghemat beberapa byte.

Pada akhirnya, fungsi gmenghitung produk nim.

JavaScript (ES6), 142 128 byte

f=(x,y,z=Math.log2,v=x&-x,t=z(x),u=z(y),s=t&u,r=s&-s)=>x<2|y<2?x*y:x>v?f(v,y)^f(x^v,y):y&y-1?f(y,x):r?f(f(x>>r,y>>r),3<<r-1):x*y

<div oninput=o.textContent=f(x.value,y.value)><input id=x><input id=y><pre id=o>

Langkah pertama adalah untuk membagi keduanya xdan ymenjadi XOR kekuatan 2, mengambil produk nim berpasangan mereka, dan kemudian XOR hasilnya (karena produk nim mendistribusikan lebih dari XOR). Setelah kami berulang pada kasus xdan ykedua kekuatan 2, kami mencatat bahwa kekuatan Fermat saling berlipat ganda menggunakan aritmatika biasa, sehingga kami dapat memfaktorkan xdan ymenjadi kekuatan Fermat. Jika xdan ytidak membagikan kekuatan Fermat, kami dapat membalik prosesnya dan mengembalikannya x * y. Namun jika mereka berbagi kekuatan Fermat, maka kami membagi keduanya xdan ydengan kekuatan itu, menghitung produk nim, kemudian mengambil produk nim dengan nim square dari kekuatan Fermat. Tidak Terkumpul:

function nimprod(x, y) {
    if (x < 2 || y < 2) return x * y;
    var v = x & -x;
    if (x > v) return nimprod(v, y) ^ nimprod(x ^ v, y); // nimprod distributes over ^
    if (y & (y - 1)) return nimprod(y, x); // x is a power of 2 but y is not
    var t = Math.log2(x);
    var u = Math.log2(y);
    var s = t & u;
    if (!s) return x * y; // x and y do not share a Fermat power
    var r = s & -s;
    return nimprod(nimprod(x >> r, y >> r), 3 << r - 1); // square the Fermat power
}

Bahasa Wolfram (Mathematica) , 81 byte

x_±y_:=Min@Complement[Range[0,x*y],##&@@Array[BitXor[x±#2,#±y,±##]&,{x,y},0]]

Cobalah online!

Menggunakan rumus:

$\alpha \beta = \operatorname{mex}(\{\,\alpha' \beta + \alpha \beta' + \alpha' \beta' : \alpha' < \alpha , \beta' < \beta \,\}).$