What?
This is just a quick post documenting my recent forays into Python programming and the kinds of things I managed to (quickly) do with it. You might ask “Why?”, well aside from the fact that learning new languages is fun and can keep you on your development toes, I’m seeing a lot of job adverts asking for skill sets which include scripting languages such as Ruby and Python. Since I’ve done a spot of Ruby in the past, I figured why not spend some time messing around with Python.
Do What?
This is the problem to solve. Given a triangle of numbers, find the shortest path from the top of the triangle to the bottom. So consider the triangle;
9
8 5
5 10 7
13 4 12 11
Moving between rows can only be done by going to the ‘root’ of any particular number. (Here, “root” in relation to trees not Maths). So, if we were are number 10 in the second to last row, our only options of moving to the final row are to select 4 or 12.
For this triangle, the shortest path is “9, 8, 5, 4″ which has a total weight of 26.
Starting from the top of the triangle will lead to a lot of messy backtracking, which, although doable, is a bit more complex than I want it to be. Another top-down solution might be to start lots of threads and start them exploring the triangle[1]. Again, this is a potential solution, but there is a much simpler approach we could take.
Starting at the bottom of the triangle, we can easily work out the cheapest way to get from row-1 to row. With that data, we can move up the triangle, working out the cheapest way to get from the row below, to the current row until we get up to the top, in which case we would have calculated the shortest path.
Because we care about the path and not just it’s weight, I created a class to represent both the path and the weight.
Classes
class Path:
def __init__(self,v):
if isinstance(v,int):
self.path = [v]
self.weight = v
else:
self.path = list(v.path)
self.weight = v.weight
def append(self, num):
self.path.append(num)
self.weight += num
def weight(self):
return self.weight
def __repr__(self):
str_list = ['Path:',`self.weight`,'\t',`self.path`]
return ''.join(str_list)
The only interesting part of the code above, I think, is the use of ‘isinstance’ to provide a form of constructor overloading.
Accepting the input
Accepting command line input from Python was also very easy, as it is in most scripting languages.
def readInput():
triangle = []
while True:
l = raw_input()
if l == 'EOF':
break
else:
row = buildRow(l);
triangle.append(row)
return triangle
def buildRow(line):
numRow = []
strRow = line.rsplit(' ')
for s in strRow:
numRow.append(int(s))
return numRow
This code accepts the input from the command line and returns us our triangle represented as a list of lists. Using the same example as above, we get the list;
[[9], [8, 5], [5, 10, 7], [13, 4, 12, 11]]
Note, that I didn’t bother with any checking or validating that the input formed a correct triangle.
Then I needed a method to be able to convert a [int] to a [Path]. As I was beginning to expect, this was going to be a simple matter.
def convertToPaths(row):
paths = []
for n in row:
paths.append(Path(n))
return paths
Being able to return tuples is also a very nice feature in Python and one I miss in Java after having spent time writing Haskell. I used this feature when working out the parents of a particular number in the triangle. In Java, I’d be forced to either create a “Parents” class which contained two numbers or return some kind of array or Collection which introduces a lot of places for errors and misuse. Tuples here keep things very plain and simple.
def parents(cIndex, row):
left = row[cIndex]
right = row[cIndex+1]
return (left,right)
I’m now ready for the algorithm proper. Converting the bottom row of the triangle in a [Path] gives me a starting point. Looking at the row above, I can calculate the cheapest way to get to it, knowing the current Path back to the bottom.
Put another way, I take the bottom two rows of the table (one which is a [Path] and the one above which is a [int]) and merge them together to make a new row, of type [Path] but which is of the same length as the [int] row. I repeat this process until there is only one row left, which should have only one element in it; a Path.
Here’s the code.
def calcPaths(base, row):
newBase = []
for i in range(0, len(row)):
(l,r) = parents(i, base)
if l.weight < r.weight:
new = Path(l)
else:
new = Path(r)
new.append(row[i])
newBase.append(new)
return newBase
def calcShortestPath(triangle):
row = len(triangle)-1
base = convertToPaths(triangle[len(triangle)-1])
while len(base) != 1:
base = calcPaths(base, triangle[row-1])
row -= 1
return base.pop(0)
triangle = readInput()
shortestPath = calcShortestPath(triangle)
print shortestPath
Then What?
The algorithm I chose, merging one row of the triangle into the row above, looks very much like a fold. (I can’t express who pleased with myself I was when such a functional solution magically popped into my brain when thinking about this problem). I couldn’t find a fold function in Python, luckily, writing my own was very simple.
def foldl(f, a, l):
if 0 == len(l):
return a
else:
head = l.pop(0)
a = f(a,head)
return foldl(f,a,l)
As you can see this is a left fold. This is not intended to be introduction into folds, but basically it works by accepting as arguments a function, an accumulator and a list. It then applies the function to the accumulator and the head of the list. It then recursively calls itself with the same function, the updated accumulator and the rest of the list until the list is empty.
So my main method now a bit more simple, with it’s intention more simply expressed by use of the fold method.
triangle.reverse()
def merge(paths, roots):
if 0 == len(paths):
return convertToPaths(roots)
else:
return calcPaths(paths,roots)
shortestPath = foldl(merge,[],triangle)
print shortestPath[0]
Although finding the shortest path is now expressed a bit more elegantly. We have to reverse the triangle. This is because we received the input in such a way as the ‘base’ of the triangle is the last element of the list, but we need to processes the bottom of the triangle first.
So What?
The thing that surprised me the most about programming Python was how easy it was. And it was really easy. The language syntax is simple and followed the same rules as most of the other languages I’ve picked up.
I particularly likes the way that everything, including functions, are objects and so can be passed around as arguments. I first encountered passing functions as parameters in Haskell, and since picking up that trick have often been frustrated that Java hasn’t offered me a simple way of doing the same thing.
The only thing that put me off was the convoluted way of “overloading” a constructor. Due to the way Python handles it’s types, overloading as we understand it in Java wasn’t possible. I think that’s a pretty small price to pay for the simplicity and power that Python programming provides.
[1] I’ve taken this problem from an tech test for an interview I had recently which I failed. The reason being that I’d spent many weeks prior to this particular interview reading about multi-threading at the new concurrency packages available in Java 5/6. Whilst all that is great and important, because I’d become so immersed in that kind of programming, I forgot to look for the simple solution first. My bad. I guess when you spend a long time studying hammers, new problems instantly present themselves as nails. There’s a lesson I won’t be forgetting in a hurry. Interestingly, my multi-threaded approach just wasn’t per formant enough for large triangles (more than 60 rows) because it found more and more work to do the longer the algorithm ran. With the above approach, the algorithm actually gets less work to do the closer it comes to a solution.
Posted by Tom 
