Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- (a, b, c, d, e, f, g, h, i, j, k, z) = range(12)
- names = {a : 'a', b : 'b', c : 'c', d : 'd', e : 'e', f : 'f', g : 'g',\
- h : 'h', i : 'i', j : 'j', k : 'k', z : 'z'}
- cities = {'a' : a, 'b' : b, 'c' : c, 'd' : d, 'e' : e, 'f' : f, 'g' : g,\
- 'h' : h, 'i' : i, 'j' : j, 'k' : k, 'z' : z}
- # a, b, c, d, e, f, g, h, i, j, k, z
- ways = ((0, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0), # a
- (2, 0, 0, 2, 3, 0, 0, 0, 0, 0, 0, 0), # b
- (3, 0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 0), # c
- (0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0), # d
- (0, 3, 1, 0, 0, 4, 2, 0, 0, 0, 0, 0), # e
- (0, 0, 0, 1, 4, 0, 0, 3, 2, 0, 0, 0), # f
- (0, 0, 2, 0, 2, 0, 0, 0, 0, 1, 0, 0), # g
- (0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3), # h
- (0, 0, 0, 0, 0, 2, 0, 0, 0, 5, 0, 2), # i
- (0, 0, 0, 0, 0, 0, 1, 0, 5, 0, 3, 0), # j
- (0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 3), # k
- (0, 0, 0, 0, 0, 0, 0, 3, 2, 0, 3, 0)) # z
- def shortest_path(start, finish):
- def neighbors(dists):
- return filter(lambda x: dists[x] != 0, range(len(dists)))
- def cost(path):
- if len(path) == 1:
- return 0
- return ways[path[0]][path[1]] + cost(path[1:])
- def go_wide(paths):
- if len(paths) == 0:
- return None
- path = paths[0]
- city = path[-1]
- if city == finish:
- return path
- children = filter(lambda c: c not in path, neighbors(ways[city]))
- next = map(lambda c: path + [c], children)
- return go_wide(sorted(paths[1:] + next, lambda x, y: cost(x) - cost(y)))
- return go_wide([[start]])
- start = cities[raw_input("from ")]
- finish = cities[raw_input("to ")]
- print map(lambda a: names[a], shortest_path(start, finish))
- raw_input()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement