pre.handle{
      height: 2em;
      width: 4em;
      margin: auto;
      margin-bottom: 0 !important;
      background: none !important;
      
      border-radius: 0.5em 0.5em 0 0; 
      border-top: 5px solid saddlebrown;
      border-left: 5px solid saddlebrown;
      border-right: 5px solid saddlebrown;
  }

  table.example-piece{
      width: fit-content;
      height: fit-content;
      
      margin: auto;
  }

  pre.piece{
      font-size: 1.75em;
      line-height: 1.4;
      letter-spacing: 0.1em;
      
      background: none !important;
  }

  pre.bag{
      border-radius: 0.5em; 
      border:5px solid saddlebrown; 
      width: fit-content; 
      background: burlywood;
      
      font-size: 1.75em;
      line-height: 1.4;
      letter-spacing: 0.1em;
      color: white;
      text-align: center;
      
      margin: auto;
      padding: 0.2em;
      
  }
  
  pre b{
      padding: 0.1em;  
  }
  
  .a{ background: darkolivegreen; }
  .b{ background: seagreen;}
  .c{ background: limegreen; }
  .d{ background: darkgreen; }


# On a business trip, again...

I love traveling, just like everyone else. If only they were not business trips... They force me to go to places I don't want to go and listen to people that I don't care about. But, by far, the thing I hate the most is **packing my bag**.

The thing is, I can only carry one bag in the plane and I **NEED** to bring some important items. Every item is numbered and has a specific shape. Here is an example of a well-sorted bag:



11112233
14444233
14442223



Will I be able to fit all the items I need in the bag?

# Your task

Write a funtion `fit_bag(height: int, width: int, items: List[List[List[int]]]) -> List[List[int]]` that takes a bag height and width and a list of items and returns a bag with all the items in a correct place.


The pieces will be given as a square bidimensional array that represents items as follows:




1111
1
1


 → 


[
  [1, 1, 1, 1],
  [1, 0, 0, 0],
  [1, 0, 0, 0]
]




4444
444


 → 


[
  [4, 4, 4, 4],
  [4, 4, 4, 0],
]




And, as you may have guessed, the output is represented the same way as the pieces, but it will contain the numbers of all the pieces and zeroes in the case of empty spaces. The thing is, **you cannot rotate the pieces nor flip them**.




4444
444


 → 


4
44
44
44


 ✖ 




**Technical notes:**
* Items will only contain zeroes (for empty spaces) and another number that identifies the item.
* Items will not have rows or columns of zeros at the borders. If an item's matrix is of size *n*x*m*, this means the object has a bounding box of *n*x*m*.
* There will be no two items with the same number.
* There will never be more than 9 items.
* Items do not necessarily have to be one connected component.
* The only condition for your solution to be valid is that there has to be at least one instance of each requested item. There can be empty spaces (represented by zeroes) or repeated items.
* Every test case **is solvable**.

# Preloaded code

You are given two functions for debugging purposes:

* `only_show_wrong()`: disable the bag print of the test cases that you solved successfully. Use this only once at the beginning or your code.
* `print_bag(bag)`: this function prints a bag in a human-readable format for debugging purposes. It is done by default in every test case unless it is disabled.

# Tests

Here are the tests that will be done:
* **Fixed tests (respectively):** bags of sizes 3x8, 3x6, 3x5, 3x7, 3x8 and 5x9. Six tests of each with 4 to 8 items.
* **Random tests:** 300 5x9 bags tests with 7 to 9 items.

Difficulty: interview

Starter code:

