Asteroid Collision Logic Problem (v2)

Revision 2 of this 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 using For and Math
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
Stack Approach Fine-Tuned
function asteroidCollision(asteroids) {
  let i = 0;
  const stack = []
  while (i < asteroids.length) {
    if (asteroids[i] >= 0 || !stack.length || stack[stack.length - 1] < 0) {
      // If the current asteroid is positive or if the stack is empty or if the top of the stack is negative, push the asteroid onto the stack.
      stack.push(asteroids[i++]);
    } else if (asteroids[i] + stack[stack.length - 1] < 0) {
      // Otherwise, the top of the stack is positive and the current asteroid is negative. If the absolute value of the current asteroid is greater than the top of the stack, pop the stack.
      stack.pop();
    } else if (asteroids[i] + stack[stack.length - 1] === 0) {
      // Otherwise, if the absolute value of the current asteroid is the same as the top of the stack, pop the stack and discard both asteroids.
      stack.pop();
      i++;
    } else {
      // Otherwise, if the absolute value of the current asteroid is less than the top of the stack, discard the current asteroid.
      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.