Exam 2: Conditionals and Recursion

Topics: Lists, recursion, higher-order procedures.

Before you learned about recursion over lists, you learned about the (map proc lst) procedure. Observe that map can be implemented recursively.

Implement (my-map proc lst), which produces a new list containing the results of applying proc to each value in lst. You should not use the built-in map procedure. Instead, use recursion.

Topics: Boolean values, recursive procedures, predicates

The reading on list recursion, revisited discusses patterns for writing recursive procedures that test whether all values, or any value, in a list satisfy some predicate. We can implement each pattern directly as a higher-order procedure: that is, a procedure that takes another procedure as a parameter.

(a) Using the given template for all-___? as a guide, write a procedure (all? pred? lst) that returns #t if pred? is true for every value in lst, and #f otherwise.

(b) Using the given template for any-___? as a guide, write a procedure (any? pred? lst) that returns #t if pred? is true for at least one value in lst, and #f otherwise.

Make this procedure easier to read as follows.

First, reformat the procedure so that the indentation properly demonstrates nesting. That is, you should choose appropriate points to put in carriage returns. Remember that MediaScheme will re-indent for you after you put in those returns, as long as you select the text and type control-tab.

Then, figure out what the procedure does. After doing so, change the names in the procedure to clarify the roles of various things. You should certainly rename the procedure a and the parameters f and s. (As a hint, start by figuring out what types f and s should be.)

Write introductory comments (the six P's) to explain the purpose (and the other P's) of the procedure formerly named a. Pay particular attention to the preconditions.

Modify the procedure so that it uses husk-and-kernel style and checks whether its preconditions are met. Throw a separate error for each failed precondition.

Topics: Characters, strings, map, composition, numeric operations

(a) Write a procedure (shift-down x) that takes as its parameter the collating-sequence number of a capital letter (A-Z), and returns an integer in the canonical range 0-25.

