Conceitualmente, esse desafio é realmente simples. Você recebe uma lista de números inteiros não negativos . Se possível, encontre um número inteiro não negativo , de modo que a lista composta seja classificada. Se não existir, a saída deve ser algo que não possa ser confundido com um válido , por exemplo, um número negativo, absolutamente nada, um erro etc.aiNbi = ai XOR NNN

Aqui está um exemplo:

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

Se pegarmos todos os elementos desta lista XOR 5, obtemos

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

qual é classificado. (Observe que não é necessário que a lista resultante tenha elementos exclusivos e não contenha lacunas. Se o resultado de uma operação [0, 1, 1, 3]desse tipo ainda fosse válido.) Por outro lado, a lista

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

não Nexiste.

Você pode escrever um programa ou função, recebendo entrada via STDIN (ou alternativa mais próxima), argumento da linha de comando ou argumento da função e exibindo o resultado via STDOUT (ou alternativa mais próxima), valor de retorno da função ou parâmetro da função (saída).

A entrada pode estar em qualquer formato conveniente de lista ou string. Você pode assumir que são menores que cada um e que a lista contém pelo menos um elemento.ai231

Seu código deve lidar com qualquer um dos casos de teste (especialmente os quatro grandes) em questão de segundos.

Aplicam-se as regras de código-golfe padrão .

Casos de teste

Para cada caso de teste que não retorna, -1há um número infinito de respostas corretas. O listado aqui é o menor. Soluções adicionais existem configurando adicionalmente os bits iguais em todos os números inteiros na entrada (principalmente aqueles que são maiores que o bit mais significativo no maior número da lista).

