minimum travel from point to point with incremental steps

It's my first time to make a question here.
I have a curious problem about algorithm, in the center of Cartesian plane (0,0) I need to go to another point (x,y) -x and y are belong to Z numbers - but I only can use horizontaly and verticaly steps and this steps increases one by one units, a unit is a distance from (0,0) to (0,1), (1,0), (-1,0) or (0,-1).

For example, I need to go to (1,1) point and steps are:

• Go to (1,0), a step of 1 unit.

• Go to (1,-2) a step of 2 units.

• Finally, go to (1,1) a step of 3 units.

And for this example the answer is I need 3 steps with 6 units of distance.

Obviously, there are several ways to go to a point from center but
the problem needs the minimal.

Are there a formula or an algorithm to find the minimum count of steps and the distance of this way?

Well, if you find one of them (steps or distance), the other one is easy to find because the distance is a sum of N (count of steps) first natural numbers.

Thanks for read this and for your answers and suggestions.

Interesting question. It is surprising that the answer depends only on $|x|+|y|$. For example, the same number of the steps is needed to reach $(1,1)$ or $(0,2)$.

The minimum step is the least non-negative integer $n$ such that $n(n+1)/2-(|x|+|y|)$ is even and nonnegative.

Here is an $O(1)$-time algorithm that returns the value described above, where least_n, i.e., $\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$, is the least nonnegative integer $n$ such that $n(n+1)/2-(|x|+|y|)\ge0$.

def minimum_steps(x,y):
    distance_to_origin := absolute_value(x) + absolute_value(y)
    least_n := ceiling((-1 + square_root(8 * distance_to_origin + 1)) / 2)
    gap := n * (n + 1) / 2 - distance_to_origin
    # 0 <= gap <= n - 1

    if gap is even:
        return least_n
    else if n is even:
        return least_n + 1
    else:
        return least_n + 2

Given the number of steps $s$, the distance travelled is $1+2+\cdots+s=s(s+1)/2$.

The correctness of the formula and algorithm above comes from the following characterization.

Proposition. The minimum count of steps from $(0,0)$ to $(x,y)$ is the least non-negative integer $n$ such that $n(n+1)/2-(|x|+|y|)$ is nonnegative and even.

Proof. If we can go to $(x,y)$ in $n$ steps, the sum of some numbers between 1 and $n$ or their negations must be $x$ and the sum of the remaining numbers or their negations must be $y$, i.e.,
$$\pm1\pm2\pm\cdots\pm n = |x| + |y|$$
for some choice of all $\pm$'s. That means,
$$1+2+\cdots+ n - (|x| + |y|)$$
is nonnegative and even.

Now it is enough to prove that $(x,y)$ is reachable in $n$ steps if $n(n+1)/2-(|x|+|y|)$ is nonnegative and even. Let us prove it by induction on $n$.

The base cases, $n=0$ or $1$ means $(x,y)=(0,0), (0,1), (1,0)$. These cases are immediate to verify.

Suppose, as induction hypothesis, it is correct for smaller $n$'s. Now consider the case of $n\ge2$ with $n(n+1)/2-(|x|+|y|)$ nonnegative and even. We can assume $x$ and $y$ are non-negative; otherwise, for example, if $x$ is negative, we can change $x$ to its absolute value and reverse the direction of all steps that are parallel to $X$-axis.

There are three cases.

• $x \ge n$. Let $x'= x-n$. Then $$(n-1)n/2-(|x'|+|y|)=n(n+1)/2-(|x|+|y|)$$ is nonnegative and even. By induction hypothesis, we can go to $(x',y)$ in $n-1$ steps. To reach $(x,y)$ in $n$ steps, we continue $n$ units in X-direction.

• $y\ge n$. This is symmetric to the case above.

• $0\le x\lt n$ and $0\le y\lt n$. There are two subcases.

• $x\ge 2$ and $y\ge 2$. Let $x'=(n-1)-x$ and $y'=n-y$. Then $|x'|\le n-3$ and $|y'|\le n-2$. $$(n-2)(n-1)/2-(|x'|+|y'|)\ge(n-3)(n-4)/2\ge0.$$ The parity of $(n-1)(n-1)/2-(|x'|+|y'|)$ is the same as $n(n+1)/2-(|x|+|y|)$, i.e, even. By induction hypothesis, we can go to $(x',y')$ in $n-2$ steps . Reversing all the steps, we can go to $(-x', -y')$ in $n-2$ steps as well. To reach $(x,y)$ in $n$ steps, we can continue with two more steps, $n$ units in X-direction and $n+1$ units in Y-direction.

• One of $x$ and $y$ is $0$ or $1$. Let $g(k)=k(k+1)/2-(|x|+|y|)$. The smallest nonnegative integer such that $g(k)\ge0$ is $m=\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$. Since both $x$ and $y$ are $\lt n$ and one of them is $0$ or $1$, $$m\le \frac{1+\sqrt{8n+1}}2.$$

When $g(m)$ is even, $n=m$ by definition. When $g$ is odd, since either $g(m+1)=g(m)+(m+1)$ or $g(m+2)=g(m)+(m+1)+(m+2)$ must be even, either $m+1$ or $m+2$ must be $n$. So, whether $g(m)$ is even or odd, we have $$n\le m+2.$$
Combing the two inequalities above, we have
$$n\le \frac{5+\sqrt{8n+1}}2,$$
which implies $n\le 6$. Since X-direction and Y-direction are symmetric, let us assume $y=0,1$. Since $x\lt n$, $x\lt 6$. So it is enough to verify the cases where $(x,y)$ $\in $ $\{(0,0),(0,1),$ $(1,0),(1,1),$ $(2,0), (2,1),$ $(3,0), (3,1),$ $(4,0), (4,1),$ $(5,0), (5,1)\}.$ It is easy to verify each of them.

$\ \checkmark$

StackExchange Computer Science Q#129385, answer score: 2