Co to jest ROT? - odszyfruj ROT-n

25

Oto litery alfabetu angielskiego w kolejności według częstotliwości:

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

Oznacza to, że ejest najczęściej używaną literą i zjest najmniej powszechna. (Dane z Wikipedii .)

Twoim wyzwaniem jest pobranie tekstu ROT-n'd, takiego jak:

ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz

Jest to tekst „tenissecretmessagetatisverysecureandsafe”, który jest „szyfrowany” przez ROT-21 (połowa z 42). Twój program, korzystając z powyższej tabeli częstotliwości, powinien być w stanie określić, o ile każdy znak został obrócony i oryginalny tekst.

(Jeśli nie znasz ROT-n, zasadniczo przesuwa on każdy znak o n. Na przykład w ROT-2,. a -> c, b -> d, ..., x -> z, y -> a, z -> b)

Jak pytasz (Bardzo naiwnym) algorytmem, którego musisz użyć, jest:

  • dla każdego nod 0do 25włącznie zastosuj ROT- -ndo ciągu wejściowego. (Negatywne, nponieważ chcemy odwrócić szyfrowanie. ROT- -njest równoważne z ROT- 26-n, jeśli jest to łatwiejsze).
  • przekonwertować każdy ciąg wejściowy na liczbę, dodając względne częstotliwości znaków. ejest 0, tjest 1, ajest 2itd. Na przykład odpowiednia liczba dla łańcucha "hello"to 7 + 0 + 10 + 10 + 3 = 30.
  • znajdź ciąg, który ma najniższą odpowiadającą mu liczbę.
  • wypisuje ten ciąg i odpowiadający mu ciąg n.

Zasady:

  • dane wejściowe mogą być w dowolnym miejscu uzasadnione (STDIN, argumenty funkcji, z pliku itp.), a zatem mogą generować (STDOUT, wartość zwracana funkcji, do pliku itp.)
  • możesz użyć innego algorytmu, o ile zawsze daje on identyczne wyniki. Na przykład posiadanie z0 i e25 i wybranie najwyższej liczby również jest w porządku.
  • jeśli dwa ciągi mają identyczne wyniki, możesz wybrać wyjście jednego (lub obu) z nich. To jest przypadek skrajny i nie musisz tego rozliczać.
  • to jest , więc wygra najkrótszy kod w bajtach!

Przypadki testowe:

Wejście: ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz
Wyjście:21 thisisaverysecretmessagethatisverysecureandsafe

Wejście: pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom
Wyjście:8 hellopeopleofprogrammingpuzzlescodegolfstackexchange

Wejście: ftueimeqzodkbfqpiuftdaffiqxhqeaufygefnqbqdrqofxkemrq
Wyjście:12 thiswasencryptedwithrottwelvesoitmustbeperfectlysafe

Wejście: jgtgkuvjghkpcnvguvecugvjcvaqwowuvfgetarv
Wyjście:2 hereisthefinaltestcasethatyoumustdecrypt

Jeśli się zastanawiasz, oto JSFiddle kodu testowego JavaScript, który napisałem, który z powodzeniem odszyfrował wszystkie testowane przeze mnie przypadki testowe.

Klamka
źródło
Przydatne może być zanotowanie przypadków krawędzi. Na przykład wtaadpowinien dać 0 wtaadjako wynik i vszzcpowinien dać 25 wtaadjako wynik.
mellamokb
Powinieneś dać dodatkowe punkty za wykrycie implementacji TrippleROT-N.
user19713
@ user19713 Co to jest triplerot? To znaczy, jaka jest różnica między ROT-6 a trzykrotnym ROT-2?
Pan Lister
2
@mllister to stary żart kryptowalutowy, który wysika z TripleDES.
user19713,
Czy możemy wyprowadzić n-root po odszyfrowanym ciągu?
MayorMonty,

Odpowiedzi:

6

GolfScript - 87

Cheat tutaj polega na budowaniu każdego obrotu jednocześnie. Ponieważ musimy zapętlić każdy ROT, a następnie każdy znak, po prostu zapętlmy każdy znak, pokroimy cały alfabet, a następnie spakujemy. Następnie postępuj zgodnie z oczekiwaniami: policz wynik dla każdego ROT i wybierz minimum.

Extra golfed:

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

Tylko trochę golfa:

# 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
źródło
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])

Bieganie

% ./rot-n <<< "pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom"
8 hellopeopleofprogrammingpuzzlescodegolfstackexchange
śmigać
źródło
Zamiast sumowania długości, można tworzyć listy reprezentujące liczby jednoargumentowe, np. [1,1,1,1]I to da takie samo uporządkowanie. Następnie concatMappowstaje mapowanie i sumowanie, które można napisać zwięźle, używając listy. W połączeniu z kilkoma innymi sztuczkami, ja skrócić go do 152 znaków: 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 znaków

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

