Erkundung des Xorspace

14

Der Xorspace einer Menge von Ganzzahlen ist die Menge aller Ganzzahlen, die durch Kombinieren der Start-Ganzzahlen mit dem üblichen bitweisen xor-Operator ( ^) erhalten werden können. Zum Beispiel kann die xorspace von (8, 4)IST (0, 4, 8, 12): 0 4 ^ 4, 12 4 ^ 8, und es wird keine andere Zahlen erreicht werden können. Beachten Sie, dass die Startnummern nach dieser Definition immer enthalten sind (z. B. 4 ist 4 ^ 4 ^ 4).

Ihr Ziel ist es, das kürzeste Programm zu schreiben, das eine Liste nicht negativer Ganzzahlen als Eingabe verwendet und die Anzahl der Elemente in ihrem Xorspace ausgibt.

  • Standardlücken sind verboten.
  • Die Ein- und Ausgabe kann in einem der üblichen Formate erfolgen . Die Eingabe ist garantiert gültig, nicht leer und ohne Duplikate.
  • Ihr Code sollte in der Lage sein, alle Testfälle in weniger als einem Tag zu verarbeiten .

Testfälle

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
Grimmig
quelle

Antworten:

2

Pyth, 8 Bytes

lu{+xM*Q

Testsuite

Erläuterung:

Um den Xorspace zu erzeugen, finden wir den Fixpunkt, der darin besteht, das Xor jedes Zahlenpaares zu nehmen, jede Zahl hinzuzufügen und zu deduplizieren. Dann nehmen wir die Länge des Ergebnisses. Dies dauert im letzten Testfall 20 Sekunden (nur offline).

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.

Gepackter Pyth , 7 Bytes

Hexdump:

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

Dasselbe wie oben, mit einer 7-Bit-ASCII-Codierung.

Fügen Sie das Obige in eine Datei mit ein xxd -rund führen Sie es wie folgt aus:

py packed-pyth.py xorspace.ppyth '[256, 259, 3]'
isaacg
quelle
Ich denke, du kannst es tun l{mxFdy.
Donnerstag,
@xnor yfür den Testfall 1 bis 63 ist viel zu langsam. Ich habe keinen 2 ^ 63 Speicher.
Isaacg
10

MATL , 11 Bytes

t"G!Z~Ghu]n

Probieren Sie es online!

Der letzte Testfall wird aufgrund von Speicherbeschränkungen nicht im Online-Interpreter ausgeführt, sondern auf einem modernen Computer in weniger als 2 Sekunden offline ausgeführt.

Erläuterung

Bei der Eingabe der Größe ngeschieht Folgendes:

  1. Ergebnis zur Eingabe initialisieren.
  2. Wiederholen Sie die nZeiten:
    1. Wenden Sie bitweises XOR auf alle Einträge des aktuellen Ergebnisses und der aktuellen Eingabe an.
    2. Fügen Sie dem Ergebnis Eingabewerte hinzu.
    3. Deduplizieren
  3. Die Ausgabe ist die Anzahl der Elemente des Endergebnisses.

Kommentierter Code.

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

Beispiel

Die Zwischenergebnisse (Schritte 2.1 und 2.3) für die Eingabe [256 259 3]sind:

Erste Iteration: [256 259 3]mit [256 259 3]: Berechnung aller Paare von bitweisem XOR ergibt die Matrix

  0   3 259
  3   0 256
259 256   0

Anhängen [256 259 3]und Deduplizieren

0 3 259 256

Zweite Iteration: aktuelles Ergebnis [0 3 259 256]mit [256 259 3]. Nach dem Deduplizieren ergibt dies wieder

0 3 259 256

Dritte Iteration: wieder

0 3 259 256

Die Ausgabe ist also 4(Anzahl der Einträge des Ergebnisses).

Luis Mendo
quelle
Erklärung bitte? Sie können O (2 ^ n) nicht verwenden.
Erik der Outgolfer
Ich habe keine Ahnung, wie es funktioniert, aber es ist definitiv nicht O (2 ^ n). Tatsächlich wird der (1 2 3… 63) -Testfall ziemlich schnell gelöst, obwohl dies der schlimmste Fall für die Brute-Force-Methode ist.
Grimmy
2
Wie geht das so schnell? Ich habe versucht, in Jelly so ziemlich dasselbe zu tun, aber der erste Versuch wurde nach 19 Minuten getötet ... (Jetzt mit mehr RAM versuchen.)
Dennis
2
Ich glaube, dies ist der schlimmste Fall von O (2ⁿ). es ist nur so, dass in dem Test, der es ausübt, n nur 15 ist, so dass das Programm immer noch ziemlich schnell läuft.
2
@ ais523 Die von bitwise-XOR erhaltenen Zwischenzahlen können niemals größer als die maximale Anzahl in der Eingabe sein, nennen Sie das M. Die Größe des Vektors der Zwischenergebnisse überschreitet also nie M, und die Komplexität ist O ( M*M). Das OP hat gesagt, dass die genaue Definition von nkeine Rolle spielt. Wenn ich also definiere, nwie Mich behaupten kann, ist dies O ( n*n).
Luis Mendo
8

Haskell , 64 Bytes

f Nimmt eine Liste von ganzen Zahlen und gibt eine ganze Zahl zurück.

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

Probieren Sie es online!

Dies behandelt keine leere Liste, dafür können Sie aber $0:statt des Leerzeichens nach maximum.

Wie es funktioniert

  • Wenn das Maximum mder Liste Null ist, wird 1 zurückgegeben.
  • Ansonsten xor jedes Element mit dem Maximum.
    • Ist das Ergebnis kleiner als das Element, wird das Element durch dieses ersetzt.
    • Dies setzt notwendigerweise das höchstwertige Bit auf Null, das irgendwo in der Liste gesetzt ist.
    • Dann kursiert die resultierende Liste und verdoppelt das Ergebnis der Rekursion.
  • Dieser Prozess führt im Wesentlichen eine Gaußsche Eliminierung durch (obwohl die letzten Zeilen weggeworfen werden, indem sie auf 0 gesetzt werden) Modulo 2 in der Matrix, deren Zeilen die Bitdarstellungen der Zahlenliste sind. Die Menge der Bitdarstellungen des "Xorspace" ist der Vektorraum Modulo 2, der von den Zeilen dieser Matrix aufgespannt wird und dessen Anzahl von Elementen 2 hoch der Zeilenrang der Matrix ist.
  • Dieser Algorithmus ist polynomial time, sollte also definitiv besser sein als O (2 ^ n).
Ørjan Johansen
quelle
Dies ist im Grunde der Algorithmus, an den ich gedacht habe (um die Komplexitätsgrenzen zu überwinden), obwohl dies eine besonders elegante Art der Darstellung ist. Es ist schön, es in einer richtig golfenen Antwort zu sehen.
4

Mathematica, 52 Bytes

2^MatrixRank[PadLeft@IntegerDigits[#,2],Modulus->2]&
Alephalpha
quelle
Warum hast du deine Pari / GP-Antwort gelöscht? Es schien gut zu funktionieren. EDIT: vergiss nicht, es sind tatsächlich einige Testfälle gescheitert.
Grimmy
@ Grimy Warum hast du meine Antwort akzeptiert? Dies ist ein Code-Golf, der kürzeste Code gewinnt.
alephalpha
Entschuldigung, ich habe die akzeptierte Antwort auf die mit 7 Bytes gepackte Pyth geändert.
Grimmy
3

05AB1E , 8 Bytes

vDy^ìÙ}g

Probieren Sie es online!

Alle Testfälle sind mit TIO in weniger als 1 Minute abgeschlossen.

Emigna
quelle
Dies verfehlt das letzte Kriterium: «Ihr Code sollte in der Lage sein, alle Testfälle in weniger als einem Tag zu verarbeiten (kein O (2 ** n) Zeug). »
Grimmy
@ Grimy: Hab den 2^nTeil nicht gelesen : /
Emigna
@Grimy: Jetzt aktualisiert, um alle Testfälle in weniger als 1 Minute (und mit weniger verwendeten Bytes) zu
beenden
Dachte âü^Ùgerst, als ich sah, dass man mehr als einmal xor kann, nette Lösung.
Magic Octopus Urn
@carusocomputing: Das spart ein Byte, aber ich bin mir nicht sicher über die Komplexität.
Emigna
2

Gelee , 9 8 Bytes

0œ|⁺^¥/L

Beendet alle Testfälle unter TIO in weniger als 8 Sekunden mit vernachlässigbarem Speicherbedarf.

Probieren Sie es online!

Wie es funktioniert

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
quelle
1

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)
user1502040
quelle
Es funktioniert, aber ich zähle 113 Bytes; Habe ich etwas verpasst?
Grimmy
@totallyhuman Das liegt wahrscheinlich daran, dass Sie Tabellierungen als 8 Byte und nicht als ein einzelnes Byte zählen.
Grimmy
Wenn der erste Einzug ein Leerzeichen ist, der nächste ein Tabulator und der letzte ein Tabulator + ein Leerzeichen (oder 2 Tabulatoren), dann sind es 113 Bytes
daniero
@Grimy Tatsächlich besteht jeder Tab aus 4 Leerzeichen und nicht aus 8.
Erik the Outgolfer
Ein vollständiges Programm wäre kürzer, da es eine Handvoll Einrückungen erspart. Die for-Schleife kann auch in einer einzigen Zeile zusammengefasst werden, u+=[c][c in s:]was Ihrer ifAnweisung entspricht.
Dennis