El xorspace de un conjunto de enteros es el conjunto de todos los enteros que se pueden obtener combinando los enteros iniciales con el operador xor bit a bit habitual ( ^). Por ejemplo, el xorspace de (8, 4)es (0, 4, 8, 12): 0 es 4 ^ 4, 12 es 4 ^ 8, y no se puede alcanzar ningún otro número. Tenga en cuenta que los números iniciales siempre se incluyen, por esta definición (por ejemplo, 4 es 4 ^ 4 ^ 4).

Su objetivo es escribir el programa más corto que tome una lista de enteros no negativos como entrada y genere la cantidad de elementos en su espacio x.

• Las lagunas estándar están prohibidas.
• La entrada y la salida pueden estar en cualquiera de los formatos habituales . Se garantiza que la entrada sea válida, no vacía y sin duplicados.
• Su código debería poder procesar todos los casos de prueba en menos de un día .

Casos de prueba

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

Pyth, 8 bytes

lu{+xM*Q

Banco de pruebas

Explicación:

Para generar el espacio x, encontramos el punto fijo de tomar el xor de cada par de números, sumar cada número y deduplicar. Luego, tomamos la longitud del resultado. Esto se ejecuta en 20 segundos (solo fuera de línea) en el caso de prueba final.

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 empaquetado , 7 bytes

Hexdump:

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

Lo mismo que el anterior, con una codificación ASCII de 7 bits.

Coloque lo anterior en un archivo con xxd -ry ejecútelo de la siguiente manera:

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

MATL , 11 bytes

t"G!Z~Ghu]n

Pruébalo en línea!

El último caso de prueba no se ejecuta en el intérprete en línea debido a limitaciones de memoria, sino que se ejecuta sin conexión en menos de 2 segundos en una computadora moderna.

Explicación

Para la entrada de tamaño n, esto hace lo siguiente:

1. Iniciar el resultado a la entrada.
2. Repetir ntiempos:
   1. Aplique XOR bit a bit a todos los pares de entradas desde el resultado actual y la entrada.
   2. Adjunte valores de entrada al resultado.
   3. Deduplicar
3. La salida es el número de elementos del resultado final.

Código comentado

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

Ejemplo

Los resultados intermedios (pasos 2.1 y 2.3) para la entrada [256 259 3]son:

Primera iteración: [256 259 3]con [256 259 3]: calcular todos los pares de bitwise-XOR da la matriz

  0   3 259
  3   0 256
259 256   0

Adjuntar [256 259 3]y deduplicar

0 3 259 256

Segunda iteración: resultado actual [0 3 259 256]con [256 259 3]. Después de deduplicar esto nuevamente da

0 3 259 256

Tercera iteración: nuevamente

0 3 259 256

Entonces la salida es 4(número de entradas de resultado).

Haskell , 64 bytes

f toma una lista de enteros y devuelve un entero.

import Data.Bits
f l|m<-maximum l,m>0=2*f(min<*>xor m<$>l)|0<1=1

Pruébalo en línea!

Esto no maneja una lista vacía, para eso puede $0:hacerlo, sino en lugar del espacio posterior maximum.

Cómo funciona

• Si el máximo m de la lista es cero, devuelve 1.
• De lo contrario, xors cada elemento con el máximo.
  • Si el resultado es más pequeño que el elemento, el elemento se reemplaza por él.
  • Esto necesariamente pone a cero el conjunto de bits más significativo en cualquier lugar de la lista.
  • Luego vuelve a aparecer en la lista resultante, duplicando el resultado de la recursión.
• Este proceso esencialmente realiza la eliminación gaussiana (aunque tira las filas finales al establecerlas en 0) módulo 2, en la matriz cuyas filas son las representaciones de bits de la lista de números. El conjunto de representaciones de bits del "xorspace" es el módulo de espacio vectorial 2 atravesado por las filas de esta matriz, y cuyo número de elementos es 2 a la potencia del rango de fila de la matriz.
• Este algoritmo es tiempo polinómico, por lo que definitivamente debería ser mejor que O (2 ^ n).

Mathematica, 52 bytes

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

05AB1E , 8 bytes

vDy^ìÙ}g

Pruébalo en línea!

Todos los casos de prueba terminan en menos de 1 minuto con TIO.

Python 2 , 55 bytes

r={0}
for n in input():r|={x^n for x in r}
print len(r)

Pruébalo en línea!

Funciones superadas:

f=lambda l,r={0}:l and f(l[1:],r|{x^l[0]for x in r})or len(r)
f=lambda l:len(reduce(lambda r,n:r|{x^n for x in r},l,{0}))

El hermoso método de eliminación de filas de Ørjan Johansen es un byte más corto.

Python 2 , 54 bytes

f=lambda l:1-any(l)or 2*f([min(x,x^max(l))for x in l])

Pruébalo en línea!

Jalea , 9 8 bytes

0œ|⁺^¥/L

Termina todos los casos de prueba en menos de 8 segundos en TIO, con requisitos de memoria insignificantes.

Pruébalo en línea!

Cómo funciona

0œ|⁺^¥/L  Main link. Argument: A (array)

0œ|       Perform multiset union with 0, prepending 0 if A doesn't contain it.
      /   Reduce A by the link to the left.
     ¥      Combine the previous two links into a dyadic chain.
            Left argument: V (array). Right argument: n (integer)
    ^           Bitwise XOR each element in V with n.
   ⁺            This quick refers to the previous link, making it a shorthand for
                the link 'œ|'. Thus, it performs multiset union on V and the array
                of bitwise XORs.
       L  Compute the length of the result.

Python, 113 bytes

def f(x):
 u,s=[0],{0}
 while u:
	a=u.pop()
	for b in x:
	 c=a^b
	 if c not in s:u+=[c]
	 s.add(c)
 return len(s)