rect.py

from fractions import gcd

def makeRect(x, y):
    return (x, y) if x < y else (y, x)

def fitsInside(larger, smaller):
    return larger[0] <= smaller[0] and larger[1] <= smaller[1]

def smallerArea(rx, ry):
    # Remember, bigger results here are still inverted.
    if rx[0] * rx[1] > ry[0] * ry[1]:
        return rx
    else:
        return ry

def simplify(n, d):
    g = gcd(n, d)
    return n // g, d // g

def egyptianSplit(n, d):
    # print "Splitting", n, d
    while n != 1:
        x = d // n + 1
        # print "Split", x
        yield x
        n, d = simplify(n * x - d, d * x)
    # print "Split", d
    yield d

def edgeMatch(r1, r2):
    return r1[0] in r2 or r1[1] in r2

def betterMatch(smaller, best, candidate):
    if best is None:
        return candidate
    elif edgeMatch(smaller, best):
        if edgeMatch(smaller, candidate):
            # Prefer using the smaller of the two boxes.
            return smallerArea(best, candidate)
        else:
            return best
    elif edgeMatch(smaller, candidate):
        return candidate
    else:
        return smallerArea(best, candidate)

def subtract(larger, smaller):
    return simplify(smaller - larger, smaller * larger)

def glueEdge(edge, larger, smaller):
    # print "Gluing", edge, larger, smaller
    n, d = subtract(larger, smaller)
    rv = set()
    for side in egyptianSplit(n, d):
        rv.add(makeRect(edge, side))
    # print "Glue results", rv
    return rv

def cutRect(larger, smaller):
    # print "Cutting", larger, smaller
    bx, by = larger
    sx, sy = smaller

    rv = set()
    # Maximize the difference in order to pick the best rects.
    longEdge = subtract(bx, sy)
    for d in egyptianSplit(*longEdge):
        rv.add(makeRect(by, d))

    shortEdge = subtract(*makeRect(by, sx))
    for d in egyptianSplit(*shortEdge):
        rv.add(makeRect(sy, d))

    # print "Cut results", rv
    return rv

def fitRect(rects, rect):
    # Exact match?
    if rect in rects:
        print "Exact match!?", rect
        rv = rects.copy()
        rv.discard(rect)
        return rv
    else:
        bestMatch = None
        for r in rects:
            if fitsInside(r, rect):
                bestMatch = betterMatch(rect, bestMatch, r)

        if bestMatch is None:
            raise Exception("Ran out of matches!")

        bx, by = bestMatch
        sx, sy = rect

        # Pop.
        rv = rects.copy()
        rv.discard(bestMatch)

        if bx == sx:
            newRects = glueEdge(bx, by, sy)
        elif by == sy:
            newRects = glueEdge(by, bx, sx)
        elif bx == sy:
            newRects = glueEdge(bx, by, sx)
        elif by == sx:
            newRects = glueEdge(by, bx, sy)
        else:
            newRects = cutRect(bestMatch, rect)

        # print "New rects", newRects

        return rv | newRects

start = set([(1, 1)])

rects = start.copy()
for i in range(1, 100):
    rect = i, i + 1
    print "Doing rect", rect
    rects = fitRect(rects, rect)
    print "I have", len(rects), "rects"
    print "Rects:", sorted(rects)