in reply to "The Skirting Board Problem"

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 )

[download]

Replies are listed 'Best First'.
Re^2: "The Skirting Board Problem"
by loris (Hermit) on Jan 22, 2008 at 11:13 UTC
    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)
[reply]

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

[reply]

In Section Seekers of Perl Wisdom