XOR-Sortierung eines Arrays

15

Bei einem gegebenen Schlüssel und einem Array von Zeichenfolgen wird das Array gemischt, sodass es sortiert wird, wenn jedes Element mit dem Schlüssel einer XOR-Verknüpfung unterzogen wird.

XOR'ing zwei Saiten

Um eine Zeichenfolge durch einen Schlüssel zu XORen, XORen Sie jeden der Zeichenwerte der Zeichenfolge durch sein Paar im Schlüssel, vorausgesetzt, der Schlüssel wird für immer wiederholt. abcde^123Sieht zum Beispiel so aus:

       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

Sortierung

Die Sortierung sollte immer lexikografisch anhand der XOR-Zeichenfolgen erfolgen. Das heißt 1 < A < a < ~(unter der Annahme einer ASCII-Codierung)

Beispiel

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

Anmerkungen

  • Der Schlüssel besteht immer aus mindestens 1 Zeichen
  • Schlüssel und Eingabe bestehen nur aus druckbarem ASCII.
  • XOR-Zeichenfolgen können nicht druckbare Zeichen enthalten.
  • Die Ein- und Ausgabe kann nach vernünftigen Methoden erfolgen
  • Standardlücken sind verboten.
  • Sie können den Schlüssel und die Eingabe in beliebiger Reihenfolge vornehmen.

Testfälle

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

Das ist Code-Golf , also gewinnt das Minimum an Bytes!

code-golf string array-manipulation sorting bitwise Ein Taco
quelle
Verwandte nirgends in der Nähe eines Betrogenen obwohl
MD XF
Sind die Saiten garantiert unterschiedlich?
Neil
@Neil Obwohl ich mir keine Situation vorstellen kann, in der sie identisch sind, können Sie davon ausgehen, dass alle Zeichenfolgen eindeutig sind.
ATaco
@ATaco Es kann sicher von Bedeutung sein, wenn Sie keinen integrierten Zeichenfolgenvergleich verwenden.
Dennis

Antworten:

7

Gelee , 9 7 Bytes

⁹ṁO^OµÞ

Vielen Dank an @EriktheOutgolfer für einen Vorschlag, der dazu beigetragen hat, 2 Bytes zu sparen!

Probieren Sie es online!

Wie es funktioniert

⁹ṁ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.
Dennis
quelle
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))])

Dadurch wird die Liste x an Ort und Stelle sortiert .

Vielen Dank an @mercator für das Golfen mit 2 Bytes!

Probieren Sie es online!

Alternative Version, 62 Bytes

Die Eingabe erfolgt als Byte-Zeichenfolge, die möglicherweise nicht zulässig ist.

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

Probieren Sie es online!

Dennis
quelle
In-Place - Sortierung spart 2 Bytes: x.sort(key=...).
Mercator
3

Haskell, 77 Bytes

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

Zu viele Importe.

Probieren Sie es online!

nimi
quelle
2

Ruby , 61 Bytes

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

Probieren Sie es online!

Eineder
quelle
2

Sauber , 101 100 94 Bytes

-6 Bytes dank Ourous!

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

Probieren Sie es online! Beispiel Nutzung: 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
Laikoni
quelle
? =toIntWenn Sie ?stattdessen verwenden, werden 2 Bytes gespeichert, und wenn Sie einen umgekehrten Wert größer als anstelle von kleiner oder gleich verwenden, wird ein weiterer Wert gespeichert.
Οurous
Noch besser, spart 6 Bytes: TIO
IOurous
1

Eigentlich 24 Bytes

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

Probieren Sie es online!

Erläuterung:

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)
Mego
quelle
@ATaco Nein, tut es nicht. Probieren Sie es mit ["who", "what", "when"]und"thisisalongkey"
Caird Coinheringaahing
1
@cairdcoinheringaahing Das wurde vor einem Patch auf Actually on TIO gepostet.
ATaco
1

