import svgwrite
from copy import copy

colours = [
('purple','purple'),
('magenta','magenta'),
('yellow','yellow'),
('lightpink','lightpink'),
('cyan','blue'),
('navy','midnightblue'),
('green','darkgreen'),
('red','darkred'),
('slategray','slategray'),
('orange','orange'),
('lightgreen','lightgreen'),
('whitesmoke','slategray')
]

pieces_s = """
....

..
 ..
  .

...
. .

....
 .

...
.
.

....
.

..
 ...

...
..

 .
...
 .

...
.

..
..

..
.
"""

def print_piece(piece):
	w,d,h,ps = piece
	print(piece)
	for z in range(h):
		for y in range(z & 1, d, 2):
			s = [' '] * w
			for x in range(z & 1, w, 2):
				if ((z,x,y) in ps):
					s[x] = '*'
			print(''.join(s))
		print('----')

def make_piece(p):
	""" make piece (w,d,h,[(z,x,y)]) -- with extra spaces for lattice"""
	rows = p.split('\n')
	d = (len(rows) - 1) * 2 + 1
	mx = 0
	sparse = []
	for y,r in enumerate(rows):
		for x,i in enumerate(r):
			if i == '.':
				if x > mx:
					mx = x
				sparse.append((0,x*2,y*2))
	sparse.sort()
	return ((mx*2)+1,d,1,sparse)

pieces = [make_piece(p) for p in pieces_s[1:-1].split('\n\n')]

def rotate_right(p):
	w,d,h,s = p
	wo = w
	if (wo & 1):
		wo -= 1
	rs = [(z,y,wo-x) for z,x,y in s]
	rs.sort()
	return (d,w,h,rs)

def _rotate_xy_z(b):
	"""assuming z == 0"""
	z,x,y = b
	x2 = x//2
	y2 = y//2
	xy = x2 + y2
	z_ = x2 - y2
	return (z_,xy,xy)

def rotate_up(p):
	"""rotate 90degrees around x = y, z = 0"""
	w,d,h,s = p
	rs = [_rotate_xy_z(b) for b in s]
	rs.sort()
	min_z = rs[0][0]
	min_xy = min([x for z,x,y in rs])
	xyo = -(min_z & 1)
	if (min_xy+xyo < 0):
		xyo += 2
	rsa = [(z-min_z,x+xyo,y+xyo) for z,x,y in rs]
	max_z = rs[-1][0]
	wd = max([x for z,x,y in rsa]) + 1
	return (wd,wd,max_z-min_z+1,rsa)

def _all_rotations(p):
	c = p
	for r in range(4):
		yield c
		ru = rotate_up(c)
		yield ru
		yield rotate_right(ru)
		c = rotate_right(c)

def rotations(p):
	a = [r for r in _all_rotations(p)]
	a.sort()
	c = a[0]
	ret = [c]
	for r in a[1:]:
		if c != r:
			ret.append(r)
		c = r
	return ret

BASE = 5
LIMIT = BASE * 2 - 1

def in_lattice(z,x,y):
	"""check if a point is in the lattice"""
	layers = BASE
	min_xy = z
	limit_xy = LIMIT - z
	odd = z & 1
	return ((z >= 0 and z < layers)
		and (odd == x & 1 and odd == y & 1)
		and (x >= min_xy and x <= limit_xy)
		and (y >= min_xy and y <= limit_xy))

def valid_piece_offset(zo,xo,yo,piece):
	"""check a piece at that place in the lattice is valid"""
	w,d,h,ps = piece
	for z,x,y in ps:
		if (not in_lattice(z+zo,x+xo,y+yo)):
			return False
	return True

def _offset_is_used(zo,xo,yo,piece,used):
	w,d,h,ps = piece
	for z,x,y in ps:
		if used[zo+z][xo+x][yo+y]:
			return True
	return False

def _use(zo,xo,yo,piece,used):
	w,d,h,ps = piece
	for z,x,y in ps:
		used[zo+z][xo+x][yo+y] = True

def _unuse(zo,xo,yo,piece,used):
	w,d,h,ps = piece
	for z,x,y in ps:
		used[zo+z][xo+x][yo+y] = False

def _is_used(point, used):
	z,x,y = point
	return used[z][x][y]

candidates = [rotations(p) for p in pieces]
p = pieces[-1]
candidates[-1] = [p, rotate_up(p), rotate_right(rotate_up(p))]

# all the positions an item can take
places = []
for z in range(BASE):
	for x in range(z, LIMIT-z, 2):
		for y in range(z, LIMIT-z,2):
			places.append((z,x,y))

def make_empty_used():
	return [[[False for y in range(LIMIT)] for x in range(LIMIT)] for z in range(BASE)] #dense (ish) used matrix

def fs(pc,used,placed,result,solutions):
	"""find a piece to fill place pc
	NOTE: assumes that places[pc] is not used"""
	z,x,y = places[pc]
	for p,piece in enumerate(candidates):
		if p in placed:
			continue
		for r,rotation in enumerate(piece):
			w,d,h,points = rotation
			fz,fx,fy = points[0]
			xo = x - fx
			yo = y - fy
			zo = z - fz
			if (valid_piece_offset(zo,xo,yo,rotation) and
				not _offset_is_used(zo,xo,yo, rotation, used)):
				result.append((pc,p,r))
				if len(result) == len(candidates):
					solutions.append(copy(result))
					result.pop()
					return
				if len(result) == 3: #increase this number for more logging output
					print(len(solutions),result)
				_use(zo,xo,yo, rotation, used)
				placed.append(p)
				#find next available point
				npc = pc + 1
				while _is_used(places[npc],used):
					npc += 1
				fs(npc, used, placed, result, solutions)
				placed.pop()
				_unuse(zo,xo,yo, rotation, used)
				result.pop()
	return

used = make_empty_used()
placed = []
result = []
solutions = []
# TAKES approx 8 minutes on Core i7-7660U
# to find the first solution (estimate 4 hours for
# all solutions - including mirror but not rotational
# symmetry)
fs(0,used,placed,result,solutions)

# Ready made solution
#stack = [0, 1, 5, 8, 10, 13, 16, 18, 20, 26, 32, 42]
#result = [(0, 1), (5, 0), (9, 2), (7, 7), (11, 0), (2, 7), (10, 0), (6, 3), (3, 6), (1, 6), (4, 5), (8, 2)]
#result = zip(stack, result)
result = solutions[0]


def zorder(solution):
	"""make a list of bits of objects in z-order,y-order
	[(z,y,x,p)]"""
	out = []
	for pc,p,r in solution:
		w,d,h,points = candidates[p][r]
		z,x,y = places[pc]
		fz,fx,fy = points[0]
		xo = x - fx
		yo = y - fy
		zo = z - fz
		for zp,xp,yp in points:
			out.append((zp+zo,yp+yo,xp+xo,p))
	out.sort()
	return out

def svg(solution):
	out = zorder(solution)
	dwg = svgwrite.Drawing('test.svg', profile='full')
	filtr = svgwrite.filters.Filter(id="Shadow", start=(0, 0), size=('200%', '200%'), filterUnits="userSpaceOnUse")
	filtr.feOffset("SourceAlpha", result="offOut", dx="20", dy="20" )
	filtr.feGaussianBlur("offOut", result="blurOut", stdDeviation="10" )
	filtr.feBlend("SourceGraphic", in2="blurOut", mode="normal" )
	dwg.defs.add(filtr)
	for z,y,x,p in out:
		fill, stroke = colours[p]
		shape = dwg.add(dwg.circle((60+x*100-z*10,60+y*100-z*25), 60, stroke=stroke, fill=fill))
		shape['filter'] = 'url(#Shadow)'
	return dwg

# save all the solutions as svg images
for i,solution in enumerate(solutions):
	dwg = svg(solution)
	dwg.saveas('solution_' + str(i) + '.svg')


"""
TODO:

Ways to speed this up.

Reduce search space by removing the rotations from one of the pieces.
Take a piece that has 12 rotations and only include 3. 4x speedup (Done)

Dense used matrix: zused for O(1) checks of place filled already

Work queue: Own stack for restartability and avoid all the extra used checking


"""