Le xorspace d'un ensemble d'entiers est l'ensemble de tous les entiers qui peuvent être obtenus en combinant les entiers de départ avec l'opérateur xor au niveau du bit habituel ( ^). Par exemple, le xorspace de (8, 4)est (0, 4, 8, 12): 0 est 4 ^ 4, 12 est 4 ^ 8 et aucun autre nombre ne peut être atteint. Notez que les nombres de départ sont toujours inclus, par cette définition (par exemple, 4 est 4 ^ 4 ^ 4).

Votre objectif est d'écrire le programme le plus court qui prend en entrée une liste d'entiers non négatifs et génère le nombre d'éléments dans leur xorspace.

• Les failles standard sont interdites.
• L'entrée et la sortie peuvent être dans l'un des formats habituels . L'entrée est garantie pour être valide, non vide et sans doublons.
• Votre code devrait pouvoir traiter tous les cas de test en moins d'une journée .

Cas de test

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 octets

lu{+xM*Q

Suite de tests

Explication:

Pour générer le xorspace, nous trouvons le point fixe de prendre le xor de chaque paire de nombres, d'ajouter chaque numéro et de dédupliquer. Ensuite, nous prenons la longueur du résultat. Cela s'exécute en 20 secondes (hors ligne uniquement) sur le scénario de test 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.

Python emballé , 7 octets

Hexdump:

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

Identique à la précédente, avec un encodage ASCII 7 bits.

Mettez ce qui précède dans un fichier avec xxd -ret exécutez-le comme suit:

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

MATL , 11 octets

t"G!Z~Ghu]n

Essayez-le en ligne!

Le dernier cas de test ne s'exécute pas dans l'interpréteur en ligne en raison de limitations de mémoire, mais s'exécute hors ligne en moins de 2 secondes sur un ordinateur moderne.

Explication

Pour l'entrée de taille n, cela fait ce qui suit:

1. Initialisez le résultat à saisir.
2. Répétez nfois:
   1. Appliquer XOR au niveau du bit à toutes les paires d'entrées du résultat et de l'entrée actuels.
   2. Attachez des valeurs d'entrée au résultat.
   3. Dédupliquer.
3. La sortie est le nombre d'éléments du résultat final.

Code commenté.

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

Exemple

Les résultats intermédiaires (étapes 2.1 et 2.3) pour la saisie [256 259 3]sont:

Première itération: [256 259 3]avec [256 259 3]: le calcul de toutes les paires de bits-XOR donne la matrice

  0   3 259
  3   0 256
259 256   0

Attacher [256 259 3]et dédupliquer

0 3 259 256

Deuxième itération: résultat courant [0 3 259 256]avec [256 259 3]. Après déduplication, cela donne à nouveau

0 3 259 256

Troisième itération: encore

0 3 259 256

La sortie est donc 4(nombre d'entrées de résultat).

Haskell , 64 octets

f prend une liste d'entiers et retourne un entier.

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

Essayez-le en ligne!

Cela ne gère pas une liste vide, pour cela vous pouvez mais $0: au lieu de l'espace après maximum.

Comment ça fonctionne

• Si le maximum m de la liste est zéro, renvoie 1.
• Sinon, xor chaque élément avec le maximum.
  • Si le résultat est plus petit que l'élément, l'élément est remplacé par lui.
  • Cela met forcément à zéro le bit le plus significatif de la liste.
  • Puis revient sur la liste résultante, doublant le résultat de la récursivité.
• Ce processus effectue essentiellement l'élimination gaussienne (tout en jetant les lignes finales en les mettant à 0) modulo 2, sur la matrice dont les lignes sont les représentations binaires de la liste des nombres. L'ensemble des représentations binaires du "xorspace" est l'espace vectoriel modulo 2 enjambé par les lignes de cette matrice, et dont le nombre d'éléments est de 2 à la puissance du rang des lignes de la matrice.
• Cet algorithme est un temps polynomial, il devrait donc certainement être meilleur que O (2 ^ n).

Mathematica, 52 octets

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

05AB1E , 8 octets

vDy^ìÙ}g

Essayez-le en ligne!

Tous les cas de test se terminent en moins d'une minute sur TIO.

Python 2 , 55 octets

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

Essayez-le en ligne!

Beats out fonctions:

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

Ørjan Johansen belle méthode d'élimination des rangs de est un octet plus courte.

Python 2 , 54 octets

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

Essayez-le en ligne!

Gelée , 9 8 octets

0œ|⁺^¥/L

Termine tous les cas de test en moins de 8 ans secondes sur TIO, avec des besoins en mémoire négligeables.

Essayez-le en ligne!

Comment ça fonctionne

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 octets

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)