avionbg · February 5, 2018 22:57 · Feb 5, 2018 · Feb 5, 2018
diff --git a/mine_exploder_performance_test.py b/mine_exploder_performance_test.py
@@ -4,7 +4,7 @@
 
 NUMBER_OF_MINES = 10 ** 5
 # Keep this low to prevent RuntimeError: maximum recursion depth exceeded
-# (we can increase it but it's ok also to avoid it just for the test)
+# (we can increase recursion depth, but it's ok also to avoid it just for the test)
 MAX_BLAST_RADIUS = 200
 MAX_COORDINATE_XY = 700000
 
@@ -95,5 +95,8 @@ def run():
   calculateChainReaction(cloned)
 
 if __name__ == '__main__':
-  print timeit.timeit(run, number=1)
-  print timeit.timeit(runOptimized, number=1)
+  res = timeit.timeit(run, number=1)
+  print "Time taken:", res
+  res = timeit.timeit(runOptimized, number=1)
+  print "Time taken:", res
+
diff --git a/mine_exploder_performance_test.py b/mine_exploder_performance_test.py
@@ -0,0 +1,99 @@
+import numpy as np
+import timeit
+from collections import deque
+
+NUMBER_OF_MINES = 10 ** 5
+# Keep this low to prevent RuntimeError: maximum recursion depth exceeded
+# (we can increase it but it's ok also to avoid it just for the test)
+MAX_BLAST_RADIUS = 200
+MAX_COORDINATE_XY = 700000
+
+def generateMines():
+  # Generate array of coordinates (x, y)
+  coordinates = np.random.randint(MAX_COORDINATE_XY, size=(NUMBER_OF_MINES,2))
+  # Generate array of random blasts
+  radiuses = np.random.randint(MAX_BLAST_RADIUS, size=NUMBER_OF_MINES)
+  # Now insert blast to each coordinate array and convert numpy list to simple one and return
+  return np.insert(coordinates, 2, radiuses, 1).tolist()
+
+mines = generateMines()
+
+def within_blast_radius(x1, y1, blast_radius, x2, y2):
+  return ((x1 - x2) ** 2 + (y1 - y2) ** 2) <= (blast_radius ** 2)
+
+
+#### NORMAL CODE ####
+def explode_mine(mines, mine, exploded):
+  destroyed = 0
+  for rest in mines:
+    if rest != mine and not rest in exploded:
+      if within_blast_radius(mine[0], mine[1], mine[2], rest[0], rest[1]):
+        exploded.append(rest)
+        destroyed += 1
+        destroyed += explode_mine(mines, rest, exploded)
+  return destroyed
+
+def calculateChainReaction(mines):
+  result = []
+  for mine in mines:
+    result.append(explode_mine(mines, mine, [mine]) + 1)
+  maxExploded = max(result)
+  indexesOfMax = [i for i, j in enumerate(result) if j == maxExploded]
+  print ('Max exploded mines: %s \nMines with maximum explosion: %s' %
+    (maxExploded, ','.join(map(str, [x+1 for x in indexesOfMax]))))
+
+
+#### OPTIMIZED CODE ####
+def collect(token, tree):
+    "returns a list of every mine in radius"
+    visited = set()
+    child_list = []
+    to_crawl = deque([token])
+    while to_crawl:
+        current = to_crawl.popleft()
+        if current in visited:
+            continue
+        visited.add(current)
+        child_list.append(current)
+        node_children = tree[current]
+        to_crawl.extend(node_children)
+    return child_list
+
+def calculateOptimized(mines):
+  # First we detect mines in radius of each mine and store them as dict of indexes
+  explosionMap = {}
+  for idx, mine in enumerate(mines):
+    explosionMap[idx] = []
+    for cidx, compareMine in enumerate(mines):
+      if compareMine != mine:
+        # First we do the simple test without expencive calculation (is the point in a square)
+        if mine[0] + mine[2] > compareMine[0] and mine[1] + mine[2] > compareMine[1]:
+          # Now we test it more precisely
+          if within_blast_radius(mine[0], mine[1], mine[2], compareMine[0], compareMine[1]):
+            explosionMap[idx].append(cidx)
+
+  result = []
+  # Now that we have all calculations done, we can collect recursive explosions by iterating trough the indexes
+  for idx in explosionMap:
+    bombs = collect(idx, explosionMap)
+    result.append(len(bombs))
+  maxExploded = max(result)
+  indexesOfMax = [i for i, j in enumerate(result) if j == maxExploded]
+  print ('Max exploded mines: %s \nMines with maximum explosion: %s' %
+    (maxExploded, ','.join(map(str, [x+1 for x in indexesOfMax]))))
+
+#### RUNNERS ####
+def runOptimized():
+  # Cloning the list in order to have exact starting point for both algorithms
+  cloned = np.copy(mines).tolist()
+  cloned = sorted(cloned, key=lambda x: x[2])
+  calculateOptimized(cloned)
+
+def run():
+  cloned = np.copy(mines).tolist()
+  cloned = sorted(cloned, key=lambda x: x[2])
+  calculateChainReaction(cloned)
+
+if __name__ == '__main__':
+  print timeit.timeit(run, number=1)
+  print timeit.timeit(runOptimized, number=1)