XOR sort an array

Question

Given a key, and an array of strings, shuffle the array so that it is sorted when each element is XOR'd with the key.

XOR'ing two strings

To XOR a string by a key, XOR each of the character values of the string by its pair in the key, assuming that the key repeats forever. For example, abcde^123 looks like:

 a b c d e
 1 2 3 1 2
--------------------------------------------
01100001 01100010 01100011 01100100 01100101
00110001 00110010 00110011 00110001 00110010
--------------------------------------------
01010000 01010000 01010000 01010101 01010111
--------------------------------------------
 P P P U W

Sorting

Sorting should always be done Lexicographically of the XOR'd strings. That is, 1 < A < a < ~ (Assuming ASCII encoding)

Example

"912", ["abcde", "hello", "test", "honk"]
-- XOR'd
["XSQ]T", "QT^U^", "MTAM", "Q^\R"]
-- Sorted
["MTAM", "QT^U^", "Q^\R", "XSQ]T"]
-- Converted back
["test", "hello", "honk", "abcde"]

Notes

• Key will always be at least 1 character
• Key and Input will only consist of printable ASCII.
• XOR'd strings may contain non-printable characters.
• Input and Output may be done through the Reasonable Methods
• Standard Loopholes are forbidden.
• You may take Key and Input in any order.

Test Cases

key, input -> output
--------------------
"912", ["abcde", "hello", "test", "honk"] -> ["test", "hello", "honk", "abcde"]
"taco", ["this", "is", "a", "taco", "test"] -> ["taco", "test", "this", "a", "is"]
"thisisalongkey", ["who", "what", "when"] -> ["who", "what", "when"]
"3", ["who", "what", "when"] -> ["what", "when", "who"]

This is code-golf, so least bytes wins!

• MD XF: Related nowhere near a dupe though
• Neil: Are the strings guaranteed to be different?
• ATaco: @Neil Although I can't imagine a situation where them being identical would cause problems, you can assume that all strings will be unique.
• Dennis: @ATaco It can certainly matter if you're not using built-in string comparison.
• lyxal: Should have been called "XORt an array" :p

Answer 1

Python 3, (削除) 75 (削除ここまで) 73 bytes

lambda k,x:x.sort(key=lambda s:[ord(x)^ord(y)for x,y in zip(s,k*len(s))])

This sorts the list x in-place.

Thanks to @mercator for golfing off 2 bytes!

Try it online!

Alternate version, 62 bytes

This takes input as byte strings, which may not be allowed.

lambda k,x:x.sort(key=lambda s:[*map(int.__xor__,s,k*len(s))])

Try it online!

• user76878: In-place sorting saves 2 bytes: x.sort(key=...).

Answer 2

Jelly, (削除) 9 (削除ここまで) 7 bytes

9ṁO^OμÞ

Thanks to @EriktheOutgolfer for a suggestion that helped saving 2 bytes!

Try it online!

How it works

9ṁO^OμÞ Dyadic link.
 Left argument: A (string array). Right argument: k (key string).
 μ Combine the code to the left into a chain.
 Begin a new, monadic chain with argument A.
 Þ Sort A, using the chain to the left as key.
 Since this chain is monadic, the key chain will be called monadically,
 once for each string s in A.
9 Set the return value to the right argument of the link (k).
 ṁ Mold k like s, i.e., repeat its characters as many times as necessary
 to match the length of s.
 O Ordinal; cast characters in the resulting string to their code points.
 O Do the same for the chain's argument (s).
 ^ Perform bitwise XOR.

Answer 3

Ruby, 61 bytes

->k,w{w.sort_by{|x|x.bytes.zip(k.bytes.cycle).map{|x,y|x^y}}}

Try it online!

Answer 4

Haskell, 77 bytes

import Data.Bits
import Data.List
t=fromEnum
sortOn.zipWith((.t).xor.t).cycle

Too many imports.

Try it online!

Answer 5

x86 opcode, 57 Bytes

0100 60 89 CD 4D 8B 74 8A FC-8B 3C AA 53 F6 03 FF 75
0110 02 5B 53 8A 23 AC 08 C0-74 0A 30 E0 32 27 47 43
0120 38 E0 74 E8 77 0A 8B 04-AA 87 44 8A FC 89 04 AA
0130 85 ED 5B 75 CE E2 CA 61-C3
 ;input ecx(length), edx(array), ebx(xor-d)
F: pushad
L1: mov ebp, ecx
L2: dec ebp
 mov esi, [edx+ecx*4-4]
 mov edi, [edx+ebp*4]
 push ebx
L6: test [ebx], byte -1 ; t1b
 jnz L4
 pop ebx
 push ebx
L4: mov ah, [ebx]
 lodsb
 or al, al
 jz L7
 xor al, ah
 xor ah, [edi]
 inc edi
 inc ebx
 cmp al, ah
 jz L6
