You are in an infinite 2D grid where you can move in any of the 8 directions : (x,y) to (x+1, y), (x - 1, y), (x, y+1), (x, y-1), (x-1, y-1), (x+1,y+1), (x-1,y+1), (x+1,y-1) You are given a sequence of points and the order in which you need to cover the points. Give the minimum number of steps in which you can achieve it. You start from the firs…

MinStepsInInfiniteGrid.cpp

/*
You are in an infinite 2D grid where you can move in any of the 8 directions :   
(x,y) to (x+1, y), (x - 1, y), (x, y+1), (x, y-1),      (x-1, y-1),      (x+1,y+1),      (x-1,y+1),      (x+1,y-1)  
You are given a sequence of points and the order in which you need to cover the points. 
Give the minimum number of steps in which you can achieve it. You start from the first point.  
Example :  Input : [(0, 0), (1, 1), (1, 2)] Output : 2 It takes 1 step to move from (0, 0) to (1, 1). 
It takes one more step to move from (1, 1) to (1, 2).  

This question is intentionally left slightly vague. 
Clarify the question by trying out a few cases in the “See Expected Output” section. 
Tags: InterviewBit Arrays Problem https://www.interviewbit.com/problems/min-steps-in-infinite-grid/
*/

// Input : X and Y co-ordinates of the points in order. 
// Each point is represented by (X[i], Y[i])
int Solution::coverPoints(vector<int> &X, vector<int> &Y) {
    int count = 0;
    int a = 0; int b = 0;
    for (int i=0; i < (X.size()-1); ++i) {
        a = abs((X[i+1]-X[i]));
        b = abs((Y[i+1]-Y[i]));
        count += max(a,b);
    }
    return count;
}

Why distance formula is not applicable for this solution?

@nolanding distance formula isn't applicable because Distance formula won't calculate the "steps" tracing the small cells in a zig-zag manner as implied by coordinates in X and Y input lists.

Instead distance formula would just calculate the shortest path between two coordinates cutting across small cells diagonally or in a straight line. Refer: https://www.khanacademy.org/math/geometry/hs-geo-analytic-geometry/hs-geo-distance-and-midpoints/v/distance-formula for clarity.

Thanks for the answer. I found it long back.

…

On Thu, 3 Sep, 2020, 4:15 am Abhishek Agrawal, ***@***.***> wrote: ***@***.**** commented on this gist. ------------------------------ @nolanding <https://github.com/nolanding> distance formula isn't applicable because Distance formula won't calculate the "steps" tracing the small cells in a zig-zag manner as implied by coordinates in X and Y input lists. Instead distance formula would just calculate the shortest path between two coordinates cutting across small cells diagonally or in a straight line. Refer: https://www.khanacademy.org/math/geometry/hs-geo-analytic-geometry/hs-geo-distance-and-midpoints/v/distance-formula for clarity. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <https://gist.github.com/829e95c4455c470f7f50e7ff77d70b8b#gistcomment-3440340>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AFCRRAGF43GGIJYOG32KYO3SD3DIRANCNFSM4PAJJIRQ> .

Sorry for the long delay in my response, I somehow missed this email. Happy coding! :) Best Regards, Abhishek Agrawal On Thu, Sep 3, 2020 at 8:23 AM deeksha chandwani <notifications@github.com> wrote:

…

***@***.**** commented on this gist. ------------------------------ Thanks for the answer. I found it long back. On Thu, 3 Sep, 2020, 4:15 am Abhishek Agrawal, ***@***.***> wrote: > ***@***.**** commented on this gist. > ------------------------------ > > @nolanding <https://github.com/nolanding> distance formula isn't > applicable because Distance formula won't calculate the "steps" tracing the > small cells in a zig-zag manner as implied by coordinates in X and Y input > lists. > > Instead distance formula would just calculate the shortest path between > two coordinates cutting across small cells diagonally or in a straight > line. Refer: > https://www.khanacademy.org/math/geometry/hs-geo-analytic-geometry/hs-geo-distance-and-midpoints/v/distance-formula > for clarity. > > — > You are receiving this because you were mentioned. > Reply to this email directly, view it on GitHub > < https://gist.github.com/829e95c4455c470f7f50e7ff77d70b8b#gistcomment-3440340 >, > or unsubscribe > < https://github.com/notifications/unsubscribe-auth/AFCRRAGF43GGIJYOG32KYO3SD3DIRANCNFSM4PAJJIRQ > > . > — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <https://gist.github.com/829e95c4455c470f7f50e7ff77d70b8b#gistcomment-3440513>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABGTMH5CPR5H5WSZCL7ARYLSD4AJHANCNFSM4PAJJIRQ> .

Why are we taking
count += max(a,b);
instead of
count +=min(a,b);
as the question asks for min no steps?

@Anjali-Sah because the number of steps or distance remains constant to reach from point A to point B. Problem statement reads, "Give the minimum number of steps in which you can achieve it." - It does not literally mean take min(a,b). If we take min(a,b) in each iteration, the number of steps and iterations will only increase to reach the end point/cell B. Taking max(a,b) ensures we find the shortest path in less iterations to reach final destination. (P.S. Distance being constant in the problem for each step distance being 1).

Hope this clarifies a bit.