SICP Exercise 2.41: Triple Sum

Write a procedure to find all ordered triples of distinct positive integers i, j, and k less than or equal to a given integer n that sum to a given integer s.

This bears some resemblance to the prime-sum-pairs procedure in the "Nested mappings" section and exercise 2.40. This time, however, we want to generate triples of integers, i, j, and k, such that 1 ≤ i < j < k ≤ n and i + j + k = s.

We already have a procedure, unique-pairs, that will generate all unique ordered pairs of distinct positive integers less than or equal to a given value. We can use this as the basis for building the triples. All we need to do is for each k, such that 3 ≤ k ≤ n, generate the unique pairs of distinct positive integers less than k (using unique-pairs), add k to each of these pairs to give all of the valid triples for that value of k and then append the results for all values of k together. And the authors have handily provided a procedure, flatmap, that encapsulates the "map and accumulate with append" process. Here's the snippet:

(flatmap (lambda (i)
                 (map (lambda (j) (cons i j))
                      (unique-pairs (- i 1))))
         (enumerate-interval 3 n))

Now all we need to do is to filter this to those triples whose sum is s and wrap it in a procedure:

(define (triples-equaling s n)
  (filter (lambda (x)
                  (= (+ (car x) (cadr x) (caddr x)) s))
          (flatmap (lambda (i)
                           (map (lambda (j) (cons i j))
                                (unique-pairs (- i 1))))
                   (enumerate-interval 3 n))))

Let's try it out:

> (triples-equaling 10 10)
'((5 3 2) (5 4 1) (6 3 1) (7 2 1))
> (triples-equaling 15 10)
'((6 5 4) (7 5 3) (7 6 2) (8 4 3) (8 5 2) (8 6 1) (9 4 2) (9 5 1) (10 3 2)
  (10 4 1))
> (triples-equaling 6 3)
'((3 2 1))
> (triples-equaling 10 5)
'((5 3 2) (5 4 1))

SICP Exercise 2.40: Unique Pairs

Define a procedure unique-pairs that, given an integer n, generates the sequence of pairs (i,j) with 1 ≤ j < i ≤ n. Use unique-pairs to simplify the definition of prime-sum-pairs given above.

In the section on "Nested mappings" the authors show us how to build this sequence of pairs using accumulate:

(accumulate append
            nil
            (map (lambda (i)
                   (map (lambda (j) (list i j))
                        (enumerate-interval 1 (- i 1))))
                 (enumerate-interval 1 n)))

They then introduce flatmap to simplify the process of mapping and accumulating with append and use this to produce their definition of prime-sum-pairs:

(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum?
               (flatmap
                (lambda (i)
                  (map (lambda (j) (list i j))
                       (enumerate-interval 1 (- i 1))))
                (enumerate-interval 1 n)))))

The highlighted section above shows the portion of the procedure that builds the sequence of pairs, and this is pretty much exactly what we want for our unique-pairs procedure:

(define (unique-pairs n)
  (flatmap (lambda (i) (map (lambda (j) (list i j))
                            (enumerate-interval 1 (- i 1))))
           (enumerate-interval 1 n)))

Note that this procedure does some unnecessary work though. There are no pairs of integers such that 1 ≤ j < i ≤ n where i=1. The smallest i we can successfully generate any such pairs for is 2 - there's only one such pair: (1,2). So there's no point in starting the sequence passed to flatmap at 1 - we can start it at 2 instead without changing the outcome:

(define (unique-pairs n)
  (flatmap (lambda (i) (map (lambda (j) (list i j))
                            (enumerate-interval 1 (- i 1))))
           (enumerate-interval 2 n)))

Let's give it a spin:

> (unique-pairs 3)
'((2 1) (3 1) (3 2))
'> (unique-pairs 4)
((2 1) (3 1) (3 2) (4 1) (4 2) (4 3))
'> (unique-pairs 5)
((2 1) (3 1) (3 2) (4 1) (4 2) (4 3) (5 1) (5 2) (5 3) (5 4))

Finally we can replace the old code to generate unique pairs in prime-sum-pairs with an appropriate call to unique-pairs:

(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum? (unique-pairs n))))

...and then test it works:

> (prime-sum-pairs 3)
'((2 1 3) (3 2 5))
> (prime-sum-pairs 4)
'((2 1 3) (3 2 5) (4 1 5) (4 3 7))
> (prime-sum-pairs 5)
'((2 1 3) (3 2 5) (4 1 5) (4 3 7) (5 2 7))

Progress Report

Well, it's been a couple of weeks since the last one...

As of tomorrow's meeting we'll have covered all the exercises up to and including 2.72, completing section 2.3 of the book. That means we've covered a grand total of 118 exercises.

I've been doing pretty well at catching up though. I've just finished writing up exercise 2.39, which means that I've written up 85 exercises in total, and a whopping 22 in the last week. So I'm now 72% of the way to being caught up with the ever-moving target.

If I'm really lucky I'll get caught up just in time to fall behind as I go away on holiday...