Last active
May 20, 2016 18:15
-
-
Save generalzhou/d65b34bf35a76b88e11f7fc88b661073 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
## 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