But my first couple of runs resulted in relatively long procedures with a lot of boundary checking. While my specs were passing, the smell of the code was really bothering me.
I found a reference implementation and gave it a run, but discovered that it failed my specs. After a double-check of the specs to confirm I didn't have something messed up, I decided to dump the RI and try it again.
Finally, the pieces fell together and I could see where most of the boundary checking fell out of the method as I changed the sequence of events.
The Code
class Chop
def self.find(lookFor, lookIn, start_index=nil, end_index=nil)
start_index ||= 0
end_index ||= lookIn.length
middle = (start_index + end_index)/2
return middle if lookFor == lookIn[middle]
return -1 if ((middle == start_index) || (middle == end_index))
return find(lookFor, lookIn, start_index, middle) if lookFor < lookIn[middle]
return find(lookFor, lookIn, middle, end_index) if lookFor > lookIn[middle]
end
end
The Specs
require "spec"
require "karate_chop"
describe Chop do
context "with an empty sorted array" do
it "indicates item not found" do
Chop.find(1, []).should == -1
end
end
context "with search target not in array" do
it "indicates item not found" do
Chop.find(1, [0,2,3]).should == -1
end
end
context "with search target in array" do
it "provides the index of the located item when in the middle of the array" do
Chop.find(1, [0,1,2,3]).should == 1
Chop.find(4, [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]).should == 4
end
it "provides the index of the located item when it is last in the array" do
Chop.find(20, [5, 10, 15, 20]).should == 3
end
it "provides the index of the located item when it is first in the array" do
Chop.find(20, [20,40,60,80]).should == 0
end
end
context "with a large array" do
it "locates the item" do
search_in = Array(0..900)
Chop.find(100, search_in).should == 100
end
end
end
I am looking for feedback on these. Please, feel free to let me know how I could improve my code or specs. Or share links to your own solutions.
Code is available on my github
ReplyDeletehttp://github.com/DocOnDev/Karate-Chop-Kata
You can drop two lines by moving your optional argument initialization into the arguments list.
ReplyDeletedef self.find(lookFor, lookIn, start_index = 0, end_index = lookIn.length)
Good point. Thanks.
ReplyDeleteVery cool, much cleaner than my attempt! It'd be cool to see the first solutions you wrote and how you managed to evolve to the current one.
ReplyDeleteDid you manage to complete it in one pomodoro? You mentioned on twitter (I Think) that that was the aim!
When I tried this one I spent way longer than that doing it.
Mark:
ReplyDeleteI did not save the earlier version. I didn't git the code until the second kata (this one). But I will do that from now on. I think that would be cool.
So - the first attempt, I did not get it done in a single pomodoro. I got pretty far, but had failures under certain conditions.
I then spent another couple of hours over the next day; reading, playing with it, and working with another posted solution.
That evening, I sat down and did this one from empty file to functional and refactored in just under 17 minutes.
Like I said, I need to do it a few more times to "burn it in".
I am going to do this one in Scheme as well.
Wouldn't this code work just as well? All your tests would pass..
ReplyDeleteclass Chop
def self.find(lookFor, lookIn, start_index=0, end_index=-1)
lookIn[start_index..end_index].index(lookFor) || -1
end
end