ant.py

"""finds the shortest path that an ant could take to reach a point from another
	 constraint: the ant can move only to the right or up at any point
"""

grid_order = 4
grid = {}
index = {}
rev_index = {}
adj_list = {}

def make_grid():
	"""initializes the basic grid of order n*n"""
	global grid
	order = grid_order + 1
	grid = [(x, y) for y in xrange(order) for x in xrange(order)]

def make_index(grid):
	"""creates an index and a reverse index for each node that is in the grid"""
	global index
	global rev_index
	for idx, i in enumerate(grid):
		index[idx] = i
	for i in index:
		rev_index[index[i]] = i

def can_be_neighbours(n1, n2):
	"""decides whether two nodes/vertices can be neighbours"""
	not_similar = n1 != n2
	right = n2[0] - n1[0] == 1 and n1[1] == n2[1]
	up = n2[1] - n1[1] == 1 and n2[0] == n1[0]
	return not_similar and (right or up)

def make_adj_list():
	"""this adj list is the graph made out of the grid. i.e, this list will 
     only have neighbours of each node and eliminates those nodes that cannot 
     be reached. essentially this eliminates the nodes that are to the left and bottom
     one step to a node. 
	"""
	global index
	global adj_list
	global grid
	for idx, i in enumerate(index):
		adj_list[idx] = [rev_index[x] for x in grid if can_be_neighbours(index[i], x)]
	return adj_list

def traverse(adj_list, start, end, path=[]):
	"""finds shortest paths from a starting point to an end point - idea referred from python docs"""
	path = path + [start]
	if start == end:
		return path
	if not adj_list.has_key(start):
		return None
	shortest = None
	for vertex in adj_list[start]:
		if vertex not in path:
			newpath = traverse(adj_list, vertex, end, path)
			if newpath:
				if not shortest or len(newpath) < len(shortest):
					shortest = newpath
	return shortest


make_grid()
#print grid

make_index(grid)
#print index
#print rev_index

adj_list = make_adj_list()
#print adj_list

print traverse(adj_list, 0, 24)