Eksploracja Xorspace

14

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
Ponury
źródło

Odpowiedzi:

2

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]'
isaacg
źródło
Myślę, że możesz l{mxFdy.
xnor
@xnor yzastosowane w przypadku od 1 do 63 jest o wiele za wolne. Nie mam pamięci 2 ^ 63.
isaacg
10

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

Luis Mendo
źródło
Wyjaśnienie proszę? Nie możesz użyć O (2 ^ n).
Erik the Outgolfer
Nie mam pojęcia, jak to działa, ale zdecydowanie nie jest to O (2 ^ n). W rzeczywistości dość szybko rozwiązuje przypadek testowy (1 2 3… 63), mimo że jest to najgorszy przypadek w przypadku metody brutalnej siły.
Grimmy,
2
Jak to jest takie szybkie? Próbowałem zrobić prawie to samo w Jelly, ale pierwsza próba zginęła po 19 minutach ... (Teraz próbuję z większą ilością pamięci RAM.)
Dennis
2
Uważam, że jest to najgorszy przypadek O (2ⁿ); po prostu w teście, który go wykonuje, n wynosi tylko 15, więc program nadal działa dość szybko.
2
@ ais523 Liczby pośrednie uzyskane z bitowego XOR nigdy nie mogą być większe niż maksymalna liczba na wejściu, wywołaj to M . Wielkość wektora wyników pośrednich nigdy nie przekracza M, a złożoność wynosi O ( M*M). PO stwierdził, że dokładna definicja nnie ma znaczenia, jeżeli zdefiniować tak n, jak Mmożna zastrzeżenia to oznaczać O ( n*n).
Luis Mendo
8

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).
Ørjan Johansen
źródło
Jest to w zasadzie algorytm, o którym myślałem (do pokonania granic złożoności), chociaż jest to szczególnie elegancki sposób na jego przedstawienie. Miło jest widzieć to w poprawnie golfowej odpowiedzi.
4

Mathematica, 52 bajty

2^MatrixRank[PadLeft@IntegerDigits[#,2],Modulus->2]&
alephalpha
źródło
Dlaczego usunąłeś swoją odpowiedź Pari / GP? Wyglądało na to, że działa dobrze. EDYCJA: nieważne, w rzeczywistości niektóre testy zakończyły się niepowodzeniem.
Grimmy,
@Grimy Dlaczego zaakceptowałeś moją odpowiedź? To jest golf golfowy, wygrywa najkrótszy kod.
alephalpha
Przepraszam, zmieniłem zaakceptowaną odpowiedź na 7-bajtowy pakiet Pyth.
Grimmy,
3

05AB1E , 8 bajtów

vDy^ìÙ}g

Wypróbuj online!

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

Emigna
źródło
To nie spełnia ostatniego kryterium: «Twój kod powinien być w stanie przetworzyć wszystkie przypadki testowe w mniej niż jeden dzień (bez O (2 ** n) rzeczy). »
Grimmy,
@Grimy: Nie przeczytałem 2^nczęści: /
Emigna
@Grimy: Teraz zaktualizowane, aby ukończyć wszystkie przypadki testowe w czasie krótszym niż 1 minuta (i przy użyciu mniejszej liczby bajtów)
Emigna
Myślałem, âü^Ùgdopóki nie zobaczyłem, że możesz xor więcej niż raz, fajne rozwiązanie.
Magic Octopus Urn
@carusocomputing: To oszczędza bajt, ale nie jestem pewien co do złożoności.
Emigna
3

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!

xnor
źródło
2

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.
Dennis
źródło
1

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)
użytkownik1502040
źródło
Działa, ale liczę 113 bajtów; przegapiłem coś?
Grimmy,
@ całkowicie ludzki to prawdopodobnie dlatego, że liczysz tabulacje jako 8 bajtów, a nie jako jeden bajt.
Grimmy,
Jeśli pierwsze wcięcie to spacja, następne to tabulacja, a ostatnia tabulacja + spacja (lub 2 tabulatory), to jest to 113 bajtów
daniero
@Grimy Właściwie każda karta ma 4 spacje, a nie 8.
Erik the Outgolfer
Pełny program byłby krótszy, ponieważ oszczędza garść wcięć. Pętlę for można również skondensować w jedną linię, co u+=[c][c in s:]jest równoważne z ifinstrukcją.
Dennis