SICP Exercise 2.41: Triple sum

"Life is all about sharing. If we are good at something, pass it on." - Mary Berry

SICP Exercise 2.41: Triple sum

2021-10-18

Exercise 2.41: 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.

unique-triples can be written easily base on unique-pairs in 2.40:

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

Define make-triple to convert a triple to a list:

(define (make-triple triple)
    (list (car triple) (cadr triple) (car (cddr triple))))

equal-given-sum? is used to check if sum of a triple is equal to a given integer s:

(define (equal-given-sum? triple s)
    (= s (+ (car triple) (cadr triple) (car (cddr triple)))))

and the final procedure:

(define (triple-sum n s)
    (map make-triple (filter equal-given-sum? (unique-triples n))))

Test:

$ racket 2.41-triple-sum.rkt
filter: contract violation
  expected: (any/c . -> . any/c)
  given: #<procedure:equal-given-sum?>
  context...:
   /Users/quanta/github.com/quantonganh/sicp-exercises/2.41-triple-sum.rkt:28:0
   body of "/Users/quanta/github.com/quantonganh/sicp-exercises/2.41-triple-sum.rkt"

Take a look at the filter syntax:

(filter pred lst) → list?

  pred : procedure?
  lst : list?

Returns a list with the elements of lst for which pred produces a true value. The pred procedure is applied to each element from first to last.

So, the reason is the predicate only takes one parameter while the equal-given-sum? takes 2 parameters.

We can fix that by using lambda:

(define (triple-sum n s)
    (map make-triple (filter (lambda (triple)
                                (equal-given-sum? triple s))
                             (unique-triples n))))

Verify:

$ racket 2.41-triple-sum.rkt
>(triple-sum 4 8)
> (accumulate #<procedure:append> '() '())
< '()
> (accumulate #<procedure:append> '() '(()))
> >(accumulate #<procedure:append> '() '())
< <'()
< '()
> (accumulate #<procedure:append> '() '(() ((3 2 1))))
> >(accumulate #<procedure:append> '() '(((3 2 1))))
> > (accumulate #<procedure:append> '() '())
< < '()
< <'((3 2 1))
< '((3 2 1))
> (accumulate #<procedure:append> '() '(() ((4 2 1)) ((4 3 1) (4 3 2))))
> >(accumulate #<procedure:append> '() '(((4 2 1)) ((4 3 1) (4 3 2))))
> > (accumulate #<procedure:append> '() '(((4 3 1) (4 3 2))))
> > >(accumulate #<procedure:append> '() '())
< < <'()
< < '((4 3 1) (4 3 2))
< <'((4 2 1) (4 3 1) (4 3 2))
< '((4 2 1) (4 3 1) (4 3 2))
> (accumulate
   #<procedure:append>
   '()
   '(() () ((3 2 1)) ((4 2 1) (4 3 1) (4 3 2))))
> >(accumulate
    #<procedure:append>
    '()
    '(() ((3 2 1)) ((4 2 1) (4 3 1) (4 3 2))))
> > (accumulate #<procedure:append> '() '(((3 2 1)) ((4 2 1) (4 3 1) (4 3 2))))
> > >(accumulate #<procedure:append> '() '(((4 2 1) (4 3 1) (4 3 2))))
> > > (accumulate #<procedure:append> '() '())
< < < '()
< < <'((4 2 1) (4 3 1) (4 3 2))
< < '((3 2 1) (4 2 1) (4 3 1) (4 3 2))
< <'((3 2 1) (4 2 1) (4 3 1) (4 3 2))
< '((3 2 1) (4 2 1) (4 3 1) (4 3 2))
<'((4 3 1))
'((4 3 1))

Tags: sicp scheme

Edit on GitHub