691.py

#!/usr/bin/env python3
import fractions
import itertools
import random

sample_size = 200
random.seed(44944755)
new_possible_holes = []
possible_holes = [[(fractions.Fraction(1, 1), fractions.Fraction(1, 1))]]

def add_possibilities(holes, rect_x, rect_y):
    for hole in holes:
        hole_x, hole_y = hole

        if rect_x <= hole_x and rect_y <= hole_y:
            # It fits, place the rectangle in the bottom left corner of the hole.
            # There will be two new holes, one above the new rectangle and one to the right.
            # The upper right corner of the hole can be assigned to each of them.
            new_holes1 = list(holes)
            new_holes1.remove(hole)
            new_holes2 = list(new_holes1)

            # The first new hole is to the right of the new rectangle.
            if rect_x != hole_x:
                new_holes1.append((hole_x - rect_x, rect_y))
                new_holes2.append((hole_x - rect_x, hole_y))

            # The second one is horizontal, above the new rectangle.
            if rect_y != hole_y:
                new_holes1.append((hole_x, hole_y - rect_y))
                new_holes2.append((rect_x, hole_y - rect_y))

            new_possible_holes.append(new_holes1)
            new_possible_holes.append(new_holes2)

def add_all_possibilities(rect_x, rect_y):
    for holes in possible_holes:
        add_possibilities(holes, rect_x, rect_y)

for i in itertools.count(1):
    rect_x = fractions.Fraction(1, i)
    rect_y = fractions.Fraction(1, i + 1)
    add_all_possibilities(rect_x, rect_y)
    add_all_possibilities(rect_y, rect_x)

    if new_possible_holes:
        print("Put", i, "rectangles.")

        if len(new_possible_holes) > sample_size:
            possible_holes = random.sample(new_possible_holes, sample_size)
        else:
            possible_holes = new_possible_holes

        new_possible_holes = []
    else:
        break