loris has asked for the
wisdom of the Perl Monks concerning the following question:
Dear DIYMonks,
The following is a bit OT, but bear with me please. I need to fit some skirting boards in my house. So I have measured out all the bits of wall and now need to know many pieces of skirting board I need to buy, so that the amount left over once I have completed the work is minimized.
This is obviously an example of the general problem of having a set of numbers and trying to find the minimum number of groups, the sum of whose members does not exceed a certain value. I am currently a bit stuck regarding an elegant approach to this problem.
I can conceive of a sort of brute force approach of just trying out a whole bunch of combinations, but there must be a more intelligent way. I assume that the best way could depend of the distribution of the numbers, e.g. whether I have and even spread or, say, large numbers and small numbers with not much in between. On the one hand I am sure some of you can tell me what the proper name of this problem is, so that I can google for information about it more easily. On the other hand, I am sure that some of you have good ideas about how to go about solving the problem in a perly way.
Thanks,
loris
Update: This is homework, but only in the literal, DIYsense.
"It took Loris ten minutes to eat a satsuma . . . twenty minutes to get from one end of his branch to the other . . . and an hour to scratch his bottom. But Slow Loris didn't care. He had a secret . . ." (from "Slow Loris" by Alexis Deacon)
Re: "The Skirting Board Problem" by GrandFather (Sage) on Jan 22, 2008 at 09:40 UTC 
It wouldn't be a half bad idea to try and write a brute force solution and, if (as you might expect) it doesn't run in reasonable time or you run into some other implementation issue, you can then legitimize your somewhat off topic node by posting some code. ;)
There is plenty of precedent for nodes related to using Perl for solving tricky problems of this sort. An interesting example is Challenge: 2D random layout of variablesized rectangular units..
Perl is environmentally friendly  it saves trees
 [reply] 
Re: "The Skirting Board Problem" by BrowserUk (Pope) on Jan 22, 2008 at 10:01 UTC 
 [reply] 
Re: "The Skirting Board Problem" by McDarren (Abbot) on Jan 22, 2008 at 10:11 UTC 
I'm not sure I understand the complexity of the problem...
I'm no builder, but I would assume that bits of skirting board come in standard lengths? And I would also assume that you then just cut them to suit?
So given that you've already measured all your walls, isn't it simply a matter of taking the sum of all these lengths, and then dividing that by the standard length of an offtheshelf skirting board?
Or, as I strongly suspect, am I missing something that makes it somewhat more complicated?
Cheers,
Darren  [reply] 

I'm also no builder and your approach would work. But the problem is to do each bit of wall with only one piece of skirting board (apart from the walls longer that the offtheshelf length, of course). With your method, I might have to use half a dozen leftover pieces on the last bit of wall. I could of course just put a cupboard in front of it ...
loris
"It took Loris ten minutes to eat a satsuma . . . twenty minutes to get from one end of his branch to the other . . . and an hour to scratch his bottom. But Slow Loris didn't care. He had a secret . . ." (from "Slow Loris" by Alexis Deacon)
 [reply] 

You also have the problem of mitres left or right, inside or outside, if you get it right first time it can save a lot of extra work not having to cut extra mitres and also save the loss that each cut takes from the skirting length.
It may sound trivial but if you have large skirtings in my house for example the boards are 14 inches wide with lots of ogees and detailing and now have to be specially made. Being economical with cutting and length can save a lot of money in the long run.
I have to admit the last time I did a room I drew it out on graph paper first, then cut paper strips to the length of the skirting and fitted them in place on the drawing first. Testing by cutting paper was a lot easier and cheaper than cutting full boards. The skirting lengths could then be matched to the appropriate board length.
 [reply] 
