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).

Difficulty: interview

Starter code:

def __init__(self):
	

Solutions:
import collections

class Tower:
    def __init__(self):
        indicesOfAlienPath = []
        shots = 0

class GameStats:
    def __init__(self):
        alienPath = collections.deque()
        towers = []
        waves = collections.deque()

DirEOL = 0
DirLeft = 1
DirRight = 2
DirUp = 3
DirDown = 4


def tower_defense(grid, turrets, aliens):
    game = FromBattlefield(grid, turrets, aliens)
    numSurvivedAliens = 0
    while AnalysisIsRunning(game.alienPath, game.remainingWaves):
        game = PrepareRound(game)
        game.alienPath = KillAliens(game.alienPath, game.towers)
        numSurvivedAliens = numSurvivedAliens + CountAliensLeavingPath(game.alienPath)
    return numSurvivedAliens

def FromBattlefield(grid, turrets, aliens):
    coords = DeterminePathCoordinates(grid)
    game = GameStats()
    game.alienPath = collections.deque([0 for a in range(len(coords))])
    game.towers = CreateTowers(grid, turrets, coords)
    game.remainingWaves = collections.deque(aliens)
    return game

def DeterminePathCoordinates(grid):
    result = []
    coord = GetCoordFor(grid, '0')
    result.append(coord)
    dir = LookForPath(grid, coord, DirEOL)
    while dir != DirEOL:
        coord = GetCoordinate(coord, dir)
        result.append(coord)
        dir = LookForPath(grid, coord, dir)
    return result

def GetCoordFor(grid, id):
    n = len(grid)
    for row in range(n):
        for col in range(n):
            if grid[row][col] == id:
                return (col, row)
    return (0,0)

def LookForPath(grid, c, dir):
    if IsOnPath(grid, (c[0]+1, c[1])) and dir != DirLeft:
        return DirRight
    elif IsOnPath(grid, (c[0]-1, c[1])) and dir != DirRight:
        return DirLeft
    elif IsOnPath(grid, (c[0], c[1]-1)) and dir != DirDown:
        return DirUp
    elif IsOnPath(grid, (c[0], c[1]+1)) and dir != DirUp:
        return DirDown
    return DirEOL

def GetCoordinate(orig, dir):
    if dir == DirLeft:
        return (orig[0]-1, orig[1])
    elif dir == DirRight:
        return (orig[0]+1, orig[1])
    elif dir == DirUp:
        return (orig[0], orig[1]-1)
    elif dir == DirDown:
        return (orig[0], orig[1]+1)
    return orig

def IsOnPath(grid, c):
    n = len(grid)
    return c[1] < n and c[0] < n and c[1] >= 0 and c[0] >= 0 and (grid[c[1]][c[0]] == '1' or grid[c[1]][c[0]] == '0')

def CreateTowers(grid, turrets, alienPathCoords):
    towers = []
    for name in sorted(turrets.keys()):
        towerCoords = GetCoordFor(grid, name)
        pathIdxInRange = DetermineIndicesOfAlienPathInRange(alienPathCoords, towerCoords, turrets[name][0])
        towers.append((pathIdxInRange, turrets[name][1]))
    return towers

def DetermineIndicesOfAlienPathInRange(alienPathCoords, towerCoords, dist):
    result = []
    sqrDist = dist*dist
    startY = max(0, towerCoords[1] - dist)
    startX = max(0, towerCoords[0] - dist)
    for y in range(startY, towerCoords[1] + dist+1):
        for x in range(startX, towerCoords[0] + dist+1):
            cur = (x, y)
            if cur in alienPathCoords and SqrDistance(cur, towerCoords) <= sqrDist:
                result.append(alienPathCoords.index(cur))
    return sorted(result)

def SqrDistance(left, right):
    y = left[1] - right[1]
    x = left[0] - right[0]
    return x*x + y*y


def AnalysisIsRunning(alienPath, waves):
    return len(waves) > 0 or any(alienPath)

def PrepareRound(game):
    game.alienPath.pop()
    if len(game.remainingWaves) > 0:
        game.alienPath.appendleft(game.remainingWaves.popleft())
    else:
        game.alienPath.appendleft(0)
    return game

def KillAliens(alienPath, towers):
    activeTowers = towers.copy()
    while CanShootAgain(activeTowers):
        alienPath, activeTowers = ShootWithTowers(alienPath, activeTowers)
        activeTowers = FilterInactiveTowers(alienPath, activeTowers)
    return alienPath

def CanShootAgain(towers):
    return len(towers) > 0

