1
$\begingroup$

The problem is informally defined as follows:

There is a pipe with holes in it, located at discrete positions. We have tubes that are used to cover the holes. Tubes come at fixed radius. Having a tube of a radius of 1, say, placed at position 3, covers holes at positions 2, 3, and 4. The puzzle is about providing positions for placing the tubes so that the lowest possible amount of tubes are used. Note that tubes are allowed to overlap each other.

For example, the tube radius is 1 and the holes are located at {2, 4, 6, 10}. Tubes need to be placed at position 3 (covering 2 and 4), 6 and 10.

Obviously this seems to be a covering problem, yet I wasn't able to find a specific, studied problem equivalent to this one. Any ideas on how to efficiently approach it?

EDIT: please consider an additional condition, which requires a tube's center to be placed exactly on top of a hole (for whatever strange reason). This should change the solution considerably.

Improve this question
$\endgroup$
2
  • $\begingroup$ So you have tubes of different radius or they are all equals for a given problem ? If there is different radius, I suppose you are limited on the use of the bigger ones while minimizing the total number used. $\endgroup$
    – Optidad
    Dec 20, 2018 at 15:00
  • $\begingroup$ Sorry, I could have been more explicit about it. The radius is fixed and the same for all the tubes. $\endgroup$
    – meliniak
    Dec 20, 2018 at 15:30

3 Answers 3

Reset to default
2
$\begingroup$

If you see your position from left=0 to right=length(pipe), you can simply cover your holes from left to right.

When adding a new tube, put the leftmost remaining hole at the leftmost covered position by the tube. Then you cannot waste tube.

For instance with radius 2, a tube centered on pos k covers [k-2, k+2]. Then a tube with leftmost on k covers [k, k+4].

With holes at {2, 4, 5, 7, 9, 11}: - first hole at 2 => first tube at [2, 6] centered on 4 - next hole at 7 => next tube at [7, 11] centered on 9

Improve this answer
$\endgroup$
4
  • $\begingroup$ Definitely makes sense, but it's not guaranteed that the solution will be optimal that way, am I right? $\endgroup$
    – meliniak
    Dec 20, 2018 at 16:47
  • 1
    $\begingroup$ Yes it is ! everytime you are covering a new leftmost hole (that you have to cover anyway), the set covered with this method is a superset of any other option. $\endgroup$
    – Optidad
    Dec 20, 2018 at 17:37
  • $\begingroup$ Thanks Vince. Do you think that computing just the amount of tubes required is equally complex or one might make a shortcut making it faster to compute? $\endgroup$
    – meliniak
    Dec 21, 2018 at 15:59
  • $\begingroup$ with this solution you only have to do one run on all holes (assuming they are already sorted). If by equally complex you mean O(n), yes it is. I cannot imagine any faster way... $\endgroup$
    – Optidad
    Dec 22, 2018 at 19:49
1
$\begingroup$

First an observation: This problem could be stated with different sets of rules. If you try to find a solution that minimises the cost, and using a tube has an associated positive cost independent of the position of the tube and the holes covered by it, then you can always find an optimal solution where each tube is positioned such that the leftmost hole it covers is at the left edge of the tube, and is not covered by any other tube.

Why is that? Because given any optimal solution where this is not the case, we can move one tube to the right until the leftmost hole it covers is not covered by any other tube (if that is not possible, then the tube would be redundant), and then further to the right until the leftmost hole it covers is at its left edge.

This shows immediately that Vince's algorithm is optimal for the case that all tubes have the same radius and the same cost, since it is always necessary to cover the leftmost hole that isn't covered yet, and we can cover it as described by Vince's algorithm, and still get an optimal solution.

With different rules, the situation becomes more difficult. For example, we might have tubes of different sizes and cost. In that case, we can use dynamic programming - the best way to cover n holes is always to cover the first m holes at optimal cost, then add a tube covering the next n-m holes.

If there are limited numbers of some tubes, then we still use dynamic programming, but we need to keep track of the optimal solutions with different usage of limited resources. For example, if we had unlimited numbers of tubes of size 1, and at most three tubes of size 5, we would separately calculate how to best cover the first n holes, using 0/1/2/3 tubes of size 5.

PS. Another condition was added: The center of a tube must be exactly on top of a hole. So if I have holes at 3 and 5 but not at 4, I cannot cover them both with a tube of radius 1 but only with a tube of radius 2, centered at either 3 or 5.

An optimal solution with all tubes the same size will still cover the leftmost uncovered hole with a tube positioned as far to the right as possible. So if the leftmost uncovered hole is at location h, and the tube has radius r, instead of always placing the center of the tube at (h + r) which may not be possible, you place it at the first of the locations (h+r, h+r-1, ..., h+1, h) which has a hole.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your insights. I just edited the original post, providing an additional condition. Can you share your thoughts on it? $\endgroup$
    – meliniak
    Dec 28, 2018 at 16:14
0
$\begingroup$

One tube of radius 4 placed at position 6 should do'er..

If you must use tubes of radius 1, then 3 tubes at positions 3,5, and 10 should suffice.

If you need an algorithm for find the most efficient placements given tube radius and hole locations, I could cook one up for you..

Otherwise you'll need to provide more rules to this puzzle.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Input for the puzzle is tube radius and positions of the holes. That was only an example. $\endgroup$
    – meliniak
    Dec 20, 2018 at 15:39
  • $\begingroup$ Can you use a brute force algorithm or does it need to be a derived solution? $\endgroup$
    – def_proxy
    Dec 20, 2018 at 15:46
  • $\begingroup$ it's just a kind of challenge, so the more efficient solution the better $\endgroup$
    – meliniak
    Dec 20, 2018 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.