minimum travel from point to point with incremental steps

Question

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.

• greybeard: (A trivial approach using as many steps again as the Manhattan distance seems obvious. And obviously non-minimal in most every case.)
• Сергей Макеев: Please clarify the condition that the steps must satisfy. Do you want each step to be larger than the last, or do you want it to be exactly 1 unit larger, or what?
• chavalife17: @СергейМакеев thanks for your feedback, I modified this.
• Narek Bojikian: Are there any constraints? How large x and y can be?
• orlp: Your problem can be alternatively stated as being able to shoot a billiard ball in the four cardinal directions on the positive quadrant of the plane. At step $k$ you shoot the ball $k$ units, and when it reaches an axis with steps left it will bounce off. That is, you move from $(x, y) \to (\textrm{abs} (x \pm k), y)$ or $(x, y) \to (x, \textrm{abs} (y \pm k))$. The way you can 'bounce off' is by assuming you change your previous moves so that you end up in the negative quadrant instead, and shoot from the negative quadrant into the positive quadrant.

Answer 1

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$

• chavalife17: I wonder how you consider that $\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil,ドル it's could be similar that solution of quadratic ecuation, and the choising of plus and this result is even, I know the non-negative step, but not the even consideration. Sorry if you consider that my question is trivial.
• 喜欢算法和数学: @chavalife17 Please come here from a chat.