CS 2510 - Assignment 1 : Review, Data, Recursion, and Accumulators

CS 2510 - Assignment 1: Review, Data, Recursion, and Accumulators

This problem set is a review of advanced CS 2500 (or CSU 211) concepts in Scheme. The HtDP book is available online.

Your solutions should be runnable in DrRacket (or DrScheme) using the HtDP Advanced Student language, and should be fully tested using the testing.ss teachpack (use check-expect). The testing teachpack can be added under the Language menu.

You will submit your assignment via the hand-in plugin/server, as discussed in the first Lab.

HtDP Problems:

31.3.3 and 31.3.4 : For each problem produce three different versions of the requested function. One version each using:

The design recipe,

An accumulator, and

Either of the loop functions foldl or foldr (your choice).

Name the different functions appropriately (e.g., how-many, how-many-acc, how-many-fold)

Other Problems:

For the last two problems you'll be using Posn structures from HtDP. In order to use them, you need to add the world.ss teachpack. Other functions will also be used in the last problem.

Remember Scheme structures? The DrRacket Advanced Student language has a built-in structure, called Posn, that represents positions on a two dimentional grid. The original definition is likely something similar to:
          ;; A Posn has an 'x' and a 'y'
          (define-struct posn (x y))
        
You should also rember that a struct definition like that one also defines some useful functions: a constructor, and accessors.
          ;; Make a new Posn
          (define a-posn (make-posn 15 7))
          ;; Get its 'x' component
          (check-expect (posn-x a-posn) 15)
        

Problem A1:
Make a few Posn examples, and write a data-definition for a [listof Posn]. Make some examples of lists of Posns.

Design a function that returns a list of all the 'x' components of a list of Posns. Remember that design means more than just writing the function. Follow the recipe!

Design the same function (with a new name) using the Scheme loop function map
Design a function, say absolute->relative, that calculates the relative Posns for each of the list elements, starting at (0,0). In otherwords, return a new list of Posns that are adjusted so that they represent the change in position from the previous Posn in the list. Hint: think accumulator, though you don't actually need one.

Here's a few tests...
    ;; Basic Test...
    (check-expect (relative->absolute '()) '())
    ;; One Posn
    (check-expect (relative->absolute (list (make-posn 4 5)))
                  (list (make-posn 4 5)))
    ;; Two Posns in the same place
    (check-expect (relative->absolute (list (make-posn 4 5) (make-posn 4 5)))
                  (list (make-posn 4 5) (make-posn 0 0)))

    ;; A bunch of Posns...
    (check-expect (relative->absolute 
                   (list (make-posn 1 6) (make-posn 20 13)
                         (make-posn 5 15) (make-posn 15 5)
                         (make-posn 20 7)))
                  (list (make-posn 1 6) (make-posn 19 7)
                        (make-posn -15 2) (make-posn 10 -10)
                        (make-posn 5 2)))
              
Design a function, say relative->absolute, that converts a list of 'relative' Posns into a list of 'absolute' Posns (again, starting at (0,0)).

Note: The two functions you've designed should have no effect when applied in sequence:
                (define a-lop (list (make-posn 5 7)
                                    (make-posn 14 13)))
                (check-expect (relative->absolute (absolute->relative a-lop)) a-lop)
              
Problem A2:
Consider the program below... study it well. In order to get it to run you need to add the world.ss teachpack. Paste the program into DrRacket and run it to see what it does. See the bottom of the page for a few screen shots from my computer.

Image (1) is the program as shown below. The other images will be features you add.
          ;; Width and Height of our Scene
          (define WIDTH 300)
          (define HEIGHT 300)

          ;; Basic empty scene
          (define base-scene (empty-scene WIDTH HEIGHT))

          ;; A World is a [listof Posn]
          
          ;; put-dot : Scene Posn -> Scene
          ;; Put a single Dot into the Scene at the given Posn
          (define (put-dot scn p)
            (place-image (circle 3 'solid 'blue)
                         (posn-x p) (posn-y p)
                         scn))

          ;; draw-dots : World -> Scene
          ;; Draw the dots of the World (a list of Posn)
          (define (draw-dots ps)
            (cond [(empty? ps) base-scene]
                  [else (put-dot (draw-dots (rest ps)) (first ps))]))

          ;; mouse-click : World Number Number Symbol -> World
          ;; Add a new Posn to the World if the mouse was clicked
          (define (mouse-event w x y what)
            (cond [(symbol=? what 'button-down)
                   (cons (make-posn x y) w)]
                  [else w]))

          ;; Create a window giving Width, Height, and an initial World
          (big-bang WIDTH HEIGHT 0.1 '())
          ;; Setup the redraw events to call our function
          (on-redraw draw-dots)
          ;; Setup the mouse events to call our function
          (on-mouse-event mouse-event)
        
Once you understand how it works, complete the following problems. Make sure you keep all the new versions of your functions. In otherwords, you can modify draw-dots in-place, but be sure that we can see all of your new functions separately.

Transform draw-dots into accumulator style. Call the new function draw-dots-acc. What does your function accumulate?

Add a number/label to each dot by designing new functions, put-num-dot and draw-num-dots. Make sure draw-num-dots is in accumulator style, and use it instead of draw-dots in setup. See Image (2) for an example of what I expect (after a few clicks).

Hint: you'll need to use text and number->string.

If your numbers arn't in order, then fix them so they do not change as dots are added. You may need to modify the accumulator's starting value and its update expression.

Design the function draw-lines, in accumulator style that draws lines between the dots. Hint: you'll also want to pass the previous point's coordinates (in addition to the accumulator) when you make your recursive call. See Image (3) for an example.

Finally, design the function draw-num-lines that draws both lines and number/labels on the dots. See Image (4) for an example. This function doesn't have to be in accumulator style, but if you're working off your other function it probably will be.
Example Screen Shots:

Image (1)
Image (2)

Image (3)
Image (4)