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

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Game theory

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]


from collections import OrderedDict

class TowerDefense:

	def __init__(self, grid, turrets, aliens):
		self._turrets = OrderedDict()
		self._path = []
		self._n = len(grid)
		grid_str = ''.join(grid)
		self._determine_turret_positions(turrets, grid_str)
		self._determine_path_and_guarded_positions(grid_str)
		self._aliens = aliens

	def _determine_turret_positions(self, turrets, grid_str):
		for (turret, settings) in sorted(turrets.items()):
			ind = grid_str.find(turret)
			x = ind % self._n
			y = ind // self._n
			self._turrets[turret] = {'pos': (x, y), 'range2': settings[0] ** 2, 'shots': settings[1], 'guards': []}

	def _determine_path_and_guarded_positions(self, grid_str):
		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):
		self._path.append(point)
		self._add_to_guarded_list(point)

	def _get_next_point_on_path(self, grid_str):
		(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):
		for (turret, settings) in self._turrets.items():
			if (point[0] - settings['pos'][0]) ** 2 + (point[1] - settings['pos'][1]) ** 2 <= settings['range2']:
				settings['guards'].insert(0, point)

	def aliens_that_pass_the_turrets(self):
		total_turns = len(self._path) + len(self._aliens)
		for turn in range(1, total_turns + 1):
			total_remaining = 0
			for turret in self._turrets:
				self._turrets[turret]['remaining'] = self._turrets[turret]['shots']
				total_remaining += self._turrets[turret]['remaining']
			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
			while total_remaining > 0:
				for turret in self._turrets:
					if self._turrets[turret]['remaining'] > 0:
						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:
							total_remaining -= self._turrets[turret]['remaining']
							self._turrets[turret]['remaining'] = 0
		return sum(self._aliens)

	def print_map(self, turn=0):
		turret_pos = {}
		for (turret, settings) in self._turrets.items():
			turret_pos[settings['pos']] = turret
		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]
		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()
		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):
	map = []
	for row in data:
		map.append(list(row))
	rows = len(map)
	cols = len(map[0])
	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)
	trail = []
	found_end = False
	next = start
	while not found_end:
		if next[1] + 1 < rows and map[next[1] + 1][next[0]] == '1':
			map[next[1] + 1][next[0]] = '0'
			trail.append(next)
			next = (next[0], next[1] + 1)
		elif next[1] - 1 >= 0 and map[next[1] - 1][next[0]] == '1':
			map[next[1] - 1][next[0]] = '0'
			trail.append(next)
			next = (next[0], next[1] - 1)
		elif next[0] + 1 < cols and map[next[1]][next[0] + 1] == '1':
			map[next[1]][next[0] + 1] = '0'
			trail.append(next)
			next = (next[0] + 1, next[1])
		elif next[0] - 1 >= 0 and map[next[1]][next[0] - 1] == '1':
			map[next[1]][next[0] - 1] = '0'
			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):
	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))
	aliens = deque()
	trail_length = len(trail)
	final_health = 0
	game_length = len(alien_data) + len(trail)
	round = 0
	while round < game_length:
		round += 1
		if len(alien_data) > 0:
			aliens.appendleft(Alien(alien_data.pop(0), len(trail)))
		else:
			aliens.appendleft(Alien(0, len(trail)))
		if len(aliens) > trail_length:
			removed_alien = aliens.pop()
			if removed_alien.health > 0:
				final_health += removed_alien.health
		for turret in turrets:
			turret.reset_shots()
		turrets_done = False
		while not turrets_done:
			for t in turrets:
				if t.current_shots > 0:
					t.shoot_nearest_alien(aliens)
			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