Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
91-liner: 2 rules only solution in Clear category for Find Rectangles by przemyslaw.daniel
from itertools import product
from collections import defaultdict
from typing import Set, List, Tuple, Dict, Iterable
GRID = List[List[int]]
POINT = Tuple[int, int]
RECTANGLE = Tuple[int, int, int, int]
DOMAIN = Dict[POINT, List[Set[POINT]]]
def get_possible(grid: GRID) -> DOMAIN:
""" Collect all possible rectangles for every piece.
Every rectangle is represented as a set of points.
For example if number 3 is put into cell (0, 0)
then we have 2 possible rectangles therefore
result[(0, 0)] = [{(0, 0), (0, 1), (0, 2)},
{(0, 0), (1, 0), (2, 0)} """
height, width = len(grid), len(grid[0])
cells = set(product(range(height), range(width)))
blocks = {(x, y) for x, y in cells if grid[x][y]}
sizes = {grid[x][y] for x, y in blocks}
result = defaultdict(list)
for x, y in cells:
for h, w in product(range(height - x), range(width - y)):
if (h + 1) * (w + 1) not in sizes:
continue
rectangle = product(range(h + 1), range(w + 1))
rectangle = {(x + i, y + j) for i, j in rectangle}
common = rectangle & blocks
if len(common) != 1:
continue
xp, yp = common.pop()
if grid[xp][yp] == len(rectangle):
result[(xp, yp)] += [rectangle]
return result
def convert_to_box(rectangle: Set[POINT]) -> RECTANGLE:
""" Every rectangle is represented as a set of points
thus we have to convert it to 2 coordinates of box
with the top left corner and the bottom right corner """
xp, yp = zip(*rectangle)
return min(xp), min(yp), max(xp), max(yp)
def is_not_only_one_solution_in(result: DOMAIN) -> bool:
""" Check if there are more solutions than 1 """
return set(map(len, result.values())) != {1}
def reduce_common(cases: DOMAIN):
""" For every piece we are able to determine points that are
occupied with every solution. We know that any other piece
cannot collide with it.
For example in case when we have piece of size 2 in (0, 1)
result[(0,1)] = [{(0, 0}, (0, 1)}, {(0, 1), (0, 2)}]
point (0, 1) is always coupied that why we can remove all
other solutions containing this point """
common = {pc: set.intersection(*sol) for pc, sol in cases.items()}
for piece in cases:
banned = set.union(*[sol for pc, sol in common.items() if pc != piece])
cases[piece] = [sol for sol in cases[piece] if not sol & banned]
def reduce_joined(cases: DOMAIN, size: int):
""" Every solution has to create solid plane with all pieces.
Another worlds we have to be always able to create valid puzzle
with all number of required points """
joined = {pc: set.union(*sol) for pc, sol in cases.items()}
for piece in cases:
used = set.union(*[sol for pc, sol in joined.items() if pc != piece])
cases[piece] = [sol for sol in cases[piece] if len(sol | used) == size]
def rectangles(grid: GRID) -> Iterable[RECTANGLE]:
""" Find all rectangles """
size = len(grid) * len(grid[0])
result = get_possible(grid)
while is_not_only_one_solution_in(result):
reduce_common(result)
reduce_joined(result, size)
result = [value.pop() for value in result.values()]
return [convert_to_box(value) for value in result]
April 29, 2020
