The skirting board problem – Solved

Gil AthorayaAPLLeave a Comment

This problem looks deceptively simple at first glance, but in the science of optimisation it is actually considered a hard problem to solve as the time to calculate a solution increases exponentially with the size of the problem.

Ignoring that I focused on coding an algorithm to find the solution for the given input. After some considerable thought and experimentation (more than I would like to admit) I came to the conclusion that solving the problem in 2 stages makes the code simpler. The final solution must satisfy two conditions:

  1. All skirts must be cut out
  2. The waste (cut off) is the largest possible

This is a combinatorial problem, ie. the solution is found by trying out different combinations of patterns and then pick the optimal solution from that set. Easy right, until you consider how many combinations there are to try out…

Let us start by sorting and padding the skirts and then putting them in bins by size:


⎕←cuts←{⍵[⍋⍵]}8+s×100
23 23 33 33 38 38 88 88 108 108 128 128 148 208 328 368 368
    ⎕←sizes counts←↓⍉{⍺,≢⍵}⌸cuts
┌───────────────────────────────────┬───────────────────┐
│23 33 38 88 108 128 148 208 328 368│2 2 2 2 2 2 1 1 1 2│
└───────────────────────────────────┴───────────────────┘

Now to generate the combinations of cuts: the patterns. Monadic Iota, the index generator, comes to the rescue again. It is most commonly used with a scalar argument, but if you pass it a vector of numbers, it will generate all combinations for you.


⍝ example, generate coordinates for a 5x3 matrix
    ⍳5 3
┌───┬───┬───┐
│1 1│1 2│1 3│
├───┼───┼───┤
│2 1│2 2│2 3│
├───┼───┼───┤
│3 1│3 2│3 3│
├───┼───┼───┤
│4 1│4 2│4 3│
├───┼───┼───┤
│5 1│5 2│5 3│
└───┴───┴───┘

⍝ generate coordinates for a 2x2x2 cube
    ⍳2 2 2
┌─────┬─────┐
│1 1 1│1 1 2│
├─────┼─────┤
│1 2 1│1 2 2│
└─────┴─────┘
┌─────┬─────┐
│2 1 1│2 1 2│
├─────┼─────┤
│2 2 1│2 2 2│
└─────┴─────┘

⍝ now generate all patterns for our skirts:
    patterns←↑,⍳counts
    ⍴patterns
128 10

⍝ only 128 patterns? 
    5↑patterns
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 2 1 1 1 1
1 1 1 1 1 2 1 1 1 2
1 1 1 1 2 1 1 1 1 1

⍝ no, we haven't allowed for the option to exclude a cut yet
    patterns←↑,¯1+⍳counts+1
    ⍴patterns
17496 10
    5↑patterns
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 1

That’s more like it. We now have 17496 cutting patterns where each column represents a skirt size and the number is how many of that size to include in the pattern. Of course, many of those patterns will be too large to fit on the boards. Let’s calculate the sizes of the patterns and assign valid patterns to each board:


pattern_sizes←patterns+.×sizes
    5⍴pattern_sizes
0 368 736 328 696

    mask←↓(b×100)∘.≥pattern_sizes
    +/¨mask
1163 809 662 662 530 455

    ×/1163 809 662 662 530 455
9.943321493E16

	board_patterns←mask⌿¨⊂patterns

Yes, that is a lot of pattern combinations to try out. The aggregated product of the combinations amounts to about 99.4 quadrillion (or 0.1 million million million). Of course, this is an upper limit and many of those would not be valid combinations as we only have one set of skirts. So when combining the boards, we need to check that we haven’t exceeded the total number of skirts available, but this large number of combinations is what makes this a hard problem to solve.

Now to the fun part, write a function that combines these board patterns and checks the resulting cut off to find the optimal solution.

Traversing a tree of combinations is easily done using a recusrsive function. We just need to define the boundaries (end conditions).


