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.
|
1 2 3 4 5 6 7 |
# **PART OF** campus-map.txt # start, end, dist, distOutdoors 32 36 70 0 36 32 70 0 32 57 30 0 57 32 30 0 32 76 80 50 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 |
# ps11.py import time class Node(object): def __init__(self, name): self.name = str(name) def getName(self): return self.name def __str__(self): return self.name def __eq__(self, other): return self.name == other.name def __repr__(self): return self.name class Edge(object): def __init__(self, src, dest): self.src = src self.dest = dest def getSource(self): return self.src def getDestination(self): return self.dest def __str__(self): return str(self.src) + '->' + str(self.dest) class Wedge(Edge): def __init__(self, *a, **k): if 'tot' in k: self.tot = k['tot'] if 'out' in k: self.out = k['out'] Edge.__init__(self, *a) def getTotal(self): return self.tot def getOutside(self): return self.out class Digraph(object): def __init__(self): self.nodes = set([]) self.edges = {} def addNode(self, node): unique = True for i in self.nodes: if i == node: unique = False if unique: self.nodes.add(node) self.edges[node] = [] def addEdge(self, edge): self.edges[edge.src].append(edge) def childrenOf(self, node): return self.edges[node] def getNode(self, node): for j in self.nodes: if j == node: return j def __str__(self): res = '' for k in self.edges: for d in self.edges[k]: res = res + str(k) + '->' + str(d) + '\n' return res[:-1] def load_map(mapFilename): campus = Digraph() print "Loading map from file..." f = open(mapFilename, 'r') for line in f: data = line.split() # if nodes on campus, copy them if campus.getNode(Node(data[0])): a = campus.getNode(Node(data[0])) else: a = Node(data[0]) if campus.getNode(Node(data[1])): b = campus.getNode(Node(data[1])) else: b = Node(data[1]) c = Wedge(a, b, tot=data[2], out=data[3]) campus.addNode(a) campus.addNode(b) # since nodes are not duplicates (new instances), edge.src won't keyError edges{} campus.addEdge(c) return campus def find_path(graph, start, end, path=[]): start = Node(start) end = Node(end) # because I want to copy the nodes, not make new instances for i in graph.nodes: if i == start: start = i if i == end: end = i path = path + [start] if start == end: return path shortest = None for wedge in graph.childrenOf(start): if wedge.getDestination() not in path: newpath = find_path(graph, wedge.getDestination(), end, path=path) if newpath: if not shortest or len(newpath) < len(shortest): shortest = newpath return shortest graph = load_map("mit_map.txt") begin = time.time() print "find_path(graph, '32', '56')" print find_path(graph, '32', '56') finish = time.time() print "seconds: ", finish - begin # had to add a shortest arg to make work, else scope and recursion headache def dp_find_path(graph, start, end, path=[], shortest=[0]*999): start = Node(start) end = Node(end) # because I want to copy the nodes, not make new instances for i in graph.nodes: if i == start: start = i if i == end: end = i path = path + [start] if start == end: return path for wedge in graph.childrenOf(start): if len(path) > len(shortest): continue if wedge.getDestination() not in path: newpath = dp_find_path(graph, wedge.getDestination(), end, path, shortest) if newpath: if not shortest or len(newpath) < len(shortest): shortest = newpath return shortest #graph = load_map("campus-map.txt") begin = time.time() print "dp_find_path(graph, '32', '56')" print dp_find_path(graph, '32', '56') finish = time.time() print "seconds: ", finish - begin begin = time.time() print "dp_find_path(graph, '2', '9')" print dp_find_path(graph, '2', '9') finish = time.time() print "seconds: ", finish - begin |