26
\$\begingroup\$

Here are the letters of the English alphabet in order by frequency:

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

That is, e is the most frequently used letter, and z is the least common. (Data from Wikipedia.)

Your challenge is to take some ROT-n'd text, such as:

ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz

This is the text "thisisaverysecretmessagethatisverysecureandsafe" that is "encrypted" through ROT-21 (half of 42). Your program, using the frequency table above, should be able to determine by how much each character was rotated and the original text.

(If you are not familiar with ROT-n, it is essentially shifting each character by n. For example, in ROT-2, a -> c, b -> d, ..., x -> z, y -> a, z -> b.)

How, you ask? The (very naive) algorithm you must use is:

  • for each n from 0 to 25 inclusive, apply ROT--n to the input string. (Negative n because we want to reverse the encryption. ROT--n is equivalent to ROT-26-n, if that's any easier.)
  • convert each input string to a number by adding up the relative frequencies of the characters. e is 0, t is 1, a is 2, etc. For example, the corresponding number for the string "hello" is 7 + 0 + 10 + 10 + 3 = 30.
  • find the string that has the lowest corresponding number.
  • output that string and its corresponding n.

Rules:

  • input can be anywhere reasonable (STDIN, function arguments, from a file, etc.), and so can output (STDOUT, function return value, to a file, etc.)
  • you may use a different algorithm, as long as it always produces identical results. For example, having z be 0 and e be 25 and choosing the highest number is also okay.
  • if two strings have identical scores, you can choose to output either one (or both) of them. This is an edge case and you do not have to account for it.
  • this is , so the shortest code in bytes will win!

Test cases:

Input: ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz
Output: 21 thisisaverysecretmessagethatisverysecureandsafe

Input: pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom
Output: 8 hellopeopleofprogrammingpuzzlescodegolfstackexchange

Input: ftueimeqzodkbfqpiuftdaffiqxhqeaufygefnqbqdrqofxkemrq
Output: 12 thiswasencryptedwithrottwelvesoitmustbeperfectlysafe

Input: jgtgkuvjghkpcnvguvecugvjcvaqwowuvfgetarv
Output: 2 hereisthefinaltestcasethatyoumustdecrypt

In case you were wondering, here is a JSFiddle of the JavaScript test code I wrote, which successfully decrypted all the test cases I threw at it.

\$\endgroup\$
6
  • \$\begingroup\$ It might be useful to note the edge cases. For example, wtaad should give 0 wtaad as the result, and vszzc should give 25 wtaad as the result. \$\endgroup\$
    – mellamokb
    Mar 23, 2014 at 3:56
  • \$\begingroup\$ You should give extra points for detecting implementation of TrippleROT-N. \$\endgroup\$
    – user19713
    Mar 24, 2014 at 8:00
  • \$\begingroup\$ @user19713 What is triplerot? I mean, what is the difference between ROT-6 and three times ROT-2? \$\endgroup\$
    – Mr Lister
    Mar 24, 2014 at 12:31
  • 3
    \$\begingroup\$ @mrlister it's an old crypto joke that takes the piss out of TripleDES. \$\endgroup\$
    – user19713
    Mar 24, 2014 at 13:14
  • \$\begingroup\$ Can we output the n-root after the decrypted string? \$\endgroup\$
    – bren
    Apr 13, 2016 at 21:23

16 Answers 16

8
\$\begingroup\$

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

Running

% ./rot-n <<< "pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom"
8 hellopeopleofprogrammingpuzzlescodegolfstackexchange
\$\endgroup\$
1
  • \$\begingroup\$ Instead of summing lengths, you can form lists representing the numbers in unary, e.g. [1,1,1,1], and this will give the same ordering. Mapping and summing then becomes concatMap which can be written succinctly using a list comprehension. Combined with a few other tricks, I shortened it to 152 chars: 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]]]). \$\endgroup\$
    – hammar
    May 15, 2014 at 2:18
7
\$\begingroup\$

GolfScript, 112 108 102 100 characters

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

I'm not happy about the repetition with the re-decrypting at the end, but meh.

Ungolfed (if that makes any sense :P) and slightly older 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+}%''+
\$\endgroup\$
1
  • \$\begingroup\$ "input can be anywhere reasonable" does help GolfScript. At first I couldn't figure out why both our scripts seemed to print an extra character at the end, until I realized echo puts a newline by default, which the interpreter picks up. \$\endgroup\$
    – couchand
    Mar 24, 2014 at 5:48
6
\$\begingroup\$

GolfScript - 87

The cheat here is to build every rotation simultaneously. Since we need to loop over every ROT then every character, let's just loop over every character, slice the whole alphabet, then zip it up. From there proceed as expected: count the score for each ROT and choose the minimum.

Extra golfed:

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

Only a little golfed:

# 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=
\$\endgroup\$
6
\$\begingroup\$

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)

I think it can still be golfed a bit more, so suggestions welcome!

