import random, collections

sizes = [6, 6.6, 7.2, 7.8, 8.4, 9.6, 12]

beams = {
    3.6: 6,
    6.7: 37,
    5.5: 4,
    7.2: 37,
    1.1: 2,
    3.2: 9,
    2.9: 2,
    4.6: 3,
    4.9: 15,
    1.2: 10,
    5.9: 4,
    4.3: 4,
    1.5: 1,
    2.2: 2,
    3.1: 4,
    3.4: 4,
    1: 4,
    1.6: 2,
    1.8: 3,
    1.9: 2,
}

sizes = [float(x) for x in sizes]
beams = [float(x) for k, v in beams.items() for x in [k] * v]

def greedy_asc(size, beams):
    return greedy_beam(size, sorted(beams))


def greedy_des(size, beams):
    return greedy_beam(size, sorted(beams, reverse=True))


def greedy_shuffle(size, beams):
    random.shuffle(beams)
    return greedy_beam(size, beams)


def greedy_beam(size, beams):
    used = []
    for b in beams:
        if b > size:
            continue
        size -= b
        used.append(b)
    if not used:
        return 100, used
    return (size, used)


def generate_order(sizes, beams):
    beams = beams[:]
    total_wastage = 0
    order = []
    while beams:
        best = (100, 100, [])
        for s in sizes:
            for f in [greedy_asc, greedy_des, greedy_shuffle]:
                waste, used = f(s, beams)
                if waste < best[0]:
                    best = (waste, s, sorted(used))
        total_wastage += best[0]
        order.append(best)
        for b in best[2]:
            beams.remove(b)
    return (total_wastage, order)


best = (100, [])
for i in range(1000):
    if i % 50 == 0:
        print(i, "...")
    cand = generate_order(sizes, beams)
    if cand[0] < best[0]:
        best = cand
        print("candidate order %d with wastage %.1f" % (i, cand[0]))
print()

counts = collections.defaultdict(int)
summary = collections.defaultdict(int)
orders = sorted((size, waste, order) for waste, size, order in best[1])
for size, waste, order in orders:
    counts[size] += 1
    summary[
        ("beam size %.1f for beams %s with wastage %.1f" % (size, order, waste))
    ] += 1

print("order description:")
for s, count in sorted(summary.items()):
    print(count, "x", s)
print()

print("order summary:")
for s, count in sorted(counts.items()):
    print(count, "x", s)
print()

print("total wastage %.1f" % best[0])