Xorting eines Arrays

105

Konzeptionell ist diese Herausforderung sehr einfach. Sie erhalten eine Liste nicht negativer Ganzzahlen . Suchen Sie nach Möglichkeit eine nicht negative Ganzzahl , sodass die Liste sortiert wird. Wenn dies nicht der Fall ist, sollte die Ausgabe alles sein, was nicht mit einer gültigen Zahl verwechselt werden kann , z. B. eine negative Zahl, gar nichts, ein Fehler usw.aiNbi = ai XOR NNN

Hier ist ein Beispiel:

[4, 7, 6, 1, 0, 3]

Wenn wir jedes Element in dieser Liste nehmen XOR 5, erhalten wir

[1, 2, 3, 4, 5, 6]

welches ist sortiert. (Beachten Sie, dass es nicht erforderlich ist, dass die resultierende Liste eindeutige Elemente enthält und keine Lücken enthält. Wenn das Ergebnis einer solchen Operation [0, 1, 1, 3]gültig wäre, wäre dies weiterhin gültig.) Auf der anderen Seite für die Liste

[4, 7, 1, 6, 0, 3]

solche Ngibt es nicht.

Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.

Die Eingabe kann in einem beliebigen geeigneten Listen- oder Zeichenfolgeformat erfolgen. Sie können davon ausgehen, dass es weniger als jedes gibt und die Liste mindestens ein Element enthält.ai231

Ihr Code muss alle Testfälle (insbesondere die vier großen) in wenigen Sekunden verarbeiten können.

Es gelten die Standardregeln für Code-Golf .

Testfälle

Für jeden nicht zurückgegebenen Testfall gibt -1es unendlich viele richtige Antworten. Das hier aufgeführte ist das kleinste. Zusätzliche Lösungen bestehen darin, dass zusätzlich Bits gesetzt werden, die für alle Ganzzahlen in der Eingabe gleich sind (insbesondere diejenigen, die größer sind als das höchstwertige Bit in der größten Nummer der Liste).

[4 7 6 1 0 3] => 5
[4 7 1 6 0 3] => -1
[0 1 3 4 6 7] => 0
[4 2 3 1] => 6
[2 3 0 0 7 7 4 5 11 11] => 2
[2 3 0 0 7 7 5 4 11 11] => -1
[1086101479 748947367 1767817317 656404978 1818793883 1143500039] => -1
[180522983 1885393660 751646477 367706848 331742205 724919510 850844696 2121330641 869882699 1831158987 542636180 1117249765 823387844 731663826 1762069894 240170102 1020696223 1212052937 2041219958 712044033 195249879 1871889904 1787674355 1849980586 1308879787 1743053674 1496763661 607071669 1987302942 178202560 1666170841 1035995406 75303032 1755269469 200581873 500680130 561748675 1749521426 1828237297 835004548 934883150 38711700 1978960635 209243689 1355970350 546308601 590319412 959613996 1956169400 140411967 112601925 88760619 1977727497 672943813 909069787 318174568 385280382 370710480 809689639 557034312 865578556 217468424 346250334 388513751 717158057 941441272 437016122 196344643 379529969 821549457 97008503 872313181 2105942402 603939495 143590999 1580192283 177939344 853074291 1288703007 1605552664 162070930 1325694479 850975127 681702163 1432762307 1994488829 780869518 4379756 602743458 1963508385 2115219284 1219523498 559301490 4191682 1918142271 169309431 346461371 1619467789 1521741606 1881525154] => -1
[37580156 64423492 87193676 91914964 93632157 96332899 154427982 176139560 184435039 228963836 230164674 279802291 301492375 309127664 345705721 370150824 380319820 403997410 410504675 416543032 418193132 424733526 428149607 435596038 477224208 515649925 519407995 525469350 614538124 624884850 642649261 653488151 679260270 685637235 690613185 739141066 825795124 832026691 832633584 833213619 852655299 913744258 917674993 921902522 925691996 931307936 954676047 972992595 997654606 1020009811 1027484648 1052748108 1071580605 1108881241 1113730139 1122392118 1154042251 1170901568 1180031842 1180186856 1206428383 1214066097 1242934611 1243983997 1244736049 1262979035 1312007069 1312030297 1356274316 1368442960 1377432523 1415342434 1471294243 1529353536 1537868913 1566069818 1610578189 1612277199 1613646498 1639183592 1668015280 1764022840 1784234921 1786654280 1835593744 1849372222 1875931624 1877593764 1899940939 2007896363 2023046907 2030492562 2032619034 2085680072 2085750388 2110824853 2123924948 2131327206 2134927760 2136423634] => 0
[1922985547 1934203179 1883318806 1910889055 1983590560 1965316186 2059139291 2075108931 2067514794 2117429526 2140519185 1659645051 1676816799 1611982084 1736461223 1810643297 1753583499 1767991311 1819386745 1355466982 1349603237 1360540003 1453750157 1461849199 1439893078 1432297529 1431882086 1427078318 1487887679 1484011617 1476718655 1509845392 1496496626 1583530675 1579588643 1609495371 1559139172 1554135669 1549766410 1566844751 1562161307 1561938937 1123551908 1086169529 1093103602 1202377124 1193780708 1148229310 1144649241 1257633250 1247607861 1241535002 1262624219 1288523504 1299222235 840314050 909401445 926048886 886867060 873099939 979662326 963003815 1012918112 1034467235 1026553732 568519178 650996158 647728822 616596108 617472393 614787483 604041145 633043809 678181561 698401105 776651230 325294125 271242551 291800692 389634988 346041163 344959554 345547011 342290228 354762650 442183586 467158857 412090528 532898841 534371187 32464799 21286066 109721665 127458375 192166356 146495963 142507512 167676030 236532616 262832772] => 1927544832
[1922985547 1934203179 1883318806 1910889055 1983590560 1965316186 2059139291 2075108931 2067514794 2117429526 2140519185 1659645051 1676816799 1611982084 1736461223 1810643297 1753583499 1767991311 1819386745 1355466982 1349603237 1360540003 1453750157 1461849199 1439893078 1432297529 1431882086 1427078318 1487887679 1484011617 1476718655 1509845392 1496496626 1583530675 1579588643 1609495371 1559139172 1554135669 1549766410 1566844751 1562161307 1561938937 1123551908 1086169529 1093103602 1202377124 1193780708 1148229310 1144649241 1257633250 1241535002 1247607861 1262624219 1288523504 1299222235 840314050 909401445 926048886 886867060 873099939 979662326 963003815 1012918112 1034467235 1026553732 568519178 650996158 647728822 616596108 617472393 614787483 604041145 633043809 678181561 698401105 776651230 325294125 271242551 291800692 389634988 346041163 344959554 345547011 342290228 354762650 442183586 467158857 412090528 532898841 534371187 32464799 21286066 109721665 127458375 192166356 146495963 142507512 167676030 236532616 262832772] => -1

Schließlich sind hier vier sehr große Testfälle aufgeführt, um sicherzustellen, dass die Einreichungen ausreichend effizient sind:

Warum sollte jemand das tun?

