The final chop method I came up with was rather uninspired. I used a for loop instead a while loop and used some array manipulation.

Here’s the code:

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

index = 0
newList = list
found = False

for number in range(0, len(list) / 2 + 1):
tempIndex = len(newList) / 2
if value == newList[tempIndex]:
return index + tempIndex
elif value > newList[tempIndex]:
newList = newList[tempIndex+1:len(newList)]
if len(newList) == 0:
return -1
index += tempIndex + 1
elif value < newList[tempIndex]:
newList = newList[0:tempIndex]
if len(newList) == 0:
return -1

return -1

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)

The second way I’ll implement binary search for Kata Two — Karate Chop will be with recursion. I haven’t used recursion much in my day-to-day work, but I’ve never thought of it as a particularly hard concept to grasp, it just seems that the problems I work aren’t optimally solved with it. The most interesting part of recursion is finding the condition that ends it. Here’s my solutions:

def chopTwo(value, list):
upper = len(list) - 1
lower = 0

return chopTwoRec(upper, lower, value, list)

def chopTwoRec(upper, lower, value, list):
index = (upper + lower) / 2

if index < 0 or upper < lower:
return -1
elif list[index] == value:
return index
elif value > list[index]:
lower = index + 1
elif value < list[index]:
upper = index - 1

return typeTwoRec(upper, lower, value, list)

For Kata Two — Karate Chop I’m supposed to implement a binary search five different ways. PragDave suggests starting of with the “traditional iterative approach.” My first thought was, “what the heck is that?” It’s been a while since my intro. to data structures and algorithms class. I figure it has something to do with a while loop and checking the middle index in the array being searched, so that’s where I started:

def chopOne(value, list):
index = (len(list) - 1) / 2

while index > -1:
if list[index] == value:
return index
elif value > list[index]:
index = (index + len(list) - 1) / 2
elif value < list[index]:
index = index / 2

return -1

Well, that didn’t work. I got into an infinite loop. As I thought about it, I remembered I had to keep track of the upper and lower bounds that I had already checked. So this got me:

def chopOne(value, list):
upper = len(list) - 1
lower = 0
index = (upper + lower) / 2

while index > -1 and upper >= lower:
if list[index] == value:
return index
elif value > list[index]:
lower = index + 1
elif value < list[index]:
upper = index - 1
index = (upper + lower) / 2

return -1

That worked! Next, time I’ll use recursion to implement the binary search.

I’ve been away for quite a while, so first a quick update. I’ve been working on a Django web app which I hope I’ll be finished with soon. I also started a podcast over at Wittenberg Media that’s been taking up most of my free time.

Since I started working with Django I obviously started working with Python. Like the Ruby on Rails learning projects I did, I was learning the framework and using the language constructs as needed. However, I feel a better match with Python than with Ruby and since I’ve been wanting to break out of the Java corner I’ve put myself in, I decided I would learn Python as well as Django.

Over the years of studying computer languages, I’ve learned that I can’t really know a language unless I do some really projects with them. I started kicking around the idea that to claim that I knew a language, I would:

1. Write a to do list or address book with a web interface without using a framework. This would force me to learn how to do database and socket programming with only standard libraries.
2. Write a Tetris clone. This would force me to learn how the language works with graphics and the native application environment.

While I think those will be my benchmarks for my claim to knowing a language, I wanted to start a little smaller. So after reading some tutorials and online documentation I thought I should do some actual programming, but what to write? Well, I ran across the old site by PragDave called CodeKata which seems like a go place to start. Over the next few posts I’ll write about my experience working on Kata Two — Karate Chop.