On this page:
1 Representing families
2 Secret messages
3 Counting words
4 Punyyratr

Problem set 7: Lists

This assignment is due on Wednesday, March 2 at 11:59pm. Submit it using Handin as assignment ps7. Corrections can be presented until Friday, April 1.

This problem set builds on the skills that we introduced in Lectures 2−9 and 11−14. To encourage you to review those lectures, your grade on this assignment will be limited by your grade on those lectures at the time you submit (or correct) this assignment. Remember that most lecture exercises can be resubmitted at any time.

Remember to follow the design recipe whenever you design or write a function. In particular, every type mentioned in a signature must be introduced by a data definition, except for these well-known types: Number, Image, String, Color, Boolean, KeyEvent, MouseEvent, Anything, Posn, NaturalNumber, ListOfNumbers, 1String.

Make sure start ur ps early

1 Representing families

Read Section 19.1 of the textbook. It develops a data definition for an ancestor family tree:
; An FT (short for family tree) is one of:
; - (make-no-parent)
; - (make-child FT FT String N String)
(define-struct no-parent [])
(define-struct child [father mother name date eyes])
Unfortunately, many ancestor family trees that people care about do not fit this data definition. To illustrate this problem, think of (or learn about) a person whose ancestor family tree cannot be represented as an FT. At the top of your homework submission, answer these questions in a comment in English:

Exercise 1. Who are you thinking of? You don’t need to have met this person or be in contact with them (so for example you can choose a celebrity). But they must be a real person (so for example you cannot choose Killmonger from Black Panther).

Exercise 2. What is this person’s ancestor family tree? (It should only contain this person’s ancestors.) If you can answer this question just by giving an FT, then you have not found “a person whose ancestor family tree cannot be represented as an FT”, and you should go back to the previous exercise and think of someone else.

Exercise 3. Why does that ancestor family tree not fit the data definition in the textbook?

2 Secret messages

One important topic studied in computer science is how to send secret messages without being found out. 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 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 substitution cipher. ROT13 (“rotate by 13 places”) is a simple substitution 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. We can write secret messages using this cipher, and will be decrypting some secret messages in this section.

