13
\$\begingroup\$

The Caesar cipher is a simple and famous cipher, where the letters of the alphabet are rotated by some secret amount. For example, if our secret rotation is 3, we would replace a with d, b with e, w with z, x with a and so on.

Here is an example (rotation amount: 10):

Robo sc kx ohkwzvo

This cipher is very weak, because short common English words like "I", "a", "is", "an", "if", etc. are easy to detect. Your task is to crack a Caesar cipher, that is, recover the rotation amount from the ciphertext. As additional input, you are given a list (or set) of words, which the plaintext can contain. It is guaranteed that there is only one answer.

Examples

"Ifmmp Xpsme!", ["world", "banana", "hello"]
-> 1

"Nc cd, Kadcn?", ["cogito", "et", "ergo", "tu", "sum", "brute"]
-> 9

"boring", ["boring"]
-> 0

"bccb foo", ["abba", "gpp", "cddc"]
-> 25

" !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~", ["zabcdefghijklmnopqrstuvwxy"]
-> 1

"bcsbdbebcsb", ["abracadabra", "za", "aq"]
-> 1

IO rules

The ciphertext can contain any printable ascii characters. The dictionary (list of words) contains strings made of lowercase letters (a-z). Words are separated by non-letters. Only letters are rotated (punctuation is ignored). You will output an integer in the range [0,25]

\$\endgroup\$
6
  • \$\begingroup\$ Would outputting in the range [1,26] instead be acceptable (this is currently prohibited by your rules)? \$\endgroup\$ Jan 21 at 14:05
  • \$\begingroup\$ @JonathanAllan I've decided against it, since [0,25] is a more natural range \$\endgroup\$
    – AnttiP
    Jan 21 at 14:12
  • \$\begingroup\$ Can you take the ciphertext as an array of words? \$\endgroup\$
    – Jonah
    Jan 21 at 17:19
  • \$\begingroup\$ @Jonah No, the annoying string processing is a part of this challenge \$\endgroup\$
    – AnttiP
    Jan 21 at 17:24
  • \$\begingroup\$ Suggested test-case (that my currently deleted post would fail with, yet pass all others): "bcsbdbebcsb", ["abracadabra", "za", "aq"] -> 1. If one looks for substrings of rotated words in the text, ignoring the fact that it is only one word long, then rotating 2 will give two matching substrings, while rotating 1 will only give one matching substring. \$\endgroup\$ Jan 21 at 17:32

7 Answers 7

6
\$\begingroup\$

Ruby, 66 bytes

Curried function that takes the dictionary first and the ciphertext second.

