brutus – Et tu, brute? – Computer Science by Example

brutus – Et tu, brute?

The Caesar cypher is an encryption method where one replaces each letter of the alphabet by the k-th letter coming after it in the alphabet while wrapping around from Z to A.

Caesar reading a scroll: "Ohw xv phhw qhdu wkh Wkhdwuh ri Srpshb dw vxqgrzq. Dyh Fdhvdu!"

Using the Caesar cypher one can encrypt a text in 26 different ways by varying the value of k. So the value of k can vary between 0 and 25 inclusive. (A k of 27 or -25 is equivalent to 1. Going to the left 25 times or going to the right 27 times is the same as going to the right one time. So in this exercise, we consider k in the interval 0 ≤ k < 26 to be canonical.)

Caesar cypher encryption and decryption represented in a circle

One can use the above circles to encrypt or decrypt a text using the Caesar cypher for the keys of 3 and -12 by replacing letters on the outer circle by adjacent letters in the inner circle.

In this exercise your task is to break the Caesar cypher. Write a program that given a set of dictionary words and an encrypted piece of text discovers the key used during encryption and the original plain text. Your program should find the plain text that maximises the use of the given dictionary words.

While counting the occurrence of dictionary words, you should ignore letter case changes: both “the”, “The” and “THE” should count as occurrences of “the”. The final text should nevertheless respect capitalization.

Arguments, input and output

Your program will be run with dictionary words given as command line arguments. The encrypted text will be given on the standard input.

$ ./brutus some dictionary words <secret-message.txt

Your program should print the unencrypted text on standard output (stdout) and print the message encryption key: <k> on stderr. If decryption is not possible, your program should print could not decrypt to standard error (stderr) and return a non-zero exit code.

The input text will have no more than 10 000 characters. Each line of input will have no more than 100 characters.

Example 1

command line arguments.

Ave Gaius Julius Caesar

input.

Ghdu Mxolxv,
Ohw xv phhw qhdu
wkh Wkhdwuh ri Srpshb
dw vxqgrzq.
Dyh Fdhvdu!

(stderr) output.

encryption key: 3

(stdout) output.

Dear Julius,
Let us meet near
the Theatre of Pompey
at sundown.
Ave Caesar!

You can use input redirection with < to test your program. Suppose the encrypted input text is stored in a file called secret.txt, your program should work like so:

$ gcc brutus.c -o brutus
$ ./brutus Ave Gaius Julius Caesar <secret.txt
encryption key: 3
Dear Julius,
Let us meet near
the Theatre of Pompey
at sundown.
Ave Caesar!

Example 2

command line arguments.

a the

input.

Gur dhvpx oebja sbk
whzcf bire gur ynml qbt.
Gur svir obkvat
jvmneqf whzc dhvpxyl.

(stderr) output.

encryption key: 13

(stdout) output.

The quick brown fox
jumps over the lazy dog.
The five boxing
wizards jump quickly.

You can use input redirection with < to test your program. Suppose the encrypted input text is stored in a file called secret.txt, your program should work like so:

$ gcc brutus.c -o brutus
$ ./brutus a the <secret.txt
encryption key: 13
The quick brown fox
jumps over the lazy dog.
The five boxing
wizards jump quickly.

Example 3

command line arguments.

the this that is are

input.

Nggnpx ng qnja.
Ngndhr nb nznaurpre.
Ngnx b fmjvpvr.

(stderr) output.

could not decrypt

(stdout) output. empty/nothing

exit code. non-zero exit code

You can use input redirection with < to test yor program. Suppose the encrypted input text is stored in a file called secret.txt, your program should work like so:

$ gcc brutus.c -o brutus
$ ./brutus the this that is are <secret.txt
could not decrypt

Scoring

2/12: works for examples 1 and 2 but produces output in an incorrect format;
4/12: works for examples 1 and 2 and produces output in the correct format;
6/12: fails to detect dictionary occurrences with varied casing/capitalization;
10/12: works for other test cases
12/12: works for edge test cases

Hints

Here are a few tips:

solve rot13 and caesar first to learn about the Caesar cypher;
solve erro and errxit first to learn about stderr and exit codes;
modularize your code using functions;
use input redirection with < to facilitate the testing of your program
for C programmers:
- use knowledge of arrays and pointers to your advantage!
- you can solve this exercise wether you choose to use fgets or getchar. But differently from rot13 and caesar you will need to store input in memory (array).
- dictionary words will be given in command line arguments: read these from argc and argv accordingly.
for Haskell programmers:
- you may need to be familiar with getArgs, hPutStrLn, stderr and exitFailure to solve this problem.
- applying toLower may be helpful to ignore case before comparing strings.

Good luck and enjoy!

try first: caesar hello-cmd erro errxit

index | submit | rank | book