May 2006 Archives

Binary Chop, Functional

This time I decided to not use any previous versions as a starting point. Again I made mistakes that ended up causing endless loops on some of the test cases. The previous solution was somewhat in the functional style, using recursion instead of looping. I went further this time and passed array slices rather than indices for good measure.

No doubt in my mind this is the worst implementation so far. It's verbose and hard to understand. It has special case checks. It uses a lot of stack for storing array slices. I particularly dislike the special handling needed for the second recursive call — when the top half of the array is searched, a correction must be applied to the index for the whole array.

I've had one lesson hammered into my skull. When the array slice gets to two elements, size/2 stays at one. Hence, when the value is in the first half of the array, it is vital to search the array up to the item before the midpoint. It's surprising that this is required for correctness as well as in order to avoid unnecessary work.

module BinChopper

    def chop(n,a)
        if a.empty?
            return -1
        end
        if n == a.midpoint_value
            return a.midpoint
        end
        if a.size == 1
            return -1
        elsif n < a.midpoint_value
            return chop(n, a[0 .. a.midpoint - 1])
        elsif n > a.midpoint_value
            return apply_correction(a.midpoint,
                        chop(n, a[a.midpoint + 1 .. a.size - 1]))
        end
    end

    def apply_correction(mid, target)
        if target < 0
            return target
        else
            return 1 + mid + target
        end
    end

end

class Array

    def midpoint
        return size / 2
    end

    def midpoint_value
        return self[midpoint]
    end

end

Binary Chop, Recursively

| No Comments

Doing it recursively is a simple re-write. The while changes to an if and the asignments of hi and lo turn into recursive calls. In a language with tail call removal, this would not be any worse than the iterative version. I don't think Ruby is one of those languages. However, I do think this version is a bit easier to read than the first one.

module BinChopper

    def chop(n, a)
        return recursive_chop(n, a, a.length - 1, 0)
    end

    def recursive_chop(n, a, hi, lo)
        if lo > hi
            return -1
        end
        mid = (lo + hi) / 2
        if a[mid] == n
            return mid
        elsif (a[mid] > n)
            return recursive_chop(n, a, mid - 1, lo)
        else
            # a[mid] must be less than n
            return recursive_chop(n, a, hi, mid + 1)
        end
    end

end

Binary Chop

| No Comments

Now that I have a laptop from work I don't need to exile myself the spare bedroom in order to try things out on the computer. Thanks to wi-fi I have ruby and vim, which means I can look at kata again.

Actually, I wanted to try out binary chop, as it's something I can use on a work project. Stupidly, I tried first to write the code cold. That didn't work. Not only did I have the fencepost errors and the endless loops — the code was getting uglier as I kept thinking of special cases. It probably didn't help that my Ruby is rusty from lack of use. I've been spoiled by IDEs and auto-completion: one almost forgets what it's like to get compile errors.

So I resorted to pen and paper. A funny thing happened: all Dave's tests passed at once. The code was easier to read and more coherent. Binary chop is about the simplest problem I know for which it's really worth taking a break from the keyboard.

Interesting to compare with other people's work. Jim Weirich did a version three years ago. Here's mine:

module BinChopper

    def chop(n, a)
        lo = 0
        hi = a.length - 1
        while lo <= hi
            mid = (lo + hi) / 2
            if a[mid] == n
                return mid
            elsif (a[mid] > n)
                hi = mid - 1
            elsif (a[mid] < n)
                lo = mid + 1
            end
        end
        return -1
    end

end

Originally, I was using single letter variable names but I like Jim's short but meaningful names better. I thought of the invariant a little differently: I decided the loop would terminate after the high and low markers went past each other. (By the way I think his calculation of the midpoint is buggy. I should lay off the crack pipe. His calculation is obviously correct and I'm stealing it.)

Now of course coming up with one implementation of binary chop is straightforward. I'll have to see how motivated I am to find four more ways to do it.