4
$\begingroup$

I've been trying to work through a math problem and wanted to see if it's feasible to solve within a certain number of moves.

A target point is placed at unknown coordinates (tx, ty) where both tx and ty are uniformly random in [-20,000,000, 20,000,000]. You start at the origin (0, 0).

Each turn, you move by a delta (dx, dy) of your choice. Your move must be at least 20 ft (sqrt(dx² + dy²) ≥ 20). After each move, you receive the change in your Euclidean distance to the target compared to your previous position, rounded deterministically to the nearest 5 ft.

Formally: feedback_delta = round_to_nearest_5(dist(new_pos, target) - dist(old_pos, target)). Positive means you got further, negative means closer.

Your goal is to move within 1 ft of the target in the fewest moves possible.

With my current approach I can make it in 70 or so moves, but it feels like there should be a more precise solution that takes fewer.

My solution so far:

1. Find the approximate angle

Move +100,000 ft on the x-axis, record the delta as a, then -100,000 ft on the x-axis to return to (0, 0). Do the same for the y-axis and record that delta as b. The approximate direction to the target is then the unit vector (a, b) / ||(a, b)||. The rounding introduces some uncertainty here though, which compounds over long distances.

2. Move toward that direction as far as possible

Since both coordinates are bounded by [-20,000,000, 20,000,000], the max distance you can travel along direction (a, b) is limited by whichever axis hits a wall first:

d_max = min(20,000,000 / |a|, 20,000,000 / |b|) · ||(a, b)||

The x and y components of the move are then:

dx = d_max · a / ||(a, b)||
dy = d_max · b / ||(a, b)||

Record the delta as c. This intentionally overshoots the target.

3. Backtrack based on delta

You moved M ft total (where M is d_max from previous step) and recorded delta c. The distance to the target before the move was:

D = (M - c) / 2

where c is signed (negative = closer, positive = further). The overshoot is M - D:

overshoot = (M + c) / 2

So to backtrack:

dx = -overshoot · a / ||(a, b)|| dy = -overshoot · b / ||(a, b)||

This gets within a few thousand ft, but lateral error from the imprecise angle in step 1 adds significant uncertainty.

4. Search for rounding boundaries for a more precise angle

To get a more precise angle than step 1 we find the exact move distance in both x and y where the rounded feedback flips between two values.

From the coarse angle I believe we can compute the minimum range guaranteed to contain a rounding boundary. A 1 ft change in move distance changes the true delta by approximately cos(α) on the x-axis and sin(α) on the y-axis. To guarantee crossing a 5 ft rounding boundary:

x_range = 5 / cos(α)
y_range = 5 / sin(α)

So for x: move +1,000 ft, record the delta, move back. Then move +(1,000 + x_range) ft, record the delta, move back. These two should be guaranteed to produce different rounded values. Now binary search between them: try the midpoint, see which way it rounds, halve the interval, repeat until the range between the two bracketing distances is less than 0.1 ft.

At that boundary, the true delta equals exactly the midpoint between the two rounded values (e.g., if 1,002.2 gives 980 and 1,002.3 gives 985, the true delta is 982.5 at move distance ≈1,002.25). This gives cos(α) = 982.5 / 1,002.25 with much higher precision.

Repeat for y. Then the refined direction vector is (cos(α), sin(α)). The cost is several turns per axis though.

5. Rinse and repeat: overshoot, backtrack, and refine the angle

We can repeat steps 2–4, getting closer to the target with each cycle. I believe if it's done correctly we should be able to get within 1 ft within a couple of cycles, but I'm not fully confident about that.

An alternative solution I considered, but haven't played with: instead of angle-based triangulation, binary search each axis independently. Move to the midpoint of the x-range, probe to determine which side the target is on, halve the range, repeat. This would probably still need some cycles though so I'm not sure if this is the best approach.

I've created a small codepen for the problem that I've been using to test strategies.

So I'm wondering: is there a more efficient strategy, and is there a way to determine the maximum number of turns a strategy would take?

My initial thoughts are that with better math we could potentially avoid returning to an origin point when probing, but I'm not sure how. It also seems like there should be a way to determine the exact precision of the angle needed to avoid multiple refinement cycles.

Also, does the 20 ft minimum displacement per turn add significant difficulty, or is the problem essentially the same without it?

I also don't have a background in math and don't fully understand all of the formulas I've been using but they are what I found when trying to find formulas that represented how my brain thought about each step.

