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.
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
c, the answer would be
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) 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][j.location]) 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?