Kata Two — Karate Chop – Part 3

by byamabe on May 13, 2008

Honestly, I had no idea what to try next. So the next suggestion from the kata was to try something functional where you pass slices of the array around. So, I started with passing the value and the list into a function and then returning a new list that had been “chopped”. This worked in finding whether the value was in the list, but it didn’t return the index of the value if it was in the list. I needed a way to pass back the number of list elements I had disregarded at each pass and sum them to find the index of the value. This was a case where I needed two return values from a function. In most languages I’d have to return one value and change the value of one of the arguments, but Python allows multiple return values, awesome! I just returned both the number of elements I had thrown out and the new list to search. So starting from no idea what to implement, this became my favorite because I felt I really learned something about Python.

Here’s the code:

def chopThree(value, list):
if len(list) == 0:
return -1

index = 0

while len(list) > 0:
throwCount, list = chopThreeFunc(value, list)

if throwCount == -1:
return -1

index = index + throwCount

return index

def chopThreeFunc(value, list):
if len(list) == 0:
return -1, []

index = len(list) / 2
newList = []
throwCount = 0

if list[index] == value:
return index, []
elif value > list[index]:
newList = list[index:len(list)]
if len(list) == 1:
return -1, []
throwCount = index
elif value < list[index]:
newList = list[0:index]
if len(list) == 1:
return -1, []

return throwCount, newList

For the next implementation, I simply did this in a recursive manner:

def chopFour(value, list):
if len(list) == 0:
return -1

return chopFourFunc(0, value, list)

def chopFourFunc(count, value, list):
index = len(list) / 2<</span>
newList = []
throwCount = 0

if list[index] == value:
return index + count
elif value > list[index]:
newList = list[index:len(list)]
if len(list) == 1:
return -1
throwCount = index
elif value < list[index]:
newList = list[0:index]
if len(list) == 1:
return -1

return chopFourFunc(throwCount, value, newList)

Previous post:

Next post: