Was ROT ist das? - ROT-n entschlüsseln

25

Hier sind die Buchstaben des englischen Alphabets nach Häufigkeit sortiert:

e t a o i n s h r d l c u m w f g y p b v k j x q z

Dies ist eder am häufigsten verwendete und am seltensten verwendete Buchstabe z. (Daten aus Wikipedia .)

Ihre Herausforderung besteht darin, einen Text mit der Aufschrift ROT-n zu verwenden, z. B .:

ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz

Dies ist der Text "thisisaverysecretmessagethatisverysecureandsafe", der über ROT-21 (Hälfte von 42) "verschlüsselt" wird. Ihr Programm sollte anhand der obigen Häufigkeitstabelle feststellen können, um wie viel jedes Zeichen gedreht wurde und um wie viel der Originaltext gedreht wurde.

(Wenn Sie mit ROT-n nicht vertraut sind, verschiebt es im Wesentlichen jedes Zeichen um n. Zum Beispiel in ROT-2,. a -> c, b -> d, ..., x -> z, y -> a, z -> b)

Wie, fragst du? Der (sehr naive) Algorithmus, den Sie verwenden müssen, ist:

  • Wenden Sie für jedes nvon 0bis 25einschließlich ROT- -nauf die Eingabezeichenfolge an. (Negativ, nweil wir die Verschlüsselung umkehren möchten . ROT- -nentspricht ROT- 26-n, falls dies einfacher ist.)
  • Konvertieren Sie jede Eingabezeichenfolge in eine Zahl, indem Sie die relativen Häufigkeiten der Zeichen addieren. eist 0, tist 1, aist 2usw. Beispielsweise ist die entsprechende Nummer für die Zeichenfolge "hello"7 + 0 + 10 + 10 + 3 = 30.
  • Suchen Sie die Zeichenfolge mit der niedrigsten entsprechenden Nummer.
  • gib diesen String und den dazugehörigen aus n.

Regeln:

  • Die Eingabe kann überall sinnvoll sein (STDIN, Funktionsargumente, aus einer Datei usw.) und kann daher ausgegeben werden (STDOUT, Funktionsrückgabewert, in eine Datei usw.).
  • Sie können einen anderen Algorithmus verwenden, sofern er immer zu identischen Ergebnissen führt. Zum Beispiel ist es auch in Ordnung z, 0 und e25 zu sein und die höchste Zahl zu wählen.
  • Wenn zwei Zeichenfolgen identische Noten haben, können Sie eine (oder beide) ausgeben. Dies ist ein Randfall und Sie müssen ihn nicht berücksichtigen.
  • Das ist , also gewinnt der kürzeste Code in Bytes!

Testfälle:

Eingabe: ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz
Ausgabe:21 thisisaverysecretmessagethatisverysecureandsafe

Eingabe: pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom
Ausgabe:8 hellopeopleofprogrammingpuzzlescodegolfstackexchange

Eingabe: ftueimeqzodkbfqpiuftdaffiqxhqeaufygefnqbqdrqofxkemrq
Ausgabe:12 thiswasencryptedwithrottwelvesoitmustbeperfectlysafe

Eingabe: jgtgkuvjghkpcnvguvecugvjcvaqwowuvfgetarv
Ausgabe:2 hereisthefinaltestcasethatyoumustdecrypt

Für den Fall, dass Sie sich wundern, hier ist eine JSFiddle des JavaScript-Testcodes, den ich geschrieben habe, die alle Testfälle, die ich darauf geworfen habe, erfolgreich entschlüsselt hat.

Türknauf
quelle
Es kann nützlich sein, die Randfälle zu notieren. Zum Beispiel wtaadsollte 0 wtaadals Ergebnis geben, und vszzcsollte 25 wtaadals Ergebnis geben.
Mellamokb
Sie sollten zusätzliche Punkte für die Erkennung der Implementierung von TrippleROT-N angeben.
user19713
@ user19713 Was ist Triplerot? Ich meine, was ist der Unterschied zwischen ROT-6 und dreimal ROT-2?
Mr Lister
2
@mrlister Es ist ein alter Kryptowitz, der TripleDES die Pisse nimmt.
user19713
Können wir den n-root nach dem entschlüsselten String ausgeben?
MayorMonty

Antworten:

6

GolfScript - 87