Nie podoba mi się powtórzenie z ponownym odszyfrowaniem na końcu, ale meh.

Ungolfed (jeśli ma to jakiś sens: P) i nieco starsza wersja:

# 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+}%''+
Klamka
źródło
„dane wejściowe mogą być wszędzie rozsądne” pomaga GolfScript. Na początku nie mogłem zrozumieć, dlaczego oba nasze skrypty wydają się drukować dodatkowy znak na końcu, dopóki nie zdałem sobie sprawy, echoże domyślnie wstawia nowy wiersz, który interpreter wybiera.
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)

Myślę, że można jeszcze trochę zagrać w golfa, więc sugestie mile widziane!

Kilka uwag, które pomogą zrozumieć rozwiązanie

  • m, ni ośledź najwyższy wynik.
  • ui wśledzić odpowiednio wynik postaci i wartości dla prądui
  • (a+a)pomaga zapobiegać przepełnieniu podczas owijania przeszłości zi jest krótszy niż robienie%26
  • Mam częstotliwość w odwrotnej kolejności, więc mogę wyszukiwać maks. Zamiast min.

Dowód: http://jsfiddle.net/J9ZyV/5/

mellamokb
źródło
4

C # + Linq - 273 264

Jako funkcja, która pobiera ciąg wejściowy i zwraca zdekodowany ciąg i offset (zgodnie z wymaganiami):

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

Niegolfowany z komentarzami:

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
}

Mały sterownik testowy (pamiętaj, aby skompilować odwołania System.Coredo Linq):

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

Dający:

$ 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
Tomasz
źródło
Myślę, że źle się przeliczyłeś - twoje obecne rozwiązanie ma w rzeczywistości 263 znaki. Możesz także zaoszczędzić jeszcze jeden znak, usuwając spację międzyTuple<string,int> d
mellamokb
Oto moja wersja, która jest bardzo blisko implementacji, ale nieco krótsza: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();}
wnosi
Myślę, że powinieneś używać Range(0, 26), nie 25.
Rawling
4

dg - 137 130 129 128 bajtów

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)

Przykłady:

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

Nieskluczony kod:

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
źródło
Nie możesz usunąć tych miejsc wokół c - 97i (0..26)?
mniip
Mogę tylko usunąć drugi. Robić to teraz. Dodam też kilka przykładów.
rubik
1
Nigdy wcześniej o tym nie słyszałem dg. Czy możesz podać link?
TheDoctor
@TheDoctor: Jasne! pyos.github.io/dg to strona główna, a pyos.github.com/dg/tutorial to samouczek.
rubik
Możesz zapisać jedną postać, dodając 7 zamiast odejmując 97. Modulo 26 są tym samym.
hammar
4

J - 92 znak

Trochę brzydkie kaczątko, ale działa. Zwraca liczbę, a następnie ciąg znaków w dwóch wierszach.

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

Jeśli chcesz, aby znajdowały się na tej samej linii, z odstępem oddzielnym, to zwiększa się tylko do 93 znaków , ale obiera bardziej brzydką trasę.

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

Wyjaśnienie (/:'ctljapqhewvknfdsyigbmuoxrz'): W tym czasowniku działamy na wartościach liter jako A = 0, B = 1, C = 2 itd. Aby zakodować wartości liter ciągu etaoinshrdlcumwfgypbvkjxqz, najkrótszym sposobem jest przyjęcie permutacji sortowania dla tego dziwny sznurek. Wynika to z tego, że A ma indeks 4, B - indeks 19, C - 0, D - 14 i tak dalej; stąd permutacja sortowania ma miejsce, 4 19 0 14 8 13 ...gdy oceniasz ją ( /:) i otrzymujesz dokładnie wartości liczbowe dla etaoin....

Stosowanie:

   (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
algorytmshark
źródło
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"
tartin
źródło
2

APL - 70 znaków

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

Przykład:

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

Jestem pewien, że istnieją sposoby na dalsze kompresowanie tego i zapraszam innych użytkowników APL, aby wymyślili rozwiązania tego problemu.

Elias Mårtenson
źródło
6
Musisz również
podać
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
źródło
1

Perl: 256 znaków (plus nowe wiersze dla czytelności), w tym tabela częstotliwości:

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

Tekst jest dostarczany w następujący sposób:

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

Zdejmij 12 znaków, jeśli chcesz upiec wartości ord (a) i długość @f

OJW
źródło
1

Wiąz - 465

Nie wygrywa żadnych nagród golfowych, ale tworzy statyczną stronę internetową, która wyświetla listę formularzy [(rotation number, rotated string)]podczas pisania.

Uwaga: jeszcze tu nie działa , ale możesz skopiować i wkleić go do oficjalnego edytora i uruchomić.

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
źródło
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
źródło