$\endgroup$
4
  • $\begingroup$ As described, it appears we don't get distance data when we start at $(0,0)$; our first distance data is provided after our first move. Is that correct? $\endgroup$ Commented Apr 13 at 3:54
  • $\begingroup$ Right, since it is not distance from the destination, but it is the difference in distance to the destination from your last point to your next point. So there is no last point to compare with the first move. So if I move from starting point at (0, 0) 100 ft directly north and the destination is directly south to me, I am told on the first move I traveled 100ft further away from it. $\endgroup$ Commented Apr 13 at 5:56
  • $\begingroup$ Must $dx$ and $dy$ be integers? $\endgroup$ Commented Apr 13 at 18:14
  • $\begingroup$ They don't need to be integers, they could have any amount of decimal places $\endgroup$ Commented Apr 13 at 21:17

2 Answers 2

Reset to default
3
$\begingroup$

Given an unknown but fixed $t = (t_x, t_y)$, let $p_i = (x_i, y_i)$ be your current position at step $i$, so $p_0 = (0,0)$. Let $$\delta_i = ||p_i - t|| - ||p_{i-1} - t||, \quad i \ge 1 \tag{1}$$ represent the (signed) change in distances to $t$ between your current position and the previous position. With some algebra, we can show that the locus of $t$ given two distinct points $p_{i-1}$, $p_i$ is in general one branch of a hyperbola.

Therefore, if the sequence of positions is chosen well, we will have $\delta_1$ and $\delta_2$ such that the locus of $t$ satisfying $(1)$ will be the intersection of two distinct hyperbolic branches, which occurs in at most two distinct points. Consequently, we would choose one of those points on the next move, and depending on the change in distance, either narrow our choice further in that neighborhood, or select the other point to test. So in practice, if there is no rounding involved, you need at most $4$ guesses.

The problem is that with rounding, you are not given precise changes in distance. To locate $t$ more precisely when you are only given $\delta_i$ to the nearest rounded distance means that you will need to compensate for the discretization, which results in two issues: first, the hyperbolic branches become bands with nonzero width, meaning you need to pick a point in their intersection, which has nonzero area.

However, the second issue is more fundamental and serious: if you are never given a $\delta_i$ to a precision within the desired error, you will need to waste more guesses simply to correct for that imprecision. One thing you can do is test points in the neighborhood until you have several that return $0$. These are points for which the absolute change in distance to $t$ is at most $5$. The minimum number of such guesses needed to ensure that we are in some region of $t$ with radius less than $1$ should be tractable, and although I do not know off the top of my head, I strongly suspect it is far less than $70$.

In summary, you have two phases to your search: there is the hyperbolic stage, in which you find the neighborhood of $t$; then there is the refinement stage, in which you reduce the error introduced by rounding. The mathematical details of these stages are left to you to derive and implement programmatically.

$\endgroup$
2
$\begingroup$

Let the first two moves travel along an equilateral triangle of maximal size (from the origin, along $15^\circ$ North of East and along $15^\circ$ East of North, until these reach the boundary of the map). This partitions the plane into small regions compatible with the two measurements. (The first move partitions the plane into non-uniform strips, each strip labelled by the change of distance a target at one of its points would give. The second move partitions the plane in not-quite-perpendicular strips. Taken together, these two change of distance measurements approximately grid the plane nonuniformly into regions labelled by what two changes of distance a point in that region would have given. Of course, only one sequence of changes of distance is given and we know the target is in the corresponding region.)

Now, repeat until the circumscribing circle of the compatible region has radius $\leq 1\,$ft:

  • find the centroid of the compatible region;
  • find the long axis (or any axis if there isn't a long axis -- maybe use inscribed or circumscribed ellipses to find this axis);
  • move to a point on the long axis where a rounding "jump" occurs at the centroid. (I'm sure there's something slick using conjugate gradient methods to be sure that new cuts are maximally independent from previous cuts.)

The area of the compatible region is approximately halved on each cycle through the list. Although the regions after two moves have a variety of sizes and shapes, repeated halving will reduce the compatible area rapidly. Even if the first region were the entire $4 \times 10^{14}$ sq. ft., 70 halvings would get you down to $\sim 10^{-7}$ sq. ft. Fifty halvings of the map would get you to $\sim 1$ sq. ft. Starting with a compatible region of $25$ sq.ft. (give or take a factor of two) you arrive at $< 1$ sq. ft. after $4-6$ halvings. So you expect to have a solution after $2+5$-ish moves.

$\endgroup$
1
  • $\begingroup$ I had not even considered this, beautifully put! Thank you! $\endgroup$ Commented Apr 14 at 15:25

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.