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: MEDIUM

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]]:
	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 itemINDEX == len(items):
		return bag
	item = items[itemINDEX]
	possibilities = PossibleCoords(bag, item, height, width)
	for p in possibilities:
		y = p[0]
		x = p[1]
		bag = FitItemInBag(bag, item, y, x)
		bag = Loop(bag, height, width, items, itemINDEX + 1)
		for i in bag:
			if max([max(i) for i in items[-1]]) in i:
				return bag
		bag = removeItem(bag, item, y, x)
	return bag

def fit_bag(height, width, items):
	bag = [[0] * width for i in range(height)]
	itemINDEX = 0
	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
	val = items[0]
	for y in range(len(grid)):
		for x in range(len(grid[0])):
			if fits_at(grid, val, y, x):
				for pos in pieces[val]:
					grid[y + pos[0]][x + pos[1]] = val
				next_list = items[1:]
				rec_solve(grid, next_list)
				if next_list == []:
					solution = deepcopy(grid)
					return
				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]]:
	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]
		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)
	bag = np.zeros((h, w), dtype=int)

	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:
		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)):
		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)