[Langton's ant](https://en.wikipedia.org/wiki/Langton%27s_ant) is a two-dimensional Turing machine invented in the late 1980s. The ant starts out on a grid of black and white cells and follows a simple set of rules that has complex emergent behavior.

## Task

Complete the function and return the `n`th iteration of Langton's ant with the given input.

### Parameters:

* `grid` - a two dimensional array of `1`s and `0`s (representing white and black cells respectively)
* `column` - horizontal position of ant
* `row` - ant's vertical position
* `n` - number of iterations
* `dir` - ant's current direction (0 - north, 1 - east, 2 - south, 3 - west), **should default to 0**

**Note:** parameters `column` and `row` will always be inside the `grid`, and number of generations `n` will never be negative.

## Output

The state of the `grid` after `n` iterations.

## Rules

The ant can travel in any of the four cardinal directions at each step it takes. The ant moves according to the rules below:

* At a white square (represented with `1`), turn 90° right, flip the color of the square, and move forward one unit.
* At a black square (`0`), turn 90° left, flip the color of the square, and move forward one unit.

The grid has no limits and therefore if the ant moves outside the borders, the grid should be expanded with `0`s, respectively maintaining the rectangle shape.

## Example

```python
ant([[1]], 0, 0, 1, 0)   # should return: [[0, 0]]
```

Initially facing north (`0`), at the first iteration the ant turns right (because it stands on a white square, `1`), flips the square and moves forward.

Difficulty: introductory

Starter code:

def ant(grid, column, row, n, direction = 0):
	

Solutions:
BLACK = 0
WHITE = 1
# N, E, S, W
CARDINALS = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def ant(grid, column, row, n, direction=0):
    r, c, d = row, column, direction
    for _ in range(n):
        # Handle direction change and current cell colour flip
        if grid[r][c] == BLACK:
            grid[r][c] = WHITE
            d = (d + 3) % 4
        else:
            grid[r][c] = BLACK
            d = (d + 1) % 4
        # Apply movement to next grid position
        r, c = r + CARDINALS[d][0], c + CARDINALS[d][1]
        # Resize grid as required
        if r < 0:
            grid.insert(0, [0] * len(grid[0]))
            r += 1
        elif r == len(grid):
            grid.append([0] * len(grid[0]))
        elif c < 0:
            grid = [[0] + row for row in grid]
            c += 1
        elif c == len(grid[0]):
            grid = [row + [0] for row in grid]
    return grid

def ant(grid, c, r, n, direction = 0):
    
    MOVES = [(-1,0), (0,1), (1,0), (0,-1)]             # directions the ant can move
    
    dims = {(min, 0): 0, (max, 0): len(grid)-1,        # min and max values of row index
            (min, 1): 0, (max, 1): len(grid[0])-1}     # min and max values of column index
            
    gridWhite = { (x,y) for x in range(len(grid)) for y in range(len(grid[0])) if grid[x][y] }    # set of white squares only
    
    for _ in range(n):                                                  # Ant is at work...
        direction = (direction + (-1)**((r,c) not in gridWhite)) % 4    # shift the ant
        gridWhite ^= {(r,c)}                                            # shift the square
        r += MOVES[direction][0]                                        # update position
        c += MOVES[direction][1]
        for func,dim in dims:
            dims[(func,dim)] = func(dims[(func,dim)], (r,c)[dim])       # update min and max values of the indexes
    
    MinX, MinY = dims[(min,0)], dims[(min,1)]                  # minimum for rows (x) and columns(y)
    lenX, lenY = dims[(max,0)]-MinX+1, dims[(max,1)]-MinY+1    # determine the final dimensions of the grid
    
    return [ [(1 if (x+MinX, y+MinY) in gridWhite else 0) for y in range(lenY)] for x in range(lenX) ]

def ant(grid, col, row, n, dir = 0):
    for _ in range(n):
        # turn
        color = grid[row][col]
        if   color == 1: dir = (dir + 1) % 4
        elif color == 0: dir = (dir - 1) % 4
        
        # flip color
        grid[row][col] ^= 1
        
        # move forward
        if   dir == 0: row -= 1
        elif dir == 1: col += 1
        elif dir == 2: row += 1
        elif dir == 3: col -= 1
        
        # expand grid
        if row < 0:
            grid.insert(0, [0] * len(grid[0]))
            row = 0
        if row == len(grid):
            grid.append([0] * len(grid[0]))
        if col < 0:
            for i in range(len(grid)):
                grid[i].insert(0, 0)
            col = 0
        if col == len(grid[0]):
            for i in range(len(grid)):
                grid[i].append(0)
    
    return grid

def ant(grid, column, row, n, dir = 0):
    w, d = len(grid[0]), len(grid)
    m = [[0 for i in range(w+2*n)] for j in range(d+2*n)]
    for i in range(d):
        m[i+n][n:n+w] = grid[i][:]
    x, y = column + n, row + n
    t = 0
    xmax, xmin = x, x
    ymax, ymin = y, y
    for _ in range(n):
        dir += (m[y][x]==1)*(1) +(m[y][x]==0)*(-1)
        dir %= 4
        m[y][x] = 1-m[y][x]
        y += (dir==0)*(-1) + (dir==2)*1
        x += (dir==3)*(-1) + (dir==1)*1
        xmax,xmin = max(xmax,x), min(xmin,x)
        ymax,ymin = max(ymax,y), min(ymin,y)
    return [m[i][min(xmin,n):max(xmax,n+w-1)+1] for i in range(min(ymin,n), max(ymax, n+d-1)+1)]

def ant(gr, cl, ro, n, di = 0):
    class ant_class():
        def __init__(self, col, row, direction):
            self.c = col
            self.r = row
            self.direction = ['N', 'E', 'S', 'W']
        def __repr__(self):
            return ('col: {}, row: {}, direction: {}'.format(self.c, self.r, self.direction[0]))
        def turn_right(self):
            self.direction.append(self.direction.pop(0))
        def turn_left(self):
            self.direction.insert(0, self.direction.pop(-1))
        def move(self, grid):
            if self.direction[0] == 'N':
                 if ant.r == 0:
                    grid.expand_north()
                 else:
                    ant.r -= 1
            elif self.direction[0] == 'S':
                if ant.r == len(grid.grid) - 1:
                    grid.expand_south()
                ant.r += 1
            elif self.direction[0] == 'W':
                if ant.c == 0:
                    grid.expand_west()
                else:
                    ant.c -= 1
            elif self.direction[0] == 'E':
                if ant.c == len(grid.grid[0]) - 1:
                    grid.expand_east()
                ant.c += 1
    
    class grid():
        def __init__(self, arr):
            self.grid = arr
        def expand_south(self):
            self.grid.append([0 for i in range(len(self.grid[0]))])
        def expand_north(self):
            self.grid.insert(0, [0 for i in range(len(self.grid[0]))])
        def expand_east(self):
            self.grid = [i + [0] for i in self.grid]
        def expand_west(self):
            self.grid = [[0] + i for i in self.grid]
        def invert(self, ant):
            self.grid[ant.r][ant.c] = int(not(self.grid[ant.r][ant.c]))
        
    ant = ant_class(cl, ro, di)
    field = grid(gr)
    for i in range(di):
        ant.turn_right()
    
    for i in range(n):
        if field.grid[ant.r][ant.c] == 1:
            ant.turn_right()
            field.invert(ant)
            ant.move(field)
        elif field.grid[ant.r][ant.c] == 0:
            ant.turn_left()
            field.invert(ant)
            ant.move(field)
    
    return field.grid


def ant(grid, x, y, n, d=0):
    g, p = {(j, i):v for j, row in enumerate(grid) for i, v in enumerate(row)}, (x, y)
    for m in range(n):
        g[p] = (g[p] + 1) % 2
        d += -1 if g[p] else 1        
        p = p[0] + [0, 1, 0, -1][d % 4], p[1] + [-1, 0, 1, 0][d % 4]
        g[p] = g.get(p, 0) 
        
    return [[g.get((x, y), 0) for x in range(min(x for x, _ in g), max(x for x, _ in g)+1)] for y in range(min(y for _, y in g), max(y for _, y in g)+1)]

def ant(grid, column, row, n, direction = 0):

    def checc(m,k,grid):
    
        if m>len(grid)-1:
            grid1 = [[0 for j in range(len(grid[0]))] for i in range(len(grid)+1)]
            for i in range(len(grid)):
                for j in range(len(grid[i])):
                    grid1[i][j]=grid[i][j]
            grid=grid1
            
        elif m<0:
            grid1 = [[0 for j in range(len(grid[0]))] for i in range(len(grid)+1)]
            for i in range(len(grid)):
                for j in range(len(grid[i])):
                    grid1[i+1][j]=grid[i][j]
            m+=1 
            grid=grid1
        
        elif k<0:
            grid1 = [[0 for j in range(len(grid[0])+1)] for i in range(len(grid))]
            for i in range(len(grid)):
                for j in range(len(grid[i])):
                    grid1[i][j+1]=grid[i][j]
            k+=1
            grid=grid1
            
        elif k>len(grid[0])-1:
            grid1 = [[0 for j in range(len(grid[0])+1)] for i in range(len(grid))]
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    grid1[i][j]=grid[i][j] 
            grid=grid1
            
        return [m,k,grid]

    m,k=row,column
    dire=direction
    directions = {(1,0):[0,1], (1,1):[0,2], (1,2):[0,3], (1,3):[0,0],
                  (0,0):[1,3], (0,1):[1,0], (0,2):[1,1], (0,3):[1,2]}
    grids ={0:[-1,0],1:[0,1],2:[1,0],3:[0,-1]}
    
    for l in range(n):
             
        m,k,grid=checc(m,k,grid)
        
        col = grid[m][k] 
        grid[m][k], dire = directions[(col,dire)]
        
        m += (grids[dire])[0]
        k += (grids[dire])[1]
        
        
        m,k,grid=checc(m,k,grid)
    
    return grid


def ant(g, c, r, n, d = 0):
    grid = {(i, j):g[i][j] for j in range(len(g[0])) for i in range(len(g))}
    D = {1: (0, 1), 2: (1, 0), 3: (0, -1), 0: (-1, 0)}
    for i in range(n):
        d = (d + (1 if grid[(r,c)] == 1 else -1))%4
        grid[(r,c)] = 1 - grid[(r,c)]
        R,C = D[d]
        r,c = r + R, c + C
        grid[(r, c)] = 0 if (r,c) not in grid else grid[(r,c)]
    S = grid.keys()
    m_y, m_x = [min(S,key=lambda x:x[i])[i] for i in [0,1]]
    M_y, M_x = [max(S,key=lambda x:x[i])[i] for i in [0,1]]
    return [[grid.get((m_y+j, m_x+i),0) for i in range(M_x-m_x+1)] for j in range(M_y-m_y+1)]

def ant(grid, column, row, n, direction = 0):
    for _ in range(n):
        direction = (direction - 1 + 2*grid[row][column]) % 4
        dx, dy = d[direction]
        grid[row][column] = 1 - grid[row][column]
        row += dy
        column += dx
        if column < 0:
            for i, r in enumerate(grid):
                grid[i] = [0] + r
            column += 1
        elif column >= len(grid[0]):
            for r in grid: r.append(0)
        if row < 0:
            grid = [[0] * len(grid[0])] + grid
            row += 1
        elif row >= len(grid):
            grid.append([0] * len(grid[0]))
    return grid

d = (0, -1), (1, 0), (0, 1), (-1, 0)

def ant(grid, col, row, n, direction=0):
    for count in range(n):
        if grid[row][col] == 1:
            direction = (direction + 1)%4
        else:
            direction = (direction - 1)%4
        
        grid[row][col] = int(not grid[row][col])
        if direction == 0:
            row -= 1 
            if row < 0:
                row = 0
                grid.insert(0, [0 for i in range(len(grid[0]))])
        elif direction == 1:
            col += 1
            if col >= len(grid[0]):
                grid = [row + [0] for row in grid]
        elif direction == 2:
            row += 1
            if row >= len(grid):
                grid.append([0 for i in range(len(grid[0]))])
        else:
            col -= 1
            if col < 0:
                col = 0
                grid = [[0] + row for row in grid]
    return grid