*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!*

Difficulty: introductory

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)

# precalculate results
LIMIT = 11000        # > 9977 + 104
CACHE = [0]
GRID  = set()        # empty grid
x , y  = 0, 0        # ant's position
dx, dy = 1, 0        # direction

for _ in range(LIMIT +1):
    if (x, y) in GRID:      # square is black
        GRID.remove((x, y))
        dx, dy = -dy, dx
    else:                   # square is white
        GRID.add((x, y))
        dx, dy = dy, -dx

    # move forward
    x += dx
    y += dy
    
    # store number of black squares
    CACHE.append(len(GRID))


def langtons_ant(n):
    if n < LIMIT:
        return CACHE[n]
    
    # a(n+104) = a(n) + 12 for n > 9976
    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:
    
        # Check if reached steady state for step count > 10000 
        # and when remaining steps evenly divisible by cycle of 104
        if step_cnt > 1e4 and step_cnt % 104 == n%104:
            prev_cnt.append(cnt_blk)
            
            # If previous 5 black square counts have same difference, 
            # assume in cycle
            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 in cycle, add up difference for however many steps 
                # left until n and then break out of walk simulation
                if cycle_flg:
                    cnt_blk += int(diff * (n-step_cnt)//104)
                    break
    
        # If on white square, flip to black and turn clockwise
        if grid[pos_x][pos_y] == 0:
            cnt_blk += 1
            grid[pos_x][pos_y] = 1
            dir = (dir+1)%4
        # If on black square, flip to white and turn counter-clockwise
        else:
            cnt_blk -= 1
            grid[pos_x][pos_y] = 0
            dir = (dir+4-1)%4
        
        # Advance one square based on new direction
        pos_x += move_x[dir]
        pos_y += move_y[dir]
        
        # Increment step counter
        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}
  # 1= clock 0 = anticlock
    turn=1
    pos=di[0]
    x,y=0,0
    for i in range(n):
      #print("curr",x,y)

      if (x,y)  not in tbl.keys():
        tbl[(x,y)]=0
      cur=tbl[(x,y)]
     #print("color",cur)

      turn = 1 if cur==1 else 0
      cur = 0 if cur == 1 else 1
      #print((4 + di.index(pos) + (1 if turn else -1)) % 4)
 
      pos = di[(4 + di.index(pos) + (-1 if turn else 1)) % 4]
      #print(pos)
      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
    #print(y+10000)
    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