Programming Praxis

We begin with the O(n²) time and O(1) space solution, stated somewhat differently than the previous solution, just for variety. The call-with-current-continuation is the Scheme idiom that permits an early return from a function; the function returns #f if there is no solution:

(define (soln1 target vec)
  (let ((len (vector-length vec)))
    (call-with-current-continuation
      (lambda (return)
        (do ((i 0 (+ i 1))) ((= i len) #f)
          (do ((j (+ i 1) (+ j 1))) ((= j len))
            (when (= target (+ (vector-ref vec i) (vector-ref vec j)))
              (return (list (+ i 1) (+ j 1))))))))))

Our second solution uses the avl trees from the Standard Prelude. We have to be careful not to take the same item twice if two items have the same value. Note that we add 1 to the position on input instead of output:

(define (soln2 target xs)
  (let ((items (make-dict <)))
    (do ((i 0 (+ i 1)) (xs xs (cdr xs))) ((null? xs))
      (set! items (items 'insert (car xs) (+ i 1))))
    (let loop ((xs xs) (i 1))
      (cond ((null? xs) #f)
            ((items 'lookup (- target (car xs))) =>
              (lambda (item)
                (if (= i (cdr item))
                    (loop (cdr xs) (+ i 1))
                    (sort < (list i (cdr item))))))
            (else (loop (cdr xs) (+ i 1)))))))

The third solution is similar to the second, but uses the hash tables of the Standard Prelude instead of avl trees:

(define (soln3 target xs)
  (let ((items (make-hash identity = #f 97)))
    (do ((i 0 (+ i 1)) (xs xs (cdr xs))) ((null? xs))
      (items 'insert (car xs) (+ i 1)))
    (let loop ((xs xs) (i 1))
      (cond ((null? xs) #f)
            ((items 'lookup (- target (car xs))) =>
              (lambda (item)
                (if (= i item)
                    (loop (cdr xs) (+ i 1))
                    (sort < (list i item)))))
            (else (loop (cdr xs) (+ i 1)))))))

The fourth solution requires a little bit more work. First a vector of value/position pairs is build, then i iterates through the vector, performing a binary search on the portion of the vector from i+1 to the end for a value of the target less the value portion of i. There is no need to check for duplicate positions, because the search vector starts at position i+1; for the same reason, it is necessary to add 2 to i and 1 to the position found in the vector.

(define (soln4 target xs)
  (define (comp a b)
    (if (< (car a) (car b)) -1
    (if (< (car b) (car a)) 1 0)))
  (define (bsearch target vec lo hi)
    (if (< hi lo) #f
      (let ((mid (quotient (+ lo hi) 2)))
        (cond ((< (car (vector-ref vec mid)) target)
                (bsearch target vec (+ mid 1) hi))
              ((< target (car (vector-ref vec mid)))
                (bsearch target vec lo (- mid 1)))
              (else (vector-ref vec mid))))))
  (let loop ((xs xs) (i 0) (vs (list)))
    (if (pair? xs)
        (loop (cdr xs) (+ i 1) (cons (cons (car xs) i) vs))
        (let ((vec (list->vector vs)))
          (vector-sort! vec comp)
          (let ((len (vector-length vec)))
            (let loop ((i 0))
              (cond ((= i len) #f)
                    ((bsearch (- target (car (vector-ref vec i)))
                              vec (+ i 1) (- len 1)) =>
                      (lambda (item)
                        (sort < (list (+ i 2) (+ (cdr item) 1)))))
                    (else (loop (+ i 1))))))))))

I really like this solution. Though it looks complicated, there is an underlying elegance that I find appealing. And there isn’t much difference between O(n) and O(n log n) unless n gets really large, and the space requirement of the O(n) solution effectively prevents n from getting really large.

You can run the program at http://programmingpraxis.codepad.org/hfZCy20U.

Pages: 1 2