Neulich ist mir aufgefallen, dass eine XOR-Operation ein Array "sortieren" kann, wodurch es möglich ist, eine binäre Suche in dem Array in O (log n) durchzuführen, ohne es zuerst sortieren zu müssen. Es scheint möglich zu sein, Nin pseudolinearer Zeit zu bestimmen , was dies zu einer schnelleren Alternative zu den meisten Sortieralgorithmen machen würde, und es hat nicht den Speicherbedarf einer Radix-Sortierung. Natürlich ist eine direkte lineare Suche durch das unsortierte Array schneller, aber wenn Sie dasselbe Array mehrmals durchsuchen möchten, kann eine einzelne lineare Vorberechnung die für jede Suche erforderliche Zeit erheblich verkürzen.

Leider ist die Klasse der Listen, an denen gearbeitet wird, eher begrenzt (es ist unwahrscheinlich, dass gleichmäßig zufällige Verteilungen eine zulassen N).

Eine interessante Frage ist, ob es andere bijektive Funktionen gibt, die einfacher zu überprüfen und / oder für eine breitere Klasse von Listen anwendbar sind.

code-golf array-manipulation sorting bitwise Martin Ender
quelle
42
" Xorting " ist dafür ein wirklich cooler Name.
insertusernamehere
7
@insertusernamehere Credits dafür gehen an randomra.
Martin Ender
3
Eine äußerst interessante Herausforderung!
DavidC
4
Paebbels: Vorausgesetzt, Sie haben den Xorting-Schlüssel, ist es möglich, den ursprünglichen Wert zu berechnen. Für die Zwecke hier (eine binäre Suche) würden Sie die Eingabe mit dem Schlüssel XOR-verknüpfen und dann überprüfen, ob sie im sortierten Array vorhanden ist. Es ist sicherlich eine Sortierung, aber die Relation / Funktion, die Sie sortieren, wird ausgewählt, wenn die Position jedes Elements gleich bleibt.
Meiamsome
8
@Paebbels Ich habe nie behauptet, dass dies sortiert wird. Ich habe es mit einem erfundenen Wort bezeichnet, und der Absatz, den Sie zitieren, enthält aus einem bestimmten Grund "sort" in Anführungszeichen. Mein Punkt war, dass dies eine bijektive Transformation ist, die es ermöglicht, das Array so zu behandeln, als ob es für bestimmte Operationen (wie eine binäre Suche) sortiert wäre, ohne es tatsächlich sortieren zu müssen.
Martin Ender

Antworten:

7

Gelee, 25 Bytes

ṡ2Zµ^/Bo1Ḅ‘×>/|/H
Ç-¹^Ç¥?

Die neuesten Commits geben diese Herausforderung nach, aber der obige Code funktioniert mit dieser Revision , die älter ist als sie. Probieren Sie es online!

Abhängig von Ihrer Shell kann es erforderlich sein, den obigen Code in ein Programm einzufügen, das Eingaben von STDIN liest, um die großen Testfälle auszuführen. Probieren Sie es online!

Testfälle

$ xxd -c 13 -g 1 xort-prog.jelly 
0000000: ae 32 5a 8c 5e 2f 42 6f 31 a4 b6 94 3e  .2Z.^/Bo1...>
000000d: 2f 7c 2f 48 0a 92 2d 8e 5e 92 84 3f     /|/H..-.^..?
$ ./jelly f xort-prog.jelly '[4, 7, 6, 1, 0, 3]'; echo
5
$ ./jelly f xort-prog.jelly '[4, 7, 1, 6, 0, 3]'; echo
-1
$ ./jelly f xort-prog.jelly '[0, 1, 3, 4, 6, 7]'; echo
0
$ ./jelly f xort-prog.jelly '[4, 2, 3, 1]'; echo
6
$ ./jelly f xort-prog.jelly '[2, 3, 0, 0, 7, 7, 4, 5, 11, 11]'; echo
2
$ ./jelly f xort-prog.jelly '[2, 3, 0, 0, 7, 7, 5, 4, 11, 11]'; echo
-1
$
$ wget -q http://pastebin.com/raw/{P96PNi79,zCNLMsx9,GFLBXn5b,6F1Yn3gG}
$ xxd -c 14 -g 1 xort-func.jelly 
0000000: ae 32 5a 8c 5e 2f 42 6f 31 a4 b6 94 3e 2f  .2Z.^/Bo1...>/
000000e: 7c 2f 48 0a 92 2d 8e 5e 92 84 3f 0a a0 92  |/H..-.^..?...
$ tr \  , < P96PNi79 | time -f '\n%es' ./jelly f xort-func.jelly
-1
3.69s
$ tr \  , < zCNLMsx9 | time -f '\n%es' ./jelly f xort-func.jelly
0
2.78s
$ tr \  , < GFLBXn5b | time -f '\n%es' ./jelly f xort-func.jelly
1096442624
2.73s
$ tr \  , < 6F1Yn3gG | time -f '\n%es' ./jelly f xort-func.jelly
-1
2.70s

Idee

Dies verwendet den gleichen Ansatz wie die Antwort von @ Jakube , aber meine Implementierung ist etwas anders.

Jelly hat noch keine Sortierung, also berechnen wir einen Xorting-Kandidaten, XOR die Eingabeliste damit, berechnen einen Xorting-Kandidaten der XOR-Liste und prüfen, ob der neue Kandidat Null ist. Wenn dies der Fall ist, drucken wir den ersten Kandidaten aus. Andernfalls geben wir -1 aus .

Außerdem scheint Jelly noch keine vernünftige Möglichkeit zu haben, auf Ganzzahl umzurechnen (sogar Ganzzahldivisionen können Floats zurückgeben), daher musste ich mir eine ziemlich kreative Methode ausdenken, um eine Liste von Zahlen auf die nächste Potenz von 2 abzurunden . Anstelle von log-floor-pow konvertiere ich alle Ganzzahlen in Binärzahlen, ersetze alle Binärzahlen durch 1 , konvertiere zurück in Ganzzahlen, addiere 1 und dividiere durch 2 .

Code

ṡ2Zµ^/Bo1Ḅ‘×>/|/H  Helper link. Argument: M (list of integers)

ṡ2                 Yield all overlapping slices of length 2 (pairs) of M.
  Z                Zip to group first and second coordinates.
   µ               Begin a new, monadic chain.
    ^/             XOR the corresponding coordinates.
      B            Convert all results to binary.
       o1          OR (logical) all binary digits with 1.
         Ḅ         Convert back to integer.
          ‘        Increment all integers.
           ×>/     Multiply each rounded (a ^ b) by (a > b).
                   This replaces (a ^ b) with 0 unless a > b.
              |/   OR all results.
                H  Halve the result.

Ç-¹^Ç¥?            Main link. Input: L (list of integers)

Ç                  Call the helper link on L. Result: C (integer)
     ¥             Create a dyadic chain:
   ^                 XOR the elements of L with C.
    Ç                Call the helper link on the result.
      ?            If the result in non-zero:
 -                   Yield -1.
  ¹                Else, yield C.
