Which algorithm should be used to find the point?-CodePudding

You need to find some unknown, predetermined point in three-dimensional space, in the smallest number of attempts, using only a function that can return the distance from any point you pass to it to the desired unknown point.

To solve the problem, first implement a function f that, by taking the coordinates of any any point s(x, y, z), return the distance between that point and a conditionally unknown, randomly generated point

point you arbitrarily generate r(x, y, z), where x, y, z can be integers between 0 и 100. For example, for an arbitrarily generated point r(0, 0, 10) and a point passed to the function s(0, 0, 0), the result of the function would be as follows: f(s) = 10 // the distance between s(0, 0, 0) and r(0, 0, 10) is 10 Next, implement the algorithm itself for the assignment. The algorithm should find the coordinates of of an arbitrarily generated point with the least number of calls to the function f.

I have a randomizer instead of an algorithm, that's all I got. Help.

const pointToFound = {
  x: 12,
  y: 9,
  z: 76,
};

let attemts = 0;
let isXFound = false;
let isYFound = false;
let isZFound = false;

const pointHistory = [];

const getRandomPoint = () => {
  return {
    x: isXFound ? isXFound : Math.floor(Math.random() * 101),
    y: isYFound ? isYFound : Math.floor(Math.random() * 101),
    z: isZFound ? isZFound : Math.floor(Math.random() * 101),
  };
};

const getDifference = (point, pointToCompare) => {
  return {
    x:
      Math.max(point.x, pointToCompare.x) - Math.min(point.x, pointToCompare.x),
    y:
      Math.max(point.y, pointToCompare.y) - Math.min(point.y, pointToCompare.y),
    z:
      Math.max(point.z, pointToCompare.z) - Math.min(point.z, pointToCompare.z),
  };
};

const condition = !isXFound && !isYFound && !isZFound;

while (condition) {
  const point = getRandomPoint();

  const difference = getDifference(point, pointToFound);
  pointHistory.push(point);

  attemts  = 1;

  if (isXFound && isYFound && isZFound) {
    console.log("Total attempts: ", attemts);
    console.log(point);
    break;
  }

  if (difference.x === 0 && !isXFound) {
    isXFound = point.x;
  }

  if (difference.y === 0 && !isYFound) {
    isYFound = point.y;
  }

  if (difference.z === 0 && !isZFound) {
    isZFound = point.z;
  }
}

console.log(pointHistory);

I have a randomizer instead of an algorithm, that's all I got. Help.

CodePudding user response：

One idea is as follows:

You pick an initial random point, and for each dimension, find the exact value. How? For the sake of symmetry, suppose that you desire to find x of the target point. Increase by one the x, and compute the distance of the new point from the target point. If it goes further, it means that you should move in the opposite direction. Hence, you can run a binary search and get the distance to find the exact x of the target point. Otherwise, it means that you are going in the right direction along X-axis. So, do a binary search between all points with the same y and z such that their x values can change from x 1 to 100. A more formal solution comes in the following (just a pseudo-code).

You should also ask about the complexity of this solution. As the dimension of the point is constant (3) and checking these conditions take a constant time, the complexity of number of calling getDifference function is O(log(n)). What is n here? the length of valid range for coordinates (here is 100).

1. p: (x,y,z) <- Pick a random coordinate
2. dist: (dist_x, dist_y, dist_z) <- getDifference(p, TargetPoint)
3. For each dimension, do the following (i can be 0 (x), 1 (y), 2 (3)):
4.       if(dist == 0):
5.           isFound[i] <- p[i]
6.           continue

7.     new_i <- p[i]   1
8.     new_point <- p
9.     new_point[i] <- new_i
10.    new_dist <- getDifference(new_point, pointToFound)
11.    if(new_dist == 0):
12.        isFound[i] <- new_point[i];
13.        continue
    
14.    if(new_dist[i] > dist[i]):
15.        isFound[i] <- binary_search for range [0, p[i]-1] to find the exact value of the pointToFound in dimension i
15.        continue
16.    else:
17.        isFound[i] <- binary_search for range [p[i]   1, 100] to find the exact value of the pointToFound in dimension i      
18.        continue

CodePudding user response：

This can be done with at most 3 guesses and often with 2 guesses:

