day12a.py

f = open('input.txt', 'r')
blobs = f.read().split('\n\n')
shapes = [blob.split('\n')[1:] for blob in blobs[:-1]]
rs = [line.split(' ') for line in blobs[-1].split('\n')]
bounds = [list(map(int, region[0][:-1].split('x'))) for region in rs]
counts = [list(map(int, region[1:])) for region in rs]


def rot(shape):
	grid = [list(row) for row in shape]
	new = [[] for _ in grid]

	for c in range(len(grid)):
		for r in range(len(grid)-1, -1, -1):
			new[c].append(grid[r][c])

	new = [''.join(row) for row in new]
	return new

def flip(shape):
	return [row[::-1] for row in shape]

def p(shape):
	for row in shape:
		print(row)
	print()


class Region:
	def __init__(self, bounds, cs):
		assert(len(cs) == 6)
		self.rows = bounds[0]
		self.cols = bounds[1]
		self.grid = [['.']*self.cols for _ in range(self.rows)]

		self.counts = cs
		self.solvable = None

	def can_place(self, r, c, shape):
		if r < 0 or c < 0:
			return False
		if r+len(shape) > self.rows or c+len(shape[0]) > self.cols:
			return False

		for dr in range(len(shape)):
			for dc in range(len(shape[0])):
				if self.grid[r+dr][c+dc] == shape[dr][dc] == '#':
					return False
		return True

	def place(self, r, c, shape):
		assert(self.can_place(r, c, shape))
		for dr in range(len(shape)):
			for dc in range(len(shape[0])):
				if self.grid[r+dr][c+dc] == '.' and shape[dr][dc] == '#':
					self.grid[r+dr][c+dc] = '#'

	def unplace(self, r, c, shape):
		for dr in range(len(shape)):
			for dc in range(len(shape[0])):
				if self.grid[r+dr][c+dc] == '#' and shape[dr][dc] == '#':
					self.grid[r+dr][c+dc] = '.'

	def print(self):
		for row in self.grid[::-1]:
			print(''.join(row))
		# print()

	def is_complete(self):

		return all(c == 0 for c in self.counts)

class Transforms:
	def __init__(self, shape):
		self.forms = [shape, rot(shape), rot(rot(shape)), rot(rot(rot(shape)))]
		self.forms += list(map(flip, self.forms))

	def tfm(self, idx):
		assert(0 <= idx <= 7)
		return self.forms[idx]



regions = [Region(b, c) for b,c in zip(bounds, counts)]
shlist = [Transforms(shape) for shape in shapes]


SHAPE_SIZES = [sum(c == '#' for c in ''.join(shape)) for shape in shapes]
MIN_SHAPE_SIZE = min(SHAPE_SIZES)


def count_gaps(region):
	visited = [[0]*region.cols for _ in range(region.rows)]
	grid = region.grid

	total = 0
	dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
	for r in range(region.rows):
		for c in range(region.cols):
			if visited[r][c]:
				continue
			if grid[r][c] == '#':
				continue

			group_size = 0
			q = [(r, c)]
			while q:
				curr = q.pop()
				if visited[curr[0]][curr[1]]:
					continue
				visited[curr[0]][curr[1]] = 1
				group_size += 1
				assert(grid[curr[0]][curr[1]] == '.')
				
				
				for dr, dc in dirs:
					new_r, new_c = curr[0]+dr, curr[1]+dc
					if not (0 <= new_r < region.rows and 0 <= new_c < region.cols):
						continue
					if grid[new_r][new_c] == '#':
						continue
					if visited[new_r][new_c]:
						continue
					q.append((new_r, new_c))


			if group_size < MIN_SHAPE_SIZE:
				total += group_size

	return total

def too_many_gaps(region):
	region_size = region.rows*region.cols
	sum_of_shapes = sum(a*b for a,b in zip(region.counts, SHAPE_SIZES))
	num_gaps = count_gaps(region)

	return num_gaps > region_size - sum_of_shapes

def backtrack(region):
	if too_many_gaps(region):
		return False

	if region.is_complete():
		return True

	for i in range(len(region.counts)):
		if region.counts[i] > 0:
			region.counts[i] -= 1
			for j in range(8):
				shape = shlist[i].tfm(j)
				for r in range(region.rows):
					for c in range(region.cols):
						if region.can_place(r, c, shape):
							region.place(r, c, shape)
							if backtrack(region):
								return True
							region.unplace(r, c, shape)

			region.counts[i] += 1
	return False


res = sum(backtrack(reg) for reg in regions)
print(res)