# Crack the Caesar cipher

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] • Would outputting in the range [1,26] instead be acceptable (this is currently prohibited by your rules)? Jan 21 at 14:05 • @JonathanAllan I've decided against it, since [0,25] is a more natural range Jan 21 at 14:12 • Can you take the ciphertext as an array of words? Jan 21 at 17:19 • @Jonah No, the annoying string processing is a part of this challenge Jan 21 at 17:24 • 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. Jan 21 at 17:32 ## 7 Answers # 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


# 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!

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

# 05AB1E (legacy), 19 18 bytes

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


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

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)


# 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  # Retina 0.8.2, 83 bytes TLl [^a-z¶]+ @ ^ ¶ {ms\A(#*)¶@?((\w+\b)(?=.*¶\3$)@?)+$.*$.1
^\B
#
Tlzl^.*¶.*


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

TLl


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. Tlzl^.*¶.*  If the ciphertext is still present then rotate it. # 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! • I guess this fails in many cases when the output should be 0: Try it online! Jan 23 at 17:10 • Quick-fix for +4 Jan 23 at 17:10 • @pajonk - Ah, thanks for spotting, I didn't think of that. Jan 23 at 18:47 # 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

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