探索xorspace

Question

一组整数的xorspace是通过将起始整数与通常的按位xor运算符(^)组合而得到的所有整数的集合。例如，(8, 4)的xorspace为(0, 4, 8, 12)：0为4^4，12为4^8，无法达到其他数字。注意，根据这个定义，起始数总是包括在内(例如，4是4^4^4)。

您的目标是编写一个最短的程序，以一个非负整数列表作为输入，并输出它们的xorspace中的元素数。

• 标准漏洞是禁止的。
• 输入和输出可以在任何常用格式中。保证输入是有效的，非空的，没有重复的.
• 您的代码应该能够在不到一天的时间内处理所有测试用例。

测试用例

Input: 0
Output: 1

Input: 6
Output: 2

Input: 8 4
Ouput: 4

Input: 0 256
Output: 2

Input: 256 259 3
Output: 4

Input: 60 62 94 101 115
Output: 32

Input: 60 62 94 101 115 40 91
Output: 32

Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
Output: 64

Input: 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384
Output: 32768

Answer 1

Pyth，8字节

lu{+xM*Q

测试套件

解释：

为了生成xorspace，我们找到了取每对数字的xor，加上每个数字，以及去重复的不动点。然后，我们取结果的长度。在最后的测试用例上，运行时间为20秒(仅脱机)。

lu{+xM*Q
lu{+xM*QGGQ    Implicit variable introduction
 u        Q    Find the fixed point of the following, starting with the input,
               where the current value is G.
      *QG      Form the Cartesian product of Q (input) and G (current)
    xM         Take the xor of every pair
   +           Add the current values
  {            Deduplicate
l              Output the length of the result.

填充Pyth，7字节

六角山：

0000000: d9d7 dabf 1355 51                        .....UQ

与上述相同，采用7位ASCII编码.

将上述内容与xxd -r放在一个文件中，并按如下方式运行：

py packed-pyth.py xorspace.ppyth '[256, 259, 3]'

Answer 2

马蒂尔，11字节

t"G!Z~Ghu]n

在网上试试！

由于内存限制，最后一个测试用例不在在线解释器中运行，而是在现代计算机上在不到2秒的时间内脱机运行。

解释

对于大小为n的输入，这样做如下：

1. 初始化结果到输入。
2. 重复n时间：
   1. 将位XOR应用于当前结果和输入的所有对条目。
   2. 将输入值附加到结果。
   3. 德雷德。

3. 输出是最终结果的元素数。

注释代码。

t      % Implicit input: row vector. Duplicate
"      % For each (i.e. do as many times as the input size)
  G!   %   Push input as a column vector
  Z~   %   Bitwise XOR with broadcast, i.e. for all pairs of entries of the
       %   two arguments. The first argument is the accumulated result
       %   from the previous iteration, the second is the input vector
  G    %   Push input again
  h    %   Postpend
  u    %   Unique values. Gives a row vector
]      % End
n      % Number of entries. Implicitly display

示例

输入[256 259 3]的中间结果(步骤2.1和2.3)是：

第一次迭代：[256 259 3]与[256 259 3]：计算所有对位-异或给出矩阵。

  0   3 259
  3   0 256
259 256   0

附加[256 259 3]和去重复

0 3 259 256

第二次迭代:当前结果[0 3 259 256]与[256 259 3]。在重复之后，再次给出

0 3 259 256

第三次迭代:再次

0 3 259 256

所以输出是4 (结果的条目数)。

Answer 3

Mathematica，52字节

2^MatrixRank[PadLeft@IntegerDigits[#,2],Modulus->2]&