L7: ja L8
 mov eax, dword[edx+ebp*4]
 xchg eax, dword[edx+ecx*4-4]
 mov dword[edx+ebp*4], eax
L8: ;call debug
 test ebp, ebp
 pop ebx
 jnz L2
 loop L1
 popad
 ret 

Test code:

if 1
 use32
else
 org 0100ドル
 mov ecx, (Qn-Q0)/4
 mov edx, Q0
 mov ebx, S
 call F
 call debug
 ret
debug:pushad
 mov ecx, (Qn-Q0)/4
 mov edx, Q0
 mov ebx, S
E3: mov esi, [edx]
 push dx
 mov ah, 2
E4: lodsb
 cmp al, 0
 jz E5
 mov dl, al
 int 21ドル
 jmp E4
E5: mov dl, 0ドルA
 int 21ドル
 mov dl, 0ドルD
 int 21ドル
 pop dx
 add edx, 4
 loop E3
 ;mov ah, 1
 ;int 21ドル
 int1
 popad
 ret
 align 128
Q0:
 dd str1, str2, str3, str4
Qn:
S db '912', 0
str1 db 'abcde', 0
str2 db 'hello', 0
str3 db 'test', 0
str4 db 'honk', 0
 align 128
end if
 ;input ecx(length), edx(array), ebx(xor-d)
F: pushad
L1: mov ebp, ecx
L2: dec ebp
 mov esi, [edx+ecx*4-4]
 mov edi, [edx+ebp*4]
 push ebx
L6: test [ebx], byte -1 ; t1b
 jnz L4
 pop ebx
 push ebx
L4: mov ah, [ebx]
 lodsb
 or al, al
 jz L7
 xor al, ah
 xor ah, [edi]
 inc edi
 inc ebx
 cmp al, ah
 jz L6
L7: ja L8
 mov eax, dword[edx+ebp*4]
 xchg eax, dword[edx+ecx*4-4]
 mov dword[edx+ebp*4], eax
L8: ;call debug
 test ebp, ebp
 pop ebx
 jnz L2
 loop L1
 popad
 ret

Answer 6

Clean, (削除) 101 (削除ここまで) (削除) 100 (削除ここまで) 94 bytes

-6 bytes thanks to Ourous!

import StdEnv
? =toInt
s k=let%s=[b bitxor?a\\a<-s&b<-[?c\\_<-s,c<-k]];@a b= %b> %a in sortBy@

Try it online! Example usage: s ['3'] [['who'], ['what'], ['when']].

Ungolfed:

import StdEnv
sort key list = 
 let
 f string = [(toInt a) bitxor (toInt b) \\ a<-string & b<-flatten(repeat key)]
 comp a b = f a <= f b
 in sortBy comp list

• Οurous: ? =toInt and using ? instead saves 2 bytes, and using a flipped greater-than instead of less-or-equals saves another one.
• Οurous: Even better, saves 6 bytes: TIO

Answer 7

JavaScript ES 6, (削除) 113 (削除ここまで) (削除) 97 (削除ここまで) 95 Bytes

k=>p=>p.sort((a,b,F=x=>[...x].map((y,i)=>1e9|y.charCodeAt()^(p=k+p).charCodeAt(i)))=>F(a)>F(b))

JavaScript is long at charcoding...

For [0,65536) +1e4 all be 5 digits so can be compared like string

Q=
k=>p=>p.sort((a,b,F=x=>[...x].map((y,i)=>1e9|y.charCodeAt()^(p=k+p).charCodeAt(i)))=>F(a)>F(b))
;
console.log(Q("912")(["abcde", "hello", "test", "honk"]));
console.log(Q("taco")(["this", "is", "a", "taco", "test"]));
console.log(Q("thisisalongkey")(["who", "what", "when"]));
console.log(Q("3")(["who", "what", "when"]));

• l4m2: Threoiy I can use k+=k instead of p=k+p but too many memory using with the small test case

Answer 8

Actually, 24 bytes

O╗⌠;O;l;╜@αH♀^♂cΣ@k⌡MS♂N

Try it online!

Explanation:

O╗⌠;O;l;╜@αH♀^♂cΣ@k⌡MS♂N
O╗ store ordinals of key in register 0
 ⌠;O;l;╜@αH♀^♂cΣ@k⌡M for each string in array:
 ;O make a copy, ordinals
 ;l; make a copy of ordinals, length, copy length
 ╜@αH list from register 0, cycled to length of string
 ♀^ pairwise XOR
 ♂cΣ convert from ordinals and concatenate
 @k swap and nest (output: [[a XOR key, a] for a in array])
 S♂N sort, take last element (original string)

• caird coinheringaahing: @ATaco No it doesn't. Try it with ["who", "what", "when"] and "thisisalongkey"
• ATaco: @cairdcoinheringaahing That was posted before a patch to Actually on TIO.

Answer 9

