def sets_of_rectangles(sides):
    "Given exactly 10 sides, yield all sets of rectangles that can be made from them."
    A = min(sides)
    for (A, B) in each_rectangle(sides):
        for (C, D) in each_rectangle(sides - {A, B}):
            for (E, F) in each_rectangle(sides - {A, B, C, D}):
                for (G, H) in each_rectangle(sides - {A, B, C, D, E, F}):
                    for (I, J) in each_rectangle(sides - {A, B, C, D, E, F, G, H}):
                        yield {(A, B), (C, D), (E, F), (G, H), (I, J)}
                        
def each_rectangle(sides):
    "Yield all (A, B) pairs, where A is minimum of sides, and B ranges over all other sides."
    A = min(sides)
    for B in (sides - {A}):
        yield (A, B)    

sides = set(range(1, 11))
sets = list(sets_of_rectangles(sides))
len(sets)

def sets_of_rectangles(sides):
    "Given a set of sides, yield all sets of rectangles that can be made from sides."
    if sides:
        A = min(sides)
        for B in (sides - {A}):
            for rest in sets_of_rectangles(sides - {A, B}):
                yield {(A, B)}.union(rest)
    else:
        yield set()

# For example, with 6 sides:
list(sets_of_rectangles({1, 2, 3, 4, 5, 6}))

# Reaffirm the answer with 10 sides
sets = list(sets_of_rectangles(sides))
len(sets)

sets[::100]

(1 * 2) + (3 * 4) + (5 * 6) + (7 * 8) + (9  * 10)

(1 * 10) + (2 * 9) + (3 * 8) + (4 * 7) + (5 * 6)

def area(rectangle): (w, h) = rectangle; return w * h

def total_area(rectangles): return sum(area(r) for r in rectangles)

areas = {total_area(s) for s in sets}

max(areas)

min(areas)

print sorted(areas) 

set(range(110, 191)) - areas

[s for s in sets if total_area(s) in {121, 144, 169}]

len(_)

empty = (0, 0)

def Grid(width, height):
    return [[empty for col in range(width)] for row in range(height)]

def Square(size): return Grid(size, size)

Square(5)

def place_rectangle_at(rect, grid, pos):
    """Place the rectangle of size (w, h) onto grid at position (x0, y0).
    Return a new grid, or None if the rectangle cannot be placed."""
    (w, h) = rect
    (x0, y0) = pos
    newgrid = map(list, grid) # make a copy
    try:
        for x in range(x0, x0+w):
            for y in range(y0, y0+h):
                if newgrid[y][x] is not empty:
                    return None   
                newgrid[y][x] = rect
        return newgrid
    except IndexError: # went off the grid
        return None

# Place a 3 x 4 rectangle on a square grid, 2 cells over and 1 down:
place_rectangle_at((3, 4), Square(5), (2, 1))

# Place two rectangles on a grid
grid2 = place_rectangle_at((3, 4), Square(5), (2, 1))
grid3 = place_rectangle_at((2, 5), grid2, (0, 0))
grid3

# Now try to place a third rectangle that does not fit; should fail
print place_rectangle_at((6, 1), grid3, (0, 2))

def pack(rectangles, grid):
    """Find a way to pack all rectangles onto grid and return the packed grid,
    or return None if not possible."""
    if not rectangles:
        return grid # Placing no rectangles give you the original grid
    elif not grid:
        return None  # Can't put rectangles on an illegal grid
    else:
        pos = first_empty_cell(grid)
        for (w, h) in rectangles: # for each rectangle
            for rect in [(w, h), (h, w)]: # in either orientation
                grid2 = place_rectangle_at(rect, grid, pos)
                solution = pack(rectangles - {(w, h)}, grid2)
                if solution:
                    return solution
        return None
    
def first_empty_cell(grid):
    "The uppermost, leftmost empty cell position on grid."
    for (y, row) in enumerate(grid):
        for (x, cell) in enumerate(row):
            if cell is empty:
                return (x, y)

pack({(1, 3), (2, 5), (3, 4)}, Square(5))

import ipythonblocks

def show(grid):
    "Convert a python grid into an ipythonblocks BlockGrid and show it."
    (w, h) = (len(grid[0]), len(grid))
    bg = ipythonblocks.BlockGrid(w, h)
    for x in range(w):
        for y in range(h):
            bg[y,x] = color(grid[y][x])
    bg.show()
            
def color(rect):
    "Determine a color for a rectangle."
    # Base the color on the length of the sides of the rectangle
    # Choose R,G,B values to give rectangles different colors
    light = 240 # R,G,B = 240,240,240 is a light grey
    short, long = sorted(rect) # Find the short and long sides
    R, G, B = light-24*short, light-24*long, light-(50*(long%3) + 70*(short%3))
    return (R, G, B)

show(pack({(1, 3), (2, 5), (3, 4)}, Square(5)))

def show_packable(sets):
    "Given a sequence of sets of rectangles, show the ones that can be packed into a square."
    for rectangles in sets:
        A = total_area(rectangles)
        side = int(A ** 0.5)
        if side ** 2 == A:
            grid = pack(rectangles, Square(side))
            if grid:
                show(grid)

%time show_packable(sets)

import IPython.display 
import time

def pack(rectangles, grid):
    """Find a way to pack all rectangles onto grid and return the packed grid,
    or return None if not possible."""
    if not rectangles:
        return grid # Placing no rectangles give you the original grid
    elif not grid:
        return None  # Can't put rectangles on an illegal grid
    else:
        show(grid)                     # <<<<<<<<<<<<<<<< CHANGE HERE
        time.sleep(0.3)                # <<<<<<<<<<<<<<<< CHANGE HERE
        IPython.display.clear_output() # <<<<<<<<<<<<<<<< CHANGE HERE        
        pos = first_empty_cell(grid)
        for (w, h) in rectangles: # for each rectangle
            for rect in [(w, h), (h, w)]: # in each orientation
                grid2 = place_rectangle_at(rect, grid, pos)
                solution = pack(rectangles - {(w, h)}, grid2)
                if solution:
                    return solution
        return None

rectangles = {(1, 2), (3, 7), (4, 6), (5, 10), (8, 9)}
show_packable([rectangles])

from __future__ import division
import itertools, string, re

def solve_all(formula):
    """Given a formula like 'NUM + BER = PLAY', fill in digits to solve it.
    Input formula is a string; generate each digit-filled-in string."""
    for exp in replace_letters(formula.replace(' = ', ' == ')):
        if valid(exp):
            yield exp

def replace_letters(formula):
    "Generate all possible replacements of letters with digits in formula."
    letters = ''.join(set(re.findall('[A-Z]', formula)))
    for digits in itertools.permutations('1234567890', len(letters)):
        trans = string.maketrans(letters, ''.join(digits))
        yield formula.translate(trans)

def valid(exp):
    "Expression is valid iff it has no numbers with leading zero, and evals true."
    try:
        return not re.search(r'\b0[0-9]', exp) and (eval(exp) is True)
    except ArithmeticError:
        return False

% time list(solve_all('NUM + BER = PLAY'))

len(_)