tło

Jeśli dużo grasz w golfa, prawdopodobnie znasz bitową operację XOR . Biorąc pod uwagę dwie liczby całkowite, daje kolejną liczbę całkowitą 1s w bitach, w których dwa wejścia różnią się. Na przykład 1010 XOR 0011 = 1001.

Okazuje się, że jest bardzo przydatny w teorii gier, gdzie jest lepiej znany jako „nim sum”. Jeśli masz sumę dwóch gier (to znaczy wykonujesz ruchy w jednej grze na raz), wartość pozycji jest nim sumą wartości pozycji w każdej grze.

Ale możemy pójść o krok dalej. Dzięki dodaniu nim i odpowiedniej definicji mnożenia nim możemy utworzyć pole z nieujemnych liczb całkowitych. Tak więc wyzwanie polega na pomnożeniu golfa nim.

Definicja

Mnożenie Nim podlega następującym zasadom:
iloczyn nim Fermata 2-power n = (2 ^ (2 ^ k)) z dowolną mniejszą liczbą jest produktem zwykłym.
Produkt nim Fermata 2-power n z samym sobą wynosi 3n / 2.
Mnożenie Nim rozkłada się na dodawanie NIM.
Mnożenie Nim jest przemienne i asocjacyjne (podobnie jak dodawanie NIM).
Tożsamość multiplikatywna wynosi 1 (a tożsamość addytywna to 0).

Dowolną nieujemną liczbę całkowitą można zapisać jako sumę nim dwóch odrębnych potęg dwóch, a każdą potęgę dwóch można zapisać jako iloczyn różnych liczb Fermata, więc to wystarczy, aby zdefiniować mnożenie nim dla wszystkich nieujemnych liczb całkowitych.

Przykład

To wszystko było dość abstrakcyjne, więc przeanalizujmy przykład. Użyję +do oznaczenia NIM Dodatkowo (XOR) i *za Nim mnożenia.

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

Dodatkowe przypadki testowe

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

Wyzwanie

Napisz program lub funkcję, która przy dwóch nieujemnych liczbach całkowitych w dowolnej dogodnej formie oblicza ich produkt nim.

To jest golf golfowy , więc wygrywa najkrótsze zgłoszenie.

Nim , 120 bajtów

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

Wypróbuj online!

OK, to może być szalone, ale ktoś musiał dokonać mnożenia Nima w Nim ...

Jest to standardowy algorytm z Wikipedii. Problem polega na tym, że nie znam języka, więc musiałem uczyć się podstaw w locie. W szczególności byłem zaskoczony -=i minnie działałem dla zestawów, a najlepszym sposobem, jaki udało mi się znaleźć do wyodrębnienia minimum, było użycie iteratora i zwrócenie pierwszej wartości. Mam nadzieję, że eksperci Nim pomogą mi to poprawić.

Python 2 , 85 bajtów

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)})

Wypróbuj online!

Powolny jak cholera. Oblicza mex ({α ′ β ⊕ α β ′ ⊕ α 'β ′: α ′ <α, β ′ <β}) rekurencyjnie.

Galaretka , 16 bajtów

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

Używa rekurencyjnej formuły xy = mex ({ay ⊕ xb ⊕ ab: a <x, b <y}) do mnożenia nimbera .

Wypróbuj online!

Jak to działa

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 bajty

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

Nie zdawałem sobie sprawy, że ma wbudowane i anonimowe „procedury”.

Wersja oryginalna, 36 bajtów:

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

Lub 25 bajtów, jeśli wejście / wyjście może być nimbers:

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

Cóż, miałem nadzieję *a**b/ a*bpracować, ale to nie działa.

Pyth , 21 bajtów

Mf-TsmmxxgkdgkHgGdGH0

Demonstracja

Wykorzystuje sformułowanie minimalnego wykluczonego elementu mnożenia nim, jak podano tutaj .

Dwie zagnieżdżone mapy są używane do iteracji wszystkich mniejszych wartości ( mm ... GH), a następnie wyniki są spłaszczane ( s). Sprytna część pochodzi z f-T ... 0, w której iterujemy liczby całkowite w górę od 0, aby znaleźć pierwszą nie zawartą w zestawie wspomnianym powyżej. Robiąc to w ten sposób, nie musimy obliczać górnej granicy iteracji, oszczędzając kilka bajtów.

Na koniec funkcja goblicza iloczyn NIM.

JavaScript (ES6), 142 128 bajtów

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>

Pierwszym krokiem jest podzielenie obu xiy na XOR mocy 2, weź ich produkty nim parami nim, a następnie XOR wyniki (ponieważ produkt nim rozprowadza się przez XOR). Kiedy już recursed do sprawy xi yobie potęgi 2, możemy zauważyć, że kompetencje Fermat pomnożyć ze sobą za pomocą zwykłej arytmetyki, więc możemy zatem na czynniki xi ydo uprawnień Fermata. Jeśli xa ynie dzielić władzę Fermata możemy odwrócić ten proces i po prostu wrócić x * y. Jeśli jednak dzielą moc Fermata, wówczas dzielimy obie xi yprzez tę moc, obliczamy iloczyn nim, a następnie bierzmy iloczyn nim z kwadratem nim tej mocy Fermata. Nie golfowany:

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
}

Wolfram Language (Mathematica) , 81 bajtów

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

Wypróbuj online!

Za pomocą wzoru:

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