Dennis
quelle
36

Pyth, 40 36 31 30 Bytes

Ju.|G^2slHxMf>FT.:Q2Z|tSIxRJQJ

Probieren Sie es online aus: Demo oder Test Suite

Jeder der großen Testfälle ist in wenigen Sekunden abgeschlossen.

Erläuterung:

Zuerst erkläre ich die Methode und warum sie funktioniert. Ich werde tun dies mit der Beispielliste: [7, 2, 13, 9].

Die ersten beiden Zahlen sind bereits falsch ( 7 > 2). Wir möchten mit einer Zahl xor, um dieses Ungleichungssymbol zu ändern ( 7 xor X < 2 xor X). Da xor die binären Darstellungen bearbeitet, schauen wir sie uns an.

7 = 1 1 1
2 =   1 0

Wenn wir x oder mit einer Zahl auf jede Zahl anwenden, ändert sich der Wert an einigen Stellen. Wenn Sie die Werte an der ersten Position ändern ( 2^0), ändert sich das Ungleichungssymbol nicht. Das gleiche passiert, wenn wir die Werte an der zweiten Position ändern ( 2^1). Auch wird das Symbol nicht ändern , wenn wir Werte in dem vierten ändern, fünften, ... Positionen ( 2^3, 2^4, ...). Das Ungleichungssymbol ändert nur dann die Richtung, wenn wir die dritte Position ändern ( 2^2).

7 xor 2^0 = 1 1 0   7 xor 2^1 = 1 0 1   7 xor 2^2 =   1 1   7 xor 2^3 = 1 1 1 1
2 xor 2^0 =   1 1   2 xor 2^1 =     0   2 xor 2^2 = 1 1 0   2 xor 2^3 = 1 0 1 0
     6 > 3               5 > 0               3 < 6               15 > 10

Wenn wir mehrere Positionen gleichzeitig ändern, passiert natürlich das Gleiche. Wenn eine der Positionen, die wir ändern, die dritte ist, ändert sich das Ungleichungssymbol, ansonsten nicht.

Das nächste Paar ist bereits sortiert: 2 < 13. Wenn wir uns die Binärdarstellung ansehen, bemerken wir, dass wir nichts dagegen tun können und das Ungleichungssymbol immer noch korrekt ist, außer wenn wir die vierte Position ändern ( 2^3).

 2 =     1 0    2 xor 2^3 = 1 0 1 0
13 = 1 1 0 1   13 xor 2^3 =   1 0 1
   2 < 13            10 > 5

Die vierte Position wollen wir also nicht ändern. Für das nächste Paar wollen wir da etwas ändern 13 > 9. Hier müssen wir wieder die dritte Position wechseln.

13 = 1 1 0 1   13 xor 2^2 = 1 0 0 1
 9 = 1 0 0 1    9 xor 2^2 = 1 1 0 1
   13 > 9            9 < 13

Fazit: Um in eine sortierte Liste zu gelangen, müssen wir erneut die dritte Position und nicht die vierte Position ändern. Alle anderen Positionen spielen keine Rolle. Die kleinste Zahl ist einfach 4 = 0100. Andere Wahlen wären 5 = 0101, 6 = 0110, 7 = 0111, 20 = 10100, 21 = 10101, ...

Xoring mit 4wird in der Liste führen [3, 6, 9, 13], mit 6wird bekommen [1, 4, 11, 15], und mit 21wird bekommen [18, 23, 24, 28].

Für eine Liste müssen wir also die Positionen finden, die das Ungleichungssymbol ändern, wenn es in die falsche Richtung zeigt. Wir finden die Position einfach, indem wir das höchstwertige Bit des xor des Paares nehmen. Wir kombinieren alle diese Positionen (mit oder), um eine Kandidatennummer zu erhalten. Wir prüfen, ob wir die bereits sortierten Paare nicht versehentlich zerstört haben.

Ju.|G^2slHxMf>FT.:Q2Z   implicit: Q = input list
                .:Q2    all substrings of length 2
            f>FT        filter for pairs that are in descending order
          xM            apply xor to each such pair
 u                  Z   reduce this list, start value G = 0
                           iteration value is H
     ^2slH                 2 to the power of floor(logarithm base 2 of H)
                           this gives a mask representing the most significant bit
  .|G                      update G with the bitwise or of G and ^
J                       store the result in J


|tSIxRJQJ   
    xRJQ      xor each element of the input list with J
  SI          check if the list is sorted
 t            subtract 1
|       J     this number or (if equal to zero) J
              implicit print
Jakube
quelle
3
Ich ermahne, dass es eine so saubere und einfache Lösung gibt.
Quintopia
Es wäre fantastisch, wenn Sie erklären könnten, warum dies für diejenigen von uns funktioniert, die mathematisch stumpfer sind. Ich verstehe alle Schritte, verstehe aber nicht ganz, warum das bitweise oder das MSB jedes xor'ed absteigenden Paares der richtige Wert sein wird.
Luke
1
@ Luke Hinzugefügt eine lange Erklärung. Hoffentlich hilft es.
Jakube
Wunderbare Erklärung!
edc65
1
Wenn Sie 2 Binärwerte beibehalten, die Bits, die geändert werden müssen, und die Bits, die nicht geändert werden müssen, erhalten Sie Ihr Endergebnis ohne weitere Iterationen
edc65 31.12.15
15

Ruby 2, 119

->a,*o{a.each_cons(2){|x,y|x==y||o[i=(x^y).bit_length-1]==1-(o[i]=x[i])&&(return-1)};(o.map(&:to_i).reverse*'').to_i 2}

Läuft in 42 Millisekunden auf den großen Testfällen.

Ungolfed:

def first_differing_bit(a,b)
  (a^b).bit_length - 1
end

def xort(ary)
  required_bits = []
  ary.each_cons(2) do |a,b|
    i = first_differing_bit(a,b)
    if i > -1
      bit = a[i]
      if required_bits[i] && required_bits[i] != bit
        return -1
      else
        required_bits[i] = bit
      end
    end
  end
  required_bits.map(&:to_i).reverse.join.to_i(2)
end

Ausnahmsweise habe ich zuerst die ungolfed-Version geschrieben und dann Golf gespielt, da es eine Herausforderung für sich war, den richtigen Algorithmus zu finden.

Ich habe vor ein paar Jahren tatsächlich versucht, so etwas zu schreiben, um eine binäre Baumstruktur zu erstellen, die sich lokal selbst ausgleicht, indem jeder Knoten seine Vergleichsfunktion dynamisch neu definiert. Zuerst dachte ich, ich könnte einfach xor verwenden, aber wie Sie sagen, ist es unwahrscheinlich, dass es einen brauchbaren Wert gibt.

Histokrat
quelle
Gute Lösung, ich mag die Array-Initialisierung und Ruby's Bit [] -Funktion. Aber probieren Sie zum Beispiel die Liste aus [4,4,4], diese gibt einen SyntaxError aus, wenn versucht wird, diese auszuwerten 0b. Glücklicherweise gibt es, wie es mir oft passiert ist, eine andere Möglichkeit, dasselbe in der gleichen Anzahl von Bytes zu tun. Das sollte funktionieren, hoffe ich:->a,*o{a.each_cons(2){|x,y|x==y||o[i=(x^y).bit_length-1]==1-(o[i]=x[i])&&(return-1)};(o.map(&:to_i).reverse*'').to_i 2}
blutorange
In der Tat, schöner Fang!
Histokrat
11