findOptimalCut←{
     ⎕IO←0
     boards←100×⍺
     cuts←8+100×⍵[⍋⍵]
     sizes counts←↓⍉{⍺,≢⍵}⌸cuts
     all_patterns←↑,¨,⍳counts+1
     pattern_sizes←all_patterns+.×sizes
     cut_offs←↓boards∘.-pattern_sizes
     mask←cut_offs≥0
     patterns←(mask/¨cut_offs),¨mask⌿¨⊂all_patterns

     findValidPatterns←{
         ⎕IO←0
         ⍺←0⌿⊃patterns
         i←≢node←⍺
         node_count←⍵
         counts≡node_count:,⊂(node⍪↑i↓0⌷¨patterns)
         tot←node_count+[1]1↓[1]i⊃patterns
         mask←~∨/counts<[1]tot
         next_count←↓mask⌿tot
         next_nodes←node∘⍪¨↓mask⌿i⊃patterns
         (i+1)=≢boards:(next_count∊⊂counts)/next_nodes
         r←next_nodes ∇¨next_count
         (⊃,/r)~⊂⍬
     }
     pickBestPattern←{
         ⎕IO←0
         0∊⍴⍵:⍬
         (⊃⍒{⍵[⍒⍵]}⍤1⊢↑0⌷[1]¨⍵)⊃⍵
     }

     valid_patterns←findValidPatterns 0×counts
     best←pickBestPattern valid_patterns
     ('board' 'cut_off',sizes)⍪boards,best
 }

his takes a few seconds for a small subset of the problem, but trying to solve the full set would not be feasible (read “would take months”). I found a sample script on Dyalog’s github that makes it easy to use the isolates offered in a recent version of Dyalog. Download it here.

Below is the same function modified to make use of isolates, thereby splitting the work across all cores available on the machine:


findOptimalCutII←{
     ⎕IO←0
     boards←100×⍺
     cuts←8+100×⍵[⍋⍵]
     sizes counts←↓⍉{⍺,≢⍵}⌸cuts
     all_patterns←↑,¨,⍳counts+1
     pattern_sizes←all_patterns+.×sizes
     cut_offs←↓boards∘.-pattern_sizes
     mask←cut_offs≥0
     patterns←(mask/¨cut_offs),¨mask⌿¨⊂all_patterns

     findValidPatterns←{
         ⎕IO←0
         ⍺←0⌿⊃patterns
         i←≢node←⍺
         node_count←⍵
         counts≡node_count:,⊂(node⍪↑i↓0⌷¨patterns)
         tot←node_count+[1]1↓[1]i⊃patterns
         mask←~∨/counts<[1]tot
         next_count←↓mask⌿tot
         next_nodes←node∘⍪¨↓mask⌿i⊃patterns
         (i+1)=≢boards:(next_count∊⊂counts)/next_nodes
         r←next_nodes ∇¨next_count
         (⊃,/r)~⊂⍬
     }
     pickBestPattern←{
         ⎕IO←0
         0∊⍴⍵:⍬
         (⊃⍒{⍵[⍒⍵]}⍤1⊢↑0⌷[1]¨⍵)⊃⍵
     }
     fvcEach←{
         vc←⍺ findValidPatterns ⍵
         pickBestPattern vc
     }
     nodes←1⊂[0]⊃patterns
     node_counts←↓1↓[1]⊃patterns

     nprocs←#.isolate.Config'processors'
     iss←#.ø¨nprocs⍴⊂'' ⍝ Make isolates
     iss.boards←⊂boards
     iss.counts←⊂counts
     iss.patterns←⊂patterns
     x←iss.⎕FX⊂⎕CR'findValidPatterns'
     x←iss.⎕FX⊂⎕CR'pickBestPattern'
     x←iss.⎕FX⊂⎕CR'fvcEach'
     valid_patterns←nodes('fvcEach' ''#.IIX.PEACH iss)node_counts
     best←pickBestPattern valid_patterns
     ('board' 'cut_off',sizes)⍪boards,best
 }

As a conclusion, I ran the full problem through on an 8-core server with 2GB of ram for each isolate and in just 49.5 hours (!) it produced the result:



┌─────┬───────┬──────┬───┬───┬───┬───┐
│board│cut_off│skirts│   │   │   │   │
├─────┼───────┼──────┼───┼───┼───┼───┤
│520  │4      │148   │368│0  │0  │0  │
├─────┼───────┼──────┼───┼───┼───┼───┤
│460  │352    │108   │0  │0  │0  │0  │
├─────┼───────┼──────┼───┼───┼───┼───┤
│430  │1      │23    │38 │368│0  │0  │
├─────┼───────┼──────┼───┼───┼───┼───┤
│430  │6      │88    │128│208│0  │0  │
├─────┼───────┼──────┼───┼───┼───┼───┤
│400  │1      │33    │38 │328│0  │0  │
├─────┼───────┼──────┼───┼───┼───┼───┤
│380  │0      │23    │33 │88 │108│128│
└─────┴───────┴──────┴───┴───┴───┴───┘

The conclusion of all this? If you spend 2 days calculating the optimal cut pattern, you really should follow the old advice of “measure twice, cut once”.