fundo

Se você pratica muito código de golfe, provavelmente conhece a operação XOR bit a bit . Dados dois números inteiros, ele fornece outro número inteiro com 1s nos bits, onde as duas entradas diferem. Então, por exemplo 1010 XOR 0011 = 1001,.

Isso acaba sendo muito útil na teoria dos jogos, onde é mais conhecida como "nim sum". Se você tiver a soma de dois jogos (ou seja, você está fazendo movimentos em um jogo de cada vez), o valor da posição é a soma nim dos valores das posições em cada jogo individual.

Mas podemos dar um passo adiante. Com a adição de nim e uma definição apropriada de multiplicação de nim , podemos formar um campo a partir de números inteiros não negativos. Portanto, o desafio é multiplicar o golfe.

Definição

A multiplicação de nim obedece às seguintes regras:
O produto nim de uma Fermat 2-potência n = (2 ^ (2 ^ k)) com qualquer número menor é o produto comum.
O produto nim de um Fermat 2-power n é 3n / 2.
A multiplicação de nim distribui sobre a adição de nim.
A multiplicação de nim é comutativa e associativa (como é a adição de nim).
A identidade multiplicativa é 1 (e a identidade aditiva é 0).

Qualquer número inteiro não negativo pode ser escrito como a soma nim de potências distintas de dois e qualquer potência de dois pode ser escrito como o produto de números Fermat distintos, portanto, isso é suficiente para definir a multiplicação de nim para todos os números inteiros não negativos.

Exemplo

Isso foi tudo bastante abstrato, então vamos trabalhar com um exemplo. Vou usar +para denotar disso nim (XOR) e *para a multiplicação 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

Casos de teste adicionais

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

Desafio

Escreva um programa ou função que, dados dois inteiros não negativos em qualquer forma conveniente, calcule seu produto nim.

Este é o código-golfe , pelo que o envio mais curto vence.

Nim , 120 bytes

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

Experimente online!

OK, isso pode ser uma loucura, mas alguém tinha que fazer multiplicação Nim em Nim ...

Este é um algoritmo padrão da Wikipedia. O problema é que eu não conheço o idioma, então tive que aprender o básico rapidamente. Em particular, fiquei surpreso que -=e minnão funcionou para conjuntos, e a melhor maneira que conseguiu encontrar para extrair o mínimo era usar o iterador e retornar o primeiro valor. Felizmente, os especialistas em Nim me ajudarão a melhorar isso.

Python 2 , 85 bytes

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

Experimente online!

Lento como o diabo. Calcula mex ({α ′ β ⊕ α β ′ ⊕ α 'β ′: α ′ <α, β ′ <β}) recursivamente.

Gelatina , 16 bytes

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

Usa a fórmula recursiva xy = mex ({ay xb ⊕ ab: a <x, b <y}) para multiplicação de nimber .

Experimente online!

Como funciona

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 bytes

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

Não sabia que ele tinha esse "procedimento" interno e anônimo.

Versão original, 36 bytes:

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

Ou 25 bytes, se a entrada / saída puder ser nimbers:

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

Bem, eu esperava *a**b/ a*btrabalhar, mas não funciona.

Pitão , 21 bytes

Mf-TsmmxxgkdgkHgGdGH0

Demonstração

Usa a formulação mínima de elementos excluídos da multiplicação nim, conforme indicado aqui .

Dois mapas aninhados são usados ​​para iterar sobre todos os valores menores ( mm ... GH), e os resultados são achatados ( s). A parte inteligente vem com f-T ... 0, onde iteramos números inteiros para cima de 0 para encontrar o primeiro não contido no conjunto mencionado acima. Fazendo dessa maneira, não precisamos calcular um limite superior da iteração, economizando alguns bytes.

No final, a função gcalcula o produto nim.

JavaScript (ES6), 142 128 bytes

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>

A primeira etapa é dividir ambos xe yem um XOR de potências de 2, tomar seus produtos nim em pares e depois XOR os resultados (porque o produto nim é distribuído pelo XOR). Uma vez que tenhamos recursed ao caso de xe yambas as potências de 2, nota-se que os poderes Fermat multiplicam uns com os outros usando a aritmética ordinária, para que possamos, portanto, factorise xe yem poderes Fermat. Se xe ynão compartilharmos um poder Fermat, podemos reverter o processo e simplesmente retornar x * y. No entanto, se eles compartilham um poder Fermat, então dividimos ambos xe ypor esse poder, calculamos o produto nim e, em seguida, levamos o produto nim com o quadrado nim desse poder Fermat. Ungolfed:

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 bytes

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

Experimente online!

Usando a fórmula:

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