"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

Categories:

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:

Related Posts: