Problem set 7: Lists🔗

This assignment is due on Wednesday, October 16 at 11:59pm. Submit it using Handin as assignment ps7. Corrections can be presented until Friday, November 8.

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 capped by your grade on those lectures. You can resubmit lecture exercises 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, Posn, Anything, NaturalNumber, ListOfNumbers, 1String.

1 Representing ancestors🔗

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).

Hint: If you have trouble thinking of a real person, try yourself first: try to write down your own ancestors by giving an FT. Then, think of someone else you know and try to write down their ancestors by giving another FT.

Exercise 2. Who are this person’s ancestors? If you can answer this question just by giving an FT, then you have not found “a person whose ancestors cannot be represented as an FT”, and you should go back to the previous exercise and think of someone else. In particular, just because an ancestor is unknown doesn’t mean that they cannot be represented as an FT; the textbook discusses such a situation explicitly.

Exercise 3. Why do this person’s ancestors 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.

2.1 Reading secret messages🔗

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.

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. In the previous exercise, you should have written at least one function example where the input to convert-to-r13 is a ListOf1Strings with some 1Strings. Calculate step-by-step from this example.

But when you get to the point where rot13 is called, step directly to what the result of the call should be. And when you get to the point where convert-to-r13 is recursively called, step directly to what the result of the call should be.

Exercise 10. 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 11. 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. Use combine-1strings.

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

2.2 Writing our own secret messages🔗

Exercise 12. 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 13. 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.

2.3 Punyyratr🔗

Exercise 14. Guvf vf n punyyratr rkrepvfr.

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 15. Guvf vf n punyyratr rkrepvfr. 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.

3 Counting words🔗

This section is required for all students.

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

Exercise 17. 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 18. 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.

Exercise 19. 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 20. 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 21. 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.

Exercise 22. 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.