def ShootWithTowers(alienPath, towers):
    towersShot = []
    for t in towers:
        alienPath, t = ShootAliensInFormostPosition(alienPath, t)
        towersShot.append(t)
    return alienPath, towersShot

def ShootAliensInFormostPosition(alienPath, tower):
    for idx in reversed(tower[0]):
        if alienPath[idx] > 0:
            shots = tower[1] - 1
            alienPath[idx] = alienPath[idx] - 1
            return alienPath, (tower[0], shots)
    return alienPath, tower

def FilterInactiveTowers(alienPath, towers):
    result = []
    for t in towers:
        if t[1] > 0 and AreAliensInRange(alienPath, t[0]):
            result.append(t)
    return result

def AreAliensInRange(alienPath, towerRange):
    for idx in towerRange:
        if alienPath[idx] > 0:
           return True
    return False

def CountAliensLeavingPath(alienPath):
    return alienPath[-1]

import collections

class Tower:
    def __init__(self):
        indicesOfAlienPath = []
        shots = 0

class GameStats:
    def __init__(self):
        alienPath = collections.deque()
        towers = []
        waves = collections.deque()

DirEOL = 0
DirLeft = 1
DirRight = 2
DirUp = 3
DirDown = 4


def tower_defense(grid, turrets, aliens):
    print(grid)
    print(turrets)
    print(aliens)
    game = FromBattlefield(grid, turrets, aliens)
    numSurvivedAliens = 0
    while AnalysisIsRunning(game.alienPath, game.remainingWaves):
        game = PrepareRound(game)
        game.alienPath = KillAliens(game.alienPath, game.towers)
        numSurvivedAliens = numSurvivedAliens + CountAliensLeavingPath(game.alienPath)
    return numSurvivedAliens

def FromBattlefield(grid, turrets, aliens):
    coords = DeterminePathCoordinates(grid)
    game = GameStats()
    game.alienPath = collections.deque([0 for a in range(len(coords))])
    game.towers = CreateTowers(grid, turrets, coords)
    game.remainingWaves = collections.deque(aliens)
    return game

def DeterminePathCoordinates(grid):
    result = []
    coord = GetCoordFor(grid, '0')
    result.append(coord)
    dir = LookForPath(grid, coord, DirEOL)
    while dir != DirEOL:
        coord = GetCoordinate(coord, dir)
        result.append(coord)
        dir = LookForPath(grid, coord, dir)
    return result

def GetCoordFor(grid, id):
    n = len(grid)
    for row in range(n):
        for col in range(n):
            if grid[row][col] == id:
                return (col, row)
    return (0,0)

def LookForPath(grid, c, dir):
    if IsOnPath(grid, (c[0]+1, c[1])) and dir != DirLeft:
        return DirRight
    elif IsOnPath(grid, (c[0]-1, c[1])) and dir != DirRight:
        return DirLeft
    elif IsOnPath(grid, (c[0], c[1]-1)) and dir != DirDown:
        return DirUp
    elif IsOnPath(grid, (c[0], c[1]+1)) and dir != DirUp:
        return DirDown
    return DirEOL

def GetCoordinate(orig, dir):
    if dir == DirLeft:
        return (orig[0]-1, orig[1])
    elif dir == DirRight:
        return (orig[0]+1, orig[1])
    elif dir == DirUp:
        return (orig[0], orig[1]-1)
    elif dir == DirDown:
        return (orig[0], orig[1]+1)
    return orig

def IsOnPath(grid, c):
    n = len(grid)
    return c[1] < n and c[0] < n and c[1] >= 0 and c[0] >= 0 and (grid[c[1]][c[0]] == '1' or grid[c[1]][c[0]] == '0')

def CreateTowers(grid, turrets, alienPathCoords):
    towers = []
    for name in sorted(turrets.keys()):
        towerCoords = GetCoordFor(grid, name)
        pathIdxInRange = DetermineIndicesOfAlienPathInRange(alienPathCoords, towerCoords, turrets[name][0])
        towers.append((pathIdxInRange, turrets[name][1]))
    return towers

def DetermineIndicesOfAlienPathInRange(alienPathCoords, towerCoords, dist):
    result = []
    sqrDist = dist*dist
    startY = max(0, towerCoords[1] - dist)
    startX = max(0, towerCoords[0] - dist)
    for y in range(startY, towerCoords[1] + dist+1):
        for x in range(startX, towerCoords[0] + dist+1):
            cur = (x, y)
            if cur in alienPathCoords and SqrDistance(cur, towerCoords) <= sqrDist:
                result.append(alienPathCoords.index(cur))
    return sorted(result)

