CODEWITHSUNDEEP
python
Perplexityy
Perplexityy

Reputation: 569

Python - Calculate the number of steps between two points

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

Upvotes: 1

Views: 775

Answers (4)

Jai248
Jai248

Reputation: 1649

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))

Upvotes: 1

Paul Kocian
Paul Kocian

Reputation: 529

You could do like this:

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

Upvotes: 0

EllipticBike38
EllipticBike38

Reputation: 111

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

Upvotes: 4

Iain Shelvington
Iain Shelvington

Reputation: 32294

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))

Upvotes: 2

Related Questions