• Anonymous (unregistered)

... snipped all sorts of whining and boo-hooing about metric...

Note from Alex: We use feet and inches here, not your goofy metric systems. Yeah, yeah, we all get it... metric's better, you're superior, we should all look at you because you have a snarky comment about how outdated it is, blah blah blah.

• Chendar (unregistered)

I'm not familiar enough with carpentry to understand what a splice is in this context. Is it something like each piece of board used must have one original end of the board?

• Anonymous (unregistered) in reply to Chendar
Chendar:
I'm not familiar enough with carpentry to understand what a splice is in this context. Is it something like each piece of board used must have one original end of the board?
It's just referring to a join in the wood. Header casings should be a single bit of wood, not two bits of wood joined (spliced) together. Hence the task is to figure out how many bits of wood you would need to deck out a home without any splices. I must admit, I'm having trouble summoning the enthusiasm for this one. It's far more of a maths challenge than a coding challenge.
• (cs)

16 feet = 4.88 meters 8 feet = 2.44 meters

I'm American, so I have no idea what would be standard board length in the rest of the world. Maybe 5 and 2.5 meters?

• Chendar (unregistered) in reply to Anonymous
Anonymous:
It's just referring to a join in the wood. Header casings should be a single bit of wood, not two bits of wood joined (spliced) together. Hence the task is to figure out how many bits of wood you would need to deck out a home without any splices.

Ah, I understand. I also know this problem under a different name. The bin packing problem, which is one of those pesky NP complete problems.

Some guy:
Protip: The exercise in this article has nothing to do with units. At all. Get over your fear and hatred and either comment on the exercise itself or save your comments for the next article.

Thanks, that's really helpful. Now when I see examples such as "84 + 84 + 34 can't fit in to 16" I will clear my mind of hatred and fear. Thanks. You really helped.

• ClutchDude (unregistered)

For those not sure

Imagine a single board running without a cut in it, wall to wall.

A splice occurs when the contractor, wanting to only buy min(x) amount of boards, uses "scraps" to finish that wall.

You can probably get away with this by caulking the final product to hide the seam then paint it.

Staining over the seam, on the other hand, would not look right.

For instance....we have a 4x 12'(3.67m) walls. I COULD only buy 3x 16'(4.88m) boards and use the scrap to finish the other wall. BUT....then I end up with a crappy looking seam @ 4ft & 8ft.

A good contractor would buy 4x 16'(4.87m) boards and do it right.

• The Mole (unregistered) in reply to frits

Generally wood (in the uk at least in DIY stores) is sold in multiples of 300mm, 1.2m, 2.4m or 3m being particularly common depending on what you are buying (sheet or lengths). Any similarity to lengths measured in feet are of course entirely co-incidental.

• shaggs (unregistered)

This is a classic bin packing problem:

http://en.wikipedia.org/wiki/Bin_packing_problem

• Ramses So let it be written so let it be done (unregistered)

Solution used in most American produced housing: Don't give the customer stained wood trim or charge them way extra so they don't want to pay for it. Force painted wood on them because most carpenters can't afford a computer and are too dumb to figure it out manually and rely on the lumber yard to figure it out for them and the lumber yard is usually wrong. You see, with painted wood trim you can splice whereever you want and hide it by caulking the joint in the wood and painting over it so the customer will never see it. In a past life I was a construction manager and these were the tricks of the trade.

• (cs)

Isn't using integers a bit of a WTF? How do I resolve less than 1/16 of available length with integers. I propose we use floting point numbers instead. Also, using inches and feet is probably a pitfall. Shouldn't we just provide a dimensionless solution and let the caller take care of inches to feet conversions?

• (cs)

TRWTF is people on the INTERNET who are helpless when confronted by "inches", "feet", and "splice". Really?

http://www.lmgtfy.com/?q=splice http://www.lmgtfy.com/?q=imperial+units

• biozinc (unregistered)

If the goal is to minimise the number of boards, then you'll never use a board other than of the maximum length! What's should we be optimising for in the Medium and Hard case?

-- Note from Alex: Longer boards are usually cheaper by the foot; a 16' length might cost \$30, while a 8' could be \$16. But if you only need a 8', then no sense in buying a 16'.

