SICP Exercise 2.44: Splitting Up

Define the procedure up-split used by corner-split. It is similar to right-split, except that it switches the roles of below and beside.

up-split is very similar... Here's right-split:

(define (right-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (right-split painter (- n 1))))
        (beside painter (below smaller smaller)))))

To produce up-split we simply rename the procedure and recursive call and switch below and beside around to give:

(define (up-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (up-split painter (- n 1))))
        (below painter (beside smaller smaller)))))

Using the spiral we produced earlier we can put this to the test:

((up-split spiral 3) window)

...produces the following:

SICP's Picture Language in DrRacket

Section 2.2.4 of SICP introduces us, bit by bit, to a language that can be used for representing and drawing pictures. Unfortunately, as graphics support tends to be implementation-dependent the author's don't (and can't, without tying themselves to a particular Scheme interpreter) provide a way of actually drawing the graphics. The closest they get is to posit the existence of a procedure, draw-line, which takes two vectors representing the start and end points of the line and draws a line between those points.

When I originally did the exercises in this section I didn't worry myself too much about this. After all, some of the exercises rely upon the existence of procedures that aren't addressed until later exercises, so I wouldn't necessarily be able to produce sensible pictures for each exercise until I'd completed them all.

Of course now I'm writing up the exercises after the fact, and have a full picture language at my disposal. So I decided I'd produce at least an implementation of draw-line that would allow me to produce some pictures to post in the exercises as I write them up.

I've noted before that one of the interpreters I'm using is DrRacket, which has its own graphical interface toolkit. After a bit of head-scratching and hitting the docs, here's what I came up with:

#lang racket
(require racket/gui/base)

(define picture-size 300)

(define bitmap
  (make-object bitmap% (+ picture-size 1) (+ picture-size 1)))

(define bitmap-dc
  (new bitmap-dc% [bitmap bitmap]))

(define frame
  (new frame% [label "SICP Picture Language"]))

(define canvas
  (new canvas%
     [parent frame]
     [min-width (+ picture-size 1)]
     [min-height (+ picture-size 1)]
     [paint-callback (lambda (canvas dc)
                       (send dc draw-bitmap bitmap 0 0))]))

(define (draw-line start end)
  (send bitmap-dc 
        draw-line
        (xcor-vect start)
        (ycor-vect start)
        (xcor-vect end)
        (ycor-vect end)))

(define window (make-frame (make-vect 0 picture-size)
                           (make-vect picture-size 0)
                           (make-vect 0 (- 0 picture-size))))

(send frame show #t)

You'll need the vector constructor and selectors from exercise 2.46 and the same for one of the frame representations from exercise 2.47 for these to work.

Note that window provides a frame that will map a picture with x and y coordinates in the ranges [0..1] into the [0..picture-size] that's provided. It needs to map standard Cartesian coordinates into an inverted coordinate system as, like many windowing systems, the coordinates (0, 0) correspond to the top-left corner of the window, as opposed to the bottom-left as is used by the picture language.

We can also give ourselves a shape to play with. I'm using a procedure I produced as part of exercise 2.49, build-segments-list, that basically takes a list of vectors and turns those into a list of segments. I've used this to produce a spiral:

(define spiral
  (segments->painter (build-segments-list (make-vect 0.0 0.0)
                                          (make-vect 1.0 0.0)
                                          (make-vect 1.0 1.0)
                                          (make-vect 0.0 1.0)
                                          (make-vect 0.0 0.1)
                                          (make-vect 0.9 0.1)
                                          (make-vect 0.9 0.9)
                                          (make-vect 0.1 0.9)
                                          (make-vect 0.1 0.2)
                                          (make-vect 0.8 0.2)
                                          (make-vect 0.8 0.8)
                                          (make-vect 0.2 0.8)
                                          (make-vect 0.2 0.3)
                                          (make-vect 0.7 0.3)
                                          (make-vect 0.7 0.7)
                                          (make-vect 0.3 0.7)
                                          (make-vect 0.3 0.4)
                                          (make-vect 0.6 0.4)
                                          (make-vect 0.6 0.6)
                                          (make-vect 0.4 0.6)
                                          (make-vect 0.4 0.5)
                                          (make-vect 0.5 0.5))))

We can then display our spiral... Invoking this:

(spiral window)

Produces this: Now with that done we can actually get on to the exercises themselves.

SICP Exercise 2.43: Louis' Queens

Louis Reasoner is having a terrible time doing exercise 2.42. His queens procedure seems to work, but it runs extremely slowly. (Louis never does manage to wait long enough for it to solve even the 6× 6 case.) When Louis asks Eva Lu Ator for help, she points out that he has interchanged the order of the nested mappings in the flatmap, writing it as

(flatmap
 (lambda (new-row)
   (map (lambda (rest-of-queens)
          (adjoin-position new-row k rest-of-queens))
        (queen-cols (- k 1))))
 (enumerate-interval 1 board-size))

Explain why this interchange makes the program run slowly. Estimate how long it will take Louis's program to solve the eight-queens puzzle, assuming that the program in exercise 2.42 solves the puzzle in time T.

Here's Louis' full version of the queens procedure:

(define (queens board-size)
  (define (queen-cols k)  
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (new-row)
            (map (lambda (rest-of-queens)
                   (adjoin-position new-row k rest-of-queens))
                 (queen-cols (- k 1))))
          (enumerate-interval 1 board-size)))))
  (queen-cols board-size))

