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:

1(define (unique-triples n)
2    (flatmap
3        (lambda (i)
4            (flatmap
5                (lambda (j)
6                    (map (lambda (k) (list i j k))
7                         (enumerate-interval 1 (- j 1))))
8                (enumerate-interval 1 (- i 1))))
9        (enumerate-interval 1 n)))

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

1(define (make-triple triple)
2    (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:

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

and the final procedure:

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

Test:

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

Take a look at the filter syntax:

1(filter pred lst) → list?
2
3  pred : procedure?
4  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:

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

Verify:

 1$ racket 2.41-triple-sum.rkt
 2>(triple-sum 4 8)
 3> (accumulate #<procedure:append> '() '())
 4< '()
 5> (accumulate #<procedure:append> '() '(()))
 6> >(accumulate #<procedure:append> '() '())
 7< <'()
 8< '()
 9> (accumulate #<procedure:append> '() '(() ((3 2 1))))
10> >(accumulate #<procedure:append> '() '(((3 2 1))))
11> > (accumulate #<procedure:append> '() '())
12< < '()
13< <'((3 2 1))
14< '((3 2 1))
15> (accumulate #<procedure:append> '() '(() ((4 2 1)) ((4 3 1) (4 3 2))))
16> >(accumulate #<procedure:append> '() '(((4 2 1)) ((4 3 1) (4 3 2))))
17> > (accumulate #<procedure:append> '() '(((4 3 1) (4 3 2))))
18> > >(accumulate #<procedure:append> '() '())
19< < <'()
20< < '((4 3 1) (4 3 2))
21< <'((4 2 1) (4 3 1) (4 3 2))
22< '((4 2 1) (4 3 1) (4 3 2))
23> (accumulate
24   #<procedure:append>
25   '()
26   '(() () ((3 2 1)) ((4 2 1) (4 3 1) (4 3 2))))
27> >(accumulate
28    #<procedure:append>
29    '()
30    '(() ((3 2 1)) ((4 2 1) (4 3 1) (4 3 2))))
31> > (accumulate #<procedure:append> '() '(((3 2 1)) ((4 2 1) (4 3 1) (4 3 2))))
32> > >(accumulate #<procedure:append> '() '(((4 2 1) (4 3 1) (4 3 2))))
33> > > (accumulate #<procedure:append> '() '())
34< < < '()
35< < <'((4 2 1) (4 3 1) (4 3 2))
36< < '((3 2 1) (4 2 1) (4 3 1) (4 3 2))
37< <'((3 2 1) (4 2 1) (4 3 1) (4 3 2))
38< '((3 2 1) (4 2 1) (4 3 1) (4 3 2))
39<'((4 3 1))
40'((4 3 1))

Tags: sicp scheme

Edit on GitHub