Python - Calculate the number of steps between two points

Question

Assuming two points, (x1, y1) and (x2, y2), how do we find the minimum number of steps required to reach (x2, y2) from (x1, y1), assuming we can move vertically, horizontally or diagonally?

I have the following code that produces this result, but does so slowly. I'd like this result in O(1). How can I do this, preferably without using libraries?

def _dist(x1, y1, x2, y2):
    steps = 0
    while (x1, y1) != (x2, y2):
        dX, dY = calculate_delta(x1, y1, x2, y2)
        (x1, y1) = (x1 + dX, y1 + dY)
        steps += 1
    return steps


def calculate_delta(s_i, s_j, e_i, e_j):
    i = 0 if s_i == e_i else -1 if e_i < s_i else 1
    j = 0 if s_j == e_j else -1 if e_j < s_j else 1
    return i, j

You can't do this in constant time, unless you have precomputed routes stored in a table somewhere (or if the grid size is fixed). Constant time doesn't mean "fast", it means "independent of the input size". — chepner
– chepner, Commented Jan 8, 2022 at 14:49
In your code however it looks like a diagonal step is counted as a horizontal/vertical step, is it right? — Gabriele
– Gabriele, Commented Jan 8, 2022 at 14:49
yes you could move from (2, 2) to (1, 1) in a single diagonal step — Perplexityy
– Perplexityy, Commented Jan 8, 2022 at 14:54
I think I'm assuming an incomplete graph. To confirm, you can always move to any adjacent point (with integer coordinates)? — chepner
– chepner, Commented Jan 8, 2022 at 15:17
no, the points are all contained in a finite grid, such as a chessboard — Perplexityy
– Perplexityy, Commented Jan 9, 2022 at 11:17

EllipticBike38 · Accepted Answer · 2022-01-08 14:55:09Z

4

Assuming he could move diagonally the answer is:

def _dist(x1, y1, x2, y2):
    return max(abs(x1 - x2),abs(y1 - y2))

That's because he would do diagonally as many steps as there are units on the shortest axis plus as many steps as the difference in length between the axes: min + max - min = max

answered Jan 8, 2022 at 14:55

EllipticBike38

1115 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Iain Shelvington · Accepted Answer · 2022-01-08 14:54:47Z

2

The min steps is just the greatest difference in a single axis

def dist(x1, y1, x2, y2):
    return max(abs(x1 - x2), abs(y1 - y2))

answered Jan 8, 2022 at 14:54

Iain Shelvington

32.5k3 gold badges36 silver badges55 bronze badges

Comments

Jai248 · Accepted Answer · 2022-01-08 14:59:18Z

1

The answer is simple use math function, it will take O(1):

def _dist(x1, y1, x2, y2):
    return max(abs(x1 - x2),abs(y1 - y2))

edited Jan 8, 2022 at 14:59

answered Jan 8, 2022 at 14:50

Jai248

1,64910 silver badges24 bronze badges

3 Comments

Perplexityy Over a year ago

This assumes you only move horizontally or vertically, not diagonally.

Perplexityy Over a year ago

Hi there, for future reference, please do not do as you have done (delete your comment because it was initially incorrect, then subsequently edit and re-publish with the accepted solution, leading to a confusing scenario for readers).

Jai248 Over a year ago

Yeah , Sorry I won't do it again

Paul Kocian · Accepted Answer · 2022-01-08 14:57:20Z

0

You could do like this:

def _dist(x1, y1, x2, y2):
    return max(abs(x1-x2), abs(y1-y2))

answered Jan 8, 2022 at 14:57

Paul Kocian

5294 silver badges22 bronze badges

Collectives™ on Stack Overflow

Python - Calculate the number of steps between two points

4 Answers 4

Comments

Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related