Exercise 4. 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 is a String of length 1
; rot13 : 1String -> 1String
; returns the letter 13 spaces ahead in the alphabet
(define (rot13 letter)
    [(or (and (string<=? "a" letter) (string<=? letter "m"))
         (and (string<=? "A" letter) (string<=? letter "M")))
     (int->string (+ (string->int letter) 13))]
    [(or (and (string<=? "n" letter) (string<=? letter "z"))
         (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.

Exercise 5. Recall data definitions for lists from class. Write down the data definition for a ListOf1Strings. Define three examples of it. Write down the template for a function that processes a ListOf1Strings; make it look like a function called process-1strings, and do not put it in a comment.

Exercise 6. Design a function combine-1strings which takes a ListOf1Strings and returns it as a single String. combine-1strings should return "" if the ListOf1Strings is empty.

Exercise 7. Download the following five text files into the same folder as the file where you are completing this assignment:
To download these files, don’t use “Save Page As” or “Save As”; use “Save Link As” or “Download Linked File” in your Web browser. If you can’t find the command, try right-clicking or two-finger-tapping or long-pressing.

Go ahead and try to read the files. Looks like a bunch of gibberish! Let’s get to cracking these messages.

Exercise 8. Design a function convert-to-r13 which takes a ListOf1Strings and returns a ListOf1Strings with each 1String in the list converted to its rotated representation.

Exercise 9. Design a function file-to-r13 which takes a String (a file name) and returns the file as a ListOf1Strings with each 1String converted to its rotated representation.

You will need to use the 2htdp/batch-io library to examine the contents of files. You should use its read-1strings function to create a ListOf1Strings from a text file.

Use the files you downloaded as tests. They should start looking less like gibberish!

Exercise 10. Finally, put it all together. Design a function decrypt-file which takes a String (a file name) and returns the contents as a single String converted to its rotated representation. Remember combine-1strings from Exercise 6.

Now you should be able to read the secret messages! Terng wbo!

Next, let’s write our own secret messages.

Exercise 11. Design a function encrypt-string which takes a String and returns the rotated representation of the String. Use the built-in function explode, which takes a String and converts it to a ListOf1Strings.

Exercise 12. Design a function encrypt-string-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 write-file function 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, make sure you can read your own secret messages using decrypt-file.

3 Counting words

Exercise 13. Warmup: Design a function remove-<=100 that takes a ListOfNumbers and removes every number less than or equal to 100.

Exercise 14. Develop a data and structure definition for storing a Frequency, which combines a String and a Number and represents that many uses of that string. Call the structure frequency with fields word and count.

Exercise 15. Like in Exercise 5, develop a data definition ListOfStrings that uses cons and empty to hold arbitrarily many Strings. Also, develop a data definition ListOfFrequencies that uses cons and empty to hold arbitrarily many Frequencys.

Note Throughout the rest of this assignment, a ListOfFrequencies should never contain multiple Frequencys with the same word. You can make this assumption when your code receives a ListOfFrequencies in its input, and you must maintain this guarantee when your code produces a ListOfFrequencies in its output. For example, the following is a valid ListOfFrequencies:
(cons (make-frequency "hi" 5)
      (cons (make-frequency "hello" 4)
            (cons (make-frequency "bye" 2)
But the following is not a valid ListOfFrequencies, so you don’t need to worry about receiving it as input, and you must not produce it as output:
(cons (make-frequency "hi" 5)
      (cons (make-frequency "hello" 4)
            (cons (make-frequency "hi" 2)

Exercise 16. Design a function count-word that consumes a ListOfFrequencies and a String and adds 1 to the frequency count for that string, producing a new ListOfFrequencies. If there is no Frequency for that string, the resulting ListOfFrequencies should have a Frequency with that string and the number 1.

Exercise 17. Design a function count-all-words that takes a ListOfStrings and produces a ListOfFrequencies with the frequencies counted from the entire list of strings.

Exercise 18. Download the text of Hamlet into the same folder as your file where you are completing this assignment.

Then, create a list of words from the downloaded file. You should use the read-words function from the 2htdp/batch-io library.

Then compute the frequencies of all of the words in the file. Because this operation might take a while, don’t define it as a constant. Instead, put the operation (not its result) in a short comment, like this:
; (define hamlet-frequencies ...)

Exercise 19. Design a function frequents that consumes a ListOfFrequencies and produces a ListOfFrequencies that contains only the Frequencys from the original list where the number is more than 100. Use this to compute all the words used more than 100 times in Hamlet. Include this list in your submission, as another comment. (Did you know about the “Comment Out with Semicolons” command under the “Racket” menu in DrRacket? It’s handy.)

Help other students by answering this ungraded question: what did you have to learn to finish this problem set that we didn’t teach? Post your answer to Discord in the #ps7 channel, or put it as a comment at the bottom of your Handin submission.

4 Punyyratr

Exercise 20. Qrfvta gur shapgvbaf rapelcg-fgevat-a naq qrpelcg-fgevat-a juvpu gnxr n Fgevat naq n AnghenyAhzore a naq rapelcg (be qrpelcg) gur fgevat hfvat EBGa. Gung vf, (rapelcg-fgevat-a f 13) fubhyq or gur fnzr nf (rapelcg-fgevat f).

Exercise 21. Guvf rkrepvfr vf rapelcgrq jvgu EBG17.

Uvjzxe kyv wletkzfe kizkyvdzlj-tzgyvi. Zk jyflcu ljv ifkrkzfe czbv vetipgk-jkizex, slk zk jyflcu ifkrkv vrty tyrirtkvi rttfiuzex kf zkj gfjzkzfe ze kyv jkizex. Kyrk zj, zk jyflcu rtk czbv IFK1 fe kyv wzijk tyrirtkvi, czbv IFK13 fe kyv 13ky tyrirtkvi, IFK26 (nyzty ufvj efkyzex) fe kyv 26ky tyrirtkvi, reu IFK1 fe kyv 27ky tyrirtkvi rxrze. Kyve uvjzxe r uvtipgkzfe wletkzfe.