# cutlist, a nearly optimal way to cut your wood

# Introduction

I built myself a kitchen, and it had more than 30 drawers. So I went to buy the wood, but whole sheets of plywood, and a sheet has 1.25 m by 2.5 m. Since each drawer consists of six parts, it was worth to think about the process of breaking down the sheets.

The first thing to notice is that it's relatively easy to first create stripes of a particular width, and then cut the parts with a miter saw, see the schema below.

But what is the particular width and which lengths do I have to cut then? A pragmatic solution for this problem is the scope of this article.

# Preparations & expected result

First we need to agree that measures of drawer parts are not completely random. If the drawer bottom for instance is 40×60 and the height is 10, then a side is 40×10 and the other side is 60×10. To simulate this, I created an array with measures and to create a part, two samples are drawn at random.

def random_part():
    measures = [10.2, 14.2, 17.5, 56.7, 62.8, 12.3, 34.3, 12.4, 41.5]
    return random.choice(measures), random.choice(measures)

The task is now: Partition these parts so that we have many parts of one particular width, and then distribute them so that we need only a few stripes which are used optimally.

So an example output could look like this:

12.3 [[34.3, 56.7], [34.3, 56.7]]
12.4 [[10.2, 12.3, 12.3, 12.3]]
14.2 [[12.3, 14.2, 14.2, 17.5, 34.3], [10.2, 12.4, 12.4, 62.8], [12.3, 14.2]]
17.5 [[10.2, 17.5]]
34.3 [[34.3]]
41.5 [[12.4, 12.4, 14.2, 56.7], [10.2, 12.4, 12.4, 62.8], [12.3, 12.3, 62.8], [34.3, 56.7], [62.8], [62.8], [56.7]]
56.7 [[17.5, 17.5, 56.7], [34.3]]
62.8 [[10.2, 10.2, 17.5, 17.5, 34.3], [12.4, 12.4, 56.7]]

This means we need zwo stripes of 12.3 cm width and need to cut parts of 34.3 cm and 56.7 cm from each stripe, one stripe of 12.4 cm and so on.

# The methods in detail

# Partitioning

A part is a tuple (a, b). We want to have a small set of required widths (and a high number of parts per width), so the first thing I do here is to simmply count the number. This is what the counts dictionary is there for.

def partition(parts):
    counts = defaultdict(int)
    for (a, b) in parts:
        counts[a] += 1
        counts[b] += 1
        
    parts = [sorted(p, key=lambda m: -counts[m]) for p in parts]
    parts = sorted(parts, key=lambda p: p[0])
    
    return groupby(parts, key=lambda p: p[0])

Now that we know which measures occur more often it is a good idea to »rotate« the parts so that the first value of the tuple occurs more often (or as often) as the second value. This is what the first sorted() does: Sort the items by looking up their count in the dictionary. Note the - sign, that is because Python sorts ascending. But we want the bigger number to go first.

Now we can group them by the first value. groupby assumes that the iterable is sorted, so we do that. Ascending or descending does not matter in this case.

# Distributing

The idea here is to have Stripe objects which accept items (since the width is equal for each item in a stripe we can only consider the length). If there is no capacity left I want it to throw an exception. That is one of the Python principles: don't ask for permission, but expect exceptions.

As we lose capacity with each cut (the saw blade has a certain thickness) I consider the kerf as well.

class Stripe():
    def __init__(self, length=100, kerf=1, items=[]):
        self.kerf = kerf
        self.items = items
        self.length = length
        
    def insert(self, length):
        if self.capacity >= length:
            self.items.append(length)
        else:
            raise NoSpaceLeft()
        
    @property
    def capacity(self):
        return self.length - (len(self.items) - 1) * self.kerf - sum(self.items)

So we can create a new stripe of a particular length (width does not matter), insert items, and get an exception if the item does not fit.

The distribute() method is relatively simple: we maintain a list of stripes and insert the item into the first stripe which accepts the item. If no stripe accepted the item (yes, a for loop in Python also has an else which is called if the loop was not left with a break), we instantiate a new stripe which initially receives the item which could not be inserted somewhere else.

And after all we are lazy and don't want to adjust the saw after each cut, so I have a final sort which groups the items of equal width within a single stripe.

def distribute(lengths, max_length=100, kerf=1):
    stripes = []
    for l in lengths:
        for s in stripes:
            try:
                s.insert(l)
                break
            except NoSpaceLeft:
                pass
        else:
            stripes.append(Stripe(max_length, kerf, [l]))
    
    return [sorted(s.items) for s in stripes]

# The complete script

import random
from collections import defaultdict
from itertools import groupby

random.seed(0)

def random_part():
    measures = [10.2, 14.2, 17.5, 56.7, 62.8, 12.3, 34.3, 12.4, 41.5]
    return random.choice(measures), random.choice(measures)
    

def partition(parts):
    counts = defaultdict(int)
    for (a, b) in parts:
        counts[a] += 1
        counts[b] += 1
        
    parts = [sorted(p, key=lambda m: -counts[m]) for p in parts]
    parts = sorted(parts, key=lambda p: p[0])
    
    return groupby(parts, key=lambda p: p[0])

class NoSpaceLeft(Exception):
    pass

class Stripe():
    def __init__(self, length=100, kerf=1, items=[]):
        self.kerf = kerf
        self.items = items
        self.length = length
        
    def insert(self, length):
        if self.capacity >= length:
            self.items.append(length)
        else:
            raise NoSpaceLeft()
        
    @property
    def capacity(self):
        return self.length - (len(self.items) - 1) * self.kerf - sum(self.items)

def distribute(lengths, max_length=100, kerf=1):
    stripes = []
    for l in lengths:
        for s in stripes:
            try:
                s.insert(l)
                break
            except NoSpaceLeft:
                pass
        else:
            stripes.append(Stripe(max_length, kerf, [l]))
    
    return [sorted(s.items) for s in stripes]
            
    
parts = [random_part() for i in range(50)]
for width, items in partition(parts):
    lengths = [item[1] for item in items]
    stripes = distribute(lengths)
    print(width, stripes)