# Task
 Pac-Man got lucky today! Due to minor performance issue all his enemies have frozen. Too bad Pac-Man is not brave enough to face them right now, so he doesn't want any enemy to see him. 
 
 Given a gamefield of size `N` x `N`, Pac-Man's position(`PM`) and his enemies' positions(`enemies`), your task is to count the number of coins he can collect without being seen.

 An enemy can see a Pac-Man if they are standing on the same row or column. 
 
 It is guaranteed that no enemy can see Pac-Man on the starting position. There is a coin on each empty square (i.e. where there is no Pac-Man or enemy).

# Example

 For `N = 4, PM = [3, 0], enemies = [[1, 2]]`, the result should be `3`.
```
Let O represent coins, P - Pac-Man and E - enemy.
OOOO
OOEO
OOOO
POOO```
Pac-Man cannot cross row 1 and column 2. 

 He can only collect coins from points `(2, 0), (2, 1) and (3, 1)`, like this:
 ```
x is the points that Pac-Man can collect the coins.
OOOO
OOEO
xxOO
PxOO
 ```

# Input/Output


 - `[input]` integer `N`

  The field size.


 - `[input]` integer array `PM`

  Pac-Man's position (pair of integers)


 - `[input]` 2D integer array `enemies`

  Enemies' positions (array of pairs)


 - `[output]` an integer

  Number of coins Pac-Man can collect.
  
  