def fit_bag(height:
	

Solutions:
from itertools import chain

def fit_bag(H, W, items):

    def deploy(item):
        X,Y    = len(item), len(item[0])
        v      = (set(chain.from_iterable(item))-{0}).pop()
        deltas = [(x,y) for x,r in enumerate(item) for y,n in enumerate(r) if n]
        return (len(deltas), X*Y, max(X,Y), min(X,Y), X,Y,deltas,v)
    
    def dfs(i=0):
        if i==len(items): yield bag
        _,_,_,_,X,Y,deltas,v = items[i]
        for x in range(H-X+1):
            for y in range(W-Y+1):
                if all(not bag[x+dx][y+dy] for dx,dy in deltas):
                    for dx,dy in deltas: bag[x+dx][y+dy] = v
                    yield from dfs(i+1)
                    for dx,dy in deltas: bag[x+dx][y+dy] = 0
    
    bag   = [ [0]*W for _ in range(H) ]
    items = sorted(map(deploy,items), reverse=True)
    return next(dfs())

def fit_bag(height: int, width: int, items: [[[int]]]) -> [[int]]:
    
    # sort items: largest to smallest
    get_box_size = lambda a: len(a) * len(a[0])
    items.sort(key=get_box_size, reverse=True)


    def arrange(partial_bag: [[int]], ind_item: int) -> [[int]]:
    
        if ind_item == len(items):
            return partial_bag
        
        cur_item = items[ind_item]
        for r in range(height - len(cur_item) + 1):
            for c in range(width - len(cur_item[0]) + 1):        
                if fits(partial_bag, cur_item, r, c):
                    new_bag = arrange(combine(partial_bag, cur_item, r, c) ,ind_item + 1)
                    if new_bag: return new_bag
        
        
    def fits(b1, b2, r, c) -> bool:
        for ir in range(r, r + len(b2)):
            for ic in range(c, c + len(b2[0])):
                if b1[ir][ic] and b2[ir - r][ic - c]:
                    return False
        return True
            
            
    def combine(b1, b2, r, c) -> [[int]]:
        new_bag = []
        for ir in range(height):
            new_bag.append(b1[ir][:])
        for ir in range(r, r + len(b2)):
            for ic in range(c, c + len(b2[0])):
                new_bag[ir][ic] += b2[ir - r][ic - c]
        return new_bag
    
    
    return arrange([[0] * width for _ in range(height)], 0)

def fit_bag(height: int, width: int, items: List[List[List[int]]]) -> List[List[int]]:
    result = [[0]*width for _ in range(height)]
    
    def check(i, j, item):
        return not any(x and result[i+k][j+l] for k,row in enumerate(item) for l,x in enumerate(row))
    
    def place(i, j, item):
        for k,row in enumerate(item):
            for l,x in enumerate(row):
                if x != 0:
                    result[i+k][j+l] = x
    
    def remove(i, j, item, id):
        for k,row in enumerate(item):
            for l,x in enumerate(row):
                if x == id:
                    result[i+k][j+l] = 0
    
    def rec(item_id=0):
        if item_id == len(items): return True
        item = items[item_id]
        h, w = len(item), len(item[0])
        id = next(x for row in item for x in row if x)
        for i in range(height-h+1):
            for j in range(width-w+1):
                if check(i, j, item):
                    place(i, j, item)
                    if rec(item_id+1): return True
                    remove(i, j, item, id)
        return False
    
    rec()
    return result

def ItemFitsInBag(bag, item, y0, x0):
    for y in range(y0, y0 + len(item)):
        for x in range(x0, x0 + len(item[0])):
            if bag[y][x] != 0 and item[y-y0][x-x0] != 0: return False
    return True

def removeItem(bag, item, y0, x0):
    ID = max([max(i) for i in item])
    for y in range(y0, y0 + len(item)):
        for x in range(x0, x0 + len(item[0])):
            if bag[y][x] == ID: bag[y][x] = 0
    return bag

def FitItemInBag(bag, item, y0, x0):
    for y in range(y0, y0 + len(item)):
        for x in range(x0, x0 + len(item[0])):
            if item[y-y0][x-x0] != 0: bag[y][x] = item[y-y0][x-x0]
    return bag
    
def PossibleCoords(bag, item, height, width):
    p = []
    itemHeight = len(item)
    itemWidth = len(item[0])
    for y in range(height - itemHeight + 1):
        for x in range(width - itemWidth + 1):
            if ItemFitsInBag(bag, item, y, x):
                p.append([y, x])
    return p

def Loop(bag, height, width, items, itemINDEX):
    
    # If the final item has been placed in the bag then end the loop
    if itemINDEX == len(items): return bag
      
    # Choose item
    item = items[itemINDEX]
    
    # Coordinate possibilities of item in bag
    possibilities = PossibleCoords(bag, item, height, width)
    
    # Try the possible locations to place the item in the bag
    for p in possibilities:        
        y = p[0]
        x = p[1]
        
        # Fit the item in the bag
        bag = FitItemInBag(bag, item, y, x)
        
        # Trigger backtracking
        bag = Loop(bag, height, width, items, itemINDEX + 1)
        
        # If the final item has been places then end the loop
        for i in bag:
            if max([max(i) for i in items[-1]]) in i:
                return bag
        
        # Remove the item  so that it can be differently placed 
        bag = removeItem(bag, item, y, x)
           
    return bag

def fit_bag(height, width, items):
    
    # Initialize bag with zeros
    bag = [[0] * width for i in range(height)]
    
    # Initialize item index
    itemINDEX = 0
    
    # Begin the loop
    bag = Loop(bag, height, width, items, itemINDEX)
    
    return bag

from copy import deepcopy


def insertItem(bag, item, coord):
    bag = deepcopy(bag)
    height, width = len(item), len(item[0])
    y, x = coord
    for i in range(y, y + height):
        for j in range(x, x + width):
            if item[i - y][j - x] != 0:
                bag[i][j] = item[i - y][j - x]
    return bag


def isCorrectVariant(bag, item, coord):
    height, width = len(item), len(item[0])
    y, x = coord
    for i in range(y, y + height):
        for j in range(x, x + width):
            if bag[i][j] and item[i - y][j - x] != 0:
                return False
    return True


def bags_variants(bag, item):
    bags = []
    for i in range(len(bag) - len(item) + 1):
        for j in range(len(bag[0]) - len(item[0]) + 1):
            if isCorrectVariant(bag, item, (i, j)):
                bags.append(insertItem(bag, item, (i, j)))
    return bags


def solve(bag, items):
    if not items: return bag

    for temp_bag in bags_variants(bag, items[0]):
        r = solve(temp_bag, items[1:])
        if r: return r

def fit_bag(height, width, items):
    bag = [[0] * width for _ in range(height)]
    return solve(bag, items)

from copy import deepcopy

pieces = {}
solution = []

def fits_at(grid, p, y, x):
    nonlocal pieces
    for pos in pieces[p]:
        py = y+pos[0]
        if py < 0 or py >= len(grid):
            return False
        px = x+pos[1]
        if px < 0 or px >= len(grid[0]):
            return False
        if grid[py][px] != 0:
            return False
    return True

def rec_solve(grid, items):
    nonlocal pieces, solution
    if items == [] or solution != []:
        return
    
    # fit 1st piece
    val = items[0]
    for y in range(len(grid)):
        for x in range(len(grid[0])):            
            if fits_at(grid, val, y, x):
                # piece fits
                # place piece
                for pos in pieces[val]:
                    grid[y+pos[0]][x+pos[1]] = val
                # recursive solve
                next_list = items[1:]
                rec_solve(grid, next_list)
                if next_list == []:
                    solution = deepcopy(grid)
                    return
                # remove piece
                for pos in pieces[val]:
                    grid[y+pos[0]][x+pos[1]] = 0
            

def fit_bag(height: int, width: int, items: List[List[List[int]]]) -> List[List[int]]:
    # make list of relative positions from an empty grid position
    nonlocal pieces, solution
    solution = []
    item_ids = []
    for item in items:
        i = 0
        while item[0][i] == 0:
            i += 1        
        anchor = [0,i]
        val = item[0][i]
        
        # generate list of coordinates relative to anchor
        rel_c = []
        for h in range(len(item)):
            for w in range(len(item[0])):
                if item[h][w] != 0:
                    newpos = [h,w-i]
                    rel_c.append(newpos)
        pieces[val] = rel_c
        item_ids.append(val)
    
    grid = [[0 for x in range(width)] for y in range(height)]
    rec_solve(grid, item_ids)
    return solution


def fit_bag(height: int, width: int, items: List[List[List[int]]]) -> List[List[int]]:
    bag = [[0]*width for _ in range(height)]
    return solve(bag, width, height, items)

def solve(bag, width, height, items):
    if not items:
        return bag
    item = items[0]
    item_width, item_height = len(item[0]), len(item)
    for px in range(width-item_width+1):
        for py in range(height-item_height+1):
            new_bag = place(bag, item, item_width, item_height, px, py)
            if not new_bag: continue
            solution = solve(new_bag, width, height, items[1:])
            if solution: return solution

def place(bag, item, item_width, item_height, px, py):
    for y in range(item_height):
        for x in range(item_width):
            if item[y][x] and bag[py+y][px+x]:
                return None
    new_bag = [row.copy() for row in bag]
    for y in range(item_height):
        for x in range(item_width):
            if item[y][x]:
                new_bag[py+y][px+x] = item[y][x]
    return new_bag

def fit_bag(height, width, items):
    nitems = len(items)
    blocks = sorted([(item, sum(j != 0 for i in item for j in i)) for item in items], key=lambda x: -x[1])

    def place(block_id, bag, remain):
        if block_id >= len(blocks): return
        item, item_size = blocks[block_id]
        m, n = len(item), len(item[0])
        offsets = [(i, j) for i in range(height - m + 1) for j in range(width - n + 1)]
        values = [(i, j, c) for i, row in enumerate(item) for j, c in enumerate(row) if c != 0]
        for dx, dy in offsets:
            newbag = list(map(list, bag))
            for i, j, c in values:
                if newbag[i + dx][j + dy] == 0: newbag[i + dx][j + dy] = c
                else: break
            else:
                yield newbag, remain - item_size, block_id + 1

    s = [([[0] * width for i in range(height)], height * width, 0)]
    while s:
        current, remain, block_id = s.pop()
        if block_id == nitems: return current
        for v in place(block_id, current, remain):
            s.append(v)

import numpy as np
from itertools import product

def fit_bag(h, w, items):
    items = sorted(map(np.array, items), key=lambda i: np.prod(i.shape), reverse=True) ### sort by size(area) of array by converting each item to array and sorting by product of shape(reverse)
    bag = np.zeros((h, w),dtype=int)# create zeros matrix of size of bag

    def fit_bag_rec(bag, items, n=0):    
        item = items[n]
        itemH, itemW = item.shape
        
        for i, j in product(range(h - itemH + 1), range(w - itemW + 1)):
        
            if not (bag[i:i+itemH, j:j+itemW] * item).any():
                bag[i:i+itemH, j:j+itemW] += item
                if n == len(items) - 1: yield bag
                else: yield from fit_bag_rec(bag, items, n + 1)
                bag[i:i+itemH, j:j+itemW] -= item
                
    return next(fit_bag_rec(bag, items)).tolist()

def coloque(bag,item,x,y):
    for i in range(len(item)) :
        for j in range(len(item[0])):
            if item[i][j] != 0 : bag[y+i][x+j] = item[i][j]
    return bag

def fit_recur(bag,items):
    print("\n",bag)
    item_h = len(items[0])
    item_w = len(items[0][0])
    
    for y in range(len(bag)):
        for x in range(len(bag[0])):
            if y + item_h <= len(bag) and x + item_w <= len(bag[0]):
                if sum([ (bag[y+i][x+j] == 0 or items[0][i][j] == 0) for i in range(item_h)  for j in range(item_w) ]) == item_h * item_w :
                    if len(items) > 1:
                        bag_r = []
                        for row in bag : bag_r.append(row[:])
                        bag_r = fit_recur(coloque(bag_r,items[0],x,y),items[1:])
                        if type(bag_r) == list: return bag_r
                    else: return coloque(bag,items[0],x,y)
    

def fit_bag(height: int, width: int, items: List[List[List[int]]]) -> List[List[int]]:
    bag = [[0 for i in range(width)] for j in range(height)]
    
    
    for item in items:  # First of all, if there is a null line at the border of the item, it is deleted
        while sum([ ite == 0 for ite in item[0] ]) == len(item[0])  : del item[0]
        while sum([ ite == 0 for ite in item[-1] ]) == len(item[-1])  : del item[-1]
      


    for i in range(1,len(items)):    #We sort the items to make the algorithm more eficient
        while i > 0 and  len(items[i]) >= len(items[i-1]) :
            aux = items[i]
            items[i] = items[i-1]
            items[i-1] = aux
            i = i-1
            
    print("\n Sorted items:", items , "\n")  
    
    return fit_recur(bag[:],items)