This kata is inspired by Space Invaders (Japanese: スペースインベーダー), an arcade video game created by Tomohiro Nishikado and released in 1978.
Alien invaders are attacking Earth and you've been conscripted to defend.
The Bad News: You performed poorly in the manual training. As a result, you're ranked low priority and you're piloting a space jalopy.
The Good News: Your coding skill is better than your piloting and you know the movement pattern of the alien spaceships.
You're going to program an algorithm that aids in shooting down the incoming alien wave despite your limitations.
Input
The action takes place on an m x n matrix. Your function will receive two arguments:

a 2-D array where each subarray represents a row of alien ships. Subarrays consist of integers that represent each alien ship. Zero values (0) are empty spaces.
        
your [row,column] coordinates

The width (n) of a row is equal to the length of a subarray in the first argument and all rows are of the same length.
Your row coordinate will be the last row of the matrix (m - 1).
Alien Ship Movement Pattern

Each alien ship is given in the form of an integer that represents its movement speed and direction.
Alien ships move left or right. A positive integer means an alien moves right, a negative integer means an alien moves left. The absolute value of the integer is the distance the alien moves in 1 turn.
When an alien reaches an edge, it moves down one position and reverses lateral (left/right) direction.

Your Ship's Limitations

Your position is fixed.
Your pulse cannon has a time delay of 1 turn. After the delay, your cannon blasts the first target in its path.
You can fire up to one shot per turn.


Output
Your function should return an array of integers. Each integer represents the turn for each shot fired from your ship's cannon. If it is not possible to destroy all alien ships before they reach the last row, return null or None.
Test Example

Above: Turn 0 (Initial State)
Below: Turn 1

The images above represent the matrix states at Turn 0 and Turn 1 for the test example below. Note the following:

Multiple alien ships can occupy the same space concurrently. The red alien at [0,2] and the light blue alien at [0,7] at turn 0 will both end up at position [0,4] at turn 1.
The pink alien (1) at [0,9] at turn 0 is already at the right edge, so it moves one space down and changes direction from right to left.
The yellow alien (6) at [0,6] at turn 0 ends up at [1,7] at turn 1.
The green alien (7) at [0,8] at turn 0 ends up at [1,4] (white alien) and gets shot down by your cannon at turn 1. Therefore, the time of registering your first shot is at turn 0.

In the test example, there is only one subarray in the first argument, meaning only the top row (row 0) of the matrix is occupied at the initial state.

```python
alien_wave = [[3,1,2,-2,2,3,6,-3,7,1]]
position = [6,4]

blast_sequence(alien_wave,position)# [0, 2, 3, 4, 5, 9, 10, 13, 19, 22]
```

Other Technical Details

In the event where multiple alien ships occupy the same position and the position is the target of your cannon fire, the fastest alien ship will be destroyed. If two ships are going at the same speed in opposite directions, the ship moving to the right will be destroyed.
All alien ship movement speeds will be less than the width of the matrix.
Alien count upper bound is 228
Inputs will always be valid


If you enjoyed this kata, be sure to check out [my other katas](https://www.codewars.com/users/docgunthrop/authored).

Source: codewars | Difficulty: MEDIUM
Tags: Game theory

Starter code: def blast_sequence(aliens, position):
	

Solutions:
def blast_sequence(aliensStart, position):

	def moveAliens(aliens, furthest):
		(lst, shootPath) = ([], [])
		for (x, y, s) in aliens:
			y += s
			if not 0 <= y < N:
				(x, s) = (x + 1, -s)
				y = -y - 1 if y < 0 else 2 * N - y - 1
			(shootPath if y == Y else lst).append((x, y, s))
			if x > furthest:
				furthest = x
		return (lst, shootPath, furthest)

	def shootTarget(shootPath):
		if shootPath:
			z = max(shootPath, key=lambda a: (a[0], abs(a[2]), a[2]))
			shootPath.remove(z)
			shots.append(turn)
	((X, Y), N) = (position, len(aliensStart[0]))
	aliens = [(x, y, s) for (x, r) in enumerate(aliensStart) for (y, s) in enumerate(r) if s]
	(shots, furthest, turn) = ([], 0, -1)
	while aliens and furthest < X:
		turn += 1
		(aliens, shootPath, furthest) = moveAliens(aliens, furthest)
		shootTarget(shootPath)
		aliens += shootPath
	return shots if not aliens else None


class Ship:
	columns = 0

	def __init__(self, row, col, speed):
		self.row = row
		self.col = col
		self.speed = speed

	def move(self):
		new_col = self.col + self.speed
		if new_col < 0 or new_col >= Ship.columns:
			self.row += 1
			self.speed = -self.speed
			if new_col < 0:
				new_col = -new_col - 1
			else:
				new_col = 2 * Ship.columns - new_col - 1
		self.col = new_col

def blast_sequence(aliens, position):
	(rows, column) = position
	Ship.columns = len(aliens[0])
	ships = []
	for (nrow, row) in enumerate(aliens):
		ships.extend((Ship(nrow, ncol, speed) for (ncol, speed) in enumerate(row) if speed))
	(shots, turn) = ([], 0)
	while ships:
		for ship in ships:
			ship.move()
			if ship.row == rows:
				return None
		ships.sort(key=lambda x: x.speed, reverse=True)
		ships.sort(key=lambda x: abs(x.speed), reverse=True)
		ships.sort(key=lambda x: x.row, reverse=True)
		targets = [ship for ship in ships if ship.col == column]
		if targets:
			ships.remove(targets[0])
			shots.append(turn)
		turn += 1
	return shots


def blast_sequence(aliens, position):
	board_len = len(aliens[0])
	aliens = {(x, y, steps) for (y, lst) in enumerate(aliens) for (x, steps) in enumerate(lst) if steps != 0}
	solution = []
	turn = -1
	while all((alien[1] != position[0] for alien in aliens)) and aliens:
		turn += 1
		aliens = {(alien[0] + alien[2], alien[1], alien[2]) if 0 <= alien[0] + alien[2] < board_len else (-1 * (alien[0] + alien[2] + 1) % board_len, alien[1] + 1, alien[2] * -1) for alien in aliens}
		alien = max((alien for alien in aliens if alien[0] == position[1]), key=lambda alien: (alien[1], abs(alien[2]), alien[2]), default=None)
		if alien:
			aliens ^= {alien}
			solution.append(turn)
	return solution if not aliens else None


def blast_sequence(aliens, position):
	result = []
	aliens_lst = [[y, x, speed] for (x, row) in enumerate(aliens) for (y, speed) in enumerate(row) if speed != 0]
	time = 0
	while aliens_lst:
		for alien in aliens_lst:
			for _ in range(abs(alien[2])):
				if alien[0] == 0 and alien[2] < 0 or (alien[0] == len(aliens[0]) - 1 and alien[2] > 0):
					alien[1] += 1
					alien[2] *= -1
					if alien[1] == position[0]:
						return None
				else:
					alien[0] += 1 if alien[2] > 0 else -1
		targets = [alien for alien in aliens_lst if alien[0] == position[1]]
		targets.sort(key=lambda alien: (alien[1], abs(alien[2]), alien[2]))
		if targets:
			target = targets.pop()
			aliens_lst.remove(target)
			result.append(time)
		time += 1
	return result


def blast_sequence(aliens, shooter):
	(row, column) = (len(aliens[0]), shooter[0] + 1)
	board = [[0 for _ in range(row)] for _ in range(column)]
	for (i, j) in enumerate(aliens):
		board[i] = j
	find_pos = [[i, k, l] for (i, j) in enumerate(aliens) for (k, l) in enumerate(j) if l]

	def parse(x, y, z):
		c = 0
		while c < abs(z):
			if z > 0:
				y += 1
			else:
				y -= 1
			if y == row:
				x += 1
				(z, y) = (-z, row - 1)
			elif y == -1:
				x += 1
				(z, y) = (-z, 0)
			c += 1
		return [x, y, z]
	(turn, shoots) = (0, [])
	while find_pos and all((k[0] != shooter[0] for k in find_pos)):
		for (i, j) in enumerate(find_pos):
			find_pos[i] = parse(*j)
		targets = [k for k in find_pos if k[1] == shooter[1]]
		if targets:
			shoots.append(turn)
			find_pos.remove(max(targets, key=lambda x: (x[0], abs(x[2]), x[2])))
		turn += 1
	return [shoots, None][bool(find_pos)]


def blast_sequence(aliens, position):
	(si, sj) = position
	(rows, cols) = (si + 1, len(aliens[0]))
	board = [[[a] if a else [] for a in alien] for alien in aliens] + [[[]] * cols for c in range(rows - len(aliens))]
	count = len([a for al in aliens for (i, a) in enumerate(al) if a])
	turn = 0
	res = []
	while count > 0:
		board = move(board, rows, cols)
		if not board:
			return None
		for pi in range(rows - 2, -1, -1):
			col = board[pi][sj]
			if not col:
				continue
			if len(col) == 1:
				board[pi][sj] = []
			else:
				dead = sorted(col, key=lambda v: (abs(v), v)).pop()
				board[pi][sj].remove(dead)
			res.append(turn)
			count -= 1
			break
		turn += 1
	return res

def move(board, rows, cols):
	if any((l for l in board[-1])):
		return None
	temp = [[[] for a in row] for row in board]
	for (i, row) in enumerate(board):
		for (j, alien_list) in enumerate(row):
			if not alien_list:
				continue
			for (k, alien) in enumerate(alien_list):
				ni = i
				nj = j + alien
				if nj < 0:
					nj = abs(nj) - 1
					ni += 1
					alien *= -1
				elif nj >= cols:
					nj = cols - 1 - nj % cols
					ni += 1
					alien *= -1
				if ni == rows - 1:
					return None
				temp[ni][nj].append(alien)
	return temp


class alien:

	def __init__(self, speed, i, j):
		self.speed = speed
		self.positionI = i
		self.positionJ = j

class model:

	def __del__(self):
		print(' ')

	def __init__(self, aliens, defender):
		self.listOfAllAliens = []
		self.listOfShootableAliens = []
		self.countOfStaticAliens = 0
		self.blastSequence = []
		self.roundOfGame = 0
		self.gameWon = False
		self.gameOver = False
		self.TESTnumberOfAliens = 0
		self.positionOfDefenderI = defender[1]
		self.positionOfDefenderJ = defender[0]
		self.lenOfFieldJ = defender[0]
		self.lenOfFieldI = len(aliens[0])
		self.createAliens(aliens)
		self.countStaticAliens()

	def createAliens(self, aliens):
		posJ = -1
		for line in aliens:
			posJ = posJ + 1
			for i in range(0, len(aliens[0])):
				newAlien = alien(line[i], i, posJ)
				self.TESTnumberOfAliens = self.TESTnumberOfAliens + 1
				self.listOfAllAliens.append(newAlien)

	def countStaticAliens(self):
		for alien in self.listOfAllAliens:
			if alien.speed == 0:
				self.countOfStaticAliens = self.countOfStaticAliens + 1

	def increaseRoundOfGame(self):
		self.roundOfGame = self.roundOfGame + 1

	def moveAliens(self):
		for alien in self.listOfAllAliens:
			self.calculateAlienMovement(alien)
			if alien.positionJ == self.positionOfDefenderJ:
				self.gameOver = True
			if alien.positionI == self.positionOfDefenderI:
				if alien.speed != 0:
					self.putAlienInListOfShootableAliens(alien)

	def calculateAlienMovement(self, alien):
		speed = alien.speed
		distance = speed + alien.positionI
		TESTdistance = abs(speed)
		distance_remaining = 0
		TESTpositionI = alien.positionI
		TESTpositionJ = alien.positionJ
		if distance <= self.lenOfFieldI - 1 and distance >= 0:
			alien.positionI = distance
			TESTdistance = 0
		elif distance >= self.lenOfFieldI:
			distance_right = self.lenOfFieldI - 1 - alien.positionI
			distance_remaining = abs(alien.speed) - distance_right
			alien.positionI = alien.positionI + distance_right
			TESTdistance = TESTdistance - distance_right
			alien.positionJ = alien.positionJ + 1
			distance_remaining = distance_remaining - 1
			TESTdistance = TESTdistance - 1
			alien.speed = -alien.speed
			alien.positionI = alien.positionI - distance_remaining
			TESTdistance = TESTdistance - distance_remaining
		elif distance < 0:
			distance_left = alien.positionI
			distance_remaining = abs(alien.speed) - distance_left
			alien.positionI = 0
			TESTdistance = TESTdistance - distance_left
			alien.positionJ = alien.positionJ + 1
			distance_remaining = distance_remaining - 1
			TESTdistance = TESTdistance - 1
			alien.speed = -alien.speed
			alien.positionI = distance_remaining
			TESTdistance = TESTdistance - distance_remaining
		elif speed != 0:
			print('error! alien movement could not be calculated')
		if TESTpositionI == alien.positionI and TESTpositionJ == alien.positionJ and (alien.speed != 0):
			print('error! alien did not move this round')
		if TESTdistance != 0:
			print('error! calculation went wrong. remaining or negative distance left.')

	def putAlienInListOfShootableAliens(self, shootableAlien):
		self.listOfShootableAliens.append(shootableAlien)

	def shoot(self):
		if not len(self.listOfShootableAliens) == 0:
			alienToBeShot = self.findAlienToBeShot()
			self.deleteShotAlienFromListOfAllAliens(alienToBeShot)
			self.addRoundToBlastSequence()
		self.clearListOfShootableAliens()

	def clearListOfShootableAliens(self):
		self.listOfShootableAliens = []

	def findAlienToBeShot(self):
		iterator = self.lenOfFieldJ - 1
		alienFound = False
		killingList = []
		while iterator >= 0 and alienFound == False:
			for shootableAlien in self.listOfShootableAliens:
				if shootableAlien.positionJ == iterator and shootableAlien.positionI == self.positionOfDefenderI:
					killingList.append(shootableAlien)
					alienFound = True
			iterator = iterator - 1
		if len(killingList) == 0:
			print(('error! no alien to be shot found, also there are some!' + 'in the listofshootable Aliens', self.listOfShootableAliens))
			return None
		elif len(killingList) == 1:
			return killingList[0]
		else:
			return self.findAlienWithHighestAbsoluteSpeed(killingList)

	def findAlienWithHighestAbsoluteSpeed(self, killingList):
		maxAbsSpeed = 0
		highestAlien = []
		for alien in killingList:
			if abs(alien.speed) > maxAbsSpeed:
				maxAbsSpeed = abs(alien.speed)
		for alien in killingList:
			if abs(alien.speed) == maxAbsSpeed:
				highestAlien.append(alien)
		if len(highestAlien) > 1:
			for alien in highestAlien:
				if alien.speed > 0:
					return alien
		return highestAlien[0]

	def addRoundToBlastSequence(self):
		self.blastSequence.append(self.roundOfGame)

	def deleteShotAlienFromListOfAllAliens(self, shotAlien):
		if shotAlien.speed == 0:
			self.countOfStaticAliens = self.countOfStaticAliens - 1
			print(('error! static alien shot in round', self.roundOfGame))
		self.listOfAllAliens.remove(shotAlien)

	def checkIfGameOverOrGameWon(self):
		if len(self.listOfAllAliens) - self.countOfStaticAliens == 0:
			self.gameWon = True
		if self.gameOver == True or self.gameWon == True:
			return True
		else:
			return False

	def TESTNumberOfAliens(self):
		if self.TESTnumberOfAliens != len(self.listOfAllAliens) + len(self.blastSequence):
			print('error! Something went wrong. the number of aliens is not matching')
		if self.TESTnumberOfAliens < len(self.blastSequence):
			print('error! more aliens shot than existed')

def blast_sequence(aliens, position):
	game = model(aliens, position)
	check = False
	while not check:
		game.TESTNumberOfAliens()
		game.moveAliens()
		game.shoot()
		check = game.checkIfGameOverOrGameWon()
		game.increaseRoundOfGame()
	isGameWon = game.gameWon
	solution = game.blastSequence
	del game
	if isGameWon:
		return solution
	else:
		return None


class Ship:

	def __init__(self, x, y, speed):
		self.x = x
		self.y = y
		self.speed = speed

def blast_sequence(aliens, position):
	result = []
	ships = [Ship(x, y, speed) for (x, row) in enumerate(aliens) for (y, speed) in enumerate(row) if speed]
	turn = 0
	while ships:
		for ship in ships:
			for _ in range(abs(ship.speed)):
				if ship.y == 0 and ship.speed < 0 or (ship.y == len(aliens[0]) - 1 and ship.speed > 0):
					ship.x += 1
					ship.speed *= -1
					if ship.x == position[0]:
						return None
				else:
					ship.y += 1 if ship.speed > 0 else -1
		targets = [ship for ship in ships if ship.y == position[1]]
		targets.sort(key=lambda ship: (ship.x, abs(ship.speed), ship.speed))
		if targets:
			target = targets.pop()
			ships.remove(target)
			result.append(turn)
		turn += 1
	return result


def blast_sequence(aliens, position):
	dal = []
	wdh = len(aliens[0])
	for y in range(len(aliens)):
		for x in range(len(aliens[y])):
			if aliens[y][x] != 0:
				dal.append((y, x, aliens[y][x]))
	(yp, xp) = position
	hgh = yp + 1
	dr = []
	i = -1
	while len(dal) > 0:
		i += 1
		ddel = []
		for k in range(len(dal)):
			(y, x, v) = dal[k]
			x += v
			if x < 0:
				v = -v
				x = -x - 1
				y += 1
				if y == yp:
					return None
			elif x >= wdh:
				v = -v
				x = wdh + wdh - 1 - x
				y += 1
				if y == yp:
					return None
			dal[k] = (y, x, v)
			if x == xp:
				ddel.append(k)
		if len(ddel) > 0:
			ymax = 0
			for k in ddel:
				(y, x, v) = dal[k]
				ymax = max(ymax, y)
			ddel2 = []
			for k in ddel:
				(y, x, v) = dal[k]
				if y == ymax:
					ddel2.append(k)
			if len(ddel2) == 1:
				kdel = ddel2[0]
			else:
				vmax = 0
				for k in ddel2:
					(y, x, v) = dal[k]
					vmax = max(vmax, abs(v))
				ddel = []
				for k in ddel2:
					(y, x, v) = dal[k]
					if abs(v) == vmax:
						ddel.append(k)
				if len(ddel) == 1:
					kdel = ddel[0]
				else:
					for k in ddel:
						(y, x, v) = dal[k]
						if v > 0:
							kdel = k
							break
			dr.append(i)
			dal.pop(kdel)
	return dr


def blast_sequence(aliens_input, position):
	SHIP_X = position[1]
	HEIGHT = position[0] + 1
	WIDTH = len(aliens_input[0])
	turn = 0
	seq = []

	class Alien:

		def __init__(self, coords, cell):
			(self.x, self.y) = coords
			self.moves = abs(cell)
			self.dir = 1 if cell > 0 else -1
	aliens = [Alien((x, y), cell) for (y, row) in enumerate(aliens_input) for (x, cell) in enumerate(aliens_input[y]) if cell]

	def moveAlien(alien):
		for i in range(alien.moves):
			if alien.dir == -1 and alien.x == 0 or (alien.dir == 1 and alien.x == WIDTH - 1):
				alien.dir *= -1
				alien.y += 1
				if alien.y == HEIGHT - 1:
					return True
			else:
				alien.x += alien.dir

	def moveAliens():
		for alien in aliens:
			if moveAlien(alien):
				return True

	def fireCannon():
		aliensInLine = list(filter(lambda a: a.x == SHIP_X, aliens))
		if not aliensInLine:
			return
		targetAlien = None
		for alien in aliensInLine:
			if not targetAlien or alien.y > targetAlien.y or (alien.y == targetAlien.y and (alien.moves > targetAlien.moves or (alien.moves == targetAlien.moves and alien.dir == 1))):
				targetAlien = alien
		aliens.remove(targetAlien)
		seq.append(turn - 1)

	def makeTurn():
		nonlocal turn
		turn += 1
		if moveAliens():
			return True
		fireCannon()
	while aliens:
		if makeTurn():
			return None
	return seq