->w{f=->s{s=~/^([^a-z]|#{w*?|})*$/i?0:1+f[s.tr'a-zA-Z','ZA-Y'*2]}}

Attempt This Online!

From the dictionary a regex can be generated that only matches decoded text:

irb> w
=> ["world", "banana", "hello"]
irb> /^([^a-z]|#{w*?|})*$/i
=> /^([^a-z]|world|banana|hello)*$/i
\$\endgroup\$
4
\$\begingroup\$

JavaScript (Node.js), 99 bytes

Saved 1 byte thanks to @l4m2

Expects (string)(dictionary), where the dictionary is a set.

s=>g=(d,k=25)=>s.match(/[a-z]+/gi).some(s=>!d.has(Buffer(s).map(c=>(c%32+k)%26+97)+''))&&1+g(d,k-1)

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ (c|32) => c%32 with some other changes? \$\endgroup\$
    – l4m2
    Jan 21 at 15:14
  • \$\begingroup\$ @l4m2 Initializing k to 25? Or maybe there's a better way. \$\endgroup\$
    – Arnauld
    Jan 21 at 15:19
2
\$\begingroup\$

05AB1E (legacy), 19 18 bytes

[DIlÐáмS¡åP#ADÀ‡}N

First input is the list of words, second the sentence.

Try it online or verify all test cases.

Uses the legacy version of 05AB1E because of three reasons, each saving a single byte:

  1. works on a list of strings, whereas the new version requires a map around it - ADÀ‡} would have been εADÀ‡] in that case;
  2. N outputs the last index outside of a loop, whereas this is just 0 in the new version and we would have to use the counter variable - N would have been ¾, and ¼ would have to be added after the #;
  3. ¡ in the new version would keep empty strings as items, and we would have to remove them - so an additional á would have to be added after the ¡ to only keep the words.

Explanation:

[         # Loop indefinitely:
 D        #  Duplicate the current list
          #  (which will be the first implicit input-list in the first iteration)
  I       #  Push the second input-sentence
   l      #  Convert it to lowercase
    Ð     #  Triplicate it
     á    #  Only leave the letters of the top copy
      м   #  Remove all those letters from the second copy
       S  #  Convert the non-letters to a list of characters
        ¡ #  Split the lowercase sentence on these non-letters
  å       #  Check for each word if it's in the list
   P      #  Check if this is truthy for all of them
    #     #  If it is: stop the infinite loop
  ADÀ‡    #  Caesar Cipher the words in the list once:
  A       #   Push the lowercase alphabet: "abcdefghijklmnopqrstuvwxyz"
   DÀ     #   Duplicate, and rotated once: "bcdefghijklmnopqrstuvwxyza"
     ‡    #   Transliterate the words in the list
}N        # After the loop: push the last 0-based index
          # (which is output implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

Vyxal 2.4.1, 19 bytes

λ?⇩⌈Ǎka:nǓ$vĿ?vcA;ṅ

Try it Online!

Basically, try a cipher of each rotation and output the rotation number where all the words are in the dictionary.

2 can play at the legacy version saving bytes game.

Explained

λ?⇩⌈Ǎka:nǓ$vĿ?vcA;ṅ
λ                ;ṅ   # Find the first integer n, such that
 ?⇩                   #   the lowercase input
   ⌈                   #   split on spaces
    Ǎ                 #    and with all non-alphabet letters removed
             ?vcA     #    contains all words from the input after
           vĿ         #    being transliterated according to the mapping:
     ka:nǓ$           #      lowercase alphabet → lowercase alphabet rotated left n times
                  
\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 83 bytes

T`L`l
[^a-z¶]+
@
^
¶
{ms`\A(#*)¶@?((\w+\b)(?=.*¶\3$)@?)+$.*
$.1
^\B
#
T`l`zl`^.*¶.*

Try it online! Takes input as a line of ciphertext followed by each dictionary entry on a separate line. Explanation:

T`L`l

Lowercase everything.

[^a-z¶]+
@

Change non-letters to a marker to simplify matching.

^
¶

Prepend a blank line to hold the result.

{`

Repeat until the result is found.

ms`\A(#*)¶@?((\w+\b)(?=.*¶\3$)@?)+$.*
$.1

If all the words in the ciphertext are in the dictionary then replace the whole buffer with the result.

^\B
#

If the result has not been found then increment the rotation amount.

T`l`zl`^.*¶.*

If the ciphertext is still present then rotate it.

\$\endgroup\$
2
\$\begingroup\$

R, 99 103 bytes

Edit: Thanks to pajonk for bug-spotting, which unfortunately cost +4 bytes (also thanks to pajonk)

f=function(x,d)`if`(all(x%in%d),0,1+f(gsub("[^a-z]","",chartr("a-zA-Z","za-za-y",scan(t=x,,x))),d))%%26

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ I guess this fails in many cases when the output should be 0: Try it online! \$\endgroup\$
    – pajonk
    Jan 23 at 17:10
  • \$\begingroup\$ Quick-fix for +4 \$\endgroup\$
    – pajonk
    Jan 23 at 17:10
  • \$\begingroup\$ @pajonk - Ah, thanks for spotting, I didn't think of that. \$\endgroup\$ Jan 23 at 18:47
1
\$\begingroup\$

JavaScript (Node.js), 132 bytes

y=>f=x=>eval(`/(?<![a-z])(?!${y}(?![a-z]))[a-z]/i`).test(x)&&f(x.replace(/[a-z]/ig,t=>(t=parseInt(t,36)-1,t-9?t:35).toString(36)))+1

Try it online!

As always, long part adding 1 to letter

\$\endgroup\$
2
  • \$\begingroup\$ I think digits and _ may appear in the input string, making the code fail. \$\endgroup\$
    – Arnauld
    Jan 21 at 13:26
  • \$\begingroup\$ @Arnauld The point is that I don't remember what \w match \$\endgroup\$
    – l4m2
    Jan 21 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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