def gen_taboos(warehouse):

    taboo = []

    #go along the walls and find corners
    for (x,y) in warehouse.walls:
        #if we have a gap on the right, ( left wall ) and a wall above or below that:
        if (x+1,y) not in warehouse.walls and (
        (x+1,y+1) in warehouse.walls or (x+1,y-1) in warehouse.walls):
            taboo.append((x+1,y))

        #and for the gap on the left ( right wall ) yadda yadda
        if(x-1,y) not in warehouse.walls and (
        (x-1,y+1) in warehouse.walls or (x-1,y-1) in warehouse.walls):
            taboo.append((x-1,y))


    #remove any taboos that are targets
    taboo = [t for t in taboo if t not in warehouse.targets]


    #check if outside play area
    botmost = max(warehouse.walls, key=lambda x:x[1])[1] + 1
    rigmost = max(warehouse.walls, key=lambda x:x[0])[0] + 1

    #for each taboo, raycast to the top/bot/right/leftmost walls
    removal = []
    for t in taboo:
        cx,cy = t[0],t[1]
        raycast = []        #raycast ( direction, target )
        vert_ray = True
        hori_ray = True

        if(cx,cy+1) in warehouse.walls: # wall is below us
            raycast = (-1,0)
        else:
            raycast = (1,botmost)

        for i in range(cy,raycast[1],raycast[0]):
            if(cx,i) in warehouse.walls:
                vert_ray = False
                break

        if(cx+1,cy) in warehouse.walls: #wall is to the right
            raycast = (-1,0)
        else:
            raycast = (1,rigmost)

        for i in range(cx,raycast[1],raycast[0]):
            if(i,cy) in warehouse.walls:
                hori_ray = False
                break

        if hori_ray or vert_ray:
            removal.append(t) #see note below

    #remove all that are marked for removal
    #note: could not do in loop due to loop index skipping over dead elements.

    taboo = [t for t in taboo if t not in removal]


    taboo_pairs = []
    for t in taboo:
        for T in taboo:
            if (T[0] == t[0] or t[1] == T[1]) and T is not t:
                if [T,t] not in taboo_pairs or [t,T] not in taboo_pairs:
                    taboo_pairs.append([t,T])

    for pair in taboo_pairs:

        wall_check = 0      #wall runner
        gap = False     #a gap was found ( not taboo )
        a,b = pair[0],pair[1]   #each taboo

        if(a[0] == b[0]): #x components are the same, so check along y
            # (2,2) -> (2,6)

            if(a[0]+1,a[1]) in warehouse.walls: #check which side wall is on
                wall_check=a[0]+1
            else:
                wall_check=a[0]-1

            #run along wall, see if there's a gap
            for i in range(a[1],b[1]):
                if (wall_check,i) not in warehouse.walls or (a[0],i) in warehouse.walls or (a[0],i) in warehouse.targets:
                    gap = True

            #if we didn't have a gap, paint the entire wall
            if not gap:
                for i in range(a[1],b[1]):
                    taboo.append((a[0],i))


        else: #check along x direction
            if(a[0],a[1]+1) in warehouse.walls: #check which side wall is on
                wall_check=a[1]+1
            else: #it was on the other side
                wall_check=a[1]-1

            for i in range(a[0],b[0]):
                if (i,wall_check) not in warehouse.walls or (i,a[1]) in warehouse.walls or (i,a[1]) in warehouse.targets:
                    gap = True

            if not gap:
                for i in range(a[0],b[0]):
                    taboo.append((i,a[1]))



    #return the entire list of taboo tuples
    return taboo


def taboo_cells(warehouse):
    '''
    Identify the taboo cells of a warehouse. A cell is called 'taboo'
    if whenever a box get pushed on such a cell then the puzzle becomes unsolvable.
    When determining the taboo cells, you must ignore all the existing boxes,
    simply consider the walls and the target  cells.
    Use only the following two rules to determine the taboo cells;
     Rule 1: if a cell is a corner and not a target, then it is a taboo cell.
     Rule 2: all the cells between two corners along a wall are taboo if none of
             these cells is a target.

    @param warehouse: a Warehouse object

    @return
       A string representing the puzzle with only the wall cells marked with
       an '#' and the taboo cells marked with an 'X'.
       The returned string should NOT have marks for the worker, the targets,
       and the boxes.
    '''

    taboo = gen_taboos(warehouse)

    #zip it up
    #shamelessly copied from example code
    X,Y = zip(*warehouse.walls)
    x_size, y_size = 1+max(X), 1+max(Y)
    vis = [[" "] * x_size for y in range(y_size)]
    for (x,y) in warehouse.walls:
        vis[y][x] = "#"
    for (x,y) in taboo:
        vis[y][x] = "X"
    return "\n".join(["".join(line) for line in vis])