This kata is inspired by Tower Defense (TD), a subgenre of strategy video games where the goal is to defend a player's territories or possessions by obstructing enemy attackers, usually by placing defensive structures on or along their path of attack.
Objective
It's the future, and hostile aliens are attacking our planet. We've set up a defense system in the planet's outer perimeter. You're tasked with calculating the severity of a breach.
Input
Your function will receive three arguments:
Battle Area Map: An array/list of strings representing an n x n battle area.
        Each string will consist of any of the following characters:
0: entrance point (starting position on alien path)
1: alien path
" "(space character): not alien path
A - Z: turret positions
Turret Stats: An object/dict where keys are upper-case characters from the English alphabet (A - Z) and the values are subarrays in the following format:
[n,m] - where n is the attack range of a turret, and m is its shot frequency per move
Alien Wave Stats: An array of integers representing each individual alien in sequence. Each value is an integer representing the health points of each alien; health points are the number of turret shots required to take down a given alien. Integer zero (0) counts as a gap in sequence.
Output
Return the integer sum of total health points of all aliens that successfully penetrate our defense.
The image above shows the game state for the test example (below) at the 11th move.
The green square in the north-west quadrant represents the starting position of the alien wave, and the red square in the south-east quadrant represents the last position before breaching the defensive perimeter.
The blue circles represent the turret positions and are labeled A,B,C, and D.
The red alien is the first alien in the sequence.
Technical Details
There is only one path and it maintains a width of 1.
Aliens move one square per turn
Turrets only fire toward enemies in range.
        In the image above, the turret labeled A has the value [3,2], meaning it can fire at aliens that occupy any position within 3 squares' length in Euclidean distance (the pink squares). Turret A will fire 2 times per move.
        The turret labeled D with the value [1,3] can fire at targets that enter the square above it and the square to the right of it (the blue shaded squares) at a rate of 3 times per move.
Turret target priority is toward the enemy within shooting range that is furthest along on the path.
        In the image above, turret A will target the red alien because it is the alien furthest along the path that is also within shooting range. This reduces the alien's health from 8 to 6.
        The next alien will die from damage taken from turret B, which reduced its health from 4 to 0.
