Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  mellamokb Mar 23 at 3:56
    
You should give extra points for detecting implementation of TrippleROT-N. –  user19713 Mar 24 at 8:00
    
@user19713 What is triplerot? I mean, what is the difference between ROT-6 and three times ROT-2? –  Mr Lister Mar 24 at 12:31
    
@mrlister it's an old crypto joke that takes the piss out of TripleDES. –  user19713 Mar 24 at 13:14

13 Answers 13

up vote 4 down vote accepted

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=
share|improve this answer

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
share|improve this answer
    
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)"etaoinshrdlcumwfgypbvkj‌​xqz"],show(26-n)++' ':r)|n<-[0..25],r<-[[([x..'z']++['a'..])!!n|x<-s]]]). –  hammar May 15 at 2:18

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+}%''+
share|improve this answer
    
"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. –  couchand Mar 24 at 5:48

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/

share|improve this answer

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
share|improve this answer
    
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 –  mellamokb Mar 23 at 19:44
    
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=>(ch‌​ar)((c-97+n)%26+97))))).OrderBy(t=>(t.Item2.Select(c=>"etaoinshrdlcumwfgypbvkjxqz‌​".IndexOf(c))).Sum()).First();} –  Porges Mar 23 at 21:26
    
I think you should be using Range(0, 26), not 25. –  Rawling Mar 24 at 12:28

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

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
share|improve this answer

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"
share|improve this answer

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

share|improve this answer

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.

share|improve this answer
5  
You have to output the decided string too... –  Doorknob Mar 24 at 11:48

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)])
share|improve this answer

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)
share|improve this answer

Python 3 - 140

s=input()
r=ord(sorted("abcdefghijklmnopqrstuvwxyz",key=lambda x:s.count(x))[-1])-101
print(r,"".join(chr((ord(i)-97-r)%26+97)for i in s))

The method this uses is different to the one in the OP: It simply finds the most commonly used letter and determines what n is needed such that ROT-n of e is equal to itself. It then applies this ROT to the input string and voila.

EDIT: It seems that this does notwork for that last test case.

share|improve this answer
    
Of course this does not work because it's a completely different algorithm. The most common character is not guaranteed to appear the most times. -1 –  Doorknob Mar 24 at 12:49
    
@Doorknob Oh well, I tried. :P –  Trimsty Mar 24 at 13:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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