Perl 6, 37 bytes

{@^b.sort(*.comb Z~^(|$^a.comb xx*))}

Try it online!

$^a and @^b are the key and array arguments to the function, respectively. @^b.sort(...) simply sorts the input array according to the predicate function it is given. That function takes a single argument, so sort will pass it each element in turn and treat the return value as a key for that element, sorting the list by the keys of the elements.

The sorting function is *.comb Z~^ (|$^a.comb xx *). * is the single string argument to the function. *.comb is a list of the individual characters of the string. |$^a.comb xx * is a list of the characters in the xor sorting key, replicated infinitely. Those two lists are zipped together (Z) using the stringwise xor operator (~^). Since the sorting predicate returns a sort key which is a list, sort orders two elements by comparing the first elements of the returned lists, then the second elements if the first elements are the same, et cetera.

• Brad Gilbert b2gills: {sort *.comb »~^»$^a.comb,@^b}

Answer 10

C (gcc), (削除) 132 (削除ここまで) (削除) 128 (削除ここまで) 126 bytes

char*k;g(a,b,i,r)char**a,**b;{r=k[i%strlen(k)];(r^(i[*a]?:-1))-(r^(i[*b]?:-2))?:g(a,b,i+1);}f(c,v)int*v;{k=*v;qsort(v,c,8,g);}

Takes an argument count and a pointer to a string array (the key, followed by the strings to be sorted) and modifies the string array in-place.

The code is highly non-portable and requires 64-bit pointers, gcc, and glibc.

Thanks to @ceilingcat for golfing off 2 bytes!

Try it online!

Answer 11

Python 2, (削除) 204 140 134 (削除ここまで) 126 bytes

Thanks to @Mr. Xcoder for saving 64 bytes, thanks to @ovs for saving six bytes, and thanks to @Dennis for saving eight bytes!

lambda k,l:[x(k,s)for s in sorted(x(k,s)for s in l)]
x=lambda k,s:''.join(chr(ord(v)^ord(k[i%len(k)]))for i,v in enumerate(s))

Try it online!

Answer 12

Perl 5, 88 bytes

sub{[map@$_[0],sort{@$a[1]cmp@$b[1]}map[$_,substr$_^($_[0]x length),0,length],@{$_[1]}]}

Try it online.

Answer 13

Clojure, 80 bytes

#(sort-by(fn[s](apply str(apply map bit-xor(for[i[(cycle %)s]](map int i)))))%2)

Answer 14

Perl 5, (削除) 80 + 3 (anl) = 83 (削除ここまで), 67 bytes

sub{,ドル=shift;sub X{$_^substr,ドルx y///c,0,y///c};map X,sort map X,@_}

try it online

• lynn: This repeats the key 9 times, which isn’t enough in general. For example, the output will be wrong for 9; abcdeabcde abcdeabcdz (should give abcdeabcdz abcdeabcde)
• Nahuel Fouilleul: @Lynn, fixed adding 3 bytes
• Nahuel Fouilleul: could save 16 bytes using subs

Answer 15

AWK, (削除) 285 (削除ここまで) 284 bytes

{for(;z++<128;){o[sprintf("%c",z)]=z}split(substr(0,0,ドルindex(0,ドルFS)),k,"");1ドル="";split(0,ドルw);for(q in w){split(w[q],l,"");d="";for(;i++<length(l);){d=d sprintf("%c",xor(o[k[(i-1)%(length(k)-1)+1]],o[l[i]]))}a[q]=d;i=0}asort(a,b);for(j in b){for(i in a){printf(a[i]==b[j])?w[i]FS:""}}}

Try it online!

Accepts input in the form of key word word ... eg 912 abcde hello test honk

Outputs sorted words space separated

Slightly more readable

{
 for (; z++ < 128;) {
 o[sprintf("%c", z)] = z
 }
 split(substr(0,ドル 0, index(0,ドル FS)), k, "");
 1ドル = "";
 split(0,ドル w);
 for (q in w) {
 split(w[q], l, "");
 d = "";
 for (; i++ < length(l);) {
 d = d sprintf("%c", xor(o[k[(i - 1) % (length(k) - 1) + 1]], o[l[i]]))
 }
 a[q] = d;
 i = 0;
 }
 asort(a, b);
 for (j in b) {
 for (i in a) {
 printf(a[i] == b[j]) ? w[i] FS : ""
 }
 }
} 

Answer 16

Factor, 85

[ [ dup length rot <array> concat [ bitxor ] 2map ] with
[ dup bi* <=> ] curry sort ]

First try, I'll see if I can golf it further tomorrow.

I accept suggestions ;)

Answer 17

Dyalog APL, 34 bytes

Dfn, uses ⎕ml 3

{⍵[⍋⊃82⎕dr ̈⊃≠/11⎕dr ̈ ̈⍵((⍴ ̈⍵)⍴⊂⍺)]}