import numpy as np


def rotate(obj,axis,multiple):
	"""[ # z
		[[1,2,3], # y,x
		[4,5,6]],

		[[7,8,9],
		[10,11,12]]
	]"""
	matrices=[
		np.array([[1,0,0],[0,0,-1],[0,1,0]]),
		np.array([[0,0,1],[0,1,0],[-1,0,0]]),
		np.array([[0,-1,0],[1,0,0],[0,0,1]])
	]
	m=1
	for i in range(multiple): m=np.dot(m,matrices[axis])

	shape=np.array(obj.shape)
	shape_=abs(np.dot(shape,m))
	middle=(shape-1)/2
	middle_=(shape_-1)/2
	res=np.zeros(shape_,np.int32)

	for (z,plane) in enumerate(obj):
		for (y,row) in enumerate(plane):
			for (x,item) in enumerate(row):
				point=np.array([z,y,x])
				point_=np.dot(point-middle,m)+middle_
				res[tuple(map(int,point_))]=item

	return res


def listRotations(obj):
	rots=[(0,0),(1,1),(1,2),(1,3),(2,1),(2,3)]
	res=[]
	configs=set()

	for (axis,multiple) in rots: # každou stěnu natočíme nahoru
		obj_=rotate(obj,axis,multiple)
		for i in range(4): # a protočíme kolem z
			obj__=rotate(obj_,0,i)

			h=(obj__.shape,obj__.tobytes()) # zbavíme se symetrií
			if h not in configs:
				res.append(obj__)
				configs.add(h)

	return res


def listShifts(board,obj):
	return [
		(dz,dy,dx)
		for dz in range(board.shape[0]-obj.shape[0]+1)
		for dy in range(board.shape[1]-obj.shape[1]+1)
		for dx in range(board.shape[2]-obj.shape[2]+1)
	]


def fits(board,piece,shift):
	(dz,dy,dx)=shift
	res=[]

	for (z,plane) in enumerate(piece):
		for (y,row) in enumerate(plane):
			for (x,item) in enumerate(row):
				if item==0: continue
				coords=(z+dz,y+dy,x+dx)
				if board[coords]: return False
				res.append(coords)
	return res