Golomb Enumeration for Responsive Grid Systems

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)