Some notes to help understand the solution

  • m, n, and o track the highest score.
  • u and w track the character and value result, respectively for the current i
  • (a+a) helps prevent overflow when wrapping around past z, and is shorter than doing %26
  • I have the frequency in reverse order so I can search max instead of min.

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

\$\endgroup\$
1
4
\$\begingroup\$

C# + Linq - 273 264

As a function which takes the input string and returns the decoded string & offset (as per requirements):

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 with comments:

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
}

Little test driver (remember to compile referencing System.Core for 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));
            }
        }
    }
}

Giving:

$ 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
\$\endgroup\$
3
  • \$\begingroup\$ I think you miscounted - your current solution is actually 263 characters. Also you can save one more char by removing the space between Tuple<string,int> d \$\endgroup\$
    – mellamokb
    Mar 23, 2014 at 19:44
  • \$\begingroup\$ Here's my version which is very close in implementation but a bit shorter: 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();} \$\endgroup\$
    – porges
    Mar 23, 2014 at 21:26
  • \$\begingroup\$ I think you should be using Range(0, 26), not 25. \$\endgroup\$
    – Rawling
    Mar 24, 2014 at 12:28
4
\$\begingroup\$

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)

Examples:

>>> 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)
\$\endgroup\$
6
  • \$\begingroup\$ Can't you remove those spaces around c - 97 and (0..26)? \$\endgroup\$
    – mniip
    Mar 23, 2014 at 10:25
  • \$\begingroup\$ I can only remove the second one. Doing it now. I'll add some examples as well. \$\endgroup\$
    – rubik
    Mar 23, 2014 at 14:04
  • 1
    \$\begingroup\$ Never heard of dg before. Could you provide a link? \$\endgroup\$
    – TheDoctor
    Mar 23, 2014 at 14:57
  • \$\begingroup\$ @TheDoctor: Sure! pyos.github.io/dg is the homepage and pyos.github.com/dg/tutorial the tutorial. \$\endgroup\$
    – rubik
    Mar 23, 2014 at 15:01
  • \$\begingroup\$ You can save one character by adding 7 instead of subtracting 97. Modulo 26 they are the same thing. \$\endgroup\$
    – hammar
    Mar 23, 2014 at 16:48
4
\$\begingroup\$

J - 92 char

A bit of an ugly duckling, but it works. Outputs the number and then the string, on two lines.

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

If you want them to be on the same line, space separated, this only goes up to 93 char, but takes an uglier route.

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

An explanation for (/:'ctljapqhewvknfdsyigbmuoxrz'): In this verb, we operate on the letter values as A=0, B=1, C=2, etc. To encode the letter values of the string etaoinshrdlcumwfgypbvkjxqz, the shortest way is actually to take the sort permutation for this weird string. This is because A is at index 4, B at index 19, C at 0, D at 14, and so on; hence the sort permutation is 4 19 0 14 8 13 ... when you grade (/:) it, and you get exactly the number values for etaoin....

Usage:

   (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
\$\endgroup\$
3
\$\begingroup\$

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"
\$\endgroup\$
2
\$\begingroup\$

APL - 70 characters

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

Example:

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

I'm sure there are ways to compress this further, and I invite any other APL users to come up with solutions for that.

\$\endgroup\$
1
  • 6
    \$\begingroup\$ You have to output the decided string too... \$\endgroup\$
    – Doorknob
    Mar 24, 2014 at 11:48
2
\$\begingroup\$

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)])
\$\endgroup\$
1
\$\begingroup\$

Perl: 256 char (plus newlines for readability) including the frequency table:

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

Text is provided like so:

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

Take off 12 char if you want to bake-in the values of ord(a) and the length of @f

\$\endgroup\$
1
\$\begingroup\$

Elm - 465

Not going to win any golfing awards, but it makes a static webpage which displays a list of the form [(rotation number, rotated string)] as you type.

Note: not yet working here but you can copy-paste it into the official editor and run it.

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)
\$\endgroup\$
1
\$\begingroup\$

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)]
\$\endgroup\$
1
\$\begingroup\$

Ruby, 142 bytes

->s{(0..25).map{|i|[*s.map{["etaoinshrdlcumwfgypbvkjxqz".chars.index(c=((_1.ord-97-i)%26+97).chr),c]}.transpose.map{_1.reduce:+},i]}.min[1..]}

Attempt This Online!

\$\endgroup\$
0
\$\begingroup\$

Python + golfing-shortcuts, 165 161 bytes

A port of gcq's answer.

from s import*
def F(Y):R=lambda N:sj("",(Sl[Sl.find(I)-N]for I in Y));S={s("etaoinshrdlcumwfgypbvkjxqz".find(B)for B in R(A)):(A,R(A))for A in r(26)};p(S[q(S)])
\$\endgroup\$
0
\$\begingroup\$

R, 140 bytes

\(e,u=utf8ToInt,x=u(e)-97)c(n<-which.min(sapply(25:0,\(z)sum(match((x+z)%%26,u("etaoinshrdlcumwfgypbvkjxqz")-97)))),intToUtf8((x-n)%%26+97))

Attempt This Online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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