# Reducing time complexity of weighted grid pathfinder

For school, I made a pathfinder for a weighted grid, but anything beyond a 7x7 grid takes a significant portion of time. I was wondering if I can improve my code at all, or if there is a way to reduce the time complexity.

I would appreciate any pointers for improving my code whether it's readability or efficiency.

import math
import random

class Grid:
def __init__(self,width,height):
self.board = []
self.width = width;
self.height = height;
for x in range(width*height):
self.board.append([])
for x in range(width):
for y in range(height):
rand = random.randint(0,3)
self.board[x].append(rand)
def display(self):
for x in range(self.width):
for y in range(self.height):
print(str(self.board[x][y]) + " ",end="")
print()

class Point:
def __init__(self,x,y):
self.x = x
self.y = y
return Point(self.x+x,self.y+y)
def sub(self,x,y):
return Point(self.x-x,self.y-y)

class Node:
def __init__(self,start,end):
self.start = start
self.end = end
self.elements = [start]
def size(self):
return len(self.elements)
def get(self,index):
return self.elements[index]
def append(self,element):
self.elements.append(element)
def calc(self,grid):
cur_point = self.elements[self.size()-1]
total = distance(cur_point,end)
for x in range(self.size()):
point = self.elements[x]
total += grid.board[point.x][point.y]
def clone(self):
node = Node(self.start,self.end)
node.elements = self.elements[:]
return node
def display_path(self,grid):
for x in range(self.size()):
point = self.elements[x]
grid.board[point.x][point.y] = "P"
grid.display()

class PriorityList:
def __init__(self,node):
self.elements = [node]
def size(self):
return len(self.elements)
def get(self,index):
return self.elements[index]
def append(self,element):
self.elements.append(element)
def sort(self,grid):
index = 1
while index < self.size():
node = self.elements[index]
n = self.elements[index-1]
if node.calc(grid) < n.calc(grid):
self.elements[index] = n
self.elements[index-1] = node
index = 1
index += 1

def distance(p1,p2):
return math.sqrt( math.pow(p2.x-p1.x,2) + math.pow(p2.y-p1.y,2) )

def getPoint(x,y):
x = int(input("Enter " + x + ": "))
y = int(input("Enter " + y + ": "))
return Point(x,y)

print("Customize grid...")
dimensions = getPoint("Width","Height")
print("Enter the starting point...")
start = getPoint("X","Y").sub(1,1)
print("Enter the ending point...")
end = getPoint("X","Y").sub(1,1)

grid = Grid(dimensions.x,dimensions.y)
grid.display()

print()

n = Node(start,end)

queue = PriorityList(n)

class Pathfinder(Exception): pass
try:
while True:
queue.sort(grid)
node = queue.get(0)
discovered = False
for x in range(-1,2):
for y in range(-1,2):
point = node.get(node.size()-1)
if point.x + x >= 0 and point.y + y >= 0 and point.x + x < grid.width and point.y + y < grid.height:
if x != 0 or y != 0:
discovered = True
new = node.clone()
queue.append(new)
if point.x+x == end.x and point.y+y == end.y:
score = new.calc(grid)
new.display_path(grid)
print("Score: " + str(score))
raise Pathfinder
discovered = True
if discovered:
queue.elements.remove(queue.get(0))
except Pathfinder:
pass


The thing that sticks out the most is that your PriorityList, a priority queue, is a list instead of a heap.

You sort() the list every iteration, which (if implemented correctly) would be O(n log n), but in a proper priority queue adding/removing elements should be O(log n)

Your actual comparison-sort implementation is O(n), which is impossible, meaning it doesn't even work correctly as-is.

I suggest to use numpy instead of Python lists. For example your Grid class

class YourGrid:
def __init__(self,width,height):
self.board = []
self.width = width;
self.height = height;
for x in range(width*height):
self.board.append([])
for x in range(width):
for y in range(height):
rand = random.randint(0,3)
self.board[x].append(rand)
def display(self):
for x in range(self.width):
for y in range(self.height):
print(str(self.board[x][y]) + " ",end="")
print()


can be reduced to just:

class NumpyGrid:
def __init__(self, width, height):
self.width = width
self.height = height
self.board = np.random.randint(0, 4, size=(width, height))

def display(self):
print(self.board)


To compare it with bigger boardsize:

>>> %timeit YourGrid(100, 100)
17.6 ms ± 215 µs per loop
>>> %timeit NumpyGrid(100, 100)
73.7 µs ± 3.38 µs per loop


and this will of course scale up: the straight Python list implementation will become slower as you increase sizes. Avoid for loops, append methods as much as you can, these will make your code inefficient. There is a nice talk about this by Jake VanderPlas at PyCon. This is particularly true to your while True section: too much list manipulation there, which slows it down.

I think your Point class should implement more functionality. Make a distance method for example, it's not hard:

    def distance(self, other):
if not isinstance(other, Point):
raise TypeError("Point object is expected.")
return math.sqrt(math.pow(other.x-self.x,2) + math.pow(other.y-self.y,2))


If you don't use any class functionality, why make it object oriented?

Also, calculating the distance between points is much-much faster with numpy.linalg.norm or scipy.spatial.distance.cdist, but that's probably an overkill.

This

def size(self):
return len(self.elements)


should be

def __len__(self):
return len(self.elements)


and it can be accessed via len(object).

def get(self, index):


should be

def __getitem__(self, indeces):


In the Point class you return new instances of itself. I don't think you should do that. Maybe you just want to modify the x and y inplace, so it can be

def add(self, x, y):
self.x += x
self.y += y


Note that there is also a built-in method called __add__.

Your whole main script should be in a __main__ guard:

if __name__=='__main__':
print("Customize grid...")
dimensions = getPoint("Width","Height")
...


You don't validate any user input.

You break out the main while loop with a custom exception. I think it can be just break, there is no point of the try-except. Or move the condition to while loop. A little sketch what I mean:

condition = False
while not condition:
for x in range(1000):
if x == 100:
condition=True


According the style, you should follow PEP8.

I won't try to rewrite this, but probably there is a lot more to improve besides I posted above. Also you should add comments, it's hard to figure out what are you doing with each step.

• Thank you! This is very informative, but I do have a question. You said I could break, but I don't think you can break from the outer loop without a custom exception. Correct me if I'm wrong.
– ZL11378
Jan 6 '20 at 19:21
• You should be able to break out. Also instead of while True might be worth to change it to something likewhile not condition. Jan 6 '20 at 19:32
• @ZL11378 You can break out of any loop, no exceptions required, if that's what you were asking.
– AMC
Jan 9 '20 at 0:47