Last active
February 2, 2018 23:33
-
-
Save avionbg/a293f5836ae8f9031dfe9d3212fb73e0 to your computer and use it in GitHub Desktop.
Python script to calculate chain reactions
This file contains 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
import os.path | |
def within_blast_radius(x1, y1, blast_radius, x2, y2): | |
# Note that this counts points on the edge of the radius which is incorrect | |
# Proper way would be to exclude them as they are not in the radius (replace <= with <) | |
return ((x1 - x2) ** 2 + (y1 - y2) ** 2) <= (blast_radius ** 2) | |
def explode_mine(mines, mine, exploded): | |
"""Recursive explosion calculation | |
Args: | |
mines: List of all mines (their data). | |
mine: Mine for which we are detecting number of explosions. | |
exploded: List containing already exploded mines (to prevent same mine being added more than once - infinite loops) | |
Returns: | |
Number of exploded mines caused by this mine detonation | |
""" | |
destroyed = 0 | |
# Iterate trough all mines, skip currently exploding one and the mines that already exploded | |
for rest in mines: | |
if rest != mine and not rest in exploded: | |
if within_blast_radius(*mine, x2=rest[0], y2=rest[1]): | |
exploded.append(rest) | |
destroyed += 1 | |
destroyed += explode_mine(mines, rest, exploded) | |
return destroyed | |
if __name__ == '__main__': | |
from sys import argv | |
if len(argv) < 2: | |
print 'Please, provide path to mines file' | |
else: | |
# Verify that mines file exists | |
if os.path.isfile(argv[1]): | |
# Read mines file and parse it's contents into a list of integers | |
mines = [map(int, line.strip().split()) for line in open(argv[1], 'r')] | |
result = [] | |
# Detect number of explosions for all mines and store result | |
for mine in mines: | |
result.append(explode_mine(mines, mine, [mine])) | |
# Get max number in the list of explosions | |
maxExploded = max(result) | |
# Get indexes of maxExploded value (taking in consideration that we can have more than one index) | |
indexesOfMax = [i for i, j in enumerate(result) if j == maxExploded] | |
# Pretty print the result | |
print ('Max exploded mines: %s \nMines with maximum explosion: %s' % | |
(maxExploded, ','.join(map(str, [x+1 for x in indexesOfMax])))) | |
else: | |
print ('File %s doesn\'t exists' % argv[1]) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment