Monthly Archives: September 2015

Python: Problem Set 11

Problem 11 is a weighting digraph problem, finding your way across campus given building numbers and sidewalks connecting them. In order to tackle this type of problem, I did use some outside tutorials on graph problems and depth-first search from TopCoder and the Python.org websites.

Part one involves finding the shortest path using a brute force method. One key to solving this is to keep from going into an infinite loop with cycles through the same nodes over and over. My chosen method is to look for the next node in the path I’ve already taken. This way [path] does double duty as my result and keeps track of nodes visited.

I banged my head on the dynamic programming portion of the problem long enough that I have to wrap this up without taking into account path weights. First, all hops are measured equally. Think number of airport connections made on a trip, but ignores miles flown. Second, I simply could not keep track of the current shortest distance as a break/continue condition without passing it as an argument when I recursed. There may not be anything wrong with this per se, but it is outside the problem specifications, so I feel I should disclose.

Thanks to MIT for providing all the course materials. It was fun.

pathfinding