Der Cheat dabei ist, jede Umdrehung gleichzeitig aufzubauen. Da wir jedes ROT und dann jedes Zeichen durchlaufen müssen, lassen Sie uns einfach jedes Zeichen durchlaufen, das gesamte Alphabet aufschneiden und es dann komprimieren. Von dort gehen Sie wie erwartet vor: Zählen Sie die Punktzahl für jedes ROT und wählen Sie das Minimum.

Extra Golf gespielt:

{97- 26,{97+}%.+''+>}/]{27<}%zip:d{{"etaoinshrdlcumwfgypbvkjxqz"?}%{+}*}%.$0=?.26\-\d=

Nur ein bisschen Golf gespielt:

# the alphabet, and by frequency
26,{97+}%.+''+:a;
"etaoinshrdlcumwfgypbvkjxqz":f;

# build evey ROT decryption
{97-a>}/]{27<}%zip:d

# calculate likelihood
{{f?}%{+}*}%.

# find min
$0=

# output rotation factor and decryption
?.26\-\d=
couchand
quelle
8

Haskell - 192 175

f y=sum.map(\x->length.fst$break(==x)y)
main=interact(\s->snd$minimum$[(f"etaoinshrdlcumwfgypbvkjxqz"r,show(26-n)++" "++r)|n<-[0..25],let r=map(\x->([x..'z']++['a'..])!!n)s])

Laufen

% ./rot-n <<< "pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom"
8 hellopeopleofprogrammingpuzzlescodegolfstackexchange
Swish
quelle
Anstatt Längen zu summieren, können Sie Listen bilden, die die Zahlen in Unary darstellen [1,1,1,1], und dies gibt die gleiche Reihenfolge. Aus Mapping und Summation wird dann, concatMapwas mit Hilfe eines Listenverständnisses kurz und bündig geschrieben werden kann. Zusammen mit einigen anderen Tricks, ich verkürzt es auf 152 Zeichen: main=interact(\s->snd$minimum[([1|x<-r,_<-fst$span(/=x)"etaoinshrdlcumwfgypbvkjxqz"],show(26-n)++' ':r)|n<-[0..25],r<-[[([x..'z']++['a'..])!!n|x<-s]]]).
Hammar
7

GolfScript, 112 108 102 100 Zeichen

{{}/]{97-}%}:b~:|;"etaoinshrdlcumwfgypbvkjxqz"b:f,:&,{:x[|{&x-+&%f?}%{+}*\]}%$0=1=:x|{&x-+&%97+}%''+

Ich bin nicht glücklich über die Wiederholung mit der Entschlüsselung am Ende, aber meh.

Ungolfed (wenn das Sinn macht: P) und etwas ältere Version:

# store input IDs (a = 0, b = 1, etc.) in s
[{}/]{97-}%:s;
# store frequency data IDs in f (blah, repetition)
"etaoinshrdlcumwfgypbvkjxqz"[{}/]{97-}%:f

# for each number from 0 to 26 (length of previous string left unpopped)...
,,{
  # the number is x
  :x;
  # return an array of...
  [
    # the score
    s{x 26\-+26%f?}%{+}*
    # and the n
    x
  ]
}%

# use $ort to find the n to output
$0=1=:x

# get the string that the n corresponded to (blah, more repetition)
s{x 26\-+26%97+}%''+
Türknauf
quelle
"Eingaben können überall sinnvoll sein" hilft GolfScript. Zuerst konnte ich nicht herausfinden, warum unsere beiden Skripte am Ende ein zusätzliches Zeichen zu drucken schienen, bis mir klar echowurde, dass standardmäßig eine neue Zeile eingefügt wird, die der Interpreter aufnimmt.
Couchand
6

JavaScript (205)

f='zqxjkvbpygfwmucldrhsnioate';a='abcdefghijklmnopqrstuvwxyz';for(s=prompt(o=m=n=0)
,i=27;i--;w>m&&(m=w,n=i,o=u))for(u='',w=c=0;c<s.length;w+=f.indexOf(x))u+=x=(a+a)[a
.indexOf(s[c++])+i];alert((26-n)+' '+o)

Ich denke, es kann noch ein bisschen mehr golfen werden, also sind Vorschläge willkommen!