[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

Finalmente, aqui estão quatro casos de teste muito grandes para garantir que os envios sejam suficientemente eficientes:

• O Caso de Teste 1 deve render -1.
• O Caso de Teste 2 deve render 0.
• O Caso de Teste 3 deve render 1096442624.
• O Caso de Teste 4 deve render -1.

Por que alguém faria isso?

Ocorreu-me outro dia que uma operação XOR pode "classificar" uma matriz, o que torna possível realizar uma pesquisa binária na matriz em O (log n) sem precisar classificá-la primeiro. Parece ser possível determinar Nem tempo pseudolinear, o que tornaria essa uma alternativa mais rápida à maioria dos algoritmos de classificação, e não possui os requisitos de memória da classificação radix. Obviamente, uma pesquisa linear direta através da matriz não classificada será mais rápida, mas se você quiser pesquisar a mesma matriz várias vezes, um único pré-cálculo linear poderá reduzir significativamente o tempo necessário para cada pesquisa.

Infelizmente, a classe de listas em que isso funciona é bastante limitada (é improvável que as distribuições aleatórias uniformemente admitam uma N).

Uma pergunta interessante é se existem outras funções bijetivas que são mais fáceis de verificar e / ou são aplicáveis ​​a uma classe mais ampla de listas.

Gelatina, 25 bytes

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

Os commits mais recentes pós-datam esse desafio, mas o código acima funciona com esta revisão , que é anterior a ela. Experimente online!

Para executar os grandes casos de teste, dependendo do seu shell, pode ser necessário agrupar o código acima em um programa que lê as entradas do STDIN. Experimente online!

Casos de teste

$ 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éia

Isso usa a mesma abordagem da resposta do @ Jakube , mas minha implementação é um pouco diferente.

A geléia ainda não tem classificação, portanto, calculamos um candidato de xortagem, XOR a lista de entrada com ele, calculamos um candidato de xorting da lista XORed e verificamos se o novo candidato é zero. Se for, imprimimos o primeiro candidato; caso contrário, imprimimos -1 .

Além disso, Jelly parece não ter uma maneira sensata de converter para número inteiro ainda (até mesmo a divisão inteira pode retornar números flutuantes), então tive que criar uma maneira bastante criativa de arredondar uma lista de números para a próxima potência de 2 . Em vez de log-floor-pow, converto todos os números inteiros em binários, substituo todos os dígitos binários por 1 , converto novamente em números inteiros, adicione 1 e divido por 2 .

Código

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

Pitão, 40 36 31 30 bytes

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

Experimente on-line: Demonstration or Test Suite

Cada um dos grandes casos de teste termina em alguns segundos.

Explicação:

Primeiro vou explicar o método e por que ele funciona. Eu vou fazer isso com a lista de exemplo: [7, 2, 13, 9].

Os dois primeiros números já estão errados ( 7 > 2). Queremos xor com algum número para alterar esse símbolo de desigualdade ( 7 xor X < 2 xor X). Como o xor opera nas representações binárias, vamos vê-las.

7 = 1 1 1
2 =   1 0

Quando aplicamos xor com algum número para cada número, o valor em algumas posições muda. Se você alterar os valores na primeira posição ( 2^0), o símbolo de desigualdade não muda. O mesmo acontece quando alteramos os valores na segunda posição ( 2^1). Além disso, o símbolo não vai mudar se alterar os valores na quarta, quinta, ... posições ( 2^3, 2^4...). O símbolo da desigualdade apenas muda de direção, se mudarmos a terceira posição ( 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

Se mudarmos várias posições ao mesmo tempo, é claro que a mesma coisa acontece. Se alguma das posições que mudarmos for a terceira, o símbolo da desigualdade mudará, caso contrário não.

O próximo par já está classificado: 2 < 13. Se olharmos para a representação binária, notamos que podemos fazer algo para ela e o símbolo da desigualdade ainda está correto, exceto quando mudamos a quarta posição ( 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

Portanto, não queremos mudar a quarta posição. Para o próximo par, queremos mudar alguma coisa, desde então 13 > 9. Aqui, novamente, temos que mudar a terceira posição.

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

Agora, recapitulando: para terminar em uma lista classificada, precisamos mudar novamente a terceira posição e não queremos alterar a quarta posição. Todas as outras posições não importam. O menor número é simples 4 = 0100. Outras opções seriam 5 = 0101, 6 = 0110, 7 = 0111, 20 = 10100, 21 = 10101, ...

Xoring com 4resultará na lista [3, 6, 9, 13], com 6get [1, 4, 11, 15]e com 21get [18, 23, 24, 28].

Portanto, para uma lista, precisamos encontrar as posições que mudarão o símbolo da desigualdade se apontar para a direção errada. Encontramos a posição simplesmente pegando o bit mais significativo do xor do par. Combinamos todas essas posições (com ou) para resultar em um número de candidato. O check, se não destruímos acidentalmente os pares já classificados.

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

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

É executado em 42 milissegundos nos grandes casos de teste.

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

Pela primeira vez, escrevi a versão não-golfada primeiro, depois a joguei no golfe, pois descobrir o algoritmo certo era um desafio em si.

Na verdade, tentei escrever algo assim há alguns anos para criar uma estrutura de árvore binária que se equilibrasse localmente, permitindo que cada nó redefinisse sua função de comparação dinamicamente. No começo, pensei em usar o xor, mas como você diz para dados aleatórios, é improvável que exista um valor viável.

Julia, 174 144 77 75 71

[EDIT] Obrigado a Alex A. por anonimizar e várias abreviações.
[EDIT 2] Substituí minha própria implementação pelo embutido issorted().

É executado em tempo linear e lida com os arquivos grandes sem demora perceptível. Funciona tão bem para números negativos.

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

Outra variante que calcula o resultado mais próximo de uma determinada chave (a acima retorna o menor).

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

uso:

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

Exemplo, passo a passo: [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

Editar Removido estúpido, inútil último E
Edit2 Pesquisa de
topo encurtada Edit3 Uau! Descobri que o ES6 (quase) tem um builtin para encontrar o bit superior (Math.clz32 conta os 0 bits principais)

Isso é baseado na solução do @Jakube (por favor, vote isso). Eu nunca poderia ter encontrado sozinho.

Aqui vou um passo adiante, iterando a lista uma vez e mantendo uma máscara de bits com os bits que precisam ser invertidos, e outra com os bits que precisam ser mantidos.

Se houver uma sobreposição das máscaras de bits, nenhuma solução será possível; caso contrário, a solução será "bits para virar"

Como as operações binárias em javascript funcionam apenas em números inteiros de 32 bits assinados, o valor de retorno é um número inteiro de 32 bits assinado que pode ser negativo ou 0.

Se não houver solução, o valor de retorno é '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

Teste

Os testes mais longos no 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 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)

Edit: No momento em que levei para escrever a resposta, o algoritmo já havia sido publicado de forma independente pelo @Jakube; meu algoritmo é o mesmo, mas isso não foi plágio honesto! Também notei que outra resposta JavaScript também foi postada. Desculpe se estou pisando nos pés de alguém.

Editar: salvou 8 bytes graças a edc65.

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

Este é quase o padrão C99 (faltam alguns intespecificadores e tem 1 argumento para main). Também depende de 0<<-1ser 0 (o que parece ser verdade quando compilado com Clang pelo menos - eu não testei outros)

Peguei o método de Jakube e o transportei para C. Acho que é surpreendentemente bom em termos de tamanho para C. Também é super rápido (0,061s para executar todos os arquivos de teste, incluindo o maciço 4). Ele recebe a entrada de STDIN e imprime o valor correspondente ou -1 em STDOUT; portanto, execute-o com um dos seguintes:

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

Demolir:

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

Esta é uma função que aceita uma matriz inteira e retorna um número inteiro. Ele usa a abordagem 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 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

A entrada é passada como uma lista para a função f.

Este código calcula o valor de N (nomeado n no programa) um bit de cada vez, começando com o bit mais significativo. (o loop "for i")

Para cada posição de bit, o loop "for n" primeiro tenta usar 0 para esse bit de n. Se isso não funcionar, ele tenta usar 1. Se nenhum desses funcionar, não haverá solução. Observe que a cláusula else está no loop "for n", não na instrução if. No Python, uma instrução for pode ter uma cláusula else, que é executada após a conclusão do loop, mas não é executada se sairmos do loop.

A função q verifica se há problemas com a ordem da lista, dada a lista (a), uma máscara de bit (m) e o valor a ser armazenado em cada valor da lista (n). Retorna 1 se houver um problema com o pedido ou Nenhum se o pedido estiver correto. Nenhum é o valor de retorno padrão, de modo que me salvou vários caracteres.

Esse código manipula uma lista vazia ou uma lista com 1 elemento corretamente, retornando 0. A função "if a:" na q está lá apenas para evitar uma exceção IndexError quando a lista estiver vazia. Portanto, mais 5 bytes podem ser removidos se não for necessário manipular listas vazias.

No meu computador, o grande caso de teste nº 3 levou 0,226 segundos. # 2 levou o mesmo. Todos os casos de teste em conjunto levaram 0,765 segundos.

CJam, 37 bytes

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

Teste aqui.

Isso usa o mesmo algoritmo que várias das outras respostas. É essencialmente minha implementação de referência que eu usei para criar os casos de teste. No entanto, eu roubei o truque de Jakube de verificar apenas os pares ofensivos e simplesmente experimentar o resultado com uma espécie. Isso quebra a pseudolinearidade, mas O (n log n) ainda é rápido o suficiente para os casos de teste. Meu código original também verificou os pares que já estão em ordem e construiu uma lista de bits que não devem ser alternados para manter sua ordem relativa, e verificou no final se não há sobreposições entre as máscaras de dois bits. Este algoritmo foi originalmente sugerido por Ben Jackson .

Python 2, 226 214 bytes

O algoritmo simplista, construído ontem, jogou golfe hoje.

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

Define uma função que h(int*a,int l)leva um ponteiro para uma matriz e seu comprimento. Aqui está um gigante do programa de teste.

Ligeiramente não destruído:

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 caracteres

Obrigado a Martin Büttner pelos conselhos.

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

Explicação:

Faremos várias tentativas de modificar a Npartir do zero e faremos um teste para validar o candidato N.

Passo 1. Recebemos esses números (inteiros de 32 bits) "xor" ed pelo N( = 0agora) e divididas por 2^31: ⌊l~BitXor~#/#2⌋. Existem três casos:

• ordenado, por exemplo {0, 0, 1, 1, 1, 1, 1, 1};
• pode ser corrigido, por exemplo {1, 1, 1, 1, 0, 0, 0, 0};
• mais, por exemplo {0, 0, 1, 0, 0, 1, 1, 1}.

Nós não fazer nada para Npara o primeiro caso, ou nós adicionar 2^31a Ncorrigir a ordem para o segundo caso: #+#2Boole@!OrderedQ@.... Enquanto para o terceiro caso, é impossível xorting a lista o que sempre fazemos, assim, basta adicionar 2^31a Npela simplicidade (ou qualquer coisa!).

Etapa 2. Obtemos esses números "xor" ed Ne divididos por 2^30. Há novamente três casos:

• ordenado, por exemplo {0, 1, 2, 2, 2, 2, 3, 3};
• pode ser corrigido, por exemplo {1, 1 , 0, 0, 3, 2, 2, 2};
• mais, por exemplo {3, 3, 1, 3, 2, 0, 1, 0}.

Nós não fazer nada para Npara o primeiro caso, ou nós adicionar 2^30a Ncorrigir a ordem para o segundo caso. Caso contrário, percebemos que xorting é impossível, assim, basta adicionar 2^30a Npara simplificar novamente.

Passo 3 ~ 32. Nós recursivamente obter esses números "xor" ed por Ne dividido por 2^29, 2^28, ..., 2^0. E faça coisas semelhantes:Fold[...,0,2^32/2^Range[32]]

Etapa 33. Agora finalmente conseguimos um candidato N. If[OrderedQ[l~BitXor~#],#,-1]&é usado para verificar se, de Nfato, está xortando a lista. Se a lista pode ser classificada por alguns N, não é difícil provar que sempre encontraremos o primeiro ou o segundo caso.

Perl 6 , 79 bytes

Se não houvesse um limite de tempo, o menor código Perl 6 provavelmente seria

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

Em vez disso, tenho que fazer algo um pouco mais inteligente.
Como demorei um pouco para voltar a isso, já havia uma resposta que descreve um bom algoritmo e o raciocínio por trás dele.

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

Uso:

# 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 bytes

Esse desafio me ajudou a entender um pouco sobre o Xorque eu nunca havia pensado. Demorou muito tempo para reduzir o código, mas valeu a pena.

BitXortrabalha diretamente nos números da base 10. Isso reduziu bastante o código das versões anteriores.

A lógica é simples. Trabalha-se, não com pares de números (como fizeram algumas apresentações), mas com o conjunto completo de números depois de ser BitXoreditado com a "chave" atual.

Comece com uma solução provisória, ou "chave" de zero, ou seja, com todos os bits que são zero. Quando os nnúmeros originais são BitXoreditados com zero, eles são retornados inalterados. Correlacione a ordem dos números com o intervalo 1, 2, ...n, que representa uma lista perfeitamente ordenada. A correlação, com um valor entre -1 e 1, reflete como os números são ordenados.

Em seguida, defina o hi bit, obtenha a nova chave e BitXora chave com o conjunto atual de números. Se a correlação entre a nova sequência de números e a lista perfeitamente ordenada for uma melhoria, mantenha o bit definido. Caso contrário, deixe o bit desabilitado.

Prossiga dessa maneira, do oi para o bit mais baixo. Se a melhor correlação for 1, a chave é a solução. Caso contrário, é -1.

Haveria maneiras de tornar o código um pouco mais eficiente, por exemplo, interrompendo o processo assim que uma solução fosse encontrada, mas isso exigiria mais codificação e a abordagem atual é muito rápida. (O caso de teste final e mais longo leva 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 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

Adicionar ++ , 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

Experimente online!

_{Estou realmente muito orgulhoso que o Add ++ seja capaz de fazer isso e não seja a solução mais longa aqui}

Declara uma função fque assume cada elemento como um argumento separado (por exemplo $f>4>2>3>1)

Como funciona

Apertem o cinto, vai ser uma longa viagem

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 bytes

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

Execute e depure online!

Usa a solução da @ RainerP. (Veio com a parte do flipping bit de forma independente, mas usa a 32rrparte)

Complexidade de tempo linear.

Usa a versão descompactada para explicar.

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