Kata Three was a thought exercise, so I’m moving on to Kata Four. This is a 3 part kata with first being reading temperature data from a file and outputting the day the smallest temperature spread. I didn’t use RegEx to parse the input lines (I know it’s really something I should learn), so I just checked the character offsets. The day was from character 0 - 3, the max temperature was from 6 - 7, and the min was from 12 - 13. Here’s what I came up with:

def get_smallest_spread(self):
day = 0
spread = 100

lines = self.file.readlines()
for line in lines:
if len(line) >= 14:
try:
max = int(line[6:8])
min = int(line[12:14])
if max - min < spread:
day = int(line[0:4])
spread = max - min
except:
continue

return day

The code is pretty straight forward. I just read the lines, extract the appropriate character and turn them into ints and compare them, and then keep track of the smallest spread.

The second part of the kata is to read a data file with soccer (they call it football, but I’m in the U.S.) team data and output the team with the smallest goals for and goals against differential.

def get_smallest_differential(self):
team = ”
spread = 100

lines = self.file.readlines()
for line in lines:
if len(line) >= 52:
try:
gf = int(line[43:45])
ga = int(line[50:52])
if abs(gf - ga) < spread:
team = line[7:21]
spread = abs(gf - ga)
except:
continue

return team.strip()

Not much to comment on, this was pretty much the same code except the offsets were different.

The final part of the kata is to refactor the code to get as much common code a possible. This was pretty easy since the only differences were the offsets to find the values to compare and the value to return. Here’s what I ended up with:

def get_smallest_spread2(self):
return int(self.generic_spread(6, 8, 12, 14, 0, 4))

def get_smallest_differential2(self):
return self.generic_spread(43, 45, 50, 52, 7, 21).strip()

def generic_spread(self, r1_start, r1_end, r2_start, r2_end, d_start, d_end):
value = ”
spread = 100

lines = self.file.readlines()
for line in lines:
if len(line) >= self.max_index(r1_end, r2_end, d_end):
try:
r1 = int(line[r1_start:r1_end])
r2 = int(line[r2_start:r2_end])
if abs(r1 - r2) < spread:
value = line[d_start:d_end]
spread = abs(r1 - r2)
except:
continue

return value

def max_index(self, v1, v2, v3):
if (v1 >= v2):
if (v1 > v3):
return v1
else:
return v3
return v1
elif (v2 >= v3):
return v2

return v3

Not exactly elegant, but definitely multipurpose. The max_index method doesn’t feel like the most elegant way to handle line length checking, but it’s not a hack so I was pragmatic and did what worked. Other than that I’m just doing the same string parsing and comparisons, just with the index being passed in.

That’s my take on kata four. I feel like working on the katas has done what I wanted them to do, which was to get me comfortable with the Python syntax and the flow when doing Python development. Going forward I’m going to be developing the Tetris knock-off and a web-based address book.

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.