Beefy Boxes and Bandwidth Generously Provided by pair Networks Cowboy Neal with Hat
more useful options
 
PerlMonks  

"The Skirting Board Problem"

by loris (Hermit)
on Jan 22, 2008 at 09:01 UTC ( #663523=perlquestion: print w/ replies, xml ) Need Help??
loris has asked for the wisdom of the Perl Monks concerning the following question:

Dear DIY-Monks,

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, DIY-sense.


"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)

Comment on "The Skirting Board Problem"
Re: "The Skirting Board Problem"
by GrandFather (Cardinal) 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 variable-sized rectangular units..


    Perl is environmentally friendly - it saves trees
Re: "The Skirting Board Problem"
by BrowserUk (Pope) on Jan 22, 2008 at 10:01 UTC
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 off-the-shelf skirting board?

    Or, as I strongly suspect, am I missing something that makes it somewhat more complicated?

    Cheers,
    Darren

      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 off-the-shelf 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)
        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.
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

    1. Find the "odd" lengths, that is the remaining length on each wall after using the standard lengths.
    2. Sort the remainders by length, longest first.
    3. 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..
    4. 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 )

      Ah! I had overlooked second part of your third point, i.e. that the longest wall should be matched to the shortest remaining bit of skirting.

      Thanks,

      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)

        Yes, greed can be hard to wrap your mind around;) Good luck with the DIY.

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 bin-packing 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 NP-complete. 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: First-fit 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 brute-force method will not take too long. But it might take longer to code the brute-force 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 first-fit 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.

    blokhead

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 (NP-Complete), but solvable for a small testcase (how big is your house?) Google for "1D packing" Cheers Kretch

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://663523]
Approved by wfsp
Front-paged by grinder
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (16)
As of 2014-04-16 20:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (434 votes), past polls