BFS is still slow even if I use duque


This is the problem I tried to solve:

Minimum Knight Moves

My solution was slow when I use a list to implement a queue. However, even when I use deque, the platform says that I exceed the time limit. Is there any way to improve the code? Thanks!


class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        from collections import deque
        visited = {(0, 0)}
        # queue = [(0, 0)]
        queue = deque([(0, 0)])
        depth_map = {(0,0) : 0}
        while queue:
            # m = queue.pop(0)
            m = queue.popleft()
            for nbr in [(m[0]+1, m[1]+2), (m[0]-1, m[1]+2), (m[0]+1, m[1]-2), (m[0]-1, m[1]-2), (m[0]+2, m[1]+1), (m[0]-2, m[1]+1), (m[0]+2, m[1]-1), (m[0]-2, m[1]-1)]:
                if nbr not in visited:
                    # queue += [nbr]
                    depth_map[nbr] = depth_map[m] + 1 
                    if nbr == (x, y):
                        return depth_map[nbr]

This is homework? We will help with hints and explainations but not solutions.

Try using coverage to find out where your code is spending its time.

python -m pip install coverage

Can coverage do that? I thought it was just for analyzing test coverage. I can’t see anything in the docs about profiling support.

Python comes with a built-in profiler called cProfile.

These problems are meant to challenge you algorithmically.
Hints: Exploit symmetry. Use A-star if the problem allows it.

Doh! Yes you are right c profile is what you need!
Sorry for the confusion.

Try printing out each position visited. That might give you a hint.

In particular, print the knight moves going from (0, 0) to (50, 100). Notice that most of the explored moves aren’t in the direction of the target.