Julia, 174 144 77 75 71

[BEARBEITEN] Danke an Alex A. für die Anonymisierung und verschiedene Shorthands.
[EDIT 2] Ersetzte meine eigene Implementierung durch die eingebaute issorted().

Läuft in linearer Zeit und verarbeitet die großen Dateien ohne merkliche Verzögerung. Funktioniert genauso gut für negative Zahlen.

l->(r=0;s=issorted;for d=63:-1:0 s((l$r).>>d)||(r$=2^d)end;s(l$r)?r:[])

Eine andere Variante, die das Ergebnis berechnet, das einem bestimmten Schlüssel am nächsten kommt (die obige gibt das kleinste zurück).

(l,r)->(s=issorted;for d=63:-1:0 s((l$r).>>d)||(r$=2^d)end;s(l$r)?r:[])

Verwendungszweck:

julia> xort = l->(r=0;s=issorted;for d=63:-1:0 s((l$r).>>d)||(r$=2^d)end;s(l$r)?r:[])
(anonymous function)

julia> xort([4 7 6 1 0 3])
5

Beispiel Schritt für Schritt: [4 7 6 1 0 3] => 5

Start with:
     4  0b0100
     7  0b0111
     6  0b0110
     1  0b0001
     0  0b0000
     3  0b0011
result  0b0000

If the first n bits are sorted, do nothing.
        0b0
        0b0
        0b0
        0b0
        0b0
        0b0
result  0b0000
          ^
If the first n bits are not sorted, flip the nth bit.
        0b01            0b00
        0b01            0b00
        0b01            0b00
        0b00      =>    0b01
        0b00            0b01
        0b00            0b01
result  0b0000          0b0100
           ^               ^
        0b000
        0b001
        0b001
        0b010
        0b010
        0b011
result  0b0100
            ^
        0b0000          0b0001  1
        0b0011          0b0010  2
        0b0010          0b0011  3
        0b0101    =>    0b0100  4
        0b0100          0b0101  5
        0b0111          0b0110  6
result  0b0100          0b0101  5
             ^               ^
If the bit flip does not sort the truncated integers, xorting is
impossible. We continue anyway and check for success in the end.
Rainer P.
quelle
2
71 Bytes:l->(r=0;s=issorted;for d=63:-1:0 s((l$r).>>d)||(r$=2^d)end;s(l$r)?r:[])
Alex A.
8

JavaScript (ES6) 85 97 114 117

Bearbeiten Dummes, nutzloses Letztes entfernt UND
Bearbeiten2 Top-Bit-Suche verkürzt
Bearbeiten3 Wow! Ich entdeckte, dass ES6 (fast) ein eingebautes Bit hat , um das oberste Bit zu finden (Math.clz32 zählt die obersten 0 Bits)

Dies basiert auf der Lösung von @Jakube (bitte stimmen Sie dem zu). Ich hätte es niemals alleine finden können.

Hier gehe ich einen Schritt vorwärts, iteriere die Liste einmal und behalte eine Bitmaske mit den Bits, die umgedreht werden müssen, und eine andere mit den Bits, die beibehalten werden müssen.

Wenn es eine Überlappung der Bitmasken gibt, ist keine Lösung möglich, andernfalls lautet die Lösung "Bits zum Umdrehen".

Da Binäroperationen in Javascript nur für vorzeichenbehaftete 32-Bit-Ganzzahlen funktionieren, ist der Rückgabewert eine vorzeichenbehaftete 32-Bit-Ganzzahl, die negativ oder 0 sein kann.

Wenn es keine Lösung gibt, ist der Rückgabewert 'X'

l=>l.map(v=>(t=v^p&&1<<(31-Math.clz32(v^p)),v>p?k|=t:c|=t,p=v),p=l[c=k=0])&&c&k?"X":c

Prüfung

Die längeren Tests auf Jsfiddle

X=l=>l.map(v=>(t=v^p&&1<<(31-Math.clz32(v^p)),v>p?k|=t:c|=t,p=v),p=l[c=k=0])&&c&k?"X":c

console.log=x=>O.textContent+=x+'\n'
;[
[[4,7,6,1,0,3], 5],
[[4,7,1,6,0,3], 'X'],
[[0,1,3,4,6,7], 0],
[[4,2,3,1], 6], 
[[2,3,0,0,7,7,4,5,11,11], 2],
[[2,3,0,0,7,7,5,4,11,11], 'X'],
[[1086101479,748947367,1767817317,656404978,1818793883,1143500039],'X'],
[[180522983,1885393660,751646477,367706848,331742205,724919510,850844696,2121330641,869882699,1831158987,542636180,1117249765,823387844,731663826,1762069894,240170102,1020696223,1212052937,2041219958,712044033,195249879,1871889904,1787674355,1849980586,1308879787,1743053674,1496763661,607071669,1987302942,178202560,1666170841,1035995406,75303032,1755269469,200581873,500680130,561748675,1749521426,1828237297,835004548,934883150,38711700,1978960635,209243689,1355970350,546308601,590319412,959613996,1956169400,140411967,112601925,88760619,1977727497,672943813,909069787,318174568,385280382,370710480,809689639,557034312,865578556,217468424,346250334,388513751,717158057,941441272,437016122,196344643,379529969,821549457,97008503,872313181,2105942402,603939495,143590999,1580192283,177939344,853074291,1288703007,1605552664,162070930,1325694479,850975127,681702163,1432762307,1994488829,780869518,4379756,602743458,1963508385,2115219284,1219523498,559301490,4191682,1918142271,169309431,346461371,1619467789,1521741606,1881525154],'X'],
[[37580156,64423492,87193676,91914964,93632157,96332899,154427982,176139560,184435039,228963836,230164674,279802291,301492375,309127664,345705721,370150824,380319820,403997410,410504675,416543032,418193132,424733526,428149607,435596038,477224208,515649925,519407995,525469350,614538124,624884850,642649261,653488151,679260270,685637235,690613185,739141066,825795124,832026691,832633584,833213619,852655299,913744258,917674993,921902522,925691996,931307936,954676047,972992595,997654606,1020009811,1027484648,1052748108,1071580605,1108881241,1113730139,1122392118,1154042251,1170901568,1180031842,1180186856,1206428383,1214066097,1242934611,1243983997,1244736049,1262979035,1312007069,1312030297,1356274316,1368442960,1377432523,1415342434,1471294243,1529353536,1537868913,1566069818,1610578189,1612277199,1613646498,1639183592,1668015280,1764022840,1784234921,1786654280,1835593744,1849372222,1875931624,1877593764,1899940939,2007896363,2023046907,2030492562,2032619034,2085680072,2085750388,2110824853,2123924948,2131327206,2134927760,2136423634],0],
[[1922985547,1934203179,1883318806,1910889055,1983590560,1965316186,2059139291,2075108931,2067514794,2117429526,2140519185,1659645051,1676816799,1611982084,1736461223,1810643297,1753583499,1767991311,1819386745,1355466982,1349603237,1360540003,1453750157,1461849199,1439893078,1432297529,1431882086,1427078318,1487887679,1484011617,1476718655,1509845392,1496496626,1583530675,1579588643,1609495371,1559139172,1554135669,1549766410,1566844751,1562161307,1561938937,1123551908,1086169529,1093103602,1202377124,1193780708,1148229310,1144649241,1257633250,1247607861,1241535002,1262624219,1288523504,1299222235,840314050,909401445,926048886,886867060,873099939,979662326,963003815,1012918112,1034467235,1026553732,568519178,650996158,647728822,616596108,617472393,614787483,604041145,633043809,678181561,698401105,776651230,325294125,271242551,291800692,389634988,346041163,344959554,345547011,342290228,354762650,442183586,467158857,412090528,532898841,534371187,32464799,21286066,109721665,127458375,192166356,146495963,142507512,167676030,236532616,262832772],1927544832],
[[1922985547,1934203179,1883318806,1910889055,1983590560,1965316186,2059139291,2075108931,2067514794,2117429526,2140519185,1659645051,1676816799,1611982084,1736461223,1810643297,1753583499,1767991311,1819386745,1355466982,1349603237,1360540003,1453750157,1461849199,1439893078,1432297529,1431882086,1427078318,1487887679,1484011617,1476718655,1509845392,1496496626,1583530675,1579588643,1609495371,1559139172,1554135669,1549766410,1566844751,1562161307,1561938937,1123551908,1086169529,1093103602,1202377124,1193780708,1148229310,1144649241,1257633250,1241535002,1247607861,1262624219,1288523504,1299222235,840314050,909401445,926048886,886867060,873099939,979662326,963003815,1012918112,1034467235,1026553732,568519178,650996158,647728822,616596108,617472393,614787483,604041145,633043809,678181561,698401105,776651230,325294125,271242551,291800692,389634988,346041163,344959554,345547011,342290228,354762650,442183586,467158857,412090528,532898841,534371187,32464799,21286066,109721665,127458375,192166356,146495963,142507512,167676030,236532616,262832772],'X']
].forEach(t=>{
  var i=t[0],k=t[1],r=X(i)
  console.log((k==r?'OK ':'Error (expected '+k+') ')+r+' for input '+i)
})
<pre id=O></pre>
Erweitern Sie das Snippet

