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

Difficulty: interview

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):                                           #Out of the grid: move down and reverse
                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]))     # Furthest, fastest, going right is considered the highest
            shootPath.remove(z)                                           # MUTATION
            shots.append(turn)                                            # MUTATION
    
    (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)        # Move all the aliens, splitting them in 2 groups: those facing "my" ship (shootPath) and the others
        shootTarget(shootPath)                                            # Extract the target in shootPath and pop it if possible (mutation). Mutate 'shots' list at the same time
        aliens += shootPath                                               # Put the remaining aliens in the list
    
    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):
                # for whatever reason, static aliens are not shot
                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

        # only horizontal movement
        if (distance <= self.lenOfFieldI-1 and distance >= 0):
            alien.positionI = distance
            TESTdistance = 0
        
        # vertical movement right
        elif(distance >= self.lenOfFieldI):
            # move to rightmost column
            distance_right = self.lenOfFieldI -1 - alien.positionI
            distance_remaining = abs(alien.speed) - distance_right
            alien.positionI = alien.positionI + distance_right 

            TESTdistance = TESTdistance - distance_right
            
            # move up
            alien.positionJ = alien.positionJ+1
            distance_remaining = distance_remaining - 1

            TESTdistance = TESTdistance - 1
            
            alien.speed = -alien.speed

            # move left
            alien.positionI = alien.positionI -distance_remaining

            TESTdistance = TESTdistance - distance_remaining
            
        
        # vertical movement left
        elif(distance < 0):

            # move to leftmost column
            distance_left = alien.positionI
            distance_remaining = abs(alien.speed) - distance_left
            alien.positionI = 0

            TESTdistance = TESTdistance - distance_left

            # move up
            alien.positionJ = alien.positionJ+1
            distance_remaining = distance_remaining - 1

            TESTdistance = TESTdistance - 1
            
            alien.speed = -alien.speed

            # move right
            alien.positionI = distance_remaining

            TESTdistance = TESTdistance - distance_remaining
        

        else:
            if(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):
            # there will be a shot!
            alienToBeShot = self.findAlienToBeShot()
            
            self.deleteShotAlienFromListOfAllAliens(alienToBeShot)

            self.addRoundToBlastSequence()

        # in any case:
        self.clearListOfShootableAliens()


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

    def findAlienToBeShot(self):
        iterator = self.lenOfFieldJ-1
        alienFound = False
        killingList=[]

        while ((iterator >= 0) and (alienFound == False)):
            # iterate through the field by lines
            for shootableAlien in self.listOfShootableAliens:
                if ((shootableAlien.positionJ == iterator) and (shootableAlien.positionI == self.positionOfDefenderI)):
                    killingList.append(shootableAlien)
                    alienFound = True
            iterator = iterator -1

        # TEST
        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=[]

        # calculate highest speed
        for alien in killingList:
            if ( abs(alien.speed) > maxAbsSpeed):
                maxAbsSpeed = abs(alien.speed)

        # find fastest alien
        for alien in killingList:
            if ( abs(alien.speed) == maxAbsSpeed):
                highestAlien.append(alien)
        
        #more than one fastest aliens 
        if (len(highestAlien)>1):
            # choose a right-moving alien
            for alien in highestAlien:
                if (alien.speed > 0):
                    return alien

        # return any of the remaining aliens
        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



# Section of Testing

    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]
            # print(y, x, v)
            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