def SqrDistance(left, right):
    y = left[1] - right[1]
    x = left[0] - right[0]
    return x*x + y*y


def AnalysisIsRunning(alienPath, waves):
    return len(waves) > 0 or any(alienPath)

def PrepareRound(game):
    game.alienPath.pop()
    if len(game.remainingWaves) > 0:
        game.alienPath.appendleft(game.remainingWaves.popleft())
    else:
        game.alienPath.appendleft(0)
    return game

def KillAliens(alienPath, towers):
    activeTowers = FilterInactiveTowers(alienPath, towers.copy())
    while CanShootAgain(activeTowers):
        alienPath, activeTowers = ShootWithTowers(alienPath, activeTowers)
        activeTowers = FilterInactiveTowers(alienPath, activeTowers)
    return alienPath

def CanShootAgain(towers):
    return len(towers) > 0

def ShootWithTowers(alienPath, towers):
    towersShot = []
    for t in towers:
        alienPath, t = ShootAliensInFormostPosition(alienPath, t)
        towersShot.append(t)
    return alienPath, towersShot

def ShootAliensInFormostPosition(alienPath, tower):
    for idx in reversed(tower[0]):
        if alienPath[idx] > 0:
            shots = tower[1] - 1
            alienPath[idx] = alienPath[idx] - 1
            return alienPath, (tower[0], shots)
    return alienPath, tower

def FilterInactiveTowers(alienPath, towers):
    result = []
    for t in towers:
        if t[1] > 0 and AreAliensInRange(alienPath, t[0]):
            result.append(t)
    return result

def AreAliensInRange(alienPath, towerRange):
    for idx in towerRange:
        if alienPath[idx] > 0:
           return True
    return False

def CountAliensLeavingPath(alienPath):
    return alienPath[-1]

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()


class Turret:
    def __init__(self, tid, r, c, size, info):
        self.tid = tid
        self.attack = info[1]
        self.targets = set()
        atkRange = info[0]
        for dr in range(-atkRange, atkRange + 1):
            for dc in range(-atkRange, atkRange + 1):
                if dr == 0 and dc == 0:
                    continue
                ra, ca = r + dr, c + dc
                if not(0 <= ra < size and 0 <= ca < size):
                    continue
                if dr * dr + dc * dc <= atkRange * atkRange:
                    self.targets.add((ra, ca))

class Alien:
    def __init__(self, pathIdx, pos, hp):
        self.pathIdx = pathIdx
        self.pos = pos
        self.hp = hp

def tower_defense(grid, _turrets, _wave):
    answer = 0
    size = len(grid)
    lWave = len(_wave)
    wave = _wave[:]
    ones = set()
    turrets, aliens = [], []
    for r, row in enumerate(grid):
        for c, square in enumerate(row):
            if square == "1":
                ones.add((r, c))
            elif square.isalpha():
                turrets.append(Turret(square, r, c, size, _turrets[square]))
            elif square == "0":
                start = (r, c)
    for turret in turrets:
        turret.targets = turret.targets & (ones | {start})
    turrets.sort(key = lambda t: t.tid)
    path = [start]
    r, c = start
    while ones:
        for r1, c1 in ones:
            if abs(r1 - r) + abs(c1 - c) == 1:
                path.append((r1, c1))
                ones.discard((r1, c1))
                r, c = r1, c1
                break
    lPath = len(path)
    time = -1
    while time < lWave or aliens:
        time += 1
        for i in range(len(aliens) - 1, -1, -1):
            alien = aliens[i]
            if alien.hp <= 0:
                del aliens[i]
                continue
            alien.pathIdx += 1
            if alien.pathIdx == lPath:
                answer += alien.hp
                del aliens[i]
                continue
            alien.pos = path[alien.pathIdx]
        if time < lWave:
            hp = wave[time]
            if hp > 0:
                aliens.append(Alien(0, path[0], hp))
        for turret in turrets:
            turret.shots = turret.attack
        shot = True
        while shot:
            shot = False
            for turret in turrets:
                if turret.shots > 0:
                    for alien in aliens:
                        if alien.hp <= 0:
                            continue
                        if alien.pos not in turret.targets:
                            continue
                        alien.hp -= 1
                        turret.shots -= 1
                        shot = True
                        break
    return answer

import math
from collections import deque

class Alien:
    def __init__(self, health, trail_length):
        self.health = health
        self.trail_length = trail_length
        self.is_dummy = (health == 0)
        self.position = None

    def move(self):
        self.position += 1

    def place_on_board(self):
        self.position = 0

    def damage(self):
        self.health -= 1

    def on_map(self):
        return self.position < self.trail_length