edc65
quelle
8

ES6, 84 Bytes

a=>(i=e=0,a.reduce((x,y)=>(z=1<<31-Math.clz32(x^y),x>y?i|=z:y>x?e|=z:z,y)),i&e?-1:i)

Bearbeiten: Als ich zum Schreiben der Antwort brauchte, wurde der Algorithmus bereits von @Jakube unabhängig veröffentlicht. Mein Algorithmus ist derselbe, aber das war kein ehrliches Plagiat! Außerdem stelle ich fest, dass seitdem auch eine andere JavaScript-Antwort gepostet wurde. Tut mir leid, wenn ich jemandem auf die Zehen trete.

Bearbeiten: 8 Bytes dank edc65 gespeichert.

Neil
quelle
Sie treten niemandem auf die Zehen. Das ist eine gute Antwort, gute Arbeit. :)
Alex A.
Schön, dass du @ edc65 geschlagen hast! Das passiert so gut wie nie.
Mama Fun Roll
Du hast meine Stimme. Ich denke, Sie sollten auch die clz32-Funktion verwenden, um mich wieder zu schlagen.
edc65
Wenn nur 1<<31>>>32Null wäre, könnte ich weitere 4 Bytes speichern.
Neil
5

C 144 Bytes

#include <strings.h>
#include <stdio.h>
m[2],l,i;main(v){while(scanf("%d",&v)==1)m[l<v]|=(i++&&v^l)<<~-fls(v^l),l=v;printf("%d",*m&m[1]?-1:*m);}

Dies ist fast Standard-C99 (es fehlen einige intBezeichner und es gibt 1 Argument für main). Es hängt auch davon ab 0<<-1, 0 zu sein (was zumindest bei der Kompilierung mit Clang zutrifft - andere habe ich nicht getestet).

Ich habe die Methode von Jakube übernommen und auf C portiert. Ich denke, dass sie für C überraschend gut geeignet ist. Sie ist auch superschnell (0.061s, um alle Testdateien auszuführen, einschließlich der massiven 4). Es nimmt Eingaben von STDIN entgegen und gibt den passenden Wert oder -1 an STDOUT aus. Führen Sie ihn also mit einem der folgenden Befehle aus:

echo "4 7 6 1 0 0 3" | ./xort
./xort < file.txt

Nervenzusammenbruch:

// Globals initialise to 0
m[2],                                    // Stores our bit masks
                                         // (m[0]=CHANGE, m[1]=MUST NOT CHANGE)
l,                                       // Last value
i;                                       // Current iteration
main(v){
    while(scanf("%d",&v)==1)             // Read each value in turn
        m[l<v]|=                         // If they are sorted, we mark a bit as
                                         // MUST NOT CHANGE (m[1]), otherwise we
                                         // mark as CHANGE (m[0])
                (i++&&v^l)               // If this is the first iteration,
                                         // or the value is unchanged, mark nothing
                          <<~-fls(v^l),  // Mark the highest bit which has changed
                                         // = (1<<(fls(v^l)-1)
        l=v;                             // Update last value
    printf("%d",
                *m&m[1]                  // Check if result is valid (if any bits
                                         // are both MUST NOT CHANGE and CHANGE,
                                         // it is not valid)
                       ?-1               // Print -1 on failure
                          :*m);          // Print value on success
}
Dave
quelle
4

Julia, 124 Bytes

f(x,g=0)=issorted(([g|=2^Int(log2(h)÷1)for h=map(k->k[1]$k[2],filter(j->j[1]>=j[2],[x[i-1:i]for i=2:endof(x)]))];g)$x)?g:-1

Dies ist eine Funktion, die ein Integer-Array akzeptiert und eine Ganzzahl zurückgibt. Es benutzt Jakubes Ansatz .

Ungolfed:

function f{T<:Integer}(x::Array{T,1}, g::T=0)
    # Get all pairs of elements in the input array
    pairs = [x[i-1:i] for i = 2:endof(x)]

    # Filter to pairs in descending order
    desc = filter(j -> j[1] ≥ j[2], pairs)

    # Map XOR over these pairs
    xord = map(k -> k[1] $ k[2], desc)

    # For each element of this array, update the
    # parameter g (which defaults to 0) as the
    # bitwise OR of itself and 2^floor(log2(element))
    for h in xord
        g |= 2^Int(log2(h) ÷ 1)
    end

    # If the array constructed as g XOR the input is
    # sorted, we've found our answer! Otherwise -1.
    return issorted(g $ x) ? g : -1
