Reinstalling a Hardwood Floor

Thankfully, this is not a story about one of my home improvement projects.  This is a story about programming.

To deal with a termite problem, my father-in-law recently had to tear out a portion of his living room floor.  His work in the crawlspace is nearing an end and he is ready to put the hardwood floor back into place.

Problem one: When tearing out the floor he was not anal retentive and did not mark where each piece originated.

Problem two: Not all of the pieces survived the removal and a new bundle of pieces was purchased having different lengths than the originals they are replacing.

The real problem: How do we figure out which pieces need to go where to reassemble the floor?

My father-in-law is an educated man and quickly realized that this might just be a job for a computer. He measured the lengths of all the pieces and entered them in Excel.  His question to me: was there a way to get Excel to take the list of piece lengths and pick groups of lengths that would sum to the width of his living room?  This got my brain turning right away because I too realized this was the kind of problem computers were made to solve.

I know there are a lot of programmer types out there that find the lay-man's reliance on Excel maddening.  Many of these complaints I also agree with but I do not share in their derision of those Excel-users.  Excel is, well, an excellent first programming tool.  Each cell is a variable, iteration can be done by repeating the formulas down the page using previous results, and for many people I suspect it makes abstract lines of code more concrete and understandable.  "I want to multiply this value by that value to find the interest rate and see how that will impact my mortgage payments."

Excel is a victim of its own success, though.  It is so easy use that it can quickly provide users with more than enough rope to hang themselves.  And because many many of its users do not feel ready to jump into more traditional programming languages (or even dip their toes into the built-in, full-fledged Visual Basic scripting/macro/programming environment), Microsoft tries to do what it can to make that hanging less certain.  Features like dependency tracing, input validation, and error checking are all essentially debugging tools built into the program so users that have this one hammer can be more efficient and using it on all the nails they may find.

So I'm not surprised that my father-in-law turned to Excel and I'm glad he did.  But my answer to him was that I didn't think Excel was the right tool for this job and I offered to see if I could put my modest programming skills to use.

For those of you playing along at home here are the details:

• The total length of the living room is 184 inches.  Due to floor moulding on both ends, the accepted length for a giving run of pieces is 183 to 185 inches.
• Due to the way the floor is assembled, there are specific pieces that must be used to start a run on one end of the room and specific pieces that must be used to end a run.
• It will take twenty runs laid side-by-side to reinstall the floor. 
• My father-in-law has already determined that there is enough wood to reinstall the floor but no guarantee that it has been cut in appropriate lengths.  This is to say, we don't know if there is actually a solution to the problem so it might be a good idea to find the best solution.  For our purposes, the best solution will be the one that completes the most runs with the given pieces.

So get to it my friends.  Here is a list of the lengths we have to work with. Let the iterations begin!

Starting pieces
Middle pieces
Ending pieces

(Right now, only 13 start and finish pieces are given.  I'm in communication with my father-in-law as to why this is the case.)

2013-12-08 Update: I've confirmed with my father-in-law that the list of 13 start and finish pieces is not an error.  The other seven runs will start and finish with middle pieces.

2013-12-12 Update: Follow-up article here.