4
$\begingroup$

Given a rural area is only accessible via railroad. As part of a class on economic development, you've come up with a plan for electrifying these remote settlements. Your plan basically describes n wires connecting some stations along the railroad. ith wire goes between stations l[i] and r[i].

As we all know, wires can't cross because this leads to a short circuit, but they can have the same endpoints. Also, the wires cannot cross the railroad - so in other words, a wire should go either to the left or the right of the railroad.

Is it possible to place the wires in such a way that they don't intersect?

Example

For l = [1, 2, 3] and r = [4, 6, 5], it is possible to arrange the wires such that they do not intesect , so the answer is True enter image description here

For l = [1, 2, 3] and r = [4, 5, 6], it is not possible to arrange, so the answer is False enter image description here

For l=[1,3,2,4] and r=[4,5,5,6] the answer is True

What I need is a way to solve the puzzle and how to do it. It seems almost similar to the travelling sales man problem, but I can be wrong too. So how to solve it? How to understand if the arrangements are possible or not?

$\endgroup$
5
  • $\begingroup$ You don't state it explicitly, but it seems in the way you present this problem that we want to connect $n$ stations with exactly $\lceil n/2\rceil$ wires? $\endgroup$
    – Laars Helenius
    Nov 18, 2016 at 14:30
  • $\begingroup$ not necessarily @ Laars Helenius $\endgroup$
    – Indranil Ghosh
    Nov 18, 2016 at 14:34
  • 1
    $\begingroup$ @LaarsHelenius He gives an example at the end after his second picture with four wires. $\endgroup$
    – AlgorithmsX
    Nov 18, 2016 at 14:41
  • $\begingroup$ Do you just need to solve this puzzle for a few specific configurations or do you need an efficient algorithm to solve it? $\endgroup$
    – Dominik
    Nov 18, 2016 at 14:58
  • $\begingroup$ An efficient algorithm would be very helpful @ Dominik $\endgroup$
    – Indranil Ghosh
    Nov 18, 2016 at 15:25

1 Answer 1

Reset to default
2
$\begingroup$
  1. For every connection, create a set consisting of all the nodes between two connected nodes. In your first example, these sets would be $\{2,3\};\{3,4,5\}; \text{and} \{4\}$.
  2. Any intersection between two sets such that one is not a subset of another can only be connected by a subset of one of the two sets because an intersection means that there is at least one connection on both sides of the intersection. A subset, however, does not interfere with this as they can go between one of the wires and the railroad. There is an intersection at $3$ in your first example. There is a subset of $4$ between the other two sets. There is no intersection between the first and last sets. Your first example is therefore true because the intersection is covered by the $3$ to $5$ connection, which has the subset of $4$.

In short, if any set intersects two different non-subsets, it fails.

Here's a better written algorithm:

  1. For each wire, generate a set consisting of the nodes between them.
  2. For each set, check if it intersects another set.
  3. If a set intersects another set, check if one is a subset of the other.
    1. If one is a subset of the other, no conflict, move on.
    2. If not, search for another set containing the intersection.
      1. If there is not another subset containing the intersection, move on.
      2. If there is another set containing the intersection, check if it is a subset of either of the two sets.
        1. If it is a subset, no conflict, move on.
        2. If it is not a subset, there is a conflict, and this wiring does not work.
  4. If you reach the end of all the comparisons without any of the sets conflicting, this wiring works.

There are a few ways you can improve this, including not storing an entire set, just the end points, sorting the sets by their left endpoints, etc.

$\endgroup$
1
  • $\begingroup$ @AlorithmsX isn't it similar to checking whether a given graph is bipartite or not? $\endgroup$
    – Indranil Ghosh
    Nov 18, 2016 at 17:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .