Dynamic Programming Fail

This is a story about a failure to apply dynamic programming to a woodworking project.

I’ve been building a shed in my backyard, and for one section I decided to build the floor by laying 2x4 planks side by side. I didn’t feel the need to join them with tongue-and-groove, but I did notice that using 2x4s alone wouldn’t fit the width they were supposed to fill.

I also had some 2x6 boards left over from a different part of the shed, and I realized that gave a neat dynamic programming problem: Can you fill a given width by laying planks of standard dimensional lumber? If you have a cost for each dimension, you could also ask for the cheapest solution. Then I figured out the solution for my particular width, finding a number of 2x4s and 2x6s that exactly filled the space.

If you’re an experienced woodworker, you’ve already spotted where this idea failed. Exactness was too good to be true. The dimensions of “dimensional” lumber are just not that precise. Some of the planks I had were 1/8" larger or smaller than their advertised width.

Moreover, the planks were not perfectly straight, and that could add 1/16" to the effective width of some planks. Altogether, laying down the planks, even with clamps to make them as straight as possible, left the last 2x4 about 3/4" too long. I ended up just ripping the last board to fit the remaining space.

I think a woodworker worth their weight in salt might have instead just tongue-and-groove joined the boards, not really caring about matching the exact width, and then ripping the whole assembly at the end to fit.

But for a moment there I thought: what a fun and realistic application of dynamic programming! They should use this in introductory algorithms classes in place of the silly exact-coin-change problem. The messiness of the real world has foiled me again.