end
Alex A.
quelle
Warum ist XOR aus Neugier $?
Caird Coinheringaahing
3

Python 2, 204 Bytes

def f(a):
 m=n=0
 for i in range(32):
  b=2**(31-i);m|=b
  for n in[n,n|b]:
   if not q(a,m,n):break
  else:return-1
 return n
def q(a,m,n):
 if a:p=a[0]&m^n
 for t in a:
  t=t&m^n
  if t<p:return 1
  p=t

Die Eingabe wird als Liste an die Funktion f übergeben.

Dieser Code berechnet bitweise den Wert von N (im Programm mit n bezeichnet), beginnend mit dem höchstwertigen Bit. (die "for i" -Schleife)

Für jede Bitposition versucht die "für n" -Schleife zuerst, 0 für dieses Bit von n zu verwenden. Wenn das nicht funktioniert, wird versucht, 1 zu verwenden. Wenn keines dieser Verfahren funktioniert, gibt es keine Lösung. Beachten Sie, dass sich die else-Klausel in der "for n" -Schleife befindet, nicht in der if-Anweisung. In Python kann eine for-Anweisung eine else-Klausel enthalten, die ausgeführt wird, nachdem die Schleife vollständig ausgeführt wurde , aber nicht ausgeführt wird, wenn wir die Schleife verlassen.

Die q-Funktion prüft anhand der Liste (a), einer Bitmaske (m) und des Wertes, der mit jedem Wert in der Liste (n) gespeichert werden soll, auf Probleme mit der Listenreihenfolge. Es gibt 1 zurück, wenn ein Problem mit der Bestellung vorliegt, oder None, wenn die Bestellung in Ordnung ist. Keiner ist der Standardrückgabewert, sodass ich mehrere Zeichen gespeichert habe.

Dieser Code behandelt eine leere Liste oder eine Liste mit 1 Element korrekt und gibt 0 zurück. Das "if a:" in Funktion q dient nur dazu, eine IndexError-Ausnahme zu vermeiden, wenn die Liste leer ist. Es könnten also 5 weitere Bytes entfernt werden, wenn die Behandlung leerer Listen nicht erforderlich ist.

Auf meinem Computer dauerte der große Testfall Nr. 3 0,262 Sekunden. # 2 dauerte ungefähr das gleiche. Alle Testfälle zusammen dauerten 0,765 Sekunden.

Gary Culp
quelle
1
Der Umgang mit leeren Listen ist nicht erforderlich, das kläre ich.
Martin Ender
3

CJam, 37 Bytes

