Conceptuellement, ce défi est très simple. On vous donne une liste d'entiers non négatifs . Si possible, recherchez un entier non négatif , tel que la liste en est triée. Si tel n’est pas le cas , la sortie doit contenir tout ce qui ne peut être confondu avec une valeur valide , par exemple un nombre négatif, rien du tout, une erreur, etc.aiNbi = ai XOR NNN

Voici un exemple:

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

Si nous prenons chaque élément de cette liste XOR 5, nous obtenons

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

qui est trié. (Notez qu'il n'est pas nécessaire que la liste résultante comporte des éléments uniques et ne contient aucun espace. Si le résultat d'une telle opération était [0, 1, 1, 3]toujours valide, il serait valide.) D'autre part pour la liste

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

aucun tel Nn'existe.

Vous pouvez écrire un programme ou une fonction en prenant l’entrée via STDIN (ou l’alternative la plus proche), un argument de ligne de commande ou une argumentation de fonction et en générant le résultat via STDOUT (ou l’alternative la plus proche), une valeur de retour de fonction ou un paramètre de fonction (out).

L'entrée peut être dans n'importe quelle liste ou format de chaîne. Vous pouvez supposer qu’ils sont inférieurs à chacun et que la liste contient au moins un élément.ai231

Votre code doit traiter tous les cas de test (en particulier les quatre grands) en quelques secondes.

Les règles standard de code-golf s'appliquent.

Cas de test

Pour chaque cas de test qui ne revient pas, -1il existe un nombre infini de réponses correctes. Celui énuméré ici est le plus petit. Des solutions supplémentaires existent en définissant en plus des bits qui sont identiques pour tous les entiers de l’entrée (notamment ceux qui sont plus grands que le bit le plus significatif dans le plus grand nombre de la 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

Enfin, voici quatre très grands cas tests pour garantir que les soumissions sont suffisamment efficaces:

• Le cas de test 1 devrait céder -1.
• Le cas de test 2 devrait céder 0.
• Le cas de test 3 devrait céder 1096442624.
• Le cas de test 4 devrait céder -1.

Pourquoi quelqu'un ferait-il cela?

L'autre jour, je me suis dit qu'une opération XOR peut "trier" un tableau, ce qui permet d'effectuer une recherche binaire sur le tableau dans O (log n) sans avoir à le trier auparavant. Il semble possible de déterminer Nen temps pseudolinéaire, ce qui en ferait une alternative plus rapide à la plupart des algorithmes de tri, et il n’a pas les besoins en mémoire du tri de base. Bien entendu, une recherche linéaire directe dans le tableau non trié sera plus rapide, mais si vous souhaitez effectuer plusieurs recherches dans le même tableau, un seul pré-calcul linéaire peut réduire considérablement le temps requis pour chaque recherche.

Malheureusement, la classe de listes sur laquelle elle fonctionne est plutôt limitée (des distributions uniformément aléatoires ont peu de chances d’admettre une N).

Une question intéressante est de savoir s'il existe d'autres fonctions bijectives plus faciles à vérifier et / ou applicables à une classe de listes plus étendue.

Gelée, 25 octets

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

Les dernières mises à jour postérieures à ce défi, mais le code ci-dessus fonctionne avec cette révision , qui la précède. Essayez-le en ligne!

Pour exécuter les cas de test volumineux, selon votre shell, il peut être nécessaire d’envelopper le code ci-dessus dans un programme qui lit les entrées de STDIN. Essayez-le en ligne!

Cas de test

$ 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

Idée

Ceci utilise la même approche que la réponse de @ Jakube , mais mon implémentation est un peu différente.

Jelly n'a pas encore de tri. Nous calculons donc un candidat xorting, XOR la ​​liste d'entrées avec elle, ainsi qu'un candidat xorting de la liste XORed et vérifions si le nouveau candidat est zéro. Si c'est le cas, nous imprimons le premier candidat; sinon, nous imprimons -1 .

En outre, Jelly ne semble pas avoir encore de moyen sain de convertir un entier en entier (même une division entière peut renvoyer des flottants), je devais donc trouver un moyen plutôt créatif d’arrondir une liste de nombres à la puissance suivante de 2 . Plutôt que de log-floor-pow, je convertis tous les entiers en binaires, remplace tous les chiffres binaires par 1 , les reconvertis en entier, ajoute 1 et divise par 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.

Pyth, 40 36 31 30 octets

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

Essayez-le en ligne: démonstration ou suite de tests

Chacun des gros cas de test se termine en quelques secondes.

Explication:

Je vais d'abord expliquer la méthode et pourquoi cela fonctionne. Je vais le faire avec la liste d'exemples: [7, 2, 13, 9].

Les deux premiers nombres sont déjà faux ( 7 > 2). Nous voulons utiliser un nombre pour changer ce symbole d’inégalité ( 7 xor X < 2 xor X). Puisque xor opère sur les représentations binaires, regardons-les.

7 = 1 1 1
2 =   1 0

Lorsque nous appliquons xor avec un certain nombre à chaque nombre, la valeur à certains emplacements changera. Si vous modifiez les valeurs à la première position ( 2^0), le symbole d'inégalité ne change pas. La même chose se produit lorsque nous modifions les valeurs à la deuxième position ( 2^1). De plus , le symbole ne changera pas si on change les valeurs à la quatrième, cinquième, ... positions ( 2^3, 2^4...). Le symbole d'inégalité ne change de direction que si nous modifions la troisième position ( 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

Si nous changeons plusieurs positions à la fois, bien sûr, la même chose se produit. Si l'une des positions que nous changeons est la troisième, le symbole d'inégalité change, sinon, pas.

La paire suivante est déjà triée: 2 < 13. Si nous regardons la représentation binaire, nous remarquons que nous pouvons tout corriger ou que le symbole d’inégalité est toujours correct, sauf lorsque nous changeons la quatrième position ( 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

Donc, nous ne voulons pas changer la quatrième position. Pour la paire suivante, nous voulons changer quelque chose, depuis 13 > 9. Ici encore, nous devons changer la troisième position.

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

Récapitulons maintenant: pour finir dans une liste triée, nous devons encore changer la troisième position et ne pas vouloir changer la quatrième position. Toutes les autres positions ne comptent pas. Le plus petit nombre est simplement 4 = 0100. D' autres choix seraient 5 = 0101, 6 = 0110, 7 = 0111, 20 = 10100, 21 = 10101, ...

Xoring avec 4entraînera dans la liste [3, 6, 9, 13], avec 6obtiendra [1, 4, 11, 15], et avec 21obtiendra [18, 23, 24, 28].

Donc, pour une liste, nous devons trouver les positions, cela changera le symbole d'inégalité s'il pointe dans la mauvaise direction. Nous trouvons la position simplement en prenant le bit le plus significatif du xor de la paire. Nous combinons toutes ces positions (avec ou) pour aboutir à un numéro de candidat. Nous vérifions si nous n'avons pas accidentellement détruit les paires déjà triées.

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

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}

S'exécute en 42 millisecondes sur les grands cas de test.

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

Pour une fois, j’ai tout d’abord écrit la version non-lingue, puis j’ai joué au golf car trouver le bon algorithme était un défi en soi.

En fait, j’ai essayé d’écrire quelque chose comme cela il ya quelques années pour créer une arborescence binaire qui s’équilibrerait localement en laissant chaque nœud redéfinir sa fonction de comparaison de manière dynamique. Au début, je pensais pouvoir utiliser simplement xor, mais comme vous le dites pour les données aléatoires, il est peu probable que cette valeur soit viable.

Julia, 174 144 77 75 71

[EDIT] Merci à Alex A. pour l'anonymisation et divers raccourcis.
[EDIT 2] Remplacé ma propre implémentation par la commande intégrée issorted().

Fonctionne en temps linéaire et gère les gros fichiers sans retard notable. Fonctionne aussi bien pour les nombres négatifs.

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

Une autre variante qui calcule le résultat le plus proche d’une clé donnée (la plus haute renvoie le plus petit).

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

usage:

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

Exemple, étape par étape: [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.

JavaScript (ES6) 85 97 114 117

Edit Supprimé stupide, inutile dernier ET
Edit2 Recherche bit peu abrégé
Edit3 Wow! J'ai découvert que ES6 (ou presque) a une fonction intégrée pour trouver le bit du haut (Math.clz32 compte les 0 bits du haut)

Ceci est basé sur la solution de @Jakube (pls upvote that). Je n'aurais jamais pu le trouver par moi-même.

Ici, je fais un pas en avant, itérant une fois la liste et gardant un masque de bits avec les bits à retourner, et un autre avec les bits à conserver.

S'il y a un chevauchement des masques de bits, aucune solution n'est possible, sinon la solution est "bits à retourner"

Comme les opérations binaires en javascript ne fonctionnent que sur des entiers 32 bits signés, la valeur de retour est un entier signé 32 bits pouvant être négatif ou égal à 0.

S'il n'y a pas de solution, la valeur de retour est '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

Tester

Les tests les plus longs sur 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>

ES6, 84 octets

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)

Edit: Au moment où il m’avait fallu pour écrire la réponse, l’algorithme avait déjà été posté de manière indépendante par @Jakube; mon algorithme est le même mais ce n'était pas du plagiat honnête! De plus, je remarque qu'une autre réponse JavaScript a été postée depuis. Désolé si je marche sur les pieds de quelqu'un.

Edit: 8 octets sauvegardés grâce à edc65.

C, 144 octets

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

C'est presque C99 standard (il manque quelques intspécificateurs et a 1 argument pour main). Il repose également sur 0<<-10 (ce qui semble être vrai lorsque compilé avec Clang au moins - je n'ai pas testé les autres)

J'ai pris la méthode de Jakube et l'ai portée sur C. Je pense que sa taille est étonnamment bonne pour C. C'est aussi très rapide (0.061s pour exécuter tous les fichiers de test, y compris le très gros 4). Il prend une entrée de STDIN et imprimera la valeur correspondante ou -1 dans STDOUT, exécutez-le ainsi:

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

Panne:

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

Julia, 124 octets

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

C'est une fonction qui accepte un tableau d'entiers et retourne un entier. Il utilise l'approche de Jakube .

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

Python 2, 204 octets

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

L'entrée est transmise sous forme de liste à la fonction f.

Ce code détermine la valeur de N (nommée n dans le programme), bit par bit, en commençant par le bit de poids fort. (le "pour i" boucle)

Pour chaque position de bit, la boucle "pour n" tente d'abord d'utiliser 0 pour ce bit de n. Si cela ne fonctionne pas, il essaie d'utiliser 1. Si aucune de ces méthodes ne fonctionne, il n'y a pas de solution. Notez que la clause else est sur la boucle "pour n", pas l'instruction if. En Python, une instruction for peut avoir une clause else, qui est exécutée une fois la boucle terminée, mais ne l' est pas si nous sortons de la boucle.

La fonction q recherche les problèmes liés à l'ordre de la liste en fonction de la liste (a), du masque binaire (m) et de la valeur à sauvegarder avec chaque valeur de la liste (n). Il retourne 1 s'il y a un problème avec la commande ou None si la commande est correcte. None est la valeur de retour par défaut, de sorte que plusieurs caractères ont été enregistrés.

Ce code gère correctement une liste vide ou une liste avec 1 élément, en renvoyant 0. Le "if a:" de la fonction q est là uniquement pour éviter une exception IndexError lorsque la liste est vide. Donc, 5 octets supplémentaires peuvent être supprimés si la gestion des listes vides n'est pas requise.

Sur mon ordinateur, le grand cas de test n ° 3 a pris 0,262 seconde. # 2 a pris à peu près la même chose. Tous les cas de test pris ensemble ont pris 0,765 secondes.

CJam, 37 octets

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

Testez-le ici.

Ceci utilise le même algorithme que plusieurs des autres réponses. C'est essentiellement mon implémentation de référence que j'ai utilisée pour créer les cas de test. Cependant, j’ai volé l’astuce de Jakube consistant à ne vérifier que les paires incriminées et à essayer simplement le résultat avec une sorte. Cela rompt la pseudo-linéarité, mais O (n log n) est encore assez rapide pour les cas de test. Mon code d'origine vérifiait également les paires déjà en ordre et constituait une liste de bits qu'il ne fallait pas permuter pour conserver leur ordre relatif, et vérifiait à la fin qu'il n'y avait pas de chevauchement entre les masques à deux bits. Cet algorithme a été initialement proposé par Ben Jackson .

Python 2, 226 214 octets

Algorithme simple, construit hier, joué au golf aujourd'hui.

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

C, 312 octets

#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;}

Définit une fonction h(int*a,int l)prenant un pointeur sur un tableau et sa longueur. Voici un programme de test béhémoth.

Légèrement non-golfé:

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

Mathematica, 99 à 97 caractères

Merci à Martin Büttner pour les conseils.

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

Explication:

Nous allons faire plusieurs tentatives pour modifier à Npartir de zéro et faire un test pour valider le candidat N.

Étape 1. Nous obtenons ces chiffres (entiers 32 bits) ed « XOR » par N( = 0maintenant) et divisé par 2^31: ⌊l~BitXor~#/#2⌋. Il y a trois cas:

• commandé, par exemple {0, 0, 1, 1, 1, 1, 1, 1};
• peut être corrigé, par exemple {1, 1, 1, 1, 0, 0, 0, 0};
• autrement, par exemple {0, 0, 1, 0, 0, 1, 1, 1}.

Nous ne faisons rien pour Nle premier cas, ou nous ajoutons 2^31à Ncorriger l'ordre pour le second cas: #+#2Boole@!OrderedQ@.... Alors que pour le troisième cas, il est impossible de modifier la liste quoi que nous fassions, nous ajoutons donc simplement 2^31pour plus Nde simplicité (ou quoi que ce soit!).

Étape 2. Nous obtenons ces nombres "xor" édités par Net divisés par 2^30. Il y a encore trois cas:

• commandé, par exemple {0, 1, 2, 2, 2, 2, 3, 3};
• peut être corrigé, par exemple {1, 1 , 0, 0, 3, 2, 2, 2};
• autrement, par exemple {3, 3, 1, 3, 2, 0, 1, 0}.

Nous ne faisons rien pour Nle premier cas, ou nous ajoutons 2^30à Ncorriger l'ordre pour le second cas. Autrement, nous réalisons que le xorting est impossible, nous ajoutons donc simplement 2^30à la Nsimplicité.

Étape 3 ~ 32. Nous récursive obtenir ces chiffres ed « XOR » par Net divisé par 2^29, 2^28..., 2^0. Et faire des choses similaires:Fold[...,0,2^32/2^Range[32]]

Étape 33. Nous avons enfin un candidat N. If[OrderedQ[l~BitXor~#],#,-1]&est utilisé pour vérifier si tel est Neffectivement le cas de la liste. Si la liste peut être modifiée par certains N, il n’est pas difficile de prouver que nous rencontrerons toujours le premier ou le deuxième cas.

Perl 6 , 79 octets

S'il n'y avait pas de limite de temps, le code Perl 6 le plus court serait probablement

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

Au lieu de cela, je dois faire quelque chose d'un peu plus intelligent.
Depuis que j'ai mis du temps à y revenir, il existait déjà une réponse décrivant un bon algorithme et son raisonnement.

{$/=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 ｢@_｣
}

Usage:

# 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

Mathematica 650 415 194 octets

Ce défi m'a aidé à comprendre pas mal de choses Xorauxquelles je n'avais jamais pensé. Il a fallu beaucoup de temps pour réduire le code, mais cela en valait la peine.

BitXorfonctionne directement sur les chiffres de base 10. Cela a grandement réduit le code des versions précédentes.

La logique est simple. L'un fonctionne, pas avec des paires de nombres (comme l'ont fait certaines soumissions), mais avec l'ensemble complet des nombres après avoir été BitXorédité avec la "clé" actuelle.

Commencez avec une solution provisoire ou "clé" de zéro, c’est-à-dire que tous les bits sont à zéro. Lorsque les nnuméros d' origine sont BitXorédités à zéro, ils sont retournés sans modification. Corréler le classement des nombres avec la plage 1, 2, ...n, ce qui représente une liste parfaitement ordonnée. La corrélation, avec une valeur comprise entre -1 et 1, reflète la qualité de l'ordre des nombres.

Ensuite, définissez le bit hi, obtenez la nouvelle clé et BitXorla clé avec le jeu de chiffres actuel. Si la corrélation entre la nouvelle séquence de nombres et la liste parfaitement ordonnée constitue une amélioration, conservez le bit activé. Sinon, laissez le bit non défini.

Procédez de la sorte du haut vers le bas. Si la meilleure corrélation est 1, la solution est la clé. Sinon, c'est -1.

Il y aurait moyen de rendre le code un peu plus efficace, par exemple en interrompant le processus dès qu'une solution est trouvée, mais cela nécessiterait davantage de codage et l'approche actuelle est très rapide. (Le cas de test final et le plus long prend 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

Ajouter ++ , 125 119 octets

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

Essayez-le en ligne!

_{En fait, je suis vraiment fier qu'Add ++ puisse le faire et ce n'est pas la solution la plus longue ici}

Déclare une fonction fqui prend chaque élément comme un argument séparé (par exemple $f>4>2>3>1)

Comment ça fonctionne

Bouclez votre ceinture, ça va être long

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

Stax , 29 octets

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

Exécuter et déboguer en ligne!

Utilise la solution de @ RainerP. (A créé la partie de basculement de bit indépendamment mais utilise la 32rrpartie)

Complexité temporelle linéaire.

Utilise la version décompressée pour expliquer.

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