generalzhou · May 20, 2016 18:15 · May 20, 2016 · May 20, 2016 · May 20, 2016
diff --git a/asteroids.rb b/asteroids.rb
@@ -19,6 +19,7 @@
 # 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
@@ -40,7 +41,7 @@ def calculate_all_collisions(asteroids)
     else
       current_asteroids = new_asteroids
     end
-  while
+  end
 end
 
 def calculate_next_collisions(asteroids)
@@ -74,7 +75,8 @@ def initialize(mass, direction, distance)
 end
 
 
-# Tests:
+
+
 def test_data_1
   # tests that asteroid with mass 2 destroys mass 1 before being destroyed by mass 3
   [
@@ -94,6 +96,12 @@ def test_data_2
   ]
 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)
@@ -104,5 +112,19 @@ def run_tests
   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
 
-run_tests
+# time: 4.630726 seconds
diff --git a/asteroids.rb b/asteroids.rb
@@ -19,36 +19,6 @@
 # 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
 
-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 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 space_station_collisions(asteroids)
   # create an array of asteroids, where the end of the array is asteroid closest to the space station
@@ -103,4 +73,36 @@ def initialize(mass, direction, distance)
   end
 end
 
+
+# Tests:
+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 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
+
+
 run_tests
diff --git a/asteroids.rb b/asteroids.rb
@@ -0,0 +1,106 @@
+## 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
+
+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 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 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
+  while
+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
+
+run_tests