Prob 17

17.py

def add_to_list(w, in_boxes):
    if len(in_boxes) == 0:
        return [1.0-w]
    else:
        boxes = in_boxes[:]
        max_box = max(boxes)
        if w >= max_box and w != 0.0:
            boxes.append(1.0-w)
            return boxes
        else:
            boxes.remove(max_box)
            boxes.append(max_box-w)
            return boxes


def fill_boxes(n1, w1, n2, w2, n3, w3):
    T = [[([[]] * (n3+1)) for j in range(n2+1)] for i in range(n1+1)]
    print(T)
    for i in range(n1+1):
        for j in range(n2+1):
            for k in range(n3+1):
                if i != 0 or j != 0 or k != 0:
                    poss1 = add_to_list(w1, T[i-1][j][k])
                    poss2 = add_to_list(w2, T[i][j-1][k])
                    poss3 = add_to_list(w3, T[i][j][k-1])
                    a = len(poss1)
                    b = len(poss2)
                    c = len(poss3)
                    if a <= b and a <= c:
                        T[i][j][k] = poss1
                    elif b <= a and b <= c:
                        T[i][j][k] = poss2
                    elif c <= a and c <= b:
                        T[i][j][k] = poss3
                    else:
                        print(a, b, c)
                        print(i,j,k)
                        raise
    result = T[n1][n2][n3]
    for i in range(n1+1):
        print('{}: {}'.format(i, '\n'.join(['\t'.join([str(x) for x in row]) for row in T[i]])))

    print
    print(result)    
    return len(result)

assert(add_to_list(1.0, []) == [0.0])
assert(add_to_list(1.0, [0.0]) == [0.0, 0.0])
print(add_to_list(0.5, [0.8, 0.3]) == [0.3, 0.3])
print(add_to_list(0.5, [0.8, 0.3]) == [0.3, 0.3])

assert(fill_boxes(1, 1.0, 1, 0.0, 1, 0.0) == 1)
# assert(fill_boxes(1, 0.8, 1, 0.5, 1, 0.3) == 2)
# fill_boxes(2, 0.5, 1, 0.3, 1, 0.2)