Codingame Solution: Apple tree

Solution

This problem can easily be made computational expensive, with a high polynomial or even exponential runtime. The best algorithm I was able to come up with lives in \(O(n^2)\) and goes like this: We push all apples to a list for simple lookup by index and add all indices not being the initial falling apple to a maybe list \(M\) and the initial index to a working set \(W\).

For each \(w\in W\) we hittest any \(m\in M\). Every hit allows us to remove the element from the maybe list and will be added to the working list. After all elements have been processed recursively in the tree structure, we can stop and the elements in the maybe set are now definitely the apples that will remain. This algorithm can be implemented like this:

var inputs = readline().split(' ');
var N = +inputs[0];
var I = +inputs[1];

var apples = [];

var M = new Set; // maybe
var W = new Set; // working set

for (var i = 0; i < N; i++) {
  var inputs = readline().split(' ').map(Number);

  apples.push({
    x: inputs[0],
    y: inputs[1],
    z: inputs[2],
    r: inputs[3]
  });

  if (I !== i) M.add(i);
  else         W.add(i);
}

W.forEach(w => {
  M.forEach(m => {
    if (hits(apples[w], apples[m])) {
      W.add(m);
      M.delete(m);
    }
  });
});

print(M.size);

The remaining problem is the hittest when an apple is falling vertically to the ground. When we look at the x-y-plane from the top, we only see two dimensional circles. So, the distance from the falling apple to another apple must be less than the sum of their radii to be interesting at all. In 3D this can be seen as tubes that intersect. But there is more, since we work in 3D, we also need to take the z-axis into account. We know the direction vector \(\mathbf{d}=[0, 0, -1]^T\) and the vector \(\mathbf{c}\) between the center points of apples. The dot-product now states that \(\mathbf{c}\cdot\mathbf{d} = |\mathbf{c}|\cdot|\mathbf{d}|\cos\theta\) from which follows that the angle \(\theta\) is \(\cos^{-1}\left(-\frac{\Delta z}{|\mathbf{c}|}\right)\), where \(\Delta z\) is the height difference of the apples. Since we require the angle \(\theta\) to be \(<90^{\circ}\) it follows that \(\Delta z < 0\), which makes sense. It just says that the z-coordinate of the apple to be tested must be below the falling apple to be affected for a straight fall. When implemented we get:

function hits(a, b) {

  var dx = b.x - a.x;
  var dy = b.y - a.y;
  var pr = b.r + a.r;
    
  // touch horizontally?
  if ((dx * dx + dy * dy) > (pr * pr)) {
    return false;
  }
  return b.z < a.z;
}