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!

@Neil Although I can't imagine a situation where them being identical would cause problems, you can assume that all strings will be unique. — ATaco, Dec 28, 2017 at 10:07
@ATaco It can certainly matter if you're not using built-in string comparison. — Dennis, Dec 28, 2017 at 19:00

Dennis · Accepted Answer · 2017-12-28 19:17:04Z

10

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!

edited Dec 28, 2017 at 19:17

answered Dec 28, 2017 at 3:53

Dennis

210k41 gold badges370 silver badges823 bronze badges

\$\begingroup\$ In-place sorting saves 2 bytes: x.sort(key=...). \$\endgroup\$
– mercator
Dec 28, 2017 at 19:02

Add a comment |

Dennis · Accepted Answer · 2017-12-28 14:13:14Z

Jelly, 9 7 bytes

⁹ṁO^OµÞ

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

Try it online!

How it works

⁹ṁ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.
⁹            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.

Unihedron · Accepted Answer · 2017-12-28 09:46:31Z

3

Ruby, 61 bytes

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

Try it online!

answered Dec 28, 2017 at 9:46

Unihedron

1,29514 silver badges21 bronze badges

Add a comment |

nimi · Accepted Answer · 2017-12-28 11:12:30Z

3

Haskell, 77 bytes

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

Too many imports.

Try it online!

answered Dec 28, 2017 at 11:12

nimi

35.8k4 gold badges34 silver badges96 bronze badges

Add a comment |

l4m2 · Accepted Answer · 2017-12-29 20:12:14Z

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, $0A
    int $21
    mov dl, $0D
    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

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Dec 28, 2017 at 14:47

Laikoni

26.2k6 gold badges51 silver badges115 bronze badges

\$\begingroup\$ ? =toInt and using ? instead saves 2 bytes, and using a flipped greater-than instead of less-or-equals saves another one. \$\endgroup\$
– Οurous
Dec 28, 2017 at 19:59
\$\begingroup\$ Even better, saves 6 bytes: TIO \$\endgroup\$
– Οurous
Dec 29, 2017 at 0:38

Add a comment |

l4m2 · Accepted Answer · 2018-05-04 02:19:02Z

2

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"]));

edited May 4, 2018 at 2:19

answered Dec 28, 2017 at 4:22

l4m2

23.9k2 gold badges23 silver badges91 bronze badges

\$\begingroup\$ Threoiy I can use k+=k instead of p=k+p but too many memory using with the small test case \$\endgroup\$
– l4m2
Dec 28, 2017 at 4:25

Add a comment |

user45941user45941 · Accepted Answer · 2017-12-28 03:35:06Z

1

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)

answered Dec 28, 2017 at 3:35

user45941

\$\begingroup\$ @ATaco No it doesn't. Try it with ["who", "what", "when"] and "thisisalongkey" \$\endgroup\$
– caird coinheringaahin g ♦
Dec 28, 2017 at 7:57
1

\$\begingroup\$ @cairdcoinheringaahing That was posted before a patch to Actually on TIO. \$\endgroup\$
– ATaco
Dec 28, 2017 at 8:55

Add a comment |

Sean · Accepted Answer · 2017-12-28 16:03:40Z

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.

\$\begingroup\$ {sort *.comb »~^»$^a.comb,@^b} \$\endgroup\$
– Brad Gilbert b2gills
Dec 29, 2017 at 3:52 — Brad Gilbert b2gills, Dec 29, 2017 at 3:52

Dennis · Accepted Answer · 2017-12-29 01:44:29Z

1

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!

edited Dec 29, 2017 at 1:44

answered Dec 28, 2017 at 20:36

Dennis

210k41 gold badges370 silver badges823 bronze badges

Add a comment |

Steadybox · Accepted Answer · 2017-12-29 01:48:05Z

1

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!

edited Dec 29, 2017 at 1:48

answered Dec 28, 2017 at 3:51

Steadybox

16.5k5 gold badges40 silver badges84 bronze badges

Add a comment |

Denis Ibaev · Accepted Answer · 2017-12-28 09:22:37Z

0

Perl 5, 88 bytes

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

Try it online.

answered Dec 28, 2017 at 9:22

Denis Ibaev

1,2227 silver badges7 bronze badges

Add a comment |

NikoNyrh · Accepted Answer · 2017-12-28 11:06:51Z

0

Clojure, 80 bytes

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

answered Dec 28, 2017 at 11:06

NikoNyrh

2,6419 silver badges8 bronze badges

Add a comment |

Nahuel Fouilleul · Accepted Answer · 2017-12-28 14:05:08Z

0

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

edited Dec 28, 2017 at 14:05

answered Dec 28, 2017 at 8:52

Nahuel Fouilleul

8,5041 gold badge9 silver badges18 bronze badges

\$\begingroup\$ 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) \$\endgroup\$
– Lynn
Dec 28, 2017 at 12:40
\$\begingroup\$ @Lynn, fixed adding 3 bytes \$\endgroup\$
– Nahuel Fouilleul
Dec 28, 2017 at 13:43
\$\begingroup\$ could save 16 bytes using subs \$\endgroup\$
– Nahuel Fouilleul
Dec 28, 2017 at 14:06

Add a comment |

Noskcaj · Accepted Answer · 2017-12-29 02:49:36Z

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 : ""
    }
  }
}

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Dec 29, 2017 at 3:56

fede s.

9756 silver badges10 bronze badges

Add a comment |

Lobachevsky · Accepted Answer · 2017-12-29 11:38:08Z

0

Dyalog APL, 34 bytes

Dfn, uses ⎕ml 3

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

answered Dec 29, 2017 at 11:38

Lobachevsky

1714 bronze badges

Add a comment |

Stack Exchange Network

XOR sort an array

XOR'ing two strings

Sorting

Example

Notes

Test Cases

17 Answers 17

Python 3, 75 73 bytes

Alternate version, 62 bytes

Jelly, 9 7 bytes

How it works

Ruby, 61 bytes

Haskell, 77 bytes

x86 opcode, 57 Bytes

Clean, 101 100 94 bytes

Ungolfed:

JavaScript ES 6, 113 97 95 Bytes

Actually, 24 bytes

Perl 6, 37 bytes

C (gcc), 132 128 126 bytes

Python 2, 204 140 134 126 bytes

Perl 5, 88 bytes

Clojure, 80 bytes

Perl 5, 80 + 3 (`anl`) = 83, 67 bytes

AWK, 285 284 bytes

Factor, 85

Dyalog APL, 34 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
string
array
sorting
bitwise
or ask your own question.

Linked

Hot Network Questions

XOR sort an array

XOR'ing two strings

Sorting

Example

Notes

Test Cases

17 Answers 17

Python 3, 75 73 bytes

Alternate version, 62 bytes

Jelly, 9 7 bytes

How it works

Ruby, 61 bytes

Haskell, 77 bytes

x86 opcode, 57 Bytes

Clean, 101 100 94 bytes

Ungolfed:

JavaScript ES 6, 113 97 95 Bytes

Actually, 24 bytes

Perl 6, 37 bytes

C (gcc), 132 128 126 bytes

Python 2, 204 140 134 126 bytes

Perl 5, 88 bytes

Clojure, 80 bytes

Perl 5, 80 + 3 (anl) = 83, 67 bytes

AWK, 285 284 bytes

Factor, 85

Dyalog APL, 34 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfstringarraysortingbitwise or ask your own question.

Linked

Related

Hot Network Questions

Perl 5, 80 + 3 (`anl`) = 83, 67 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
string
array
sorting
bitwise
or ask your own question.