Фон

Если вы много играете в код, вы, вероятно, знаете о побитовой операции XOR . Учитывая два целых числа, оно дает другое целое число с 1s в битах, где два входа различаются. Так, например 1010 XOR 0011 = 1001.

Это оказывается очень полезным в теории игр, где она более известна как «nim sum». Если у вас есть сумма двух игр (то есть вы делаете ходы в одной игре за раз), значение позиции - это минимальная сумма значений позиций в каждой отдельной игре.

Но мы можем сделать еще один шаг вперед. С добавлением nim и соответствующим определением умножения nim мы можем сформировать поле из неотрицательных целых чисел. Таким образом, задача состоит в том, чтобы умножить игру в гольф.

Определение

Умножение Nim подчиняется следующим правилам:
Произведение nim 2-степени Ферма n = (2 ^ (2 ^ k)) с любым меньшим числом является обычным произведением.
Произведение nim n-степени Ферма n само по себе равно 3n / 2.
Умножение Нима распределяется по сложению Нима.
Умножение по Nim коммутативно и ассоциативно (как и сложение по nim).
Мультипликативная идентичность равна 1 (а аддитивная идентичность равна 0).

Любое неотрицательное целое число может быть записано как сумма nim различных степеней двойки, а любая степень два может быть записана как произведение различных чисел Ферма, поэтому этого достаточно для определения умножения nim для всех неотрицательных целых чисел.

пример

Все это было довольно абстрактно, поэтому давайте рассмотрим пример. Я буду использовать +для обозначения nim сложения (XOR) и *для умножения 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

Дополнительные тестовые случаи

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

Вызов

Напишите программу или функцию, которая, учитывая два неотрицательных целых числа в любой удобной форме, вычисляет их произведение nim.

Это код-гольф , поэтому выигрывает самое короткое представление.

Nim , 120 байт

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

Попробуйте онлайн!

Хорошо, это может быть сумасшествием, но кто-то должен был умножить Nim в Nim ...

Это стандартный алгоритм из Википедии. Проблема в том, что я не знаю языка, поэтому пришлось изучать основы на лету. В частности, я был удивлен , что -=и minне работает для множеств, и лучший способ мне удалось найти для извлечения минимум должен был использовать итератор и возвращает первое значение. Надеюсь, эксперты Nim помогут мне улучшить это.

Python 2 , 85 байт

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

Попробуйте онлайн!

Медленно, как черт. Вычисляет mex ({α ′ β ⊕ α β ′ ⊕ α 'β ′: α ′ <α, β ′ <β}) рекурсивно.

Желе , 16 байт

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

Использует рекурсивную формулу xy = mex ({ay ⊕ xb ⊕ ab: a <x, b <y}) для умножения Нимбера .

Попробуйте онлайн!

Как это устроено

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 байта

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

Не осознавал, что имеет такие встроенные и анонимные «процедуры».

Оригинальная версия, 36 байт:

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

Или 25 байтов, если ввод / вывод может быть nimbers:

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

Ну, я надеялся *a**b/ a*bработал, но это не так.

Pyth , 21 байт

Mf-TsmmxxgkdgkHgGdGH0

демонстрация

Используется минимальная исключаемая формулировка элемента умножения nim, как указано здесь .

Две вложенные карты используются для перебора всех меньших значений ( mm ... GH), затем результаты сглаживаются ( s). Умная часть идет с f-T ... 0, где мы перебираем целые числа вверх от 0, чтобы найти первую, не содержащуюся в наборе, упомянутом выше. Делая это таким образом, нам не нужно вычислять верхнюю границу итерации, сохраняя несколько байтов.

В конце функция gвычисляет произведение nim.

JavaScript (ES6), 142 128 байт

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>

Первый шаг состоит в том, чтобы разделить оба xи yна XOR степеней 2, взять их попарно продукты nim, а затем XOR результаты (потому что продукт nim распределяется по XOR). Как только мы вернулись к случаю xи yобеим степеням 2, отметим, что мощности Ферма умножаются друг на друга, используя обычную арифметику, поэтому мы можем разложить xи yна степени Ферма. Если xи yне разделяем власть Ферма, мы можем повернуть процесс вспять и просто вернуться x * y. Однако, если они делят мощность Ферма, то мы делим их xи yна эту мощность вычисляем произведение nim, а затем берем произведение nim с квадратом nim этой мощности Ферма. 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 байт

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

Попробуйте онлайн!

Используя формулу:

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