Karate Chop

June 16, 2015

Thomas gives a simple test suite, which we copy here; it complains on any error but is otherwise silent, on the theory that no news is good news:

(define (test chop)
  (assert (chop 3 '#()) -1)
  (assert (chop 3 '#(1)) -1)
  (assert (chop 3 '#(3)) 0)
  (assert (chop 1 '#(1 3 5)) 0)
  (assert (chop 3 '#(1 3 5)) 1)
  (assert (chop 5 '#(1 3 5)) 2)
  (assert (chop 0 '#(1 3 5)) -1)
  (assert (chop 2 '#(1 3 5)) -1)
  (assert (chop 4 '#(1 3 5)) -1)
  (assert (chop 6 '#(1 3 5)) -1)
  (assert (chop 1 '#(1 3 5 7)) 0)
  (assert (chop 3 '#(1 3 5 7)) 1)
  (assert (chop 5 '#(1 3 5 7)) 2)
  (assert (chop 7 '#(1 3 5 7)) 3)
  (assert (chop 0 '#(1 3 5 7)) -1)
  (assert (chop 2 '#(1 3 5 7)) -1)
  (assert (chop 4 '#(1 3 5 7)) -1)
  (assert (chop 6 '#(1 3 5 7)) -1)
  (assert (chop 8 '#(1 3 5 7)) -1))

Here is Thomas’ traditional imperative approach, complete with a while loop, variable assignment, and a return statement built from call-with-current-continuation:

(define (chop1 needle haystack)
  (call-with-current-continuation
    (lambda (return)
      (let ((lo 0) (hi (- (vector-length haystack) 1)))
        (while (<= lo hi)
          (let ((mid (quotient (+ lo hi) 2)))
            (cond ((< needle (vector-ref haystack mid))
                    (set! hi (- mid 1)))
                  ((< (vector-ref haystack mid) needle)
                    (set! lo (+ mid 1)))
                  (else (return mid)))))
        (return -1)))))

> (test chop1)

I’m pretty sure this is what Thomas intends when he talks about the recursive approach:

(define (chop2 needle haystack)
  (chop2-aux needle haystack 0 (- (vector-length haystack) 1)))

(define (chop2-aux needle haystack lo hi)
  (call-with-current-continuation
    (lambda (return)
      (if (< hi lo) (return -1)
        (let ((mid (quotient (+ lo hi) 2)))
          (cond ((< needle (vector-ref haystack mid))
                  (return (chop2-aux needle haystack lo (- mid 1))))
                ((< (vector-ref haystack mid) needle)
                  (return (chop2-aux needle haystack (+ mid 1) hi)))
                (else (return mid))))))))

> (test chop2)

Thomas talks about a functional style passing array slices around, but I’m not entirely sure what he means. Here is the traditional Scheme version of binary search:

(define (chop3 needle haystack)
  (let loop ((lo 0) (hi (- (vector-length haystack) 1)))
    (if (< hi lo) -1
      (let ((mid (quotient (+ lo hi) 2)))
        (cond ((< needle (vector-ref haystack mid))
                (loop lo (- mid 1)))
              ((< (vector-ref haystack mid) needle)
                (loop (+ mid 1) hi))
              (else mid)))))))

> (test chop3)

Those three versions of binary search all work whether or not the values in the array are distinct, but if they are not distinct, they may return the index of any of the equal items. It’s generally better to return the first such index, which can be done by delaying the test for equality until the end. That means you can never return early with a lucky match, so each search takes log2 comparisons, but it also means there is only one comparison at each step. Here’s the iterative version of that algorithm:

(define (chop4 needle haystack)
  (call-with-current-continuation
    (lambda (return)
      (let ((lo 0) (hi (- (vector-length haystack) 1)))
        (while (< lo hi)
          (let ((mid (quotient (+ lo hi) 2)))
            (if (< (vector-ref haystack mid) needle)
                (set! lo (+ mid 1))
                (set! hi mid))))
        (if (and (= lo hi) (= needle (vector-ref haystack lo)))
            (return lo)
            (return -1))))))

> (test chop4)

And to complete Thomas’ requirement of five different implementations, here’s a Scheme-ly version of chop4:

(define (chop5 needle haystack)
  (let loop ((lo 0) (hi (- (vector-length haystack) 1)))
    (if (<= hi lo)
        (if (and (= lo hi) (= needle (vector-ref haystack lo))) lo -1)
          (let ((mid (quotient (+ lo hi) 2)))
            (if (< (vector-ref haystack mid) needle)
                (loop (+ mid 1) hi)
                (loop lo mid))))))

> (test chop5)

We used the assert and while macros from the Standard Prelude. You can run the program at http://ideone.com/BxXfot.

Pages: 1 2

3 Responses to “Karate Chop”

  1. Mike said

    I don’t give the code for the standard interative, recursive and functional functions. But here is a somewhat different approach. Basically, for each bit in the index, starting at the msb, you decide whether that bit should be set or clear by comparing el with the value at lst[index with the bit set]. four() is an iterative version, five() is a recursive version; nine() is a functional version based on the same idea.

    
    def four(el, lst):
        index = 0
        mask = 1 << len(lst).bit_length()
        while mask:
            mask >>= 1
            tmp = index | mask
            if tmp < len(lst) and el >= lst[tmp]:
                index = tmp
            
        return index if lst and el == lst[index] else -1
    
    def five(el, lst):
        def _five(index, mask):
            if mask:
                if index | mask < len(lst) and el >= lst[index | mask]:
                    return _five(index | mask, mask >> 1)
                else:
                    return _five(index, mask >> 1)
            else:
                return index if el == lst[index] else -1
    
        return _five(0, 1 << len(lst).bit_length()) if lst else -1
    
    def nine(el, lst):
        t = lambda i, b: i|b if i|b < len(lst) and el >= lst[i|b] else i
        m = 1 << (len(lst).bit_length() - 1)
        index = reduce(t, [m >> i for i in range(x+2)], 0)
        return index if el == lst[index] else -1
    
  2. Mike said

    Somehow, I pasted the wrong version of nine(). Here’s the correct version:

    def nine(el, lst):
        t = lambda i, b: i|b if i|b < len(lst) and el >= lst[i|b] else i
        m = (1 << len(lst).bit_length()) >> 1
        index = reduce(t, [m >> i for i in range(m+2)], 0)
        return index if el == lst[index] else -1
    
  3. matthew said

    @Mike: nice solution, I wish I’d thought of that…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: