I am trying to solve a maze problem.
The input data is a matrix, where the individual element represents the height of the mountain in that particular area, I have to start from position (0,0) and go to the position (n-1, n-1); where n is the size of the maze, my goal is to return the minimum number of possible climb round that I have to make in order to achieve this goal.
For example:
b = 010
010
010
In the matrix b,If I start from (0,0) I have to climb to height 1, now I am on the hill and I have to go down, so the total number of climb round is
abs(0(height of starting position) - 1(height of mountain)) + abs(1(height of mountain) - 0(height of the third column)) = 2
If I reach to third column then I do nnot have to climb any further round as my goal (2,2) would be at same level
c = 010
101
010
Similarly for c, the answer would be 4
A typical example would be
75218176
00125954
30062751
01192976
24660156
14932066
44532310
60429682
"""
self.location stores the location of current node
self.cost stores the cost or path length from adjacent node approaching from a particular path, for example in the above example If I have coming along the path 752
then cost of the node whose location is (0,2) would be 3, as the difference of height 5 and height 2 is 3
self.altitude simply stores the number which is at the location
self.totalCost represent the totalCost from the begenning, for example: for the path 752, the total cost of '2' would be 7- 5 + 5 -2 = 5
getTotalcost() simply add the parent cost with the difference in altitude of parent and self
neighbours() returns the possible node which can be reached from the current position.
Open is basically implementation of priority queue, I have not used heapq because in order to maintain the invariancy in structure I am not supposed to delete any element at random, although I can re-heapify after deletion but that seems to an obvious choice for inefficiency
"""
class node:
def __init__(self, loc):
self.location = loc
self.cost = 0
self.altitude = 0
self.parent = None
self.totalCost = 0
def __eq__(self, other):
return self.location == other.location
def __hash__(self):
return hash(self.location)
def getTotalcost(self):
if self.parent:
self.totalCost = self.cost + self.parent.totalCost
return self.totalCost
def __lt__(self, other):
return self.getTotalcost() < other.getTotalcost()
def neighbours(S, Node):
a,b = Node.location
options = []
for i in (a, b + 1), (a, b - 1), (a + 1, b), (a - 1, b):
if min(i) >= 0 and max(i) < S:
options.append(node(i))
return options
class Open:
def __init__(self, point):
self.container = [point]
self.se = set(self.container)
self.l = 1
def push(self, other):
if not(other in self.se):
self.properPlace(other)
else:
a = other
b = self.container.index(other)
k = self.container[b]
if k.getTotalcost() > a.getTotalcost():
del self.container[b]
self.l -= 1
self.se.remove(k)
self.properPlace(other)
def __iter__(self):
return iter(self.container)
def rem(self):
self.l -= 1
return self.container.pop(0)
def properPlace(self, other):
i = 0
while i < self.l and self.container[i].getTotalcost() < other.getTotalcost():
i += 1
self.container.insert(i, other)
self.l += 1
self.se.add(other)
def path_finder(maze):
maze= maze.split("\n")
l = len(maze)
start = node((0,0))
start.altitude = int(maze[0][0])
start.totalCost = 0
r = Open(start)
visited = set()
while True:
i = r.rem()
if i.location == (l - 1, l- 1):
return i.getTotalcost()
for j in neighbours(l, i):
j.altitude = int(maze[j.location[0]][j.location[1]])
if j not in visited:
j.cost = abs(i.altitude - j.altitude)
j.parent = i
r.push(j)
visited.add(i)
I have some thoughts that my implementation of priority queue is inefficient, am I right? If yes, then how can I make it more efficient? How can I make the program efficient?