q~_2ew{:>},{:^2mLi2\#}%0+:|_@f^_$=\W?

Teste es hier.

Dabei wird derselbe Algorithmus wie bei mehreren anderen Antworten verwendet. Es ist im Wesentlichen meine Referenzimplementierung, mit der ich die Testfälle erstellt habe. Allerdings habe ich Jakubes Trick gestohlen, nur die beleidigenden Paare zu überprüfen und das Ergebnis einfach mit einer Sortierung auszuprobieren. Das bricht die Pseudolinearität, aber O (n log n) ist immer noch schnell genug für die Testfälle. Mein ursprünglicher Code überprüfte auch die Paare, die bereits in Ordnung sind, und erstellte eine Liste von Bits, die nicht umgeschaltet werden dürfen, um ihre relative Reihenfolge beizubehalten, und überprüfte am Ende, dass es keine Überlappungen zwischen den beiden Bitmasken gibt. Dieser Algorithmus wurde ursprünglich von Ben Jackson vorgeschlagen .

Martin Ender
quelle
2

Python 2, 226 214 Bytes

Einfacher Algorithmus, gestern gebaut, heute golfen.

o=input()
s=sorted
p=s(set(o),key=o.index)
n=q=0
while 1:
 a=1
 while 1-q and p[0]<p[1]:p=p[1:];q=len(p)==1
 if q:break
 while not p[0]^a<p[1]^a:a*=2
 n+=a;p=[i^a for i in p]
t=[a^n for a in o]
print[-1,n][s(t)==t]

Ungolfed:

def xor(a,b): return a^b

def rm_dupes(seq):
    seen = set()
    seen_add = seen.add
    return [x for x in seq if not (x in seen or seen_add(x))]

def rm_sorted(seq):
    while seq[0] < seq[1]:
        seq = seq[1:]
        if len(seq) == 1: return seq
    return seq

inp = input()
oi = inp

inp = rm_dupes(inp)
n=0
old_inp=0
while old_inp != inp:
    old_inp = inp
    inp = rm_sorted(inp)
    if len(inp)==1:break
    highest_set0 = len(bin(inp[0]))-3 # bin returns in form 0bxxx
    highest_set1 = len(bin(inp[1]))-3 # bin returns in form 0bxxx
    if highest_set1 == 0:
        try:
            t0 = max(int(bin(inp[0])[3:], 2), 1)
        except ValueError: toggle_amount = 1
        else: toggle_amount = t0^inp[0]
    else:
        fallen = False
        for i in xrange(max(highest_set0,highest_set1)+1):
            toggle_amount = 2**i
            if inp[0]^toggle_amount < inp[1]^toggle_amount:
                fallen = True
                break
        assert(fallen)
    n+=toggle_amount
    inp = [i^toggle_amount for i in inp]

out=map(xor, oi, [n]*len(oi))
if sorted(out)==out :print n
else:print -1
Blau
quelle
2

C 312 Bytes

#define R return
t,i,*b;f(int*a,int l,int k){int s=a[0]>>k&1,j=-1,i=1;if(k<0)R 0;for(;i<l;++i){t=a[i]>>k&1;if(s!=t)if(j<0)j=i,s=t;else R 1;}if(j<0)R f(a,l,k-1);else{if(s+b[k]==2)R 1;b[k]=s+1;R f(a,j,--k)||f(a+j,l-j,k);}}h(int*a,int l){int c[32]={0};b=c;if(f(a,l,30))R -1;t=0;for(i=0;i<32;++i)t|=(b[i]&1)<<i;R t;}

Definiert eine Funktion, h(int*a,int l)die einen Zeiger auf ein Array und seine Länge nimmt. Hier ist ein Testprogramm-Gigant.

Leicht ungolfed:

int t, i, *b;

int f(int * a, int l, int k) {
    int s = a[0] >> k & 1;
    int j = -1;
    int i = 1;
    if (k < 0) return 0;
    for (; i < l; ++i) {
        t = a[i] >> k & 1;
        if (s != t) {
            if (j < 0) {
                j = i;
                s = t;
            } else return 1;
        }
    }
    if (j < 0) {
        return f(a, l, k - 1);
    } else {
        if (s + b[k] == 2) return 1;
        b[k] = s + 1;
        return f(a, j, --k) || f(a + j, l - j, k);
    }
}

int h(int * a, int l) {
    int c[32] = {0};
    b = c;
    if (f(a, l, 30)) return -1;
    t = 0;
    for (i = 0; i < 32; ++i) {
        t |= (b[i] & 1) << i;
    }
    return t;
}
jcai
quelle
2

Mathematica, 99 97 Zeichen

Vielen Dank an Martin Büttner für Ratschläge.

x@l_:=If[OrderedQ[l~BitXor~#],#,-1]&@Fold[#+#2Boole@!OrderedQ@⌊l~BitXor~#/#2⌋&,0,2^32/2^Range@32]

Erläuterung:

Wir werden mehrere Änderungsversuche durchführen N beginnend mit Null, und einen Test durchführen, um den Kandidaten zu validieren N.

Schritt 1. Wir erhalten diese Zahlen (32-Bit-Ganzzahlen) durch N( = 0jetzt) "xor" und dividiert durch 2^31:⌊l~BitXor~#/#2⌋ . Es gibt drei Fälle:

  • bestellt, zB {0, 0, 1, 1, 1, 1, 1, 1} ;
  • korrigiert werden kann, z {1, 1, 1, 1, 0, 0, 0, 0} ;
  • sonst zb {0, 0, 1, 0, 0, 1, 1, 1} .

Wir tun nichts Nfür den ersten Fall, oder wir hinzufügen , 2^31um Nden Auftrag für den zweiten Fall zu korrigieren: #+#2Boole@!OrderedQ@.... Während es für den dritten Fall unmöglich ist, die Liste zu xortieren, was auch immer wir tun, fügen wir dies einfach hinzu2^31 zu der NEinfachheit halber (oder irgendetwas!).

Schritt 2. Wir bekommen diese Zahlen "xor" Nund dividiert durch 2^30. Es gibt wieder drei Fälle:

  • bestellt, zB{0, 1, 2, 2, 2, 2, 3, 3} ;
  • kann korrigiert werden, zB{1, 1 , 0, 0, 3, 2, 2, 2} ;
  • sonst zb{3, 3, 1, 3, 2, 0, 1, 0} .

Wir tun nichts Nfür den ersten Fall, oder wir hinzufügen , 2^30um Nden Auftrag für den zweiten Fall zu korrigieren. Ansonsten erkennen wir , dass xorting unmöglich ist, so dass wir nur hinzufügen , 2^30um Nwieder der Einfachheit halber.

Schritt 3 ~ 32. Wir bekommen rekursiv diese Zahlen „xor“ ed durch Nund dividiert durch 2^29, 2^28, ..., 2^0. Und mache ähnliche Dinge:Fold[...,0,2^32/2^Range[32]]

Schritt 33. Jetzt haben wir endlich einen Kandidaten N. If[OrderedQ[l~BitXor~#],#,-1]&wird verwendet, um zu überprüfen, ob solche Ntatsächlich die Liste xortieren. Wenn die Liste für einige unpassend sein kann N, ist es nicht schwierig zu beweisen, dass wir immer auf den ersten oder zweiten Fall stoßen werden.

njpipeorgan
quelle
2

Perl 6 , 79 Bytes

Wenn es kein Zeitlimit gäbe, wäre der kürzeste Perl 6-Code wahrscheinlich

{first {[<=] $_ X+^@_},^2*.max} # 31 bytes

Stattdessen muss ich etwas schlaueres tun.
Da ich eine Weile gebraucht habe, um darauf zurückzukommen, gab es bereits eine Antwort , die einen guten Algorithmus und die Gründe dafür beschreibt.

{$/=0;for @_.rotor(2=>-1) ->(\a,\b){b>=a or$/+|=2**msb a+^b};$/if [<=] $/X+^@_} # 79
{
  # cheat by using a special variable
  # so there is no need to declare it
  $/=0;

  # takes the elements two at a time, backing up one
  for @_.rotor(2=>-1)
    # since that is a non-flat list, desugar each element into 2
    # terms
    ->(\a,\b){
      # if they are not sorted
      b>=a or
      # take the most significant bit of xoring the two values
      # and numeric or ｢+|｣ it into ｢$/｣
      $/+|=2**msb a+^b
    };


  # returns ｢$/｣ if the list is Xorted
  # otherwise returns Empty
  $/if [<=] $/X+^@_

  # ｢ $/ X[+^] @_ ｣
  # does numeric xor ｢+^｣ between ｢$/｣
  # and each element of the original list ｢@_｣
}

Verwendungszweck:

# give it a lexical name for ease of use
my &code = {...}

say code [8,4,3,2,1];     # 15

say code [4,7,6,1,0,3]; # 5
say code [4,7,1,6,0,3]; # ()
say code [0,1,3,4,6,7]; # 0
say code [4,2,3,1];     # 6
say code [2,3,0,0,7,7,4,5,11,11]; # 2
say code [2,3,0,0,7,7,5,4,11,11]; # ()
say code [1086101479,748947367,1767817317,656404978,1818793883,1143500039]; # ()

# the example files
for 'testfiles'.IO.dir.sort».comb(/«\d+»/) {
  printf "%10s in %5.2f secs\n", code( @$_ ).gist, now - ENTER now;
}
#         () in  9.99 secs
#          0 in 11.70 secs
# 1096442624 in 13.54 secs
#         () in 11.44 secs
Brad Gilbert b2gills
quelle
1

Mathematica 650 415 194 Bytes

Diese Herausforderung half mir, einiges darüber zu verstehen, woran Xorich nie gedacht hatte. Es hat lange gedauert, den Code zu optimieren, aber die Mühe hat sich gelohnt.

BitXorFunktioniert direkt auf Basis 10 Zahlen. Dadurch wurde der Code gegenüber früheren Versionen erheblich reduziert.

Die Logik ist einfach. Man arbeitet nicht mit Zahlenpaaren (wie es manche Einreichungen taten), sondern mit dem kompletten Satz von Zahlen nach dem SeinBitXor mit dem aktuellen "Schlüssel" bearbeitet hat.

Beginnen Sie mit einer vorläufigen Lösung oder einem "Schlüssel" von Null, dh alle Bits sind Null. Wenn die ursprünglichen nZahlen BitXormit Null bearbeitet werden, werden sie unverändert zurückgegeben. Korrelieren Sie die Reihenfolge der Zahlen mit dem Bereich 1, 2, ...n, der eine perfekt geordnete Liste darstellt. Die Korrelation mit einem Wert zwischen -1 und 1 gibt an, wie gut die Zahlen geordnet sind.

Setzen Sie dann das Hi-Bit, beziehen Sie den neuen Schlüssel und BitXorden Schlüssel mit dem aktuellen Satz von Zahlen. Wenn die Korrelation zwischen der neuen Zahlenfolge und der perfekt geordneten Liste eine Verbesserung darstellt, lassen Sie das Bit gesetzt. Wenn nicht, lassen Sie das Bit nicht gesetzt.

Gehen Sie auf diese Weise vom Hi-Bit zum Low-Bit vor. Wenn die beste Korrelation 1 ist, ist der Schlüssel die Lösung. Wenn nicht, ist es -1.

Es gibt Möglichkeiten, den Code ein bisschen effizienter zu gestalten, indem Sie beispielsweise den Prozess unterbrechen, sobald eine Lösung gefunden wird. Dies würde jedoch mehr Codierung erfordern, und der derzeitige Ansatz ist sehr schnell. (Der letzte und längste Testfall dauert 20 ms.)

c@i_:=Correlation[Ordering@i,Range[Length[i]]]//N;
t@{i_,k_,b_,w_}:=(v= c@BitXor[i,m=k+2^(b-1)];{i,If[v>w,m,k],b-1,v~Max~w})
g@i_:= (If[#4==1,#2,-1] &@@Nest[t,{i,0,b=1+Floor@Log[2,Max@i],x=c@i},b])

g[{4, 7, 6, 1, 0, 3}]

5

g[{4, 7, 1, 6, 0, 3}]

-1 

g2@{0, 1, 3, 4, 6, 7}

0

g@{1922985547, 1934203179, 1883318806, 1910889055, 1983590560, 1965316186,2059139291, 2075108931, 2067514794, 2117429526, 2140519185, 1659645051, 1676816799, 1611982084, 1736461223, 1810643297, 1753583499, 1767991311, 1819386745, 1355466982, 1349603237, 1360540003, 1453750157, 1461849199, 1439893078, 1432297529, 1431882086, 1427078318, 1487887679, 1484011617, 1476718655, 1509845392, 1496496626, 1583530675, 1579588643, 1609495371, 1559139172, 1554135669, 1549766410, 1566844751, 1562161307,1561938937, 1123551908, 1086169529, 1093103602, 1202377124, 1193780708, 1148229310, 1144649241, 1257633250, 1247607861, 1241535002, 1262624219, 1288523504, 1299222235,840314050, 909401445, 926048886, 886867060, 873099939, 979662326,963003815, 1012918112, 1034467235, 1026553732, 568519178, 650996158,647728822, 616596108, 617472393, 614787483, 604041145, 633043809, 678181561, 698401105, 776651230, 325294125, 271242551, 291800692, 389634988, 346041163, 344959554, 345547011, 342290228, 354762650, 442183586, 467158857, 412090528, 532898841, 534371187, 32464799, 21286066, 109721665, 127458375, 192166356, 146495963, 142507512, 167676030, 236532616, 262832772}

1927544832

DavidC
quelle
1

Add ++ , 125 119 Bytes

D,g,@@,BxBBBDbU1€oB]BJ2$Bb1+
D,j,@,bUBSVcGbU£{g}B]BkAbUBSVcGbU£>B]BKBcB*¦Bo2/i
L!,B#a=
D,f,?!,{j}Vad{j}BF€Bx1]G$0=-1$Qp

Probieren Sie es online!

Ich bin wirklich stolz darauf, dass Add ++ dies kann und nicht die längste Lösung hier ist

Deklariert eine Funktion f, die jedes Element als separates Argument verwendet (zB $f>4>2>3>1)

Wie es funktioniert

Schnallt euch an, es wird eine lange Fahrt

D,g,@@,		; Declare a function 'g'
		; Example arguments: 		[4 7]
	Bx	; Xor;			STACK = [3]
	BB	; To binary;		STACK = [11]
	BD	; Digits;		STACK = [[1 1]]
	bU	; Unpack;		STACK = [1 1]
	1€o	; Replace 0s with 1s;	STACK = [1 1]
	B]	; Wrap;			STACK = [[1 1]]
	BJ	; Concatenate;		STACK = ['11']
	2$Bb	; From binary;		STACK = [3]
	1+	; Increment;		STACK = [4]
		;			Return   4

D,j,@,		; Declare a function 'j'
		; Example argument:		[[4 7 6 1 0 3]]
	bU	; Unpack;		STACK = [4 7 6 1 0 3]
	BS	; Overlapping pairs;	STACK = [4 7 6 1 0 3 [[4 7] [4 6] [6 1] [1 0] [0 3]]]
	VcG	; Keep first element;	STACK = [[[4 7] [4 6] [6 1] [1 0] [0 3]]]
	bU	; Unpack;		STACK = [[4 7] [4 6] [6 1] [1 0] [0 3]]
	£{g}	; Apply 'g' over each;	STACK = [4 2 8 2 4]
	B]	; Wrap;			STACK = [[4 2 8 2 4]]
	Bk	; Global save;		STACK = []		; GLOBAL = [4 2 8 2 4]
	A	; Push arguments;	STACK = [[4 7 6 1 0 3]]
	bU	; Unpack;		STACK = [4 7 6 1 0 3]
	BSVcGbU	; Overlapping pairs;	STACK = [[4 7] [4 6] [6 1] [1 0] [0 3]]
	£>	; Greater than each;	STACK = [0 1 1 1 0]
	B]	; Wrap;			STACK = [[0 1 1 1 0]]
	BK	; Global get;		STACK = [[0 1 1 1 0] [4 2 8 2 4]]
	BcB*	; Products;		STACK = [[0 2 8 2 0]]
	¦Bo	; Reduce by logical OR;	STACK = [10]
	2/i	; Halve;		STACK = [5]
		;			Return   5

