All you Math Wizzes, Here is One For You

[GregFreeman]

This is going to sound like an academic problem, but I assure you it's not homework  .

TL;DR: Assume you have a piece of pipe that has some holes drilled in it. You have some other smaller diameter pieces of pipe that can be used as inserts to cover the holes. You can insert these from the right, left, or both the right and the left. What are the possible combinations, given the lengths of the inserts, that could be used to cover these holes.

Full version -- more details:

Assume you have a piece of PVC pipe some length, L. This piece of PVC may have some holes drilled in it that in certain situation you want covered. In order to cover these holes, you have combinations of slightly smaller diameter PVC pipes available that you can slide in. Now, based on where the holes are, you need to calculate which lengths of pipe to use. 

This would be a very easy problem to solve if you had the constraint of only inserting from the left or the right. But, let's say you have a pipe of length L=40 inches, and you have holes at +18 and -18 inches from the center. It may be more efficient material wise to put in, say, one 7 inch piece from each side so you only use 14 inches of material, rather than a 38 inch piece (assuming you had an insert that length). 

Of course, there are other constraints like time. It may be a lot quicker to put in one long piece than worry about saving material and putting in shorter pieces. But, I can filter out solutions based on those constraints. What I really need is, given inserts of lengths 7 inch, 14 inch, 22 inch, and 27 inch, what are the possible combinations that will cover up the holes in a given material. So, as an example.

PVC Pipe Length L=30, we will call the right edge 0, so with holes at +6 and +25 inches, a solution may be a 7 inch piece from the right, and 7 inch piece from the left. Another solution may be a 27 inch piece from the right and yet another solution just a 27 inch piece from the left. 

You get the idea. Also, I figured the worst case scenario for number of pieces used was L/(shortest insert) assuming they were all inserted from the same side. This puts an upper bounds on the number of pieces that can be used. But, this lead to tons of possible solutions still, because we have 7 possible insert lengths. So, we put a constraint on it -- combinations must include 3 pieces or less. One other constraint is, when inserting from the right and the left, you can't have the inserts overlap. So, you can't use a 27 inch piece from the left and the right on a 30 inch PVC pipe piece. And finally, the sum of the lengths of the inserts used has to be less than the PVC pipe itself (i.e. no overhang). 

So, I hope that was enough information. Curious if anyone can solve this; it is not an easy problem.

[crossrulz]

I would just use 2 of the 7" pipes and shove them in with the 27" piece, one at a time, to cover up each respective hole.  Remove the 27" after placing each 7" pipe.

That's why I'm an engineer and not a mathmetician.

[GregFreeman]

That works until the PVC  with the holes is 100 inches.

[nathand]

This sounds a lot like the classic knapsack problem (which someone asked about a few months ago: http://forums.ni.com/t5/LabVIEW/CS-nerd-friday-problem/m-p/3013671).

[JÞB]

Use Duct Tape instead

[GregFreeman]

---

@nathand wrote:

This sounds a lot like the classic knapsack problem (which someone asked about a few months ago: http://forums.ni.com/t5/LabVIEW/CS-nerd-friday-problem/m-p/3013671).

---

I used to work with him, actually talking to him now 

[nathand]

Oh, also, there are specific-purpose languages for solving problems like this (I have no idea if you can integrate one into LabVIEW). In college we had a class that used GAMS, which appears to be available for free. Of course then you need to learn the syntax for it, but it's not that complicated and there are examples available, so it might not take you more time than trying to write LabVIEW code to solve the problem.

[Darin.K]

I would actually make the inner and outer pipes the same length and  use a hole pattern which allows holes to be openned or closed based on rotation of the inner pipe.

[GregFreeman]

---

@Darin.K wrote:

I would actually make the inner and outer pipes the same length and  use a hole pattern which allows holes to be openned or closed based on rotation of the inner pipe.

---

Ugh, you got me. I slightly modified the problem as to not give away what the customer's industry was. The pieces aren't actually cylindrical . 

[GregFreeman]

Had a bit of a breakthrough. Once I list the combinations, I can just iterate on each row of a 2D array in a for loop, calling "split 1D Array" in the inner for loop. I can split at index 0, then 1, then 2 ...When split at 0, it is essentially inserting them all from the right. When split at 1, it is inserting one from the left and the rest from the right. And so on. This lets me use simple nested loops in a pretty simple way to find solutions, as long as I have that limit on the number of inserts that may be used.