Perl 6 , 37 Bytes

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

Probieren Sie es online!

$^aund @^bsind die Schlüssel- bzw. Array-Argumente für die Funktion. @^b.sort(...)Sortiert das Eingabearray einfach nach der angegebenen Prädikatfunktion. Diese Funktion verwendet ein einzelnes Argument, sortübergibt es also der Reihe nach jedem Element und behandelt den Rückgabewert als Schlüssel für dieses Element, wobei die Liste nach den Schlüsseln der Elemente sortiert wird.

Die Sortierfunktion ist *.comb Z~^ (|$^a.comb xx *). *ist das einzelne Zeichenfolgenargument für die Funktion. *.combist eine Liste der einzelnen Zeichen der Zeichenfolge. |$^a.comb xx *ist eine Liste der Zeichen im xor-Sortierschlüssel, die unendlich repliziert wird. Diese beiden Listen werden Zmit dem Operator stringwise xor ( ~^) zusammengepackt ( ). Da das Sortierprädikat einen Sortierschlüssel zurückgibt, der eine Liste ist, sortordnet es zwei Elemente durch Vergleichen der ersten Elemente der zurückgegebenen Listen und der zweiten Elemente, wenn die ersten Elemente identisch sind, usw. an.

Sean
quelle
{sort *.comb »~^»$^a.comb,@^b}
Brad Gilbert b2gills
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);}

Nimmt eine Argumentanzahl und einen Zeiger auf ein Zeichenfolgenarray (den Schlüssel, gefolgt von den zu sortierenden Zeichenfolgen) und ändert das Zeichenfolgenarray direkt.

Der Code ist nicht portierbar und erfordert 64-Bit-Zeiger, gcc und glibc.

Vielen Dank an @ceilingcat für das Golfen mit 2 Bytes!

Probieren Sie es online!

Dennis
quelle
1

Python 2,  204 140 134  126 Bytes

Vielen Dank an @Mr. Xcoder für das Speichern von 64 Bytes, danke an @ovs für das Speichern von sechs Bytes und danke an @Dennis für das Speichern von acht 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))

Probieren Sie es online!

Steadybox
quelle
1

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

Testcode:

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
l4m2
quelle
1

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 ist lang beim Zeichnen ...

Für [0,65536) + 1e4 sind alle 5 Stellen, können also wie ein String verglichen werden

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"]));
Erweitern Sie das Snippet

l4m2
quelle
Threoiy Ich kann k+=kanstelle von p=k+paber zu viel Speicher mit dem kleinen Testfall verwenden
l4m2
0

Perl 5, 88 Bytes

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

Probieren Sie es online aus .

Denis Ibaev
quelle
0

Clojure, 80 Bytes

#(sort-by(fn[s](apply str(apply map bit-xor(for[i[(cycle %)s]](map int i)))))%2)
NikoNyrh
quelle
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,@_}

versuche es online

Nahuel Fouilleul
quelle
Dies wiederholt die Taste neunmal, was im Allgemeinen nicht ausreicht. Beispielsweise ist die Ausgabe für falsch 9; abcdeabcde abcdeabcdz(sollte geben abcdeabcdz abcdeabcde)
Lynn
@Lynn, das Hinzufügen von 3 Bytes wurde korrigiert
Nahuel Fouilleul
konnte 16 Bytes mit Subs sparen
Nahuel Fouilleul
0

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

Probieren Sie es online!

Akzeptiert Eingaben in Form von key word word ...z912 abcde hello test honk

Gibt sortierte Wörter getrennt voneinander aus

Etwas besser lesbar

{
  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 : ""
    }
  }
}
Noskcaj
quelle
0

Faktor 85

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

Versuchen Sie zuerst, ich werde sehen, ob ich morgen weiter Golf spielen kann.

Ich akzeptiere Vorschläge;)

fede s.
quelle
0

Dyalog APL, 34 Bytes

Dfn, benutzt ⎕ml 3

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