L!,		; Declare 'lambda 1'
		; Example argument:		[[1 2 3 4 5]]
	B#	; Sort;			STACK = [[1 2 3 4 5]]
	a=	; Equal to argument;	STACK = [1]
		; 			Return   1

D,f,?!,		; Declare a function 'f'
		; Example arguments:		[[4 7 6 1 0 3]]
	{j}	; Call 'j';		STACK = [5]
	V	; Save;			STACK = []		; REGISTER = 5
	ad	; Push arguments twice;	STACK = [[4 7 6 1 0 3] [4 7 6 1 0 3]]
	{j}	; Call 'j';		STACK = [[4 7 6 1 0 3] 5]
	BF	; Flatten;		STACK = [4 7 6 1 0 3 5]
	€Bx	; Xor each with 5;	STACK = [1 2 3 4 5 6]
	1]	; Call 'lambda 1';	STACK = [1]
	G$	; Retrieve REGISTER;	STACK = [5 1]
	0=	; If equal to 0:
	-1$Q	;   Return -1
	p	; Else, pop condition;	STACK = [5]
		;			Return   5
Caird Coinheringaahing
quelle
1

Stax , 29 Bytes

¬√▬ⁿ{j╔■α√ï(íP♫_z(.▀ng▒JU↨@b┬

Online ausführen und debuggen!

Verwendet die @ RainerP.-Lösung (hat den Flip-Bit-Teil unabhängig entwickelt, verwendet aber den 32rrTeil)

Lineare Zeitkomplexität.

Verwendet die entpackte Version, um zu erklären.

32rr{|2Y;{y/m:^!c{,{y|^m~}Mm,:^ud:b
32rr                                   Range [32,31..0]
    {                      m           Map each number `k` in the range with
     |2Y                                   `2^k`
        ;{y/m                              Map each number `l` in the input to `floor(l/2^k)`
             :^!                           The mapped array is not non-decreasing
                                           This is the binary digit `l` is mapped to
                c{       }M                If that's true, do
                  ,{y|^m~                  Flip the corresponding bit of every element in the input
                            ,:^        The final array is sorted
                               ud      Take inverse and discard, if the final array is not sorted this results in zero-division error
                                 :b    Convert mapped binary to integer
Weijun Zhou
quelle