I’m still trudging through the CodeKata exercices.

Code Kata 2 is a challenge to implement the binary search algorithm. Binary search is an algorithm
that is used to search sorted arrays. The idea is very much like a “guess the number” game, where you
are pretty much guaranteed to win in a maximum of log₂(n) guesses (n being the size of the array). Compare this to a linear search,
where you start at the beginning of the array and search sequentially until you find the value. In the worst case,
you’d need to search every element (though binary search doesn’t work on an unsorted array).

The challenge is not to write a single binary search method, but 5 of them. The obvious first 2 are
recursive and iterative–everyone did those in those college. But what about another 3? This turned out
to be the most challenging part to me, and one that I did not ultimately succeed at.

My first method was recursive. With the method signature that’s given by the Code Kata test cases, this
was more challenging than I thought. Sure, I could basically make it a wrapper method, but I opted against
that. Instead, I had to learn to use Array.Copy. Note that this pretty much defeats the purpose of using
binary search instead of linear search, but it does confine the search to one method. In C++ or some other
unmanaged language, Array.Copy would not be necessary.

Secondly, I did the iterative approach, and this was much easier. There are 4 total cases and 3 comparisons
per iteration in this implementation. It felt suboptimal to me, and it turns out I was right.

Next, I hit a brick wall. What else can I really do? So I thought I would pull a Kirk and rig the
exam so that I could win. I simply made a chop() method that wraps around the built-in C# Array.BinarySearch
method. I had to kajagger the return value a bit to pass the test cases, but it works. Yeah it’s not
very interesting, but I didn’t know what else to do.

Finally, I broke down for the last two and just plain cheated. I looked up a couple of iterative implementations.
The first one did a single comparison per iteration,
and the second one is just a little nicer looking with max of 2 compares per iteration.

Here are the 3 Code Kata questions:

1. Keep notes on the errors. Did you learn from experience on one technique when coding
another?

Exactly as stated in the kata description, the errors I ran into were “fencepost” errors where it would pass most tests except maybe
one edge case. A quick adjustment of a -1 or +1 here and there made the fixes. It’s difficult sometimes when
using 0-based arrays to separate the maximum index and the length when juggling numbers in my head.

2. What can you say about the relative merits of the various techniques you’ve
chosen? Which is the most likely to make it in to production code? Which was the most
fun to write? Which was the hardest to get working? And for all these questions, ask yourself “why?”

My two methods are definitely smelly, and I wouldn’t want to use them in production. However, they all
passed test cases, so I could use them in a pinch. However, the only one I would want in production would be
the Kirk method: using the C# built-in search. Binary search has been written millions of times by thousands
of people smarter than me: there’s no sense in reinventing the wheel. That one was also the most fun to write,
because it was the quickest and easiest to write. The hardest to get working was the initial recursive method,
and this is only because I was committed to using one method with the given signature, and I was using a
managed language.

3. It’s fairly hard to come up with five unique approaches to a binary chop. How did
you go about coming up with approaches four and five? What techniques did you use to fire those “off the wall” neurons?

Heh, well, I really didn’t. I only came up with 3 totally on my own, and one of those didn’t really
count. Additionally, the two iterative methods that I stole were really just (better) variations of my own
lousy iterative method, so I’d be very much interested in seeing the code of someone who has written
5 unique approaches to binary search.

That’s the end of the second kata. It took me well over the standard week, but I actually only spent about 4-5
nights really cranking at this problem.

Here’s the code for Code Kata 2. Just rename the method you want to
run tests on to “chop”. I used C# with MbUnit.

I’m going to attempt to go through all of the CodeKata exercices.
Why? I think it will help me to become a better developer, and I think it will be a lot of fun. (Note that the catalyst for this was Alan Stevens’s presentation on “Coding in Public“). I will
be recording brief overviews of my “solutions” here. Please feel free to suggest improvements or point out
weaknesses, because constructive criticism is, well, constructive.

Code Kata 1 is more of a thought exercise than a coding exercise. However, once I read through it,
I thought I would use some code to organize my thoughts better, and actually try to design some classes.

I struggled with the design for a while. The “can of beans” case is a trivial one, but I tried the “three for a dollar”
case and ran into a wall. It might sound equally simple, but I thought of Speedway, which sometimes
has Coke 2-Liters priced at 3/$3.33, but $1.59 if you buy less than 3. That really stumped me, until I realized
that the price depends on the total quantity purchased, which means I need some way to track the total
quantity purchased: Each item would contain a UPC code, and a quantity of that item.

The $1.99/pound case seemed pretty trivial: just store a price for weight, and then the weight. The Price()
method can do the math. I didn’t want to overthink this, so I didn’t.

Finally, the “buy two, get one free” case might sound tough, but it is trivial as well, since I
think the “three for a dollar” case at Speedway that I described pretty much covers that. So, I don’t even
need a new subclass for that.

Here is my complete class diagram:

I didn’t design a UI or anything, just some classes and tests. The source code is in C#, and I used MbUnit
for unit testing.

Here are the 5 other questions, which I didn’t really do any coding for:

1. Does fractional money exist?

Yes. Why not?

2. When (if ever) does rounding take place?

Well, since fractional money exists, we really don’t have to round. However, when paying with legal
tender, there is an actual smallest unit of payment that the consumer can use (a penny, for instance, or a Yen).
Prices needed to be rounded to that smallest unit. When the rounding takes place, I think, should be at
the last possible moment. However, that may depend on the grocery store, and if they have some rounding
logic they want to use to nickel & dime their customers. If it was me, I’d add up all the fractional
cents, and then round right at the very end.

3. How do you keep an audit trail of pricing decisions (and do you need to)?

In my code, the only thing to audit is the adding of items to the basket, and then the calculation of the
final price (itemized). In the real world, items would need to be able to be removed from the basket, coupons
added, etc. In that case, I would consider an itemized receipt to be the final audit: I don’t care how many
times you change your mind about buying that box of cereal, I just care about what you finally paid for, how
many you paid for, and how much you paid for it. So, my Basket could generate an entire receipt, not just
a Total scalar.

4. Are costs and prices the same class of thing?

I didn’t do any costing, but costs should be totally separate from price! If I buy 144 boxes of Raisin Bran
at $1.00 a box, that’s my cost no matter what I sell them at. Now, in a real supermarket, often times there
are “return” agreements, in which the vendor will take back unsold stock. There might be some logic to that,
and it would certainly vary on the vendor and agreement.

5. If a shelf of 100 cans is priced using “buy two, get one free”, how do you value the stock?

Again, my costs wouldn’t change based on the pricing or promotion. 3 boxes of Raisin Bran cost me $1.00 each, so
my stock is valued at $144. Real inventory systems may need to follow LIFO or FIFO rules, but I still don’t
see prices having any affect on that.

That concludes my first Kata. It took me about 4 nights of coding-pondering-starting over to come to
this solution. What could have been done better?