Xorspace zestawu liczb jest zbiorem wszystkich liczb, które mogą być uzyskane przez połączenie liczb całkowitych, zaczynające się zwykle operator bitowy XOR ( ^). Na przykład xorspace (8, 4)wynosi (0, 4, 8, 12): 0 to 4 ^ 4, 12 to 4 ^ 8 i nie można uzyskać innych liczb. Zauważ, że numery początkowe są zawsze uwzględnione w tej definicji (na przykład 4 to 4 ^ 4 ^ 4).

Twoim celem jest napisanie najkrótszego programu, który przyjmuje na wejściu listę liczb całkowitych nieujemnych i wyświetla liczbę elementów w swoim obszarze xorspace.

• Standardowe luki są zabronione.
• Dane wejściowe i wyjściowe mogą mieć dowolny zwykły format . Dane wejściowe są poprawne, niepuste i bez duplikatów.
• Twój kod powinien być w stanie przetworzyć wszystkie przypadki testowe w mniej niż jeden dzień .

Przypadki testowe

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 bajtów

lu{+xM*Q

Zestaw testowy

Wyjaśnienie:

Aby wygenerować xorspace, znajdujemy punkt stały polegający na pobraniu xor każdej pary liczb, dodaniu każdej liczby i deduplikacji. Następnie bierzemy długość wyniku. Trwa to w ciągu 20 sekund (tylko offline) w ostatnim przypadku testowym.

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.

Pakiety Pyth , 7 bajtów

Hexdump:

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

To samo co powyżej, z 7-bitowym kodowaniem ASCII.

Umieść powyższe w pliku za pomocą xxd -ri uruchom go w następujący sposób:

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

MATL , 11 bajtów

t"G!Z~Ghu]n

Wypróbuj online!

Ostatni przypadek testowy nie działa w tłumaczu online z powodu ograniczeń pamięci, ale działa offline w mniej niż 2 sekundy na nowoczesnym komputerze.

Wyjaśnienie

W przypadku wprowadzania rozmiaru nwykonuje się następujące czynności:

1. Zainicjuj wynik do wprowadzenia.
2. Powtórz nczasy:
   1. Zastosuj bitową XOR do wszystkich par wpisów z bieżącego wyniku i danych wejściowych.
   2. Dołącz wartości wejściowe do wyniku.
   3. Deduplikacja.
3. Dane wyjściowe to liczba elementów wyniku końcowego.

Skomentowany kod.

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

Przykład

Wyniki pośrednie (kroki 2.1 i 2.3) dla danych wejściowych [256 259 3]to:

Pierwsza iteracja: [256 259 3]z [256 259 3]: obliczenie wszystkich par bitów-XOR daje macierz

  0   3 259
  3   0 256
259 256   0

Dołączanie [256 259 3]i deduplikacja

0 3 259 256

Druga iteracja: bieżący wynik [0 3 259 256]z [256 259 3]. Po deduplikacji daje to ponownie

0 3 259 256

Trzecia iteracja: znowu

0 3 259 256

Tak więc wynikiem jest 4(liczba wpisów wyniku).

Haskell , 64 bajty

f pobiera listę liczb całkowitych i zwraca liczbę całkowitą.

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

Wypróbuj online!

To nie obsługuje pustej listy, ponieważ możesz $0:zamiast tego wstawiać spacjęmaximum .

Jak to działa

• Jeśli maksimum m listy wynosi zero, zwraca 1.
• W przeciwnym razie xors każdy element z maksimum.
  • Jeśli wynik jest mniejszy niż element, element jest przez niego zastępowany.
  • To koniecznie zeruje najbardziej znaczący bit ustawiony w dowolnym miejscu na liście.
  • Następnie powraca na wynikowej liście, podwajając wynik rekurencji.
• Proces ten zasadniczo eliminuje Gaussa (chociaż wyrzuca ostatnie rzędy, ustawiając je na 0) modulo 2, na macierzy, której rzędy są bitowymi reprezentacjami listy liczb. Zbiór reprezentacji bitowych „przestrzeni xorspace” jest modułem przestrzeni wektorowej 2 rozpiętym przez rzędy tej macierzy, którego liczba elementów wynosi 2 w stosunku do rangi rzędu macierzy.
• Ten algorytm jest czasem wielomianowym, więc zdecydowanie powinien być lepszy niż O (2 ^ n).

Mathematica, 52 bajty

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

05AB1E , 8 bajtów

vDy^ìÙ}g

Wypróbuj online!

Wszystkie przypadki testowe kończą się w TIO w czasie krótszym niż 1 minuta.

Python 2 , 55 bajtów

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

Wypróbuj online!

Wyróżnia funkcje:

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

Piękna metoda eliminacji wierszy Ørjan Johansen jest krótsza o jeden bajt.

Python 2 , 54 bajty

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

Wypróbuj online!

Galaretka , 9 8 bajtów

0œ|⁺^¥/L

Kończy wszystkie przypadki testowe poniżej 8 TIO w czasie krótszym sekund, przy znikomych wymaganiach dotyczących pamięci.

Wypróbuj online!

Jak to działa

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 bajtów

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)