Asteroid Collision Logic Problem

Benchmark created on


Test runner

Ready to run.

Testing in
TestOps/sec
Double Loops and Supporting Functions
function asteroidCollision(asteroids) {
  const isPositive = (n) => Math.sign(asteroids[n]) === 1;
  const isNegative = (n) => Math.sign(asteroids[n]) === -1;
  const areSameSign = (x, y) => Math.sign(asteroids[x]) === Math.sign(asteroids[y]);
  const areAbsoluteEquals = (x, y) => Math.abs(asteroids[x]) === Math.abs(asteroids[y]);
  const isAbsoluteLower = (x, y) => Math.abs(asteroids[x]) < Math.abs(asteroids[y]);

  for (let x = 0; x < asteroids.length - 1; x++) {
    if (isNegative(x)) continue;

    for (let y = x + 1; y < asteroids.length; y++) {
      if (areSameSign(x, y)) break;

      if (areAbsoluteEquals(x, y)) {
        asteroids.splice(x, 2);
        if (isPositive(x - 1)) x -= 2;
        else x--;
        break;
      } else if (isAbsoluteLower(x, y)) {
        asteroids.splice(x, 1);
        if (isPositive(x - 1)) x -= 2;
        break;
      } else {
        asteroids.splice(y, 1);
        y--;
      }
    }
  }

  return asteroids;
};

asteroidCollision([5, 10, -5]);
asteroidCollision([8, -8]);
asteroidCollision([10, 2, -5]);
asteroidCollision([-2, -1, 1, 2]);
asteroidCollision([-2, -1, 2, 1]);
asteroidCollision([-2, 1, -2, -1]);
asteroidCollision([-2, 2, -1, -2]);
asteroidCollision([1, -2, -2, -2]);
asteroidCollision([2, -1, 1, -2]);
asteroidCollision([1, 1, -1, -2]);
asteroidCollision([1, -1, 1, -2]);
asteroidCollision([1, -1, -2, 1]);
ready
Double Loops and Direct Comparisons
function asteroidCollision(asteroids) {
  for (let x = 0; x < asteroids.length - 1; x++) {
    if (Math.sign(asteroids[x]) === -1) continue;

    for (let y = x + 1; y < asteroids.length; y++) {
      if (Math.sign(asteroids[x]) === Math.sign(asteroids[y])) break;

      if (Math.abs(asteroids[x]) === Math.abs(asteroids[y])) {
        asteroids.splice(x, 2);
        if (Math.sign(asteroids[x - 1]) === 1) x -= 2;
        else x--;
        break;
      } else if (Math.abs(asteroids[x]) < Math.abs(asteroids[y])) {
        asteroids.splice(x, 1);
        if (Math.sign(asteroids[x - 1]) === 1) x -= 2;
        break;
      } else {
        asteroids.splice(y, 1);
        y--;
      }
    }
  }

  return asteroids;
};

asteroidCollision([5, 10, -5]);
asteroidCollision([8, -8]);
asteroidCollision([10, 2, -5]);
asteroidCollision([-2, -1, 1, 2]);
asteroidCollision([-2, -1, 2, 1]);
asteroidCollision([-2, 1, -2, -1]);
asteroidCollision([-2, 2, -1, -2]);
asteroidCollision([1, -2, -2, -2]);
asteroidCollision([2, -1, 1, -2]);
asteroidCollision([1, 1, -1, -2]);
asteroidCollision([1, -1, 1, -2]);
asteroidCollision([1, -1, -2, 1]);
ready
Stack Approach
function asteroidCollision(asteroids) {
  const stack = [];

  for (let i = 0; i < asteroids.length; i++) {
    let shouldRemain = true;

    while (
      stack.length > 0 &&
      stack[stack.length - 1] > 0 &&
      asteroids[i] < 0
    ) {
      if (Math.abs(stack[stack.length - 1]) < Math.abs(asteroids[i])) {
        // If the top asteroid in the stack is smaller, then it will explode.
        // Hence pop it from the stack, also continue with the next asteroid in the stack.
        stack.pop();
        continue;
      } else if (Math.abs(stack[stack.length - 1]) === Math.abs(asteroids[i])) {
        // If both asteroids have the same size, then both asteroids will explode.
        // Pop the asteroid from the stack; also, we won't push the current asteroid to the stack.
        stack.pop();
      }

      // If we reach here, the current asteroid will be destroyed.
      // Hence, we should not add it to the stack.
      shouldRemain = false;
      break;
    }

    if (shouldRemain) stack.push(asteroids[i]);
  }

  return stack;
}

asteroidCollision([5, 10, -5]);
asteroidCollision([8, -8]);
asteroidCollision([10, 2, -5]);
asteroidCollision([-2, -1, 1, 2]);
asteroidCollision([-2, -1, 2, 1]);
asteroidCollision([-2, 1, -2, -1]);
asteroidCollision([-2, 2, -1, -2]);
asteroidCollision([1, -2, -2, -2]);
asteroidCollision([2, -1, 1, -2]);
asteroidCollision([1, 1, -1, -2]);
asteroidCollision([1, -1, 1, -2]);
asteroidCollision([1, -1, -2, 1]);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.