4sum


One more from Programming Praxis, this time we're dealing with summing combinations of a sequence. More formally, given a secquence S, either choose four elements \(s_1\) through \(s_4\) from S such that \(s_1 + s_2 + s_3 + s_4 = 0\) or verify that it isn't possible. This immediately makes me about working through possible solutions until we find one and then bailing out, ergo call/cc:

(define (4sum ls)
  (call/cc (lambda (exit)
    (for-each (lambda (i)
      (for-each (lambda (j)
        (for-each (lambda (k)
          (for-each (lambda (l)
            (when (= 0 (+ i j l k))
              (exit (list i j k l))))
            ls))
          ls))
        ls))
      ls)
    (exit #f))))

It may look funny, but it works great:

~ (4sum '(2 3 1 0 -4 -1))
 (2 2 0 -4)

~ (4sum '(3 1 0 -4))
 (3 1 0 -4)

~ (4sum '(1 1 1 1))
 #f

I think that this may have been the first time that I legitimately used call/cc without being told to do so and I have to admit... I'm a convert. It's kind of powerful. (Even if I'm not using a fraction of what I'm capable of.)

Alternatively, we can write a more Rackety solution, using for*/first to loop over the values and return the first matching case:

(define (4sum ls)
  (for*/first ([i (in-list ls)]
               [j (in-list ls)]
               [k (in-list ls)]
               [l (in-list ls)]
               #:when (= 0 (+ i j k l)))
    (list i j k l)))

Under the hood, it's doing much the same thing, so it really comes down to which style looks more natural to you.

    comments powered by Disqus