Einige Hinweise zum besseren Verständnis der Lösung

  • m, nund overfolgen Sie die höchste Punktzahl.
  • uund wverfolgen Sie das Zeichen- bzw. Wertergebnis für den aktuellen Werti
  • (a+a)Verhindert ein Überlaufen beim Umwickeln der Vergangenheit zund ist kürzer als dies der Fall ist%26
  • Ich habe die Frequenz in umgekehrter Reihenfolge, damit ich max statt min suchen kann.

Beweis: http://jsfiddle.net/J9ZyV/5/

mellamokb
quelle
4

C # + Linq - 273 264

Als eine Funktion, die die Eingabezeichenfolge übernimmt und die dekodierte Zeichenfolge und den Offset zurückgibt (gemäß den Anforderungen):

static Tuple<string,int> d(string s){var r=Enumerable.Range(0,25).Select(i=>string.Concat(from c in s select (char)((c-97+i)%26+97))).OrderBy(x=>(from c in x select "etaoinshrdlcumwfgypbvkjxqz".IndexOf(c)).Sum()).First();return Tuple.Create(r,(s[0]-r[0]+26)%26);}

Ungolfed mit Kommentaren:

static Tuple<string,int> d(string s)
{
    var r=Enumerable.Range(0,25)                                               // for every possible offset i
          .Select(i=>string.Concat(from c in s select (char)((c-97+i)%26+97))) // calculate rot_i(input string)
          .OrderBy(                                                            // order these by their score
              x=>(
              from c in x select "etaoinshrdlcumwfgypbvkjxqz".IndexOf(c)       // lookup frequency of each character
              ).Sum()                                                          // and sum each frequency to get the score
           ).First();                                                          // get the first one (lowest score)

    return Tuple.Create(r,(s[0]-r[0]+26)%26);                                  // compute offset and return results
}

Kleiner Testtreiber (denken Sie daran, die Referenzierung System.Corefür Linq zu kompilieren ):

using System;
using System.Linq;

namespace codegolf
{
    class Program
    {
        static Tuple<string,int> d(string s){var r=Enumerable.Range(0,25).Select(i=>string.Concat(from c in s select (char)((c-97+i)%26+97))).OrderBy(x=>(from c in x select "etaoinshrdlcumwfgypbvkjxqz".IndexOf(c)).Sum()).First();return Tuple.Create(r,(s[0]-r[0]+26)%26);}

        static void Main(string[] args)
        {
            while (true)
            {
                var input = Console.ReadLine();
                if (input == null) break;
                var retval = d(input);
                Console.WriteLine(String.Format("{0} {1}", retval.Item2, retval.Item1));
            }
        }
    }
}

Geben:

$ mcs /reference:System.Core.dll main.cs && mono ./main.exe
ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz
21 thisisaverysecretmessagethatisverysecureandsafe
pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom
8 hellopeopleofprogrammingpuzzlescodegolfstackexchange
ftueimeqzodkbfqpiuftdaffiqxhqeaufygefnqbqdrqofxkemrq
12 thiswasencryptedwithrottwelvesoitmustbeperfectlysafe
jgtgkuvjghkpcnvguvecugvjcvaqwowuvfgetarv
2 hereisthefinaltestcasethatyoumustdecrypt
thisisaverysecretmessagethatisverysecureandsafe
0 thisisaverysecretmessagethatisverysecureandsafe
Thomas
quelle
Ich denke, Sie haben falsch gezählt - Ihre aktuelle Lösung besteht aus 263 Zeichen. Sie können auch ein Tuple<string,int> d
Zeichen
Hier ist meine Version, die in der Implementierung sehr eng ist, aber ein bisschen kürzer:Tuple<int,string>f(string x){return Enumerable.Range(0,25).Select(n=>Tuple.Create(26-n,string.Concat(x.Select(c=>(char)((c-97+n)%26+97))))).OrderBy(t=>(t.Item2.Select(c=>"etaoinshrdlcumwfgypbvkjxqz".IndexOf(c))).Sum()).First();}
23.03.14
Ich denke, Sie sollten verwenden Range(0, 26), nicht 25.
Rawling
4

dg - 137 130 129 128 Bytes

f=t->min key:(t->sum$map 'etaoinshrdlcumwfgypbvkjxqz'.index$snd t)$map(n->n,''.join$map(c->chr$((ord c + 7-n)%26+ 97))t)(0..26)

Beispiele:

>>> f 'ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz'
(21, 'thisisaverysecretmessagethatisverysecureandsafe')
>>> f 'pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom'
(8, 'hellopeopleofprogrammingpuzzlescodegolfstackexchange')
>>> f 'ftueimeqzodkbfqpiuftdaffiqxhqeaufygefnqbqdrqofxkemrq'
(12, 'thiswasencryptedwithrottwelvesoitmustbeperfectlysafe')
>>> f 'jgtgkuvjghkpcnvguvecugvjcvaqwowuvfgetarv'
(2, 'hereisthefinaltestcasethatyoumustdecrypt')

Ungolfed-Code:

func = t ->
  #: Compute the score of the text `t` with respect to the frequency table.
  #: score :: (int, str) -> int
  score = t ->
    sum $ map 'etaoinshrdlcumwfgypbvkjxqz'.index $ snd t

  #: Compute rot-n of the string `t`. Return the offset and the shifted text.
  #: rot :: int -> (int, str)
  rot = n ->
    n, ''.join $ map (c->chr $ ((ord c + 7 - n) % 26 + 97)) t

  # return the minimum (computed by `score`) amongst all shifted messages
  min key: score $ map rot (0..26)
rubik
quelle
Können Sie diese Leerzeichen um c - 97und nicht entfernen (0..26)?
Mittwoch,
Ich kann nur den zweiten entfernen. Mach es jetzt. Ich werde auch einige Beispiele hinzufügen.
Rubik
1
Nie dgzuvor gehört. Könnten Sie einen Link bereitstellen?
TheDoctor
@TheDoctor: Sicher! pyos.github.io/dg ist die Homepage und pyos.github.com/dg/tutorial das Tutorial.
Rubik
Sie können ein Zeichen speichern, indem Sie 7 addieren, anstatt 97 zu subtrahieren. Modulo 26: Sie sind dasselbe.
Hammar
4

J - 92 Zeichen

Ein bisschen wie ein hässliches Entlein, aber es funktioniert. Gibt die Zahl und dann die Zeichenfolge in zwei Zeilen aus.

(26|](-1!:2&2&.":)(/:'ctljapqhewvknfdsyigbmuoxrz')+/@i."1(i.<./@:)26|(i.-27)+/])&.(_97+3&u:)

Wenn Sie möchten, dass sie sich in derselben Zeile befinden, die durch Leerzeichen getrennt ist, werden nur 93 Zeichen angezeigt, die Route ist jedoch hässlicher.

((":@],[:u:32,97+26|-)(/:'ctljapqhewvknfdsyigbmuoxrz')+/@i."1(i.<./@:)26|(i.-27)+/])@(7+3&u:)

Eine Erklärung für (/:'ctljapqhewvknfdsyigbmuoxrz'): In diesem Verb bearbeiten wir die Buchstabenwerte als A = 0, B = 1, C = 2 usw. Um die Buchstabenwerte des Strings zu kodieren etaoinshrdlcumwfgypbvkjxqz, ist der kürzeste Weg tatsächlich, die Sortierpermutation dafür zu nehmen seltsame Zeichenfolge. Dies liegt daran, dass A bei Index 4 ist, B bei Index 19, C bei 0, D bei 14 und so weiter; daher ist die Sortierpermutation, 4 19 0 14 8 13 ...wenn Sie es benoten ( /:), und Sie erhalten genau die Zahlenwerte für etaoin....

Verwendung:

   (26|](-1!:2&2&.":)(/:'ctljapqhewvknfdsyigbmuoxrz')+/@i."1(i.<./@:)26|(i.-27)+/])&.(_97+3&u:) 'ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz'
21
thisisaverysecretmessagethatisverysecureandsafe

   NB. naming for convenience
   f =: (26|](-1!:2&2&.":)(/:'ctljapqhewvknfdsyigbmuoxrz')+/@i."1(i.<./@:)26|(i.-27)+/])&.(_97+3&u:)
   f 'pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom'
8
hellopeopleofprogrammingpuzzlescodegolfstackexchange
   f 'wtaad'
0
wtaad
algorithmshark
quelle
3

q, 97

{(w;m w:g?min g:(+/')("etaoinshrdlcumwfgypbvkjxqz"!t)m:(t!u!/:rotate[;u:.Q.a]'[(-)t:(!)26])@\:x)}

.

