*This kata is based on [Project Euler Problem #349](https://projecteuler.net/problem=349). You may want to start with solving [this kata](https://www.codewars.com/kata/langtons-ant) first.*

---

[Langton's ant](https://en.wikipedia.org/wiki/Langton%27s_ant) moves on a regular grid of squares that are coloured either black or white.
The ant is always oriented in one of the cardinal directions (left, right, up or down) and moves  according to the following rules:
- if it is on a black square, it flips the colour of the square to white, rotates 90 degrees counterclockwise and moves forward one square.
- if it is on a white square, it flips the colour of the square to black, rotates 90 degrees clockwise and moves forward one square.

Starting with a grid that is **entirely white**, how many squares are black after `n` moves of the ant?

**Note:** `n` will go as high as 10^(20)

---

## My other katas

If you enjoyed this kata then please try [my other katas](https://www.codewars.com/collections/katas-created-by-anter69)! :-)

#### *Translations are welcome!*

Source: codewars | Difficulty: EASY
Tags: Mathematics

Starter code: def langtons_ant(n):
	

Solutions:
move = [lambda p: (p[0] + 1, p[1]), lambda p: (p[0], p[1] + 1), lambda p: (p[0] - 1, p[1]), lambda p: (p[0], p[1] - 1)]
(start, loop, size) = (9977, 104, 12)

def langtons_ant(n):
	(pos, d, black, res) = ((0, 0), 0, set(), 0)
	if n > start:
		x = (n - start) % loop
		res = size * (n - start - x) // loop
		n = start + x
	for i in range(n):
		if pos in black:
			black.remove(pos)
			d = (d + 1) % 4
		else:
			black.add(pos)
			d = (d - 1) % 4
		pos = move[d](pos)
	return res + len(black)


LIMIT = 11000
CACHE = [0]
GRID = set()
(x, y) = (0, 0)
(dx, dy) = (1, 0)
for _ in range(LIMIT + 1):
	if (x, y) in GRID:
		GRID.remove((x, y))
		(dx, dy) = (-dy, dx)
	else:
		GRID.add((x, y))
		(dx, dy) = (dy, -dx)
	x += dx
	y += dy
	CACHE.append(len(GRID))

def langtons_ant(n):
	if n < LIMIT:
		return CACHE[n]
	x = (n - LIMIT) // 104 + 1
	return CACHE[n - x * 104] + x * 12


(M, B, r, c, d, N) = ([0], set(), 0, 0, 0, 10000)
for _ in range(N + 104):
	(d, _) = ((d - 1) % 4, B.discard((r, c))) if (r, c) in B else ((d + 1) % 4, B.add((r, c)))
	(r, c) = (r + [-1, 0, 1, 0][d], c + [0, 1, 0, -1][d])
	M.append(len(B))

def langtons_ant(n):
	return M[n] if n < N else 12 * ((n - N) // 104) + M[N + (n - N) % 104]


(l, m) = (10082, 104)
(a, d, s, t) = (0, 1, {}, [0])
for _ in range(l + m - 1):
	s[a] = 1 - s.get(a, 0)
	v = (-1) ** (-~s[a])
	d *= 1j * v
	a += d
	t.append(t[-1] + v)

def langtons_ant(n):
	if n < l:
		return t[n]
	(q, r) = divmod(n - l, m)
	return 12 * q + t[l + r]


def langtons_ant(n):
	k = (n - 11000) // 104 if n > 11000 else 0
	blacks = set()
	(x, y) = (0, 0)
	(dx, dy) = (0, 1)
	for _ in range(n - k * 104):
		if (x, y) in blacks:
			blacks.remove((x, y))
			(dx, dy) = (dy, -dx)
		else:
			blacks.add((x, y))
			(dx, dy) = (-dy, dx)
		(x, y) = (x + dx, y + dy)
	return len(blacks) + k * 12


def langtons_ant(n):
	if n == 0:
		return 0
	(width, height, i, j) = (150, 150, 75, 75)
	grid = [[1] * width for i in range(height)]
	directions = list(range(4))
	(d, count, s, black) = (0, 0, 0, [])
	while count < n and 0 <= i < height and (0 <= j < width):
		cell = grid[i][j]
		turn = -1 if cell == 0 else 1
		if cell:
			grid[i][j] = 0
			s += 1
		else:
			grid[i][j] = 1
			s -= 1
		black.append(s)
		d = directions[(4 + d + turn) % 4]
		if d == 0:
			i -= 1
		elif d == 1:
			j -= 1
		elif d == 2:
			i += 1
		elif d == 3:
			j += 1
		count += 1
	(limit, period) = (10000, 104)
	if count <= limit + period + 1:
		return black[-1]
	diff = black[limit + period] - black[limit]
	(cycles, r) = divmod(n - 1 - limit, period)
	return black[limit + r] + cycles * diff


move_y = [1, 0, -1, 0]
move_x = [0, 1, 0, -1]

def langtons_ant(n):
	grid_size = 128
	grid = [[0 for i in range(grid_size)] for j in range(grid_size)]
	pos_x = int(grid_size / 2)
	pos_y = int(grid_size / 2)
	dir = 0
	cnt_blk = 0
	step_cnt = 0
	prev_cnt = []
	while step_cnt < n:
		if step_cnt > 10000.0 and step_cnt % 104 == n % 104:
			prev_cnt.append(cnt_blk)
			if len(prev_cnt) == 6:
				prev_cnt.pop(0)
				diff = prev_cnt[-1] - prev_cnt[-2]
				cycle_flg = True
				for i in range(len(prev_cnt) - 2, 0, -1):
					if prev_cnt[i] - prev_cnt[i - 1] != diff:
						cycle_flg = False
						break
				if cycle_flg:
					cnt_blk += int(diff * (n - step_cnt) // 104)
					break
		if grid[pos_x][pos_y] == 0:
			cnt_blk += 1
			grid[pos_x][pos_y] = 1
			dir = (dir + 1) % 4
		else:
			cnt_blk -= 1
			grid[pos_x][pos_y] = 0
			dir = (dir + 4 - 1) % 4
		pos_x += move_x[dir]
		pos_y += move_y[dir]
		step_cnt += 1
	return cnt_blk


def langtons_ant(n):
	grid = [[0]]
	column = 0
	row = 0
	direction = 0
	move = {0: (-1, 0), 1: (0, 1), 2: (1, 0), 3: (0, -1)}
	rows = len(grid)
	cols = len(grid[0])
	ap = (row, column)
	dir = direction
	n_black = 0
	max_simple_range = 11000
	n_black_highway_ref = []
	ref = 0
	for i in range(1, n + 1):
		if grid[ap[0]][ap[1]] == 1:
			grid[ap[0]][ap[1]] = 0
			dir = (dir + 1) % 4
			n_black -= 1
		else:
			grid[ap[0]][ap[1]] = 1
			dir = (dir - 1) % 4
			n_black += 1
		ap = (ap[0] + move[dir][0], ap[1] + move[dir][1])
		if ap[0] >= rows:
			grid = grid + [[0] * cols]
			rows += 1
		elif ap[0] < 0:
			grid = [[0] * cols] + grid
			rows += 1
			ap = (0, ap[1])
		if ap[1] >= cols:
			for (j, r) in enumerate(grid):
				grid[j] = r + [0]
			cols += 1
		elif ap[1] < 0:
			for (j, r) in enumerate(grid):
				grid[j] = [0] + r
			cols += 1
			ap = (ap[0], 0)
		if i >= max_simple_range:
			if i == max_simple_range:
				ref = n_black
			n_black_highway_ref.append(n_black - ref)
			if i == max_simple_range + 104:
				break
	if n > max_simple_range + 104:
		n_black += n_black_highway_ref[-1] * ((n - max_simple_range) // 104 - 1)
		n_black += n_black_highway_ref[(n - max_simple_range) % 104]
	return n_black


def langtons_ant(n):

	def ant(n):
		di = 'ULDR'
		tbl = {(0, 0): 0}
		turn = 1
		pos = di[0]
		(x, y) = (0, 0)
		for i in range(n):
			if (x, y) not in tbl.keys():
				tbl[x, y] = 0
			cur = tbl[x, y]
			turn = 1 if cur == 1 else 0
			cur = 0 if cur == 1 else 1
			pos = di[(4 + di.index(pos) + (-1 if turn else 1)) % 4]
			tbl[x, y] = cur
			if pos == 'U':
				y -= 1
			elif pos == 'R':
				x -= 1
			elif pos == 'D':
				y += 1
			elif pos == 'L':
				x += 1
		rez = sum(tbl.values())
		return rez
	if n > 10000:
		y = (n - 10000) % 104
		yy = (n - 10000) // 104
		x = yy * 12 + ant(y + 10000)
	else:
		x = ant(n)
	return x


def ant(G, c, r, n, d=0, R=range, L=len, P=(-1, 0, 1, 0)):
	for _ in R(n):
		(h, w, v) = (L(G), L(G[0]), G[r][c])
		G[r][c] = (v + 1) % 2
		d += (-1, 1)[v]
		(r, c) = (r + P[d % 4], c + P[::-1][d % 4])
		if w == c:
			for i in R(L(G)):
				G[i] += [1]
		if h == r:
			G += [[1] * w]
		if c < 0:
			for i in R(L(G)):
				G[i] = [1] + G[i]
			c = c + 1
		if r < 0:
			(G, r) = ([[1] * w] + G, 0)
	return G

def langtons_ant(n, z=0):
	if 11000 < n:
		z = (n - 11000) // 104 * 12
		n = (n - 11000) % 104 + 11000
	return sum(ant([[1]], 0, 0, n, d=0, R=range, L=len, P=(-1, 0, 1, 0)), []).count(0) + z