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.
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

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