# More PacMan Katas

 - [Play PacMan: Devour all](https://www.codewars.com/kata/575c29d5fcee86cb8b000136)

 - [Play PacMan 2: The way home](https://www.codewars.com/kata/575ed46e23891f67d90000d8)

Difficulty: introductory

Starter code:

def pac_man(N, PM, enemies):
	

Solutions:
def pac_man(size, pacman, enemies):
    px, py = pacman
    mx, my, Mx, My = -1, -1, size, size
    for x, y in enemies:
        if x < px and x > mx: mx = x
        if y < py and y > my: my = y
        if x > px and x < Mx: Mx = x
        if y > py and y < My: My = y
    return (Mx - mx - 1) * (My - my - 1) - 1

def pac_man(N, PM, enemies):
    dims = [[0,N], [0,N]]   # [[minX, maxX], [minY, maxY]]
    for pos in enemies:
        for i,x in enumerate(pos):
            if PM[i] > x: dims[i][0] = max(dims[i][0], x+1)
            else:         dims[i][1] = min(dims[i][1], x)
    return (dims[0][1]-dims[0][0]) * (dims[1][1]-dims[1][0]) - 1

def pac_man(n, pm, enemies):
    # Build initial grid
    # O open, P Pacman, E enemy, # Enemy line of sight
    row = lambda c="O": [c] * n
    grid = [row() for _ in range(n)]
    grid[pm[0]][pm[1]] = "P"
    for er, ec in enemies:
        grid[er] = row("#")
        grid = [["#" if c == ec else v for c, v in enumerate(r)] for r in grid]
    for er, ec in enemies:
        grid[er][ec] = "E"
    
    # Perform a flood fill detecting O and converting to . starting from PM
    edges = [pm]
    count = 0
    while edges:
        new_edges = []
        for er, ec in edges:
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                r, c = er + dr, ec + dc
                if 0 <= r < n and 0 <= c < n:
                    if grid[r][c] == "O":
                        count += 1
                        grid[r][c] = "."
                        new_edges.append((r, c))
        edges = new_edges
    return count

def pac_man(N, PM, enemies):
  borders=[[-1, 0], [0, -1], [-1, N-1], [N-1, -1], [N, 0], [N, N-1], [0, N], [N-1, N]]
  for n in range(1, N-1):
      borders.append([-1, n])
      borders.append([n, -1])
      borders.append([n, N])
      borders.append([N, n])
  ghosts=[]
  for i in enemies:
      x=i[0]
      y=i[1]
      for n in range(N):
          ghosts.append([x, n])
          ghosts.append([n, y])
  possibilities=[]
  moved=[PM]
  while moved != []:
      moved2=moved
      moved=[]
      for i in moved2:
          x=i[0]
          y=i[1]
          mon=[[x, y+1], [x, y-1], [x+1, y], [x-1, y]]
          for m in mon:
              if m not in borders and m not in ghosts:
                  if m not in possibilities and m not in moved and m != PM:
                      possibilities.append(m)
                      moved.append(m)
  return len(possibilities)

import numpy as np


def count(gamefield, PM , N):
    gamefield[PM[0], PM[1]] = -1
    case1 = 0
    case2 = 0
    case3 = 0
    case4 = 0
#recursive case    
    if (PM[0] + 1) < N and gamefield[PM[0] + 1, PM[1]] != -1:  
        case1 = 1 + count(gamefield, [PM[0]+1, PM[1]], N)
    if (PM[0] - 1) > -1 and gamefield[PM[0] - 1, PM[1]] != -1:
        case2 =  1 + count(gamefield, [PM[0]-1, PM[1]], N)
    if (PM[1] + 1) < N and gamefield[PM[0], PM[1] + 1] != -1:
        case3 = 1 + count(gamefield, [PM[0], PM[1] + 1], N)
    if (PM[1] - 1) > -1 and gamefield[PM[0], PM[1] - 1] != -1:
        case4 = 1 + count(gamefield, [PM[0], PM[1] - 1], N)
    
    return (case1 + case2 + case3 + case4)





def pac_man(N, PM, enemies):
  #coding and coding..
    #base case 1
    if N == 1:
        return 0
    #base case 2
    if len(enemies) == 0:
        return (N**2) - 1
    
    gamefield = np.ones((N,N))
    gamefield[PM[0], PM[1]] = 7#PM
    

    for e in enemies:
        gamefield[:, e[1]] = -1#enemy
        gamefield[e[0], :] = -1#enemy
    print(gamefield)
    
  
    return count(gamefield, PM, N)


from bisect import bisect

def pac_man(n,p,es):
    if not es: return n*n-1
    l=len(es)
    y,x=list(map(sorted,list(zip(*es))))
    i=bisect(y,p[0])
    hy=y[i] if i<l else n
    ly=y[i-1] if i>0 else -1
    i=bisect(x,p[1])
    hx=x[i] if i<l else n
    lx=x[i-1] if i>0 else -1
    return (hy-ly-1)*(hx-lx-1)-1


def pac_man(n, pm, enemies):
    left, right, top, floor = -1, n, -1, n
    for y, x in enemies:
        if top < y < pm[0]: 
            top = y
        if pm[0] < y < floor: 
            floor = y
        if left < x < pm[1]: 
            left = x
        if pm[1] < x < right: 
            right = x
    return (right - left -1) * (floor - top - 1) - 1


def pac_man(N, PM, enemies):
    if not enemies:
        return N ** 2 - 1
    rows = []
    columns = []

    for i, c in enumerate(enemies):
        rows.append(c[0])
        columns.append(c[1])
    rows = sorted(rows)
    columns = sorted(columns)
    PM = list(map(lambda x: x + 1, PM))
    rows = list(map(lambda x: x + 1, rows))
    columns = list(map(lambda x: x + 1, columns))
    rows_less = list(filter(lambda a: a < PM[0], rows))
    rows_more = list(filter(lambda a: a > PM[0], rows))
    columns_less = list(filter(lambda a: a < PM[1], columns))
    columns_more = list(filter(lambda a: a > PM[1], columns))
    list(rows_more)
    if not rows_more:
        rows_more.append(N + 1)
    if not rows_less:
        rows_less.append(0)
    if not columns_more:
        columns_more.append(N + 1)
    if not columns_less:
        columns_less.append(0)
    y = min(rows_more) - max(rows_less) - 1
    x = min(columns_more) - max(columns_less) - 1

    return x*y - 1

from collections import deque

def pac_man(N, PM, enemies):
    grid = [[2] * N for i in range(N)]
    for enemy in enemies:
        for i in range(N):
            grid[enemy[0]][i] = "E"
        for j in range(N):
            grid[j][enemy[1]] = "E"
    directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    queue, ans = deque([tuple(PM)]), 0
    visited = set()
    while queue:
        node = queue.popleft()
        for dirc in directions:
            new_pos = (node[0] + dirc[0], node[1] + dirc[1])
            if 0 <= new_pos[0] < N and 0 <= new_pos[1] < N:
                if grid[new_pos[0]][new_pos[1]] == 2:
                    if new_pos not in visited:
                        ans += 1
                        visited.add(new_pos)
                        queue.append(tuple(new_pos))
    return ans - 1 if ans > 0 else 0

def pac_man(N, PM, enemies):
  print(N)
  print(PM)
  print(enemies)
  board = []
  row = []
  column = []
  if enemies == []:
      return N**2 -1
  for i in enemies:
      row.append(PM[1] - i[1])
      column.append(PM[0] - i[0])
      
  rowMinus = [(PM[1] - N) *-1]
  rowPlus = [PM[1]+1]
  columnMinus = [(PM[0] - N) *-1]
  columnPlus = [PM[0]+1]
  for i in row:
      if i<0:
          rowMinus.append(i*-1)
      else:
          rowPlus.append(i)    
  for i in column:
      if i<0:
          columnMinus.append(i*-1)
      else:
          columnPlus.append(i)
  
  ColumnD=(min(rowPlus) + min(rowMinus) -1) 
  RowD = (min(columnPlus) + min(columnMinus) -1) 
  print("x")
  print(RowD), print(columnPlus), print(columnMinus)
  print(ColumnD)
  return ColumnD*RowD -1