So what effect has interchanging the order of the nested mappings in flatmap had? Well, it still correctly constructs all of the potential positions for a queen to go in the current column. However, whereas in the original version each call to (queen-cols k) would have made only a single call to (queen-cols (- k 1)), in Louis' version each call to (queen-cols k) will result in board-size calls to (queen-cols (- k 1)).

Why is this?

Well in the original version in order to evaluate flatmap the interpreter first evaluates (queen-cols (- k 1)). flatmap then processes the resulting list by applying the nested mapping to each set of positions in the list. This nested mapping takes a set of safe positions for the previous columns, enumerates all of the possible row indexes for the board-size and then generates a new list of sets of potential positions from the set passed by appending each of these potential positions for the current column onto the passed set in turn.

In Louis' version this logic is reversed. In order to evaluate flatmap the interpreter first enumerates all of the possible row indexes for the board-size. flatmap then processes this list of row indexes, applying the nested mapping to each set of positions in the list. In this case the nested mapping takes a row index, generates all of the possible safe board positions for the previous columns and then generates a new list of sets of potential positions from the row index passed by appending it onto each of the each of the known safe positions for the previous columns in turn.

What does this mean for the run time of Louis' version?

In the original version in order to calculate the safe positions for (queens board-size) the interpreter would need to make one call to (queen-cols board-size), one to (queen-cols (- board-size 1)), and so on down to a single call to (queen-cols 0). This means that, for any given board-size, there are board-size + 1 calls to queen-cols.

In Louis version in order to calculate the safe positions for (queens board-size) the interpreter has to make one call to (queen-cols board-size), which then makes board-size calls to (queen-cols (- board-size 1)). Each of these calls in turn makes board-size calls to (queen-cols (- board-size 2)), giving a total of board-size² calls to (queen-cols (- board-size 2)). This carries on down to (queen-cols 0), which is called a grand total of board-sizeboard-size times. This increase in the number of steps required at each subsequent level gives us a geometric progression and so we can calculate the sum of this progression as:

  n
  Σ board-sizei
  i=0
= 1 - board-sizeboard-size+1
       1 - board-size

Note that we can also express the number of calls to queen-cols in the original implementation using the same denominator (i.e. 1 - board-size):

  board-size + 1
= 1 - board-size × board-size + 1
  1 - board-size  
= (1 - board-size)(board-size + 1)
            1 - board-size
= board-size + 1 - board-size2 - board-size
              1 - board-size
= 1 - board-size2
  1 - board-size

Then we can determine the ratio of calls to queen-cols that are required between the two algorithms for different board sizes by dividing the steps required for Louis algorithm by the steps required for the original algorithm:

  1 - board-sizeboard-size+1  /  1 - board-size2
       1 - board-size          1 - board-size
= 1 - board-sizeboard-size+1  ×  1 - board-size 
       1 - board-size          1 - board-size2
= 1 - board-sizeboard-size+1
      1 - board-size2

If we then make the naïve (and wildly incorrect) assumption that a single queen-cols call takes constant time then this would allow us to state that, given time T for the original algorithm, we would expect Louis' algorithm to take:

(1 - board-sizeboard-size+1)T
     1 - board-size2

It's a wildly incorrect assumption as the number of steps required to evaluate (queen-cols k) depends upon both k and board-size. However, I'm going to leave the exercise here.