Re: "The Skirting Board Problem" by hipowls (Curate) on Jan 22, 2008 at 10:22 UTC 
This is one of those NP problems which are usually tractable, this is an interesting article from American Scientist.
One greedy algorithm assuming you have a standard length of skirting board and varying wall lengths. The steps are
 Find the "odd" lengths, that is the remaining length on each wall after using the standard lengths.
 Sort the remainders by length, longest first.
 Select the longest and assign it to the shortest length of skirting board it will fit in, if it can't be fitted to an existing board then use a new one..
 Repeat previous step until there are no remaining lengths
An example
skirting length: 5
wall lengths: 24 16 21 4 3 12
remainders: 4 1 1 4 3 2
sorted rem: 4 4 3 2 1 1
Skirting 1: 4 ( available 1 )
sorted rem: 4 3 2 1 1
Skirting 1: 4 ( available 1 )
Skirting 2: 4 ( available 1 )
sorted rem: 3 2 1 1
Skirting 1: 4 ( available 1 )
Skirting 2: 4 ( available 1 )
Skirting 3: 3 ( available 2 )
sorted rem: 2 1 1
Skirting 1: 4 ( available 1 )
Skirting 2: 4 ( available 1 )
Skirting 3: 3 2 ( available 0 )
sorted rem: 1 1
Skirting 1: 4 1 ( available 0 )
Skirting 2: 4 ( available 1 )
Skirting 3: 3 2 ( available 0 )
sorted rem: 1
Skirting 1: 4 1 ( available 0 )
Skirting 2: 4 1 ( available 0 )
Skirting 3: 3 2 ( available 0 )
 [reply] [d/l] 

 [reply] 

 [reply] 
Re: "The Skirting Board Problem" by blokhead (Monsignor) on Jan 22, 2008 at 15:06 UTC 
This is obviously an example of the general problem of having a set of numbers and trying to find the minimum number of groups, the sum of whose members does not exceed a certain value.
What you describe is the binpacking problem. Each length of board represents a bin and the lengths to be cut for each wall represent the set of items to be packed into the fewest number of bins.
I can conceive of a sort of brute force approach of just trying out a whole bunch of combinations, but there must be a more intelligent way.
Not likely, since the problem is NPcomplete. On the bright side, there are many simple approximations for this problem which give a guaranteed approximation ratio^{*}. The wikipedia article mentions a few which give quite good ratios (11/9). They use very simple rules. For example: Firstfit decreasing would look like this (untested):
my $B = ...; # bucket size
my @items = qw[ ... ]; # items
my @bins;
my @binsizes;
ITEM:
for my $item (sort { $b <=> $a } @items) {
for my $bin (0 .. $#binsizes) {
if ($binsizes[$bin] + $item <= $B) {
push @{ $bins[$bin] }, $item;
$binsizes[$bin] += $item;
next ITEM;
}
}
push @bins, [$item];
push @binsizes, $item;
}
print "[@$_]\n" for @bins;
Other places to look include Algorithm::Bucketizer or Algorithm::BinPack, but I don't know which heuristic algorithm they use under the hood.
BTW, it's likely you have few enough items (with small values) so that the bruteforce method will not take too long. But it might take longer to code the bruteforce search than to execute it (or install your skirting boards)!
Appendix/Update:
A guaranteed approximation ratio of 11/9 means that if the optimal solution to a problem instance uses N bins, then the approximation/heuristic algorithm is guaranteed to return a solution for that instance that uses no more than (11/9)*N bins. (Note that I am ignoring the extra +1 in the guarantee for firstfit decreasing  it will give you a solution that uses at most (11/9)*N+1 bins)
Also note that this ratio is tight, which means that there are indeed pathological cases where the algorithm gives solutions that really are a (11/9) factor worse than optimal. However, chances are that most inputs will not yield this worst case  and at least there is a known bound about how bad things can really get.
 [reply] [d/l] 
Re: "The Skirting Board Problem" by kretch (Initiate) on Jan 23, 2008 at 00:14 UTC 
This is known as the "packing" problem.
Notoriously hard (NPComplete), but solvable for a small testcase (how big is your house?)
Google for "1D packing"
Cheers
Kretch  [reply] 

