Golomb Enumeration for Responsive Grid Systems
ODOMOJULI
2020-07-13T07:00:00.000Z
Solomon Golomb's Rectangle Puzzle.
Originally listed:
https://wordplay.blogs.nytimes.com/2014/04/14/rectangle
def rectangle_sets(sides):
if not sides:
return [ set() ]
else:
A = min(sides)
return [ {(A, B)} | other_rects
for B in sides if B is not A
for other_rects in rectangle_sets(sides - {A, B}) ]
def total_area(rectangles): return sum(w * h for (w, h) in rectangles)
empty = (0, 0)
def Square(n):
return [[empty for col in range(n)]
for row in range(n)]
def place_rectangle_at(rect, grid, pos):
(w, h) = rect
(x0, y0) = pos
newgrid = [row.copy() for row in grid]
for x in range(x0, x0+w):
for y in range(y0, y0+h):
if y >= len(grid) or x >= len(grid[y]) or newgrid[y][x] is not empty:
return None
newgrid[y][x] = rect
return newgrid
def pack(rectangles, grid):
if not rectangles:
return grid
pos = first_empty_cell(grid)
if grid and pos:
for (rectangles2, grid2) in rectangle_placements(rectangles, grid, pos):
solution = pack(rectangles2, grid2)
if solution:
return solution
def rectangle_placements(rectangles, grid, pos):
for (w, h) in rectangles:
for rect in [(w, h), (h, w)]:
grid2 = place_rectangle_at(rect, grid, pos)
if grid2:
yield rectangles - {(w, h)}, grid2
def first_empty_cell(grid):
for (y, row) in enumerate(grid):
for (x, cell) in enumerate(row):
if cell is empty:
return (x, y)