Skip to content

Instantly share code, notes, and snippets.

@generalzhou
Last active May 20, 2016 18:15
Show Gist options
  • Save generalzhou/d65b34bf35a76b88e11f7fc88b661073 to your computer and use it in GitHub Desktop.
Save generalzhou/d65b34bf35a76b88e11f7fc88b661073 to your computer and use it in GitHub Desktop.
## 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
# this example maps to this array (only values are direction):
# [1, 1, -1] (end of array is closest to space station)
# we can simply iterate over the array until to detect collisions, until there are no more collisions
# this always means we do not need to calculate the min distance to find asteroids next to each other
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_asteroids = calculate_all_collisions(sorted_asteroid_list)
return remaining_asteroids.count { |ast| ast.direction == 1}
end
def calculate_all_collisions(asteroids)
current_asteroids = asteroids
loop do
new_asteroids = calculate_next_collisions(current_asteroids)
if new_asteroids.size == current_asteroids.size
# this is done if there are no more collisions
return new_asteroids
else
current_asteroids = new_asteroids
end
end
end
def calculate_next_collisions(asteroids)
asteroids.each_with_index do |current_ast, i|
next if i == 0 # we want to check for collisions between this asteroid and the previous one
next if current_ast.direction == 1 # no collision between this and previous asteroid if this is going forward
previous_ast = asteroids[i-1]
next if previous_ast == nil # if it was destroyed in a previous collision
next if previous_ast.direction == -1 # skip if going in the same direction
if current_ast.mass > previous_ast.mass
# previous asteroid is destroyed
asteroids[i - 1] = nil
else
# current asteroid is destroyed
asteroids[i] = nil
end
end
return asteroids.compact # remove nils
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
run_benchmarking
# time: 4.630726 seconds
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment