Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
With collections.Counter and cutting generator solution in Clear category for Most Efficient Cutting by Phil15
from collections import Counter
def cutting_generator(bom):
s = sum(bom.elements())
if s <= 6000: # Easiest case
yield 6000 - s if s>0 else 0
else:
# We are building decreasing possible lists of maximum lengths
# with sum(possible_list) <= 6000
maxi = max(bom) # First element
possibilities = [[maxi]]
while possibilities:
new_pos = []
for pos in possibilities:
pos_is_not_extended = True
# With Counter, difference is simple.
# With keys, we don't look twice with same elements.
for elem in (bom - Counter(pos)).keys():
# decreasing list and sum(new_possibility) <= 6000
if elem <= pos[-1] and sum(pos) + elem <= 6000:
new_pos.append(pos + [elem])
pos_is_not_extended = False
if pos_is_not_extended:
# We can't extend 'pos' so we yield this possible cutting
# and it disappears from possibilities.
yield (6000 - sum(pos)
+ most_efficient_cutting(bom - Counter(pos)))
possibilities = new_pos
most_efficient_cutting = lambda bom: min(cutting_generator(Counter(bom)))
Sept. 7, 2018
