Rope Intranet

Another simple Code Jam problem is the part A of Round 1C 2010. We are asked to count the number of intersections among a bunch of segments. They all start and end at the same x values (not specified which, say 0 and 1) and they all have different y values, ranging in [1, 10000]. In the Large Dataset version of the problem, we can expect up to one thousand segments. This is a reasonable number, so we can avoid sweating too much trying to find a smart solution.

As usual, I started thinking on the interface my code would produce to the user, and setting a few tests that would drive me in the actual development. C++11 is my target language, and as xUnit framework I use is Google Test (AKA gtest).

The problem is simple enough to be solved by a single (and short) free function:

int interRope(std::vector<std::pair<int, int>> input); // 1

TEST(RopeIntra, Test1) // 2
{
    std::vector<std::pair<int, int>> input { {1, 10}, {5, 5}, {7, 7} };

    EXPECT_EQ(2, interRope(input));
}

TEST(RopeIntra, Test2) // 3
{
    std::vector<std::pair<int, int>> input { {1, 1}, {2, 2} };

    EXPECT_EQ(0, interRope(input));
}

TEST(RopeIntra, TestEmpty) // 4
{
    std::vector<std::pair<int, int>> input;

    EXPECT_EQ(0, interRope(input));
}

TEST(RopeIntra, TestHugeEmpty) // 5
{
    std::vector<std::pair<int, int>> input;
    input.reserve(1000);

    for(int i = 1; i <= 1000; ++i)
        input.push_back({i * 10, i * 10});

    EXPECT_EQ(0, interRope(input));
}

TEST(RopeIntra, TestHugeFull) // 6
{
    std::vector<std::pair<int, int>> input;
    input.reserve(1000);

    for(int i = 0; i < 1000; ++i)
        input.push_back({i, 1000 - i});

    EXPECT_EQ((1000 * 999) / 2, interRope(input));
}

1. The function gets in input a vector of int pairs, representing the start and end of each segment, and returns the number of detected intersections. Notice that the vector is passed by copy and not by reference. It is not a design mistake, there is a reason for this, I will talk more about it later.
2. First test provided with the problem itself. The three passed segments have three intersections.
3. In this case the two passed segments have no intersections.
4. What if no segment are passed? No intersection would be detected.
5. To ensure performance are not an issue, I try the biggest bunch of segments we should expect. I build a set of one thousand of parallel segments, no intersection is expected.
6. Another test on the biggest set of segments. Here I build the set so that each segment is intersecting all the other ones. How many intersections are expected? Quite a number. Let's count them. The first gives us a 999 partial result. For the second one, we should remember we have already counted the intersection with the first, so we have a 998. The third gives a 997, and so on. That means, we have a summation from 1 to 999, if you remember from your math studies, this is 1000 * 999 / 2. I used this formula in the test case instead of the actual value, assuming it is more clear in this way.

And here is the function definition:

int interRope(std::vector<std::pair<int, int>> input)
{
    if(input.empty()) // 1
        return 0;

    std::sort(input.begin(), input.end()); // 2

    int intersections = 0;
    for(unsigned i = 0; i < input.size() - 1; ++i) // 3
    {
        for(unsigned j = i + 1; j < input.size(); ++j)
        {
            if(input[i].second > input[j].second) // 4
                ++intersections;
        }
    }

    return intersections;
}

1. Below in the code (point 3) I assume there is at least a segment. Here I ensure that assumption is true.
2. That's why I pass the input parameter by value. It's easier to count the intersections if know that the segments are ordered. But I don't want to modify the original vector, so I need to work on a copy.
3. For each segment (but the last one) I check how many intersection it has with all the other segments above it.
4. Being the vector sorted, I know that the right points next to "i" are higher than it. If the j-th segment has its left point lower than the i-th one, there is an intersection.

Admittedly, this is an acceptable solution only because we work on limited input. The two nested for loops lead to an O-Square-N time complexity.