> (shift-down (char->integer #\A))
0
> (shift-down 65)
0
> (shift-down (char->integer #\P))
15
> (shift-down 80)
15
> (shift-down (char->integer #\Z))
25
> (shift-down 90)
25

(b) Write a procedure (add-13 x) that takes an integer as its argument and simply adds thirteen to it.

(c) Write a procedure (wrap-26 x) that takes as its argument a non-negative integer and produces a new number that results from "wrapping around" at 26. In other words, a number no larger than 25 should be produced (corresponding to the letter Z) . The idea is to produce the "rotation" effect of the 26 characters of the alphabet.

> (wrap-26 0)
0
> (wrap-26 11)
11
> (wrap-26 25)
25
> (wrap-26 26)
0
> (wrap-26 27)
1
> (wrap-26 38)
12
> (wrap-26 (+ 25 13))
12

(d) Write a procedure (shift-up x) that takes as its parameter an integer in the canonical range 0-25 and returns the corresponding the collating-sequence number of a capital letter (A-Z).

> (integer->char (shift-up 0))
#\A
> (shift-up 0)
65
> (integer->char (shift-up 15))
#\P
> (shift-up 15)
80
> (integer->char (shift-up 25))
#\Z
> (shift-up 25)
90

(e) Using the procedures from parts (a)-(d), define another procedure called char-rot13 that takes a character, and produces the ROT13-encoded character. You should make your definition as concise as possible.

> (char-rot13 #\A)
#\N
> (char-rot13 #\T)
#\G
> (char-rot13 (char-rot13 #\A))
#\A

Topics: Characters, strings, map

Write a procedure (str-rot13 str) that takes a string containing only capital letters as a parameter and returns the ROT13 version of the string. You should make your code as concise as possible.

> (str-rot13 "HELLO")
"URYYB"
> (str-rot13 (str-rot13 "HELLO"))
"HELLO"

Topics: Filters, conditionals, RGB colors as integers.

In this problem, we consider another approach to keeping messages secret. Steganography is the process of hiding a message in an image such that no one, other than the sender and receiver, even knows there is any hidden information. One simple approach is to hide a black-and-white image inside of a full-color image. No one will ever notice if a photo has been changed by only 1/255 from the original brightness values.

Here is the algorithm we used to create our steganographic image.

(a) Write a procedure, (image-steg-decode steg-image), that takes a steganographic image produced using this algorithm and produces the secret image.

Hints: Use image-variant in your procedure. Observe that if the color is represented by an odd number, this corresponds to a white pixel in the secret image. If the color is represented by an even number, this corresponds to a black pixel in the secret image.

(b) Download this image of a cute little kitty (Professor Davis's cat, Sprite, when he was a kitten), and test your procedure on it. Describe the secret image hidden inside it.

Suppose we want to draw a background and three circles on canvas.

We might write

(define color-white (rgb-new 255 255 255))
(define color-black (rgb-new 0 0 0))

(define canvas (image-new 128 128))
(image-compute-pixels! canvas
                       (lambda (col row)
                         (if (zero? (random 128))
                             color-white
                             color-black)))
(image-compute-pixels! canvas 
                       (lambda (col row)
                         (if (>= 1024 (+ (square (- col 96)) (square (- row 80))))
                             (rgb-new (+ 128 (* 255 (sin (* (/ pi 32) row)))) 
                                      0
                                      (+ 128 (* -255 (tan (* (/ pi 32) row)))))
                             rgb-transparent)))
(image-compute-pixels! canvas 
                       (lambda (col row)
                         (if (>= 512 (+ (square (- col 64)) (square (- row 96))))
                             color-black
                             rgb-transparent)))
(image-compute-pixels! canvas
                       (lambda (col row)
                         (if (>= 2048 (+ (square (- col 32)) (square (- row 128))))
                             (let ((c (* 4 (sqrt (+ (square (- col 4))
                                                    (square (- row 128)))))))
                               (rgb-new c c c))
                             rgb-transparent)))
(image-show canvas)

Rewrite this code so that, instead of using one call to image-new and three calls to image-compute-pixels!, it uses a single call to image-compute.

Hint: Use a cond to decide which, if any, of the circles each position belongs in.

Hint: Which circle appears in front, and which appears behind? Your code should produce approximately the same image as the code above (up to some randomness).

Topics: Numeric recursion, GIMP tools

;;; Procedure:
;;;   position->color
;;; Parameters:
;;;   col, an integer
;;;   row, an integer
;;; Purpose:
;;;   Compute a color based on col and row.
;;; Produces:
;;;   color, an RGB color
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   Different col/row combinations are likely to give different colors.
;;;   Nearby col/row combinations may give similar colors.
(define position->color
  (lambda (col row)
    (rgb-new (+ 128 (* 128 (sin (* pi row 0.0625))))
             (+ 128 (* 128 (cos (* pi col 0.0625))))
             (+ 128 (* 128 (sin (* pi (+ row col) 0.0625)))))))

;;; Procedure:
;;;   draw-filled-circle!
;;; Parameters:
;;;   image, an image
;;;   col, an integer
;;;   row, an integer
;;;   radius, an integer
;;; Purpose:
;;;   Draws a filled circle with the specified in the current color, centered at (col,row).
;;; Produces:
;;;   [Nothing; Called for the side effect]
;;; Preconditions:
;;;   0 <= col < (image-width image)
;;;   0 <= row < (image-height image)
;;;   0 < radius
;;; Postconditions:
;;;   The image now contains the specified circle.  (The circle may not be visible.)
(define draw-filled-circle!
  (lambda (image col row radius)
    (image-select-ellipse! image REPLACE
                           (- col radius) (- row radius)
                           (+ radius radius) (+ radius radius))
    (image-fill-selection! image)
    (image-select-nothing! image)))

;;; Procedure:
;;;   draw-moving-circles!
;;; Parameters:
;;;   image, an image
;;;   n, an integer
;;;   col, an integer
;;;   row, an integer
;;;   radius, an integer
;;;   hoffset, an integer
;;;   voffset, an integer
;;;   roffset, an integer
;;; Purpose:
;;;   Draw at most n circles, with the first centered at (col,row) 
;;;   having the radius given, and each subsequent circle center offset 
;;;   by the appropriate multiple of hoffset and voffset and radius changed
;;;   by the appropriate multiple of roffset.
;;; Produces:
;;;   [Nothing; Called for the side effect.]
;;; Preconditions:
;;;   All circles can be drawn on the image.
;;; Postcondtions:
;;;   The image has been appropriately modified. Less than n circles may 
;;;   be drawn if roffset is negative. A circle centered at (col,row) has a 
;;;   color given by (position->color col row).

(define img (image-new 100 100)) (image-show img) (draw-moving-circles! img 10 30 20 20 5 3 -2)
(define img (image-new 100 100)) (image-show img) (draw-moving-circles! img 10 30 80 5 3 -3 2)
(define img (image-new 100 100)) (image-show img) (draw-moving-circles! img 5 70 70 25 -10 -10 -8)