Problem Set 8: Caesar ciphers
Submit this assignment to ps8 on Handin.
Note: Whenever you write a function in this class, follow the design recipe. You will be graded accordingly.
1 Decrypting messages in ROT13
One important topic studied in computer science is how to send secret messages. For example, a voter should be able to send a secret vote to a counting machine. To make sure nobody else can read the secret message, we send a different, corresponding message that (ideally) nobody else can read. This is called encrypting the secret message. Recovering the secret message from the encrypted message is called decrypting it.
A basic method to encrypt a secret message is to replace some letters with other letters. This method is called a Caesar cipher. (Although this method provides no security in modern times, it seems it was useful historically.) ROT13 ("rotate by 13 places") is a simple Caesar cipher that replaces a letter with the 13th letter away from it in the alphabet. So, for example, "a" would be replaced with "n", "O" would be replaced with "B", and so on.
Problem 1. Here we provide a data definition for a 1String, and a definition for rot13. Given a 1String, rot13 checks if it is a lowercase letter between "a" and "n". If so, it will add 13 to the integer representation of the 1String, which results in the 13th letter after it in the alphabet. Similarly, rot13 checks if is a lowercase letter between "n" and "z", and subtracts 13 to get the 13th letter before it in the alphabet. rot13 does the same thing for uppercase letters. The else case handles 1Strings like " " and ".", which don’t rotate.
; A 1String a String of length 1 ; rot13: 1String -> 1String ; returns the letter 13 letters ahead in the alphabet (define (rot13 letter) (cond [(and (string<=? "a" letter) (string<=? letter "m")) (int->string (+ (string->int letter) 13))] [(and (string<=? "n" letter) (string<=? letter "z")) (int->string (- (string->int letter) 13))] [(and (string<=? "A" letter) (string<=? letter "M")) (int->string (+ (string->int letter) 13))] [(and (string<=? "N" letter) (string<=? letter "Z")) (int->string (- (string->int letter) 13))] [else letter]))
Write tests for the rot13 function. Make sure to test every possible case of the cond clause.
Problem 2. Write down the data definition for a ListOf1Strings, using empty and cons. Define three examples of ListsOf1Strings. Write down the template for ListOf1Strings.
Problem 3. Design a function combine-1strings which takes a ListOf1Strings and returns it as a single String. The function combine-1strings should return "" if the ListOf1Strings is empty.
Problem 4. Download the following three text files into the same folder as the file where you are completing this assignment (e.g., by using "Save link as"):
Go ahead and try to read the files. Looks like a bunch of gibberish! Let’s get to decrypting these messages.
Problem 5. Design a function map-rot13 which takes a ListOf1Strings and returns a ListOf1Strings with each 1String in the list rotated 13 positions.
Problem 6. Design a function decrypt13-file which takes a String (a file name) and returns the contents of the file as a decrypted String.
You will need to use the 2htdp/batch-io library to examine the contents of files. Use the built-in read-1strings function to create a ListOf1Strings from a text file. (Hint: use map-rot13 and combine-1strings as helper functions.)
Use the files you downloaded as tests. Now you should be able to read the secret messages! Terng wbo!
Problem 7. Design a function decrypt13 which takes a String encrypted in ROT13 and decrypts it. Use the explode function.
2 Encrypting messages in ROT13
Problem 8. Design a function encrypt13 which takes a String and encrypts it in ROT13. Does the definition look familiar?
Problem 9. Design a function encrypt13-to-file that takes two Strings (a message to encrypt and a file name) and writes the encrypted message to the given file name. Use the built-in write-file from the 2htdp/batch-io library. The write-file function returns the given file name, and your function should also return the given file name.
Finally, see if you can read your own secret messages using decrypt13-file.
3 More Caesar ciphers
Problem 10. Qrfvta n shapgvba ebg1 juvpu gnxrf n 1Fgevat naq ebgngrf vg bar cbfvgvba vs vg vf n yrggre bs gur nycunorg. Sbe rknzcyr, jura ebg1 vf tvira gur 1Fgevat n, vg ergheaf gur 1Fgevat o. Jura ebg1 vf tvira gur 1Fgevat m, vg ergheaf gur 1Fgevat n. Jura ebg1 vf tvira gur 1Fgevat N, vg ergheaf gur 1Fgevat O.
Problem 11. Va guvf ceboyrz lbh jvyy qrfvta n shapgvba juvpu cebprff n angheny ahzore nf n erphefvir havba. Urer vf gur qngn qrsvavgvba naq grzcyngr:
; A NaturalNumber is one of: ; - 0 ; - (add1 n) ; process-nat : NaturalNumber -> ... (define (process-nat n) (cond [(zero? n) ...] [(positive? n) (... (process-nat (sub1 n)) ...)]))
Qrfvta n shapgvba ebg juvpu gnxrf n AnghenyAhzore naq n 1Fgevat naq ebgngrf vg gur tvira ahzore bs cbfvgvbaf vs vg vf n yrggre bs gur nycunorg. Sbe rknzcyr, jura ebg vf tvira 4 naq gur 1Fgevat n, vg ergheaf gur 1Fgevat r. Jura ebg vf tvira 27 naq gur 1Fgevat N, vg ergheaf gur 1Fgevat O.
Problem 12. Qrfvta n shapgvba rapelcg juvpu gnxrf n AnghenyAhzore a naq n Fgevat naq rapelcgf vg va EBGa. Qrfvta n shapgvba qrpelcg juvpu gnxrf n AnghenyAhzore a naq n Fgevat rapelcgrq va EBGa naq qrpelcgf vg. Lbh jvyy arrq gb qrfvta n urycre shapgvba gb or hfrq va qrsvavat obgu bs gurfr shapgvbaf.
Tvira n Fgevat, rapelcgvat vg va EBGa naq gura qrpelcgvat vg fubhyq lvryq rknpgyl gur fnzr fgevat; qrpelcgvat n fgevat rapelcgrq va EBGa fubhyq nyfb lvryq rknpgyl gur fnzr fgevat. Znxr fher guvf gur pnfr.