class Turret:
    def __init__(self, loc, range, shots, name, trail):
        self.loc = loc
        self.range = range
        self.max_shots = shots
        self.name = name
        self.trail = trail
        self.current_shots = self.max_shots
        self.nothing_in_range = False
        self.in_range_list = deque()

        # Find all the spots in the trail, find which ones are in range
        for i, slot in enumerate(self.trail):
            if self.calc_dist(slot) <= self.range:
                self.in_range_list.appendleft(i)

    def reset_shots(self):
        self.nothing_in_range = False
        self.current_shots = self.max_shots

    def calc_dist(self, target):
        return math.sqrt(math.pow(target[0] - self.loc[0], 2) +
                         math.pow(target[1] - self.loc[1], 2))

    def shoot_nearest_alien(self, aliens):
        self.nothing_in_range = True

        if self.current_shots <= 0:
            return

        for slot in self.in_range_list:
            if slot < len(aliens):
                alien = aliens[slot]
                if alien.health > 0:
                    self.current_shots -= 1
                    alien.damage()
                    self.nothing_in_range = False
                    break


def gen_path(data):
    # Convert the raw string map to a mutable form so that we
    # can modify it later (to mark visited cells along the path)
    map = []
    for row in data:
        map.append(list(row))
    rows = len(map)
    cols = len(map[0])

    # Iterate through all the points and look for the unique
    # start of the trail (0) and while we're at it, find the
    # turrets (capital letters)
    start = None
    turrets = {}
    for y in range(len(map)):
        for x in range(len(map[0])):
            if map[y][x] == '0':
                start = (x, y)
            elif map[y][x].isupper():
                turrets[map[y][x]] = (x, y)

    # Now that we have the start, iterate through the map to
    # find the trail
    trail = []

    found_end = False
    next = start
    while not found_end:
        # South
        if next[1] + 1 < rows and map[next[1] + 1][next[0]] == "1":
            map[next[1] + 1][next[0]] = '0'  # mark as visited
            trail.append(next)
            next = (next[0], next[1] + 1)
        # North
        elif next[1] - 1 >= 0 and map[next[1] - 1][next[0]] == "1":
            map[next[1] - 1][next[0]] = '0'  # mark as visited
            trail.append(next)
            next = (next[0], next[1] - 1)
        # East
        elif next[0] + 1 < cols and map[next[1]][next[0] + 1] == "1":
            map[next[1]][next[0] + 1] = '0'  # mark as visited
            trail.append(next)
            next = (next[0] + 1, next[1])
        # West
        elif next[0] - 1 >= 0 and map[next[1]][next[0] - 1] == "1":
            map[next[1]][next[0] - 1] = '0'  # mark as visited
            trail.append(next)
            next = (next[0] - 1, next[1])
        else:
            trail.append(next)
            found_end = True
    return trail, turrets


def game_logic(turret_data, turret_locs, alien_data, trail):
    # Create an array of turret objects, combining the location information
    # and the range/shots information
    turrets = []
    for letter in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
        if letter in turret_locs and letter in turret_data:
            turrets.append(Turret(turret_locs[letter],
                                  turret_data[letter][0],
                                  turret_data[letter][1],
                                  letter,
                                  trail))

    # Main loop variables
    aliens = deque()
    trail_length = len(trail)
    final_health = 0
    game_length = len(alien_data) + len(trail)
    round = 0

    # Perform the game logic here
    while round < game_length:  # This is the main tick loop of the game
        round += 1

        # Move the aliens
        if len(alien_data) > 0:
            aliens.appendleft(Alien(alien_data.pop(0), len(trail)))
        else:
            # Push dummies back after all the real aliens are used
            aliens.appendleft(Alien(0, len(trail)))

        # Check the right side of the list for aliens that fall off the map
        if len(aliens) > trail_length:
            removed_alien = aliens.pop()
            if removed_alien.health > 0:
                final_health += removed_alien.health

        # Reset all the turrets back to full power
        for turret in turrets:
            turret.reset_shots()

        # Iterate through all turrets
        turrets_done = False
        while not turrets_done:
            for t in turrets:
                if t.current_shots > 0:
                    t.shoot_nearest_alien(aliens)

            # Done condition: all turrets empty or
            # Have no enemies in range
            turrets_done = True
            for t in turrets:
                if t.current_shots > 0 and not t.nothing_in_range:
                    turrets_done = False
    return final_health

def tower_defense(grid,turrets,aliens):
    trail, turret_locs = gen_path(grid)
    total_health = game_logic(turrets, turret_locs, aliens, trail)
    return total_health