q) tests:(
    "ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvazocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz";
    "pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom";
    "ftueimeqzodkbfqpiuftdaffiqxhqeaufygefnqbqdrqofxkemrq";
    "jgtgkuvjghkpcnvguvecugvjcvaqwowuvfgetarv")

q) f:{(w;m w:g?min g:(+/')("etaoinshrdlcumwfgypbvkjxqz"!t)m:(t!u!/:rotate[;u:.Q.a]'[(-)t:(!)26])@\:x)}

q) f each tests
21 "thisisaverysecretmessagethatisverysecureandsafethisisaverysecretmessagethatisverysecureandsafe"
8  "hellopeopleofprogrammingpuzzlescodegolfstackexchange"
12 "thiswasencryptedwithrottwelvesoitmustbeperfectlysafe"
2  "hereisthefinaltestcasethatyoumustdecrypt"
tmartin
quelle
2

APL - 70 Zeichen

F←{↑⍋+/'etaoinshrdlcumwfgypbvkjxqz'⍳⊃(⍳26){l[(⍺⌽l←⎕UCS 97+⍳26)⍳⍵]}¨⊂⍵}

Beispiel:

      F 'ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz'
21
      F 'pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom'
8
      F 'ftueimeqzodkbfqpiuftdaffiqxhqeaufygefnqbqdrqofxkemrq'
12
      F 'jgtgkuvjghkpcnvguvecugvjcvaqwowuvfgetarv'
2

Ich bin mir sicher, dass es Möglichkeiten gibt, dies weiter zu komprimieren, und ich lade alle anderen APL-Benutzer ein, Lösungen dafür zu finden.

Elias Mårtenson
quelle
6
Sie müssen auch die entschiedene Zeichenfolge ausgeben ...
Türknauf
2

Python 188

x="abcdefghijklmnopqrstuvwxyz"
y=input()
r=lambda n:"".join(x[x.find(i)-n]for i in y)
s={sum("etaoinshrdlcumwfgypbvkjxqz".find(b)for b in r(a)):(a,r(a))for a in range(26)}
print(s[min(s)])
gcq
quelle
1

Perl: 256 Zeichen (plus Zeilenumbrüche zur besseren Lesbarkeit) einschließlich der Häufigkeitstabelle:

@f=unpack("W*","etaoinshrdlcumwfgypbvkjxqz");
@c=unpack("W*",<>);$m=ord("a");$b=1E10;
for$n(0..25){$s=0;$t="";
for$x(0..scalar@c){$r=($c[$x]-$n-$m)%26+$m;$t.=chr($r);
for(0..scalar@f){if($r==$f[$_]){$s+=$_}}}
if($s<$b){$b=$s;$w=$t;$a=$n}}
printf"%d %s\n",$a,$w;

Der Text sieht so aus:

echo "ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz" | perl ./freq.pl 
21 thisisaverysecretmessagethatisverysecureandsafewm

Nehmen Sie 12 Zeichen ab, wenn Sie die Werte von ord (a) und die Länge von @f einbrennen möchten

OJW
quelle
1

Elm - 465

Es werden keine Golfpreise gewonnen, aber es wird eine statische Webseite erstellt, auf der eine Liste des Formulars angezeigt wird, [(rotation number, rotated string)]während Sie tippen.

Hinweis: funktioniert hier noch nicht, aber Sie können es in den offiziellen Editor kopieren und ausführen.

import String as S
import Char (..)
import Graphics.Input (..)
import Graphics.Input.Field (..)
f="ETAOINSHRDLCUMWFGYPBVKJXQZ"
r s n=let t c=mod(toCode c-65+n)26+65 in map(fromCode . t)(S.toList s)
w s=case s of 
 ""->0
 s->sum(S.indexes(S.left 1 s)f)+w(S.dropLeft 1 s)
b s=sort<|map(\x->((w . S.fromList . r s)x,(26-x,S.fromList<|r s x)))[0..25]
c=input noContent
main=above<~(field defaultStyle c.handle id""<~c.signal)~(asText . b . .string<~c.signal)
hoosierEE
quelle
1

Python 2, 171

f,R,i='zqxjkvbpygfwmucldrhsnioate',{},raw_input();a=sorted(f)*2
for n in range(26):_=''.join(a[ord(x)-71-n]for x in i);R[sum(2**f.index(x)for x in _)]=n,_
print R[max(R)]
Dieter
quelle