Let the first guess be [0, 0, 0], and ask for the distance
Find in the 100x100x100 cube all points that have that distance to [0, 0, 0]. There might be possible 200 points that have that distance: consider these all candidates.
Take the first candidate as the second guess and ask for the distance
Find among the other candidates the ones that have exactly that distance to the first candidate. Often there will be only one point that satisfies this condition. In that case we can return that candidate and only 2 guesses were necessary.
Otherwise (when there is more than one candidate remaining) repeat the previous step which will now certainly lead to a single point.

Here is an implementation that provides a blackbox function which chooses the secret point in a local variable, and which returns two functions: f for the caller to submit a guess, and report for the caller to verify the result of the algorithm and report on the number of guesses. This is not part of the algorithm itself, which is provided in the findPoint function.

const rnd = () => Math.floor(Math.random() * 101);

const distance = (a, b) =>
    a.reduce((acc, x, i) => acc   (x - b[i]) ** 2, 0) ** 0.5;

function findPoint(f) {
    // First guess is always the zero-point
    let guess = [0, 0, 0];
    let dist = f(guess);
    if (dist === 0) return guess; // Extremely lucky!
    // Find the points in the cube that have this distance to [0,0,0]
    let candidates = [];
    const limit = Math.min(100, Math.round(dist));
    for (let x = 0; x <= limit; x  ) {
        const p = [x, limit, 0];
        // Follow circle in X=x plane
        while (p[1] >= 0 && p[2] <= limit) {
            const d = distance(p, guess);
            const diff = d - dist;
            if (Math.abs(diff) < 1e-7) candidates.push([...p]);
            if (diff >= 0) p[1]--;
            else p[2]  ;
        }
    }
    // As long there are multiple candidates, continue with a guess
    while (candidates.length > 1) {
        const candidates2 = [];
        // These guesses are taking the first candidate as guess
        guess = candidates[0];
        dist = f(guess);
        if (dist === 0) return guess; // lucky!
        for (const p of candidates) {
            let d = distance(p, guess);
            let diff = d - dist;
            if (Math.abs(diff) < 1e-7) candidates2.push(p);
        }
        candidates = candidates2;
    }
    return candidates[0]; // Don't call f as we are sure!
}

function blackbox() {
    const secret = [rnd(), rnd(), rnd()];
    console.log("Secret", JSON.stringify(secret));
    let guessCount = 0;
    const f = guess => {
        guessCount  ;
        const dist = distance(secret, guess);
        console.log("Submitted guess "   JSON.stringify(guess)   " is at distance "   dist);
        return dist; 
    };
    const report = (result) => {
        console.log("Number of guesses: "   guessCount);
        console.log("The provided result is "   (distance(secret, result) ? "not" : "")   "correct");
    }
    return {f, report};
}

// Example run
const {f, report} = blackbox();
const result = findPoint(f);
console.log("Algorithm says the secret point is: "   JSON.stringify(result));
report(result);

Each run will generate a new secret point. When running this thousands of times it turns out that there is 1/9 probability that the algorithm needs a third guess. In the other 8/9 cases, the algorithm needs two guesses.

CodePudding user response：

Following method will work for coordinates with positive or negative real values as well.

Let's say you are searching for the coordinates of point P. As the first query point, use origin O. Let the distance to the origin O be |PO|. At this point, you know that P is on the surface of sphere

(P.x)^2   (P.y)^2   (P.z)^2 = |PO|^2  (1)

As the second query point, use Q = (|PO|, 0, 0). Not likely but if you find the distance |PQ| zero, Q is the point you are looking for. Otherwise, you get another sphere equation, and you know that P is on the surface of this sphere as well:

(P.x - |PO|)^2   (P.y)^2   (P.z)^2 = |PQ|^2   (2)

Now, if you subtract (1) from (2), you get

(P.x - |PO|)^2 - (P.x)^2 = |PQ|^2 - |PO|^2  (3)

Since the only unknown in this equation is P.x you can get its value:

P.x = (((-|PQ|^2   |PO|^2) / |PO|)   |PO|)/2)

Following similar steps, you can get P.y with R = (0, |PO|, 0) and P.z with S = (0, 0, |PO|). So, by using four query points O, Q, R, and S you can get the coordinates of P.