• Anonymous (unregistered)
Some guy:
Protip: The exercise in this article has nothing to do with units. At all. Get over your fear and hatred and either comment on the exercise itself or save your comments for the next article.
This is not true. Whilst the units are irrelevant to the core challenge, they are entirely relvant to the specific implementation that solves the challenge. You DO need to understand imperial units and how they relate to each other; you DO need to understand that there are 12 inches to a foot. The mathematics required to implement this are entirely affected by the choice of units and it is incredibly naive to suggest otherwise.
• ClutchDude (unregistered) in reply to ClutchDude
ClutchDude:

16'(4.88m).... 4x 16'(4.87m)...

Not sure where that centimeter went, but I'll find it!

• Ax (unregistered)

The units don't really matter as long as there are no conversions. Hell, you could write your program using a 10-inch foot and it wouldn't really change the algorithm, which is the interesting part.

Alex:
Your exercise for the day: write a function that calculates the number of boards needed to trim out a house.
``````* The input should be a series/array of integers that represent each individual measurement; for example, a single 84u door would be { 84, 32, 84 }.
* The output should be the minimum number of boards needed to complete the job
* The board lengths available can be one of three, with the longer boards preferred when possible:
o Easy - only 192u boards
o Medium - 96u or 192u
o Hard - an (additional) array of integers that is an input to the function
``````

For bonus points, have your program print the cuts needed on each board.

• Anonymous (unregistered)
OperatorBastardusInfernalis:
Here is the easy solution: <snipped copy-paste code>
Thanks for the copy-paste, glad to see you're getting into the spirit of the challenge. Seriously though, I know how you feel - in software development we're always being told "don't reinvent the wheel", so if someone has already solved this challenge, why reinvent the solution, eh? Typical software developer mindset!
• Anonymous (unregistered) in reply to The Mole
The Mole:
Generally wood (in the uk at least in DIY stores) is sold in multiples of 300mm, 1.2m, 2.4m or 3m being particularly common depending on what you are buying (sheet or lengths). Any similarity to lengths measured in feet are of course entirely co-incidental.

It comes from old imperial materials. A standard gypsum board would have been 4ft, (1219.2mm),

When it all went metric the boards were produced at 1200mm, so 300mm is 1/4 of 1200mm, which is the distance between studs.

• Bob Dole (unregistered)

This seems a lot like the making change problem. You find all the measurements, then take the largest possible [strike]demoninations[/strike] available board lengths first.

Only difference here is you have to keep track of the extra lengths you've cut off because a left over few feet could be used elsewhere.

• Anonymous (unregistered) in reply to Anonymous
Anonymous:
The Mole:
Generally wood (in the uk at least in DIY stores) is sold in multiples of 300mm, 1.2m, 2.4m or 3m being particularly common depending on what you are buying (sheet or lengths). Any similarity to lengths measured in feet are of course entirely co-incidental.

It comes from old imperial materials. A standard gypsum board would have been 4ft, (1219.2mm),

When it all went metric the boards were produced at 1200mm, so 300mm is 1/4 of 1200mm, which is the distance between studs.

I think that was the point he was trying to make (quote: "Any similarity to lengths measured in feet are of course entirely co-incidental" - sarcasm, perhaps?).

• grzlbrmft (unregistered)

I demand using old russian units! Screw english/imperial/metric or whatever systems!

http://en.wikipedia.org/wiki/Verst

Arshin FTW.

• JV (unregistered)

Wow. I solved this exact problem this past weekend. I'm redoing my dinning room in wood trim and didn't want splices. I ended up entering all the lengths into Excel and finageled them around to minimize scrap.

The advantage to doing it in Excel was that I could include the order in which I planned to cut the boards.

Regarding the metric comments: We used to work with a team in Canada (metric) and they said they still buy their plywood in 4-foot by 8-foot sheets. Must be an America thing.

• (cs) in reply to Anonymous
Alex:
metric's better,
Correct.
Alex:
you[The world except Burma, Liberia, US] are superior, (...)

That's an ad hominem conclusion. (I don't think there's an established term for deleting disagreeing comments, especially on a recreational website like TDWTF).

But then again, the units really don't matter. Just convert them to the smallest unit (or nm) and start calculating.

• Kae Verens (unregistered)

You Americans and your weird units of measurement! Is something decimal-based not good enough?

