Xorting an array
Pyth, 40 36 31 30 bytes
Ju.|G^2slHxMf>FT.:Q2Z|tSIxRJQJ
Try it online: Demonstration or Test Suite
Each of the big test-cases finishes in a couple of seconds.
Explanation:
First I'll explain the method and why it works. I'll do this with the example list: [7, 2, 13, 9].
The first two numbers are already wrong (7 > 2). We want to xor with some number to change that inequality symbol (7 xor X < 2 xor X). Since xor operates on the binary representations, lets look at them.
7 = 1 1 1
2 = 1 0
When we apply xor with some number to each number, the value at some positions will change. If you change the values at the first position (2^0), the inequality symbol doesn't change. The same thing happens, when we change the values at the second position (2^1). Also the symbol won't change if we change values at the fourth, fifth, ... positions (2^3, 2^4, ...). The inequality symbol only changes direction, if we change the third 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
If we change multiple positions at once, of course the same thing happens. If any of the positions we change is the third, than the inequality symbol changes, otherwise not.
The next pair is already sorted: 2 < 13. If we look at the binary representation, we notice, that we can xor anything to it and the inequality symbol is still correct, except when we change the fourth 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
So we don't want to change the fourth position. For the next pair we want to change something, since 13 > 9. Here we again have to change the third 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
Now recap: To end up in a sorted list, we again have to change the third position and don't want to change the fourth position. All other positions doesn't matter. The smallest number is simply 4 = 0100. Other choices would be 5 = 0101, 6 = 0110, 7 = 0111, 20 = 10100, 21 = 10101, ...
Xoring with 4 will result in the list [3, 6, 9, 13], with 6 will get [1, 4, 11, 15], and with 21 will get [18, 23, 24, 28].
So for a list, we need to find the positions, that will change the inequality symbol if it points into the wrong direction. We find the position simply by taking the most significant bit of the xor of the pair. We combine all these position (with or) to result in a candidate number. The we check, if we haven't accidentally destroyed the already sorted pairs.
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}
Runs in 42 milliseconds on the large test cases.
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
For once I wrote the ungolfed version first, then golfed it, since figuring out the right algorithm was a challenge in itself.
I actually tried to write something like this a few years ago to make a binary tree structure that would locally self-balance by letting each node redefine its comparison function dynamically. At first I thought I could just use xor, but as you say for random data there's unlikely to be a viable value.
Julia, 174 144 77 75 71
[EDIT] Thanks to Alex A. for anonymizing & various shorthands.
[EDIT 2] Replaced my own implementation by the builtin issorted().
Runs in linear time and handles the big files without noticeable delay. Works just as well for negative numbers.
l->(r=0;s=issorted;for d=63:-1:0 s((l$r).>>d)||(r$=2^d)end;s(l$r)?r:[])
Another variant that calculates the result closest to a given key (the above returns the smallest).
(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
Example, step by step: [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.