[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: EASY
Tags: Complete search
Skill types: Complete search

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

Solutions:
BLACK = 0
WHITE = 1
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):
		if grid[r][c] == BLACK:
			grid[r][c] = WHITE
			d = (d + 3) % 4
		else:
			grid[r][c] = BLACK
			d = (d + 1) % 4
		(r, c) = (r + CARDINALS[d][0], c + CARDINALS[d][1])
		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)]
	dims = {(min, 0): 0, (max, 0): len(grid) - 1, (min, 1): 0, (max, 1): len(grid[0]) - 1}
	gridWhite = {(x, y) for x in range(len(grid)) for y in range(len(grid[0])) if grid[x][y]}
	for _ in range(n):
		direction = (direction + (-1) ** ((r, c) not in gridWhite)) % 4
		gridWhite ^= {(r, c)}
		r += MOVES[direction][0]
		c += MOVES[direction][1]
		for (func, dim) in dims:
			dims[func, dim] = func(dims[func, dim], (r, c)[dim])
	(MinX, MinY) = (dims[min, 0], dims[min, 1])
	(lenX, lenY) = (dims[max, 0] - MinX + 1, dims[max, 1] - MinY + 1)
	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):
		color = grid[row][col]
		if color == 1:
			dir = (dir + 1) % 4
		elif color == 0:
			dir = (dir - 1) % 4
		grid[row][col] ^= 1
		if dir == 0:
			row -= 1
		elif dir == 1:
			col += 1
		elif dir == 2:
			row += 1
		elif dir == 3:
			col -= 1
		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