This lab gives you supervised practice with the idea that “templates plus functional examples equals code.” There are five problems, and I would like you to do two or three of them. Two of the problems are repeats from an earlier lab; do one of these problems only if neither of you has done it already.

For each problem, carry out these steps of the design recipe:

If you complete tables for three problems, you may then choose to finish one.

What tables should look like

Here is the structure of a table of examples:

Example problem I: Summing natural numbers

Data definition:

A natural is one of:

Here is a header, purpose statement, functional examples, and template:

; sum-to : natural -> number
; to return the sum of the natural numbers from zero to n inclusive
(define (sum-to n)
  (cond [(zero? n) ...]
        [(positive? n) (... (sub1 n) (sum-to (sub1 n)))]))

(check-expect (sum-to 0) 0)
(check-expect (sum-to 1) 1)
(check-expect (sum-to 4) 10)
(check-expect (sum-to 5) 15)

It is not worth making a table for the zero? case.

The table for the positive? case has one selector function and one natural recursion. It looks like this:

summing to positive natural numbers
WANTED n (sub1 n) (sum-to (sub1 n))
1 1 0 0
10 4 3 6
15 5 4 10

Explanation of combination: The case should combine n and (sum-to (sub1 n)) by adding them. The selection (sub1 n) need not be used except in the natural recursion.

Example problem II: Reversing a list

Here is a header, purpose statement, functional examples, and template:

; my-reverse : (listof number) -> (listof number)
; to reverse the given list
(define (my-reverse ns)
  (cond [(empy? ns) ...]
        [(cons? ns) (... (first ns) (rest ns) (my-reverse (rest ns)))]))

(check-expect (my-reverse '()) '())
(check-expect (my-reverse '(1 2)) '(2 1))
(check-expect (my-reverse '(1 2 3 4 5)) '(5 4 3 2 1))

It is not worth making a table for the empty? case.

The table for the cons? case has two selector functions and one natural recursion. It looks like this:

reversing nonempty lists
WANTED ns (first ns) (rest ns) (my-reverse (rest ns))
'(2 1) '(1 2) 1 '(2) '(2)
'(5 4 3 2 1) '(1 2 3 4 5) 1 '(2 3 4 5) '(5 4 3 2)

Explanation of combination: The case should combine (first ns) and (my-reverse (rest ns)) by appending the two lists (my-reverse (rest ns)) and (list (first ns)) in that order.

The real problems

  1. Symmetric substitution cipher.
    A substitution cipher (weakly) hides a message by substituting one letter for another. The cipher is symmetric if doing the same substitution twice reproduces the original message. Such ciphers are easy to break, but if all you want to do is keep people from stumbling over information accidentally, they are useful.

    Here is a diagram of a popular substitution cipher:

    Decryption Key
    (letter above equals below, and vice versa)

    Define a function substitute-char that takes as arguments a 1-character string c and two lists of 1-character strings top and bottom. The lists top and bottom together may be assumed to contain no duplicates.

    Here are a signature, purpose statement, and header:

    ;; substitute-char : 1-char (listof 1-char) (listof 1-char) -> 1-char
    ;; to return the character paired with c in the two rows,
    ;;    or if c does not appear, to return c itself
    (define (substitute-char c top bottom)

    Here are some functional examples:

    (check-expect (substitute-char "H" (explode "ABCDEFGHIJKLMabcdefghijklm")
                                       (explode "NOPQRSTUVWXYZnopqrstuvwxyz"))
    (check-expect (substitute-char "q" (explode "ABCDEFGHIJKLMabcdefghijklm")
                                       (explode "NOPQRSTUVWXYZnopqrstuvwxyz"))
    (check-expect (substitute-char "!" (explode "ABCDEFGHIJKLMabcdefghijklm")
                                       (explode "NOPQRSTUVWXYZnopqrstuvwxyz"))

    Lists are all very well, but for people it is easier to work with strings. To finish this problem, define a function two-row-cipher that takes three arguments: a cleartext string, a top-row string, and a bottom-row string. The function converts the cleartext to a corresponding ciphertext by applying the substitution to each character; it returns the ciphertext, also as a string. I recommend that you use substitute-char to substitute for each character of the cleartext string, and that you use BSL functions explode and implode.


      (two-row-cipher "Fishy" "ABCDEFGHIJKLMabcdefghijklm"

    Use your function to decrypt the following message, which contains an observation made by a keen student of human nature:

    Vg vf n gehgu havirefnyyl npxabjyrqtrq, gung n fvatyr zna va cbffrfvba bs n tbbq sbeghar zhfg or va jnag bs n jvsr.

  2. Anagrams.
    Two words are anagrams if they are made from exactly the same letters. Here are functional examples:

    Define a function that takes as arguments two lists of 1strings and returns a Boolean saying if they are anagrams.

    ;; anagrams-lists? : (listof 1string) (listof 1string) -> boolean
    ;; tells if the two given lists are made from exactly the same letters
    (define (anagrams-lists? word1 word2)
  3. Bowling pins.
    Bowling pins are laid out in rows with one pin in the first row, two in the second, and so on. The standard layout has four rows, roughly as follows:

             *     *     *     *
                *     *     *
                   *     *     

    The number of rows in a layout is a natural number:

    A natural is one of:

    • 0
    • (add1 n) where n is a natural

    When you are working with natural numbers you check conditions using BSL functions zero? and positive?, and when you get a positive natural, you use sub1 as you would use a selector function.

    Using the 2htdp/image teachpack, design a function that takes as input a number of rows and returns an image of a bowling-pin layout with the given number of rows. You’ll find use for the functions beside, above, circle, and overlay.

    Domain knowledge: you can get a pretty good layout by representing a single pin as a black circle laid on top of a somewhat larger white circle.

  4. Removing duplicates.
    Define a function nub which removes duplicates from a list of numbers. Your function may remove any duplicate numbers it likes, but the order of non-duplicate numbers must not be disturbed.

    Here are some functional examples:

    (check-expect (nub '(1 2 3 4 5)) '(1 2 3 4 5))
    (check-expect (nub '(1 2 3 4 5 5 5 5)) '(1 2 3 4 5))
    (check-expect (nub '(2 1 2 4 5 2)) '(2 1 4 5)) ; chose to remove last duplicates
  5. Scrabble words.
    If you have played Scrabble or Words With Friends, you know that you are given tiles with letters on them and you try to make words. To teach a computer to play Scrabble, one problem we have to solve is to figure out what words it can make. Here is a potentially useful function:

    ;; can-make-with? : string string -> boolean
    ;; to tell if the given word can be made with the given tiles
    (define (can-make-with? word tiles)
      (can-make-with-lists? (explode word) (explode tiles)))
    (check-expect (can-make-with? "frog" "asdflor") false)
    (check-expect (can-make-with? "frog" "gsdflor") true)

    Design the function can-make-with-lists? all the way through a template and a table of examples.

Submitting the lab

Ten minutes before the end of the lab, put the following text at the beginning of a DrRacket file. You may use an empty file or the source code you have been working on:

What I did during this lab:
   (you fill in this part)

What I learned during this lab:
   (you fill in this part)


The lab staff will help you articulate what you learned.

Finally, submit this file through the handin server as lab-templates. You will need to submit it using two usernames connected by a + sign, as in


You submit using Jane Doe’s password.