Turret shooting timing: All turrets with a target will fire their first shot in alphabetical order. The remaining turrets that still have more shots available will fire their next shot in alphabetical order once again. This repeats until there are no more shots to fire. This marks the end of the move.
Matrix size: n x n where 20 >= n >= 7
Alien list max length: 80
Full Test Suite: 10 Fixed Tests, 100 Random Tests
Input will always be valid.
Test Example
```python
battlefield = [
        '0111111',
        '  A  B1',
        ' 111111',
        ' 1     ',
        ' 1C1111',
        ' 111 D1',
        '      1'
]
turrets = {'A':[3,2],'B':[1,4],'C':[2,2],'D':[1,3]}
wave = [30,14,27,21,13,0,15,17,0,18,26]
tower_defense(battlefield,turrets,wave); #10
'''
The aliens that survive are the alien at wave[7] with an ending health of 2
and the alien at wave[8] with an ending health of 8.'''
```
For another Tower Defense-style challenge, check out Plants and Zombies
If you enjoyed this kata, be sure to check out [my other katas](https://www.codewars.com/users/docgunthrop/authored).
from collections import OrderedDict

class TowerDefense:
    def __init__(self, grid, turrets, aliens):
        """ Create dictionary for turrets (using name) and lists with path and aliens """
        self._turrets = OrderedDict()
        self._path = []

        self._n = len(grid)
        grid_str = ''.join(grid)

        # Determine the path and which path positions are covered by the turrets)
        self._determine_turret_positions(turrets, grid_str)
        self._determine_path_and_guarded_positions(grid_str)
        
        # Aliens list is used to hold current alien strength
        self._aliens = aliens
        
    def _determine_turret_positions(self, turrets, grid_str):
        """ Add turrets in sorted order to dictionary """
        for (turret, settings) in sorted(turrets.items()):
            ind = grid_str.find(turret)
            x = ind % self._n
            y = ind // self._n
            # Range**2 is calculated as it is used in self._determine_path_and_guarded_positions
            # guards will hold (x,y) pairs that the turret can reach sorted with the first point furthest along the path
            self._turrets[turret] = {'pos': (x,y), 'range2': settings[0]**2,  'shots': settings[1], 'guards': [] }

    def _determine_path_and_guarded_positions(self, grid_str):
        """ Find all positions of the path and determine which once can be reached by the turrets """
        ind_0 = grid_str.find('0')
        x = ind_0 % self._n
        y = ind_0 // self._n
        self._add_point_to_path_and_guarded_list((x,y))
        next_point = self._get_next_point_on_path(grid_str)
        while next_point:
            self._add_point_to_path_and_guarded_list(next_point)
            next_point = self._get_next_point_on_path(grid_str)
        
    def _add_point_to_path_and_guarded_list(self, point):
        """ Add the point to the path list and to any turrets that can reach it """
        self._path.append(point)
        self._add_to_guarded_list(point)

    def _get_next_point_on_path(self, grid_str):
        """ Based on the last point on the path, get the adjacent path point that is not yet on the path """
        curr_x, curr_y = self._path[-1]
        if curr_x > 0:
            test_x = curr_x - 1
            test_y = curr_y
            ind = test_x + self._n * test_y
            if grid_str[ind] == '1' and not (test_x, test_y) in self._path:
                return (test_x, test_y)
        if curr_x < self._n - 1:
            test_x = curr_x + 1
            test_y = curr_y
            ind = test_x + self._n * test_y
            if grid_str[ind] == '1' and not (test_x, test_y) in self._path:
                return (test_x, test_y)
        if curr_y > 0:
            test_x = curr_x
            test_y = curr_y - 1
            ind = test_x + self._n * test_y
            if grid_str[ind] == '1' and not (test_x, test_y) in self._path:
                return (test_x, test_y)
        if curr_y < self._n - 1:
            test_x = curr_x
            test_y = curr_y + 1
            ind = test_x + self._n * test_y
            if grid_str[ind] == '1' and not (test_x, test_y) in self._path:
                return (test_x, test_y)
        return None

    def _add_to_guarded_list(self, point):
        """ Add point to list of guarded poisitions, if it is within turret range """
        for (turret, settings) in self._turrets.items():
            if (point[0] - settings['pos'][0])**2 + (point[1] - settings['pos'][1])**2 <= settings['range2']:
                # Insert as first item such that last point on path is first on guards
                settings['guards'].insert(0, point)
    
    def aliens_that_pass_the_turrets(self):
        """ Determine the number of aliens that pass the turrets """
        total_turns = len(self._path) + len(self._aliens) 
        for turn in range(1, total_turns + 1):
            # Determine shots remaining by all turrets
            total_remaining = 0
            for turret in self._turrets:
                self._turrets[turret]['remaining'] = self._turrets[turret]['shots']
                total_remaining += self._turrets[turret]['remaining']
            # Get a mapping from alien positions on the grid to index of the strength
            alien_pos_ind = {}
            for it in range(turn):
                if it < len(self._aliens) and turn - 1 - it < len(self._path):
                    alien_pos_ind[self._path[turn - 1 - it]] = it
            # Keep firing until all shots fired or no aliens within range
            while total_remaining > 0:
                for turret in self._turrets:
                    if self._turrets[turret]['remaining'] > 0:
                        # Pick first alien position and fire
                        for pos in self._turrets[turret]['guards']:
                            if pos in alien_pos_ind and self._aliens[alien_pos_ind[pos] ] > 0:
                                total_remaining -= 1
                                self._turrets[turret]['remaining'] -= 1
                                self._aliens[alien_pos_ind[pos] ] -= 1
                                break
                        else:
                            # No alients to hit with turret range
                            total_remaining -= self._turrets[turret]['remaining']
                            self._turrets[turret]['remaining'] = 0
        # Return remaining aliens
        return(sum(self._aliens))
    
    def print_map(self, turn=0):
        """ Print a map of the current turn with path, alien strength, and turrets """
        # Helper dictionary with turret positions
        turret_pos = {}
        for turret, settings in self._turrets.items():
            turret_pos[settings['pos']] = turret

        # Helper dictionary with alien positions in this turn
        alien_pos = {}
        for it in range(turn):
            if it < len(self._aliens) and turn - 1 - it < len(self._path):
                alien_pos[self._path[turn - 1 - it]] = self._aliens[it]

        # Loop over all position and print what is there
        for y in range(self._n):
            for x in range(self._n):
                if (x,y) in alien_pos:
                    print('%02i' %  alien_pos[(x,y)], end=' ')
                elif (x,y) in self._path:
                    print('XX', end=' ')
                elif (x,y) in turret_pos:
                    print(2*turret_pos[(x,y)], end=' ')
                else:
                    print('  ', end=' ')
            print('\n')

def tower_defense(grid,turrets,aliens):
    td = TowerDefense(grid, turrets, aliens)
    return td.aliens_that_pass_the_turrets()

from collections import OrderedDict

class TowerDefense:
    def __init__(self, grid, turrets, aliens):
        """ Create dictionary for turrets (using name) and lists with path and aliens """
        self._turrets = OrderedDict()
        self._path = []

        self._n = len(grid)
        grid_str = ''.join(grid)

        # Determine the path and which path positions are covered by the turrets)
        self._determine_turret_positions(turrets, grid_str)
        self._determine_path_and_guarded_positions(grid_str)
        
        # Aliens list is used to hold current alien strength
        self._aliens = aliens
        
    def _determine_turret_positions(self, turrets, grid_str):
        """ Add turrets in sorted order to dictionary """
        for (turret, settings) in sorted(turrets.items()):
            ind = grid_str.find(turret)
            x = ind % self._n
            y = ind // self._n
            # Range**2 is calculated as it is used in self._determine_path_and_guarded_positions
            # guards will hold (x,y) pairs that the turret can reach sorted with the first point furthest along the path
            self._turrets[turret] = {'pos': (x,y), 'range2': settings[0]**2,  'shots': settings[1], 'guards': [] }

    def _determine_path_and_guarded_positions(self, grid_str):
        """ Find all positions of the path and determine which once can be reached by the turrets """
        ind_0 = grid_str.find('0')
        x = ind_0 % self._n
        y = ind_0 // self._n
        self._add_point_to_path_and_guarded_list((x,y))
        next_point = self._get_next_point_on_path(grid_str)
        while next_point:
            self._add_point_to_path_and_guarded_list(next_point)
            next_point = self._get_next_point_on_path(grid_str)
        
    def _add_point_to_path_and_guarded_list(self, point):
        """ Add the point to the path list and to any turrets that can reach it """
        self._path.append(point)
        self._add_to_guarded_list(point)

    def _get_next_point_on_path(self, grid_str):
        """ Based on the last point on the path, get the adjacent path point that is not yet on the path """
        curr_x, curr_y = self._path[-1]
        if curr_x > 0:
            test_x = curr_x - 1
            test_y = curr_y
            ind = test_x + self._n * test_y
            if grid_str[ind] == '1' and not (test_x, test_y) in self._path:
                return (test_x, test_y)
        if curr_x < self._n - 1:
            test_x = curr_x + 1
            test_y = curr_y
            ind = test_x + self._n * test_y
            if grid_str[ind] == '1' and not (test_x, test_y) in self._path:
                return (test_x, test_y)
        if curr_y > 0:
            test_x = curr_x
            test_y = curr_y - 1
            ind = test_x + self._n * test_y
            if grid_str[ind] == '1' and not (test_x, test_y) in self._path:
                return (test_x, test_y)
        if curr_y < self._n - 1:
            test_x = curr_x
            test_y = curr_y + 1
            ind = test_x + self._n * test_y
            if grid_str[ind] == '1' and not (test_x, test_y) in self._path:
                return (test_x, test_y)
        return None

    def _add_to_guarded_list(self, point):
        """ Add point to list of guarded poisitions, if it is within turret range """
        for (turret, settings) in self._turrets.items():
            if (point[0] - settings['pos'][0])**2 + (point[1] - settings['pos'][1])**2 <= settings['range2']:
                # Insert as first item such that last point on path is first on guards
                settings['guards'].insert(0, point)
    
    def aliens_that_pass_the_turrets(self):
        """ Determine the number of aliens that pass the turrets """
        total_turns = len(self._path) + len(self._aliens) 
        for turn in range(1, total_turns + 1):
            # Determine shots remaining by all turrets
            total_remaining = 0
            for turret in self._turrets:
                self._turrets[turret]['remaining'] = self._turrets[turret]['shots']
                total_remaining += self._turrets[turret]['remaining']
            # Get a mapping from alien positions on the grid to index of the strength
            alien_pos_ind = {}
            for it in range(turn):
                if it < len(self._aliens) and turn - 1 - it < len(self._path):
                    alien_pos_ind[self._path[turn - 1 - it]] = it
            # Keep firing until all shots fired or no aliens within range
            while total_remaining > 0:
                for turret in self._turrets:
                    if self._turrets[turret]['remaining'] > 0:
                        # Pick first alien position and fire
                        for pos in self._turrets[turret]['guards']:
                            if pos in alien_pos_ind and self._aliens[alien_pos_ind[pos] ] > 0:
                                total_remaining -= 1
                                self._turrets[turret]['remaining'] -= 1
                                self._aliens[alien_pos_ind[pos] ] -= 1
                                break
                        else:
                            # No alients to hit with turret range
                            total_remaining -= self._turrets[turret]['remaining']
                            self._turrets[turret]['remaining'] = 0
        # Return remaining aliens
        return(sum(self._aliens))
    
    def print_map(self, turn=0):
        """ Print a map of the current turn with path, alien strength, and turrets """
        # Helper dictionary with turret positions
        turret_pos = {}
        for turret, settings in self._turrets.items():
            turret_pos[settings['pos']] = turret

        # Helper dictionary with alien positions in this turn
        alien_pos = {}
        for it in range(turn):
            if it < len(self._aliens) and turn - 1 - it < len(self._path):
                alien_pos[self._path[turn - 1 - it]] = self._aliens[it]

        # Loop over all position and print what is there
        for y in range(self._n):
            for x in range(self._n):
                if (x,y) in alien_pos:
                    print('%02i' %  alien_pos[(x,y)], end=' ')
                elif (x,y) in self._path:
                    print('XX', end=' ')
                elif (x,y) in turret_pos:
                    print(2*turret_pos[(x,y)], end=' ')
                else:
                    print('  ', end=' ')
            print('\n')

def tower_defense(grid,turrets,aliens):
    td = TowerDefense(grid, turrets, aliens)
    return td.aliens_that_pass_the_turrets()
