Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
recursion solution in Clear category for Most Efficient Cutting by kurosawa4434
MT_LENGTH = 6000
def most_efficient_cutting(bom):
def search(bom_rest, min_waste, length_rest=MT_LENGTH, waste=0):
if waste >= min_waste or min_waste == 0:
return min_waste
if not bom_rest:
return min(waste+length_rest, min_waste)
new_min = min_waste
for b in set(bom_rest):
if length_rest - b >= 0:
i = bom_rest.index(b)
new_min = search(bom_rest[:i]+bom_rest[i+1:],
new_min, length_rest-b, waste)
else:
new_min = search(bom_rest, new_min, MT_LENGTH, waste+length_rest)
return new_min
return search(bom, len(bom)*MT_LENGTH)
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert(most_efficient_cutting([3000, 2200, 2000, 1800, 1600, 1300]) == 100)
assert(most_efficient_cutting([4000, 4000, 4000]) == 6000), "wasted: 3x2000"
assert(most_efficient_cutting([1]) == 5999), "5999"
assert(most_efficient_cutting([3001, 3001]) == 5998), "2x2999"
assert(most_efficient_cutting([3000, 2200, 1900, 1800, 1600, 1300]) == 200), "2x5900"
assert(most_efficient_cutting([3000]) == 3000)
assert(most_efficient_cutting([3000, 2200, 2000, 1800, 1600, 1400]) == 0)
print('"Run" is good. How is "Check"?')
Sept. 19, 2017
Comments: