Code Kata: Kata Two

27 Aug 2013

I haven’t been coding much at work recently, so I decided that I need to sharpen the saw a bit and exercise.

I decided to start with some Code Kata. The first one is somewhat an academical problem: implement binary search in five different ways.

Here is my first solution, the iterative way:

        //Classic iterative method
        public int Chop1(int element, IEnumerable<int> collection)
        {
            //Empty collection -> not found
            if (collection.Count() == 0) return -1;

            var lower = 0;
            var upper = collection.Count() - 1;
            int index, candidate;

            while (lower != upper)
            {
                index = lower + ((upper - lower) / 2);
                candidate = collection.ElementAt(index);

                if (candidate == element)
                {
                    return index;
                }
                else if (candidate < element)
                {
                    lower = index + 1;
                }
                else //if (candidate > element)
                {
                    upper = index;
                }
            }

            return (collection.ElementAt(upper) == element) ? upper : -1;
        }

I was actually scared at the time it took me. This is the kind of problem you are expected to solve in 5 minutes flat at university, but the lack of programming puzzles lately soften my brain. On the bright side, I challenged myself to get it right without compiling before being absolutely sure that the code would pass the tests, which it did. This involved some scratching paper to test the different corner cases, but I felt good when the green light of passing tests appeared.

Here is my second solution, recursive and passing slices of the original array:

        //Recursively passing smaller slices of the initial array
        public int Chop2(int element, IEnumerable<int> collection)
        {
            //Empty collection -> not found
            if (collection.Count() == 0) return -1;

            var index = collection.Count() / 2;
            var candidate = collection.ElementAt(index);

            if (candidate == element)
            {
                return index;
            }
            else if (candidate < element)
            {
                var offset = index + 1;
                var position = Chop2(element, collection.Skip(index + 1));
                return position > -1 ? offset + position : -1;
            }
            else //if (candidate > element)
            {
                return Chop2(element, collection.Take(index));
            }
        }

After finishing this one, I started thinking about it and found it very funny that this came more naturally than a recursive function using boundaries inside the array. I tend to use LINQ a lot when I code in C#, and I guess this is where it shows. The good news is that this led me to the third possible solution, which would have been second if I was just out of university.

Third solution, recursive and passing arrays boundaries:

        //Classic recursive method, passing boundaries around
        public int Chop3(int element, IEnumerable<int> collection)
        {
            //Empty collection -> not found
            if (collection.Count() == 0) return -1;

            return SubChop3(element, collection, 0, collection.Count() - 1);
        }
        //...and its sub method required for passing boundaries around
        private int SubChop3(int element, IEnumerable<int> collection, int lower, int upper)
        {
            //End case: lower == upper
            if (lower == upper)
            {
                if (collection.ElementAt(lower) == element) return lower;
                else return -1;
            }

            var index = lower + ((upper - lower) / 2);
            var candidate = collection.ElementAt(index);

            if (candidate == element)
            {
                return index;
            }
            else if (candidate < element)
            {
                return SubChop3(element, collection, index + 1, upper);
            }
            else //if (candidate > element)
            {
                return SubChop3(element, collection, lower, index);
            }
        }

Nothing too fancy here.

I don’t have a 4 and 5 yet, but I already have one idea that is very challenging: continuation passing style. I was also tempted to implement one version using TPL, but it wouldn’t be very different from the recursive methods, so I am not sure… Maybe using a custom partitioner?

.NET 1