With measurements like that I'm surprised you don't lose spacecraft. Oops! http://mars.jpl.nasa.gov/msp98/news/mco990930.html

• Aris (unregistered)

do NOT use "m" do speak about something else than a meter. the MKSA system has well defined unit abbreviations for each unit: m for meter, Kg for kilograms, s for seconds, A for amperes. Each can be prefixed by c,m,u,n,.. for centi,milli,micro,nano or prefixed with K,M,G for Kilo, Mega, Giga. your mph are converted into Km/h and not kph or KM/hrs.

Here is a post from someone who would like to be able to read an american article without unit errors, thanks :)

• Ian (unregistered)

Maybe this challenge is to be done on an embedded system, where there's no file system to store a decimal-based system of measurement.

• WildcatMike (unregistered)

As added bonus, if you come up with a working solution and a decent UI for it that would work on iPhone/Android, you could sell a fair number of copies. I'd only get to use it for my own house, but it would still be worth spending a few bucks on an app that is easy enough to use (and accurate, of course).

• Larry H. (unregistered)

As an added bonus, prove your solution always runs in polynomial time. :-D

• (cs) in reply to Aris
Aris:
do NOT use "m" do speak about something else than a meter. the MKSA system has well defined unit abbreviations for each unit: m for meter, Kg for kilograms, s for seconds, A for amperes. Each can be prefixed by c,m,u,n,.. for centi,milli,micro,nano or prefixed with K,M,G for Kilo, Mega, Giga. your mph are converted into Km/h and not kph or KM/hrs.
“K” is a measure of temperature (the Kelvin) and not a unit prefix. The correct prefix for “kilo” is a lower-case “k”, so “km/h” is a speed unit. Of course, the truly correct speed unit for SI is “ms⁻¹” but that's not so common outside scientific usage.
• Steve the Cynic (unregistered) in reply to Anonymous
Anonymous:
The Mole:
Generally wood (in the uk at least in DIY stores) is sold in multiples of 300mm, 1.2m, 2.4m or 3m being particularly common depending on what you are buying (sheet or lengths). Any similarity to lengths measured in feet are of course entirely co-incidental.

It comes from old imperial materials. A standard gypsum board would have been 4ft, (1219.2mm),

When it all went metric the boards were produced at 1200mm, so 300mm is 1/4 of 1200mm, which is the distance between studs.

Gypsum != wood.

saluto: "I saluto you."

• Johnny Mac (unregistered)
Note from Alex: Longer boards are usually cheaper by the foot; a 16' length might cost \$30, while a 8' could be \$16. But if you only need a 8', then no sense in buying a 16'.
But since you can always turn a 16' board into two 8' boards, that means at most you will only ever need to buy a single 8' board at the very end, for the entire house.

Basically: If the 16' board costs less than two 8' boards, it's never advantageous to buy more than one 8' board--you could instead buy 16' boards and cut them in two, if for whatever reason you wanted 8' boards.

• Programmer & Woodworker (unregistered) in reply to biozinc
biozinc:
Note from Alex: Longer boards are usually cheaper by the foot; a 16' length might cost \$30, while a 8' could be \$16. But if you only need a 8', then no sense in buying a 16'.

Not entirely true. Now this might be true for the Big Box Stores (Home Depot & Lowes), it is not true for real hardwood suppliers. Most woodworkers want pieces of wood that are 14' and greater. When a mill gets 8' boards, it is hard for them to offload because most people want the longer boards, so the shorter boards are sold at a discount. Reason being is that you want to decrease your joints/splices, so longer boards are more desirable, and therefore, in higher demand. the Big Box Stores have a huge markup on wood so the the difference doesn't matter (besides, most people going to them don't need 16' of hardwood)

• Anonymous (unregistered) in reply to dkf
dkf:
Aris:
do NOT use "m" do speak about something else than a meter. the MKSA system has well defined unit abbreviations for each unit: m for meter, Kg for kilograms, s for seconds, A for amperes. Each can be prefixed by c,m,u,n,.. for centi,milli,micro,nano or prefixed with K,M,G for Kilo, Mega, Giga. your mph are converted into Km/h and not kph or KM/hrs.
“K” is a measure of temperature (the Kelvin) and not a unit prefix. The correct prefix for “kilo” is a lower-case “k”, so “km/h” is a speed unit. Of course, the truly correct speed unit for SI is “ms⁻¹” but that's not so common outside scientific usage.
So true. It's amazing how many intelligent people just can't quite get their head around the fact that m/s = ms⁻¹.
• Dan (unregistered)

