asteroids_fast.rb

## Asteroids

# first create an array that represents the relative positions of the asteroids
# once we do this, we can ignore the actual distance from the space station as it's not relevant

# example:

#              0   |   .   |  o  | space station
# -----------------|-------|-----
# mass:        3   |   1   |  2
# direction:   1   |   1   |  -1
# distance:    3   |   2   |  1
#
# collisions: 1

require 'benchmark'

def space_station_collisions(asteroids)
  # create an array of asteroids, where the end of the array is asteroid closest to the space station
  sorted_asteroid_list = asteroids.sort_by { |ast| ast.distance }.reverse

  remaining_forward_asteroids = calculate_all_collisions(sorted_asteroid_list)

  return remaining_forward_asteroids.size
end

def calculate_all_collisions(asteroids)
  forward_ast_stack = []

  asteroids.each do |ast|
    if ast.direction == 1
      forward_ast_stack.push(ast)
    else
      # pop off forward moving asteroids and run the collisions
      while !forward_ast_stack.empty? do
        forward_ast = forward_ast_stack.pop

        if forward_ast.mass > ast.mass
          forward_ast_stack.push(forward_ast)
          break
        end
      end
    end
  end
  forward_ast_stack
end

class Asteroid
  attr_reader :mass, :direction, :distance
  def initialize(mass, direction, distance)
    @mass = mass
    @direction = direction
    @distance = distance
  end
end

def test_data_1
  # tests that asteroid with mass 2 destroys mass 1 before being destroyed by mass 3
  [
    Asteroid.new(3, 1, 3),
    Asteroid.new(1, 1, 2),
    Asteroid.new(2, -1, 1),
  ]
end


def test_data_2
  # tests that asteroid with mass 4 destroys mass 3 before mass 3 can destroy 2
  [
    Asteroid.new(2, 1, 5),
    Asteroid.new(1, -1, 4),
    Asteroid.new(4, 1, 3),
    Asteroid.new(3, -1, 1),
  ]
end

def large_test_data
  data = []
  100.times { data += test_data_2 }
  data
end

def run_tests
  puts "Running test 1 with 3 asteroids:"
  test_result = space_station_collisions(test_data_1)
  puts "Passed: #{test_result == 1}"

  puts "Running test 2 with 4 asteroids:"
  test_result = space_station_collisions(test_data_2)
  puts "Passed: #{test_result == 2}"
end

def run_benchmarking
  Benchmark.measure { 1000.times { space_station_collisions(large_test_data) } }
end

run_tests

# Running test 1 with 3 asteroids:
# Passed: true
# Running test 2 with 4 asteroids:
# Passed: true

puts run_benchmarking

# time: 0.360177 seconds