Extra hard - do it using a polynomial time algorithm (at first glance it looks NP-complete to me, so it's probably not possible, but I'm way too lazy to think about it in more detail)

• (cs) in reply to Anonymous
Anonymous:
Note from Alex: We use feet and inches here, not your goofy metric systems. Yeah, yeah, we all get it... metric's better, you're superior, we should all look at you because you have a snarky comment about how outdated it is, blah blah blah.

Ah, so that's where my comment went. Which wasn't whining or anything, but pointing out that something non-decimal, such as 12 inches to the foot, is hugely confusing to anybody outside the US (and Liberia and Burma).

But this sort of cultural sensitivity is perhaps a bit too much to expect, which would explain the callow response.

• onitake (unregistered) in reply to Ramses So let it be written so let it be done
Ramses:
Solution used in most American produced housing: Don't give the customer stained wood trim or charge them way extra so they don't want to pay for it. Force painted wood on them because most carpenters can't afford a computer and are too dumb to figure it out manually and rely on the lumber yard to figure it out for them and the lumber yard is usually wrong. You see, with painted wood trim you can splice whereever you want and hide it by caulking the joint in the wood and painting over it so the customer will never see it. In a past life I was a construction manager and these were the tricks of the trade.
That's one way of doing it.

Another is even simpler: You measure the rooms, then buy maximum length boards and add a few more than you need for good measure. While this is by no means an economically optimal solution, it provides very good results with minimal effort.

And that's also the way 90% of the workers around here would do it. 9% would buy too little and splice a lot (like in your case), 1% would try to calculate the optimal solution. Time is much more expensive than wood.

For anyone who wants to buy the boards in Central Europe: Lengths of any material are usually sold in full meter units. 2m and 3m is common, sometimes even 4m. That's already very unhandy, but it would make sense for header casings.

• NP Guy (unregistered)

While this IS known as an NP-complete problem, it is, fortunately, one that is easy to approximate. The Best Fit Decreasing algorithm will order, at most (if I recall correctly) 22% too much wood. This algorithm can be performed effectively and efficiently. I'd say more, but it's probably best to refer to wikipedia lest I make a teensy mistake about which other commentators obsess.

• (cs) in reply to Kae Verens
Kae Verens:
You Americans and your weird units of measurement! Is something decimal-based not good enough?

With measurements like that I'm surprised you don't lose spacecraft. Oops! http://mars.jpl.nasa.gov/msp98/news/mco990930.html

I'm not sure it got lost. It probably crashed or got mixed up with one of the other Mars rovers. You know the ones from all the countries who use the metric system.

• TheKoz (unregistered) in reply to Johnny Mac
Johnny Mac:
Note from Alex: Longer boards are usually cheaper by the foot; a 16' length might cost \$30, while a 8' could be \$16. But if you only need a 8', then no sense in buying a 16'.
But since you can always turn a 16' board into two 8' boards, that means at most you will only ever need to buy a single 8' board at the very end, for the entire house.

Basically: If the 16' board costs less than two 8' boards, it's never advantageous to buy more than one 8' board--you could instead buy 16' boards and cut them in two, if for whatever reason you wanted 8' boards.

Although, for a do-it-yourselfer, you may not be able to haul 16' boards, so it would be an advantage to be able to enter the length of board options the program is able to use.

• Ave (unregistered)

There are, like, 7 or 8 terms I've never heard of in the first paragraph of this writeup.

• Jamiec (unregistered)

Here in Metric-land it always makes me chuckle that wood is sold in 1200mm lengths.

It might seem more logical for them to be sold in metre (or 1000mmm) lengths but your options are limited when it comes to splitting the board into equal lengths.

You can cut a 1000mm board in half and in quarter pretty easily. But say you want it split into 3? each piece would be 333.33 mm (pretty hard to get that 1/3mm accurate).

However 1200mm boards can be split into: half: 600mm quarter: 300mm third: 400mm sixth: 200mm twelfth: 100mm etc

So for all thge wisdom of the metric system, it seems that we sell boards in quasi-imperial, metrically measured lengths.

Genius.

• (cs) in reply to Aris
Aris:
do NOT use "m" do speak about something else than a meter. the MKSA system has well defined unit abbreviations for each unit: m for meter, Kg for kilograms, s for seconds, A for amperes. Each can be prefixed by c,m,u,n,.. for centi,milli,micro,nano or prefixed with K,M,G for Kilo, Mega, Giga. your mph are converted into Km/h and not kph or KM/hrs.

You are mistaken. The symbol for kilograms is lower case k. Upper-case K stands for Kelvin. Hence a kK is a kilokelvin, and a Km/s is a Kelvin-meter per second.

• me (unregistered) in reply to Anonymous
Anonymous:
... snipped all sorts of whining and boo-hooing about metric...

Note from Alex: We use feet and inches here, not your goofy metric systems. Yeah, yeah, we all get it... metric's better, you're superior, we should all look at you because you have a snarky comment about how outdated it is, blah blah blah.

Classic. Bitter much?

• eViLegion (unregistered)

Curious Perversions in Joinery Technology

• (cs)

Simple and easy, with all requirements, written in C#. Meets the "HARD" requirements. Call "SetBoardQuantities" to specify board sizes and their quantities you have on hand (pass int.MaxValue for the quanity for an infinite quanity, such as you plan to order whatever is needed at that size). Call "GetCuts" to determine which board to use and where the cut should be made. Call "GetMinimumRequiredBoards" to get the minimum required board count--it will take into account scraps that are large enough to be used for some measurements. Call "GetMinimumRequiredBoardsUsingScrap" to just be the lazy carpenter. Oh, and by-the-way, this will work with Metric, if you simply change the default addition for the 16' board to be whatever the metric equivalent is (or just remove it and make the user enter it manually). I have no idea if this code really works. It compiles, so it ships (no testing--it wouldn't be WTF if I tested it):

using System.Collections.Generic; using System;

namespace WTF_BYOC_AvoidTheSplice { public class BoardCalculator {

``````    Dictionary<decimal, int> BoardQuantities { get; set; }
/// <summary>
/// Initializes a new instance of the <see cref="BoardCalculator"/> class.
/// </summary>
public BoardCalculator()
{

BoardQuantities = new Dictionary<decimal, int>();
//Always add 16' by default as always available.

SetBoardQuantities(16 * 12, int.MaxValue);

}

Dictionary<decimal, int> workingQuantities = null;
/// <summary>
/// Gets the minimum required boards.
/// </summary>
/// <param name="Measurements">The measurements in inches.</param>
/// <returns></returns>
public int GetMinimumRequiredBoards(decimal[] Measurements)
{
Array.Sort(Measurements);
int currentCount = 0;
workingQuantities = new Dictionary<decimal, int>(BoardQuantities);
scraps = new Dictionary<decimal, int>();
//process from largest to smallest, so that scraps can be used, if a
// measurement will fit in the scrap.
for (int i = Measurements.Length - 1; i >= 0;i-- )
{
decimal matchedBoard = FindSmallestMatch(Measurements[i]);
if (!scraps.ContainsKey(matchedBoard))
{
currentCount++;
}
}
return currentCount;
}
private Dictionary<decimal, int> scraps;
private decimal FindSmallestMatch(decimal measurement)
{
decimal matchedSize = 16 * 12;
decimal scapamount = 0;
foreach (decimal size in workingQuantities.Keys)
{
if (size < matchedSize && size > measurement)
{
matchedSize = size;
}
}

workingQuantities[matchedSize]--;
if (workingQuantities[matchedSize] <= 0)
{
workingQuantities.Remove(matchedSize);
}
if (scraps.ContainsKey(matchedSize))
{
scraps[matchedSize]--;
if (scraps[matchedSize] < 0)
{
scraps.Remove(matchedSize);
}
}

scapamount = matchedSize - measurement;
if (workingQuantities.ContainsKey(scapamount))
{
workingQuantities[scapamount]++;
}
else
{
}
if (scraps.ContainsKey(scapamount))
{
scraps[scapamount]++;
}
else
{
}
return matchedSize;
}
/// <summary>
/// Gets the minimum required boards using scrap.
/// </summary>
/// <param name="Measurements">The measurements in inches.</param>
/// <returns></returns>
public int GetMinimumRequiredBoardsUsingScrap(decimal[] Measurements)
{
decimal totallength = 0;
foreach (decimal measure in Measurements)
{
totallength += measure;
}
return (int)(totallength / (16 * 12));
}
public class BoardCuts
{
public BoardCuts(decimal boardSize, decimal makeCutAt)
{
BoardSize = boardSize;
MakeCutAt = makeCutAt;
}
/// <summary>
/// Gets or sets the size of the board.
/// </summary>
/// <value>The size of the board in inches.</value>
public decimal BoardSize { get; private set; }
/// <summary>
/// Where the make cut, in inches.
/// </summary>
/// <value>Where to make cut, in inches.</value>
public decimal MakeCutAt { get; private set; }
}
/// <summary>
/// Gets the cuts.
/// </summary>
/// <param name="Measurements">The measurements in inches.</param>
/// <returns></returns>
public BoardCuts[] GetCuts(decimal[] Measurements)
{
Array.Sort(Measurements);
List<BoardCuts> cuts = new List<BoardCuts>();
workingQuantities = new Dictionary<decimal, int>(BoardQuantities);
//process from largest to smallest, so that scraps can be used, if a
// measurement will fit in the scrap.
for (int i = Measurements.Length - 1; i >= 0;i-- )
{

}
return cuts.ToArray();
}
/// <summary>
/// Sets the board quantities.  use int.MaxValue for infinite quantity.
/// </summary>
/// <param name="size">The size in inches.</param>
/// <param name="quantity">The quantity.</param>
public void SetBoardQuantities(decimal size, int quantity)
{
if (BoardQuantities.ContainsKey(size))
{
BoardQuantities[size] = quantity;
}
else
{
}
}
}
``````

}

• (cs) in reply to Severity One
Severity One:
...something non-decimal, such as 12 inches to the foot, is hugely confusing to anybody outside the US (and Liberia and Burma)
speak for yourself! :)
• Anon (unregistered)

The solution is simple. Don't worry about the splices, just stick a couch (or chair, or table, or the TV) in front of it so you can't see it. With enough furniture you can hide many sins. Also, fix problems with the paint (or wallpaper) on walls by buying a picture of hanging it over it. Easy!

• grammer nasty (unregistered)

My experience in the UK is that most lengths of wood are very rough metric equivalents of imperial measures. e.g. 6' becomes 180cm. Problem is of course that 6' is 182.88cm, so if you're doing something to an older house many of the standard lengths are pretty useless - if you want 6' you have to buy 240cm and trim off 57cm...

• getofmymetriclawn (unregistered) in reply to Anonymous
Anonymous:
... snipped all sorts of whining and boo-hooing about metric...

Note from Alex: We use feet and inches here, not your goofy metric systems. Yeah, yeah, we all get it... metric's better, you're superior, we should all look at you because you have a snarky comment about how outdated it is, blah blah blah.

Hey, this is like the Streisand Effect, just with mod edit.

Btw, how may square feet are in one acre? But it's good to know that 1 acre = 1 forlong*1 chain ;-)

• (cs) in reply to Johnny Mac
Johnny Mac:
Note from Alex: Longer boards are usually cheaper by the foot; a 16' length might cost \$30, while a 8' could be \$16. But if you only need a 8', then no sense in buying a 16'.
But since you can always turn a 16' board into two 8' boards, that means at most you will only ever need to buy a single 8' board at the very end, for the entire house.

Basically: If the 16' board costs less than two 8' boards, it's never advantageous to buy more than one 8' board--you could instead buy 16' boards and cut them in two, if for whatever reason you wanted 8' boards.

err not quite, if you cut a 16[whatever unit] board in half, you do not get 2 8[whatever unit] boards in return. You will loose 1/2 the width of your saw blade on each side.

The other problem involves cutting mitered edges in the corners, you can also loose 1/2 the thickness of the board - as the cut may not be on the correct face of the board to match up with another - moldings may not have symmetrical top to bottom faces, and cannot just be "turned around".

• Chippy (unregistered)

"Take the casing on a 7’ door, for example" Why use a none standard door size instead of 6'6"?