Showing posts with label math. Show all posts
Showing posts with label math. Show all posts

Codility MinPerimeterRectangle

Given an integer that represents the area of a rectangle, return the minimal perimeter of a rectangle having that area and integer sides.

You could find and submit your solution to this problem in the Codility Prime and composite numbers section.

It is easy to see that if a rectangle has area 30, its integers sides could only be (1, 30), (2, 15), (3, 10), and (5, 6). The latter giving the minimal perimeter.

My original C++ solution was clumsier than the one you are seeing now. I was checking the input for squares and worse, I started looping from the wrong side. Thanks to the anonymous suggestion below, I have cleaned up my code in this way:
int solution(int input)
{
    assert(input > 0 && input < 1000000001); // 1

    for(int i = static_cast<int>(std::sqrt(input)); i > 0; --i) // 2
    {
        if(input % i == 0) // 3
            return 2 * ((input / i) + i);
    }

    return 0; // 4
}
1. Enforce the problem requirements in the code through an assert.
2. Remembering that among all rectangles having the same area, the square is the one with minimal perimeter, I should start checking from the closest to the optimum down to the minimal rectangle.
3. If the current candidate divides the area with no remainder, it is the best solution. Calculate the perimeter and return it.
4. We should never reach this line. However usually the C++ compilers complain for a missing return value if they don't see it.

Go to the full post

Codility CountFactors

Return the number of factors for a given positive integer.

You can find this problem in the Codility Prime and composite numbers section. In the pdf associated to this block of exercises it is explained why we shouldn't check all the possible factors, but we could stop at the square root of the examined number.

Still, the solution there is written in Python. If you want to use a strong typed language, you'd better pay attention to large int's, because overflow is a risk we should directly take care of.

That's the reason why I added to the test case provided with the problem also an explicit check on the biggest integer that could be passed in input:
TEST(CountFactors, Given)
{
    ASSERT_EQ(8, solution(24));
}

TEST(CountFactors, Simple)
{
    EXPECT_EQ(1, solution(1));
    EXPECT_EQ(2, solution(2));
    EXPECT_EQ(2, solution(3));
    EXPECT_EQ(3, solution(4));
    EXPECT_EQ(2, solution(5));
}

TEST(CountFactors, Max)
{
    ASSERT_EQ(2, solution(std::numeric_limits<int>::max()));
}
Here is my C++ solution. Since this is a problem almost completely based on numbers properties, it is very simple to port this piece of code to other languages:
int solution(int input)
{
    assert(input > 0);
    if(input == 1) // 1
        return 1;

    int result = 2; // 2
    unsigned i = 2; // 3
    for(; i * i < static_cast<unsigned>(input); ++i)
        if(input % i == 0)
            result += 2;
    if(i * i == static_cast<unsigned>(input))
        ++result;

    return result;
}
1. Trivial case.
2. The algorithm is designed to be symmetric, any factor we find has its own double that has to be considered. Here we are considering 1, that implies also input itself.
3. Let's loop on all the other possible factors, starting from 2, up to the root of the input value. As I hinted above, I should pay attention to possible overflow, this is why I am using unsigned int instead of plain int.

Go to the full post

Shortest path by breadth-first search

Given an undirected unweighted graph that has no loop, we can use a basic breadth-first search algorithm to determine the shortest path from a specified vertex to any (other) one in the graph.

In the previous post I showed a way to store a graph in a C++11 STL container (a vector of forward list of unsigned int). This is the Graph class you are going to see in the code below. Besides, Vertex is a typedef for unsigned int, meaning that we identify a vertex simply by an unsigned number, starting from zero.

This is the class I want to develop:
class BreadthFirstSearch
{
private:
    std::vector<Vertex> parents_; // 1
    Vertex start_; // 2
public:
    BreadthFirstSearch(const Graph& graph, Vertex start); // 3
    std::vector<Vertex> path(Vertex end); // 4
    std::vector<Vertex> backpath(Vertex end); // 5
    void printPath(Vertex end); // 6
};
1. As a result of the breadth-first search algorithm I want to put in this vector the closest ancestor to the start one of any vertex in the associated graph.
2. This is the vertex that I want to use as starting point for BFS algorithm.
3. The ctor gets in input a Graph and one of its vertex and fills the parents_ vector as expected.
4. This method returns the path from the start vertex, as specified by the ctor, to the passed end one.
5. Not strictly a necessity, it could be a private method. Provides the shortest path in reversed order, from end to start.
6. Utility method, dump to standard output a shortest path.

The BreadthFirstSearch constructor implements the BFS algorithm in this way:
BreadthFirstSearch::BreadthFirstSearch(const Graph& graph, Vertex start) :
        parents_(graph.vertices_.size(), std::numeric_limits<Vertex>::max()), start_(start) // 1
{
    if (start >= graph.vertices_.size()) // 2
        return;

    std::vector<bool> seen(graph.vertices_.size()); // 3
    std::queue<Vertex> queue; // 4

    queue.push(start); // 5
    seen[start] = true;
    while (!queue.empty()) // 6
    {
        Vertex vertex = queue.front();
        queue.pop();

        for (auto it = graph.vertices_[vertex].begin(); it != graph.vertices_[vertex].end(); ++it) // 7
        {
            Vertex next = *it;
            if (!seen[next]) // 8
            {
                queue.push(next);
                seen[next] = true;
                parents_[next] = vertex;
            }
        }
    }
}
1. Initially, the parents_ vector contains just "no parent" elements. I used the largest value available for a Vertex to represent such state.
2. Event though this code is not production ready, I couldn't help to put at least a minimal error handling in it. The vertex passed as starting point should be an actual Graph element.
3. This vector keep track of all the vertices that have been already checked in a previous step of the algorithm. Initially no one is, so we could rely on the default behavior for the vector ctor that sets to false all its elements.
4. On this queue I'll put all the vertices that are connected to the one is currently checked.
5. Let's put the control variables in the initial condition. The start vertex is enqueued, and it is marked as seen.
6. Loop until all the elements in the queue are processed.
7. Loop on all the vertices connected to the current one.
8. If this vertex has not already processed, push it in queue, mark it as seen, set as its next the current vertex.

The BreadthFirstSearch ctor has filled the parents_ vector, now we can use it to create the shortest path from the start vertex to a specific one:
std::vector<Vertex> BreadthFirstSearch::path(Vertex end)
{
    std::vector<Vertex> backtrace = backpath(end); // 1
    return std::vector<Vertex>(backtrace.rbegin(), backtrace.rend()); // 2
}
1. Actually, the real job is delegated to backpath().
2. Since backpath() returns a reversed path, the only real task of this method is reverting the vector to return a "stright" one.

If you want the path to be stored in a vector, you will find that it is in the nature of the problem to generate a reversed solution. Or maybe you could use a deque, filling it from the front. Anyway, this is my solution:
std::vector<Vertex> BreadthFirstSearch::backpath(Vertex end)
{
    std::vector<Vertex> backtrace; // 1
    if (end >= parents_.size()) // 2
        return backtrace;

    for (Vertex cur = end; cur != std::numeric_limits<Vertex>::max(); cur = parents_[cur])
        backtrace.push_back(cur); // 3
    return backtrace;
}
1. I am going to backtracing from the passed graph vertex up to the starting one, pushing each parent in this vector.
2. Better to ensure the caller won't pass a nonexistent vertex.
3. Each ancestor is pushed back in the vector, until the "no parent" element is found.

The utility method that dumps the path to standard shows how to use backpath():
void BreadthFirstSearch::printPath(Vertex end)
{
    std::vector<Vertex> vxs = backpath(end);
    std::copy(vxs.rbegin(), vxs.rend(), std::ostream_iterator<Vertex>(std::cout, " "));
    std::cout << std::endl;
}
Here is a piece of code that uses my BreadthFirstSearch class:
BreadthFirstSearch bfs(graph, 0); // 1
bfs.printPath(3); // 2
1. I pass to bfs the graph object as created in the previous post example, and I specify zero as the starting vertex.
2. Ask to print the shortest path from zero to three.

The expected result is:
0 4 3 

Go to the full post

Graph by adjacency list

If you need to work with graphs in your C++11 code, you'd usually rely on someone else's job, like the Boost Graph Library, friendly known as BGL. Sometimes it happens you simply can't, and you have to work it out by yourself. Here I am writing a trivial Graph class that would let me to store an undirected unweighted graph in a compact form.

I have a simple graph as the one showed in the picture. Each vertex is represented by an unsigned integer starting from zero, that helps me to keep the code even simpler. Edges have no weight nor direction, so we can move from vertex 0 to vertex 5 and vice versa, and we are not interested in the cost of moving from one vertex to another one. We only want to know if we can actually go from here to there.

The two common ways to represent a graph differ by using a matrix or a list to store the adjacency of each vertex. As often happens, you should know the actual problem you are tackling to decide which data structure would suit you better. Still, list is usually the primary suspect.

In this first implementation, my class Graph provides only a constructor to set it up and a print method to show what it has in its belly. The main focus here is about showing how the data is stored in it.
using Vertex = unsigned int; // 1
using Edge = std::pair<Vertex, Vertex>; // 2
using Edges = std::vector<Edge>; // 3
using Vertices = std::forward_list<Vertex>; // 4

class Graph
{
public:
    std::vector<Vertices> vertices_; // 5

    Graph(int nv, Edges edges) : vertices_(nv) // 6
    {
        std::for_each(edges.begin(), edges.end(), [this](const Edge& edge) // 7
        {
            if(edge.first < vertices_.size() && edge.second < vertices_.size()) // 8
            {
                vertices_[edge.first].push_front(edge.second); // 9
                vertices_[edge.second].push_front(edge.first);
            }
        });
    }

    void print() // 10
    {
        for(Vertex i = 0; i < vertices_.size(); ++i)
        {
            std::cout << i << ": ";
            std::copy(vertices_[i].begin(), vertices_[i].end(), std::ostream_iterator<Vertex>(std::cout, " "));
            std::cout << std::endl;
        }
    }
};
1. Each vertex is represented by an unsigned integer, starting from zero.
2. An edge is defined by the two vertices delimiting it.
3. I want to pass all the edges in my graph to the class constructor. This is the collection I am going to use for this task.
4. Any vertex in the graph has an associated collection of vertices, all the ones to which it is connected. The cheap C++11 forward_list suffices for this job.
5. A graph is a collection of Vertices. Each element in the vector is an actual vertex of the graph and the associated Vertices keeps track of all the connected vertices.
6. The Graph constructor requires as input the number of vertices in the graph, and all the edges on it. The data member vertices_ is initialized as a collection of empty Vertices.
7. Loop on all the passed edges to associate each vertex in the graph to its connections.
8. A real piece of code should have more effective error handling than this. Here I just discard any wrong edge. It would make sense let the user know that something went wrong.
9. Being the graph undirected, any edge creates two relations.
10. Utility method, just to show that anything worked as expected (hopefully).

Here is how my Graph class is used:
Edges edges { { 0, 1 }, { 0, 4 }, { 0, 5 }, { 1, 2 }, { 1, 4 }, { 2, 3 }, { 3, 4 } };
Graph graph(6, edges);
graph.print();
The expected output:
0: 5 4 1 
1: 4 2 0 
2: 3 1 
3: 4 2 
4: 3 1 0 
5: 0 

Go to the full post

Narcissistic numbers

You could find a thorough description of narcissistic number, also known as Armstrong number, perfect digital invariant, plus perfect number, on Wolfram Mathworld. In a few words, a narcissistic number is an n-digit numbers that equals the sum of all its digits at the nth power.

We want to write a function that checks if a given number respects this definition.

It is easy to see as any positive one-digit number is narcissistic, and the Wolfram page I linked above provides a list of other narcissistic numbers. I used them to write these test cases (in C++ for GoogleTest):
bool isNarcissistic(const std::string& input);

TEST(Narcissus, Simple)
{
  ASSERT_TRUE(isNarcissistic("2"));
  ASSERT_FALSE(isNarcissistic("42"));
}

TEST(Narcissus, Three)
{
  ASSERT_TRUE(isNarcissistic("153"));
  ASSERT_TRUE(isNarcissistic("370"));
  ASSERT_TRUE(isNarcissistic("371"));
  ASSERT_TRUE(isNarcissistic("407"));
  ASSERT_FALSE(isNarcissistic("497"));
}

TEST(Narcissus, Eight)
{
  ASSERT_TRUE(isNarcissistic("24678050"));
  ASSERT_TRUE(isNarcissistic("24678051"));
  ASSERT_TRUE(isNarcissistic("88593477"));
  ASSERT_FALSE(isNarcissistic("88583475"));
}

Here is a possible implementation for such function:
bool isNarcissistic(const std::string& input)
{
  assert(!input.empty()); // 1
  if(input.size() == 1) // 2
    return input[0] != '0';

  int powered = 0; // 3
  for(unsigned i = 0; i < input.size(); ++i)
    powered += std::pow((input[i] - '0'), input.size());

  return powered == std::atoi(input.c_str()); // 4
}
1. This should never happen. It should be user code responsibility ensure that the passed input parameter is not empty. Production code should also ensure that the input strings contains only decimal digits.
2. All one-digit numbers are accepted, with the noteworthy exception of zero.
3. Each digit in the number are elevated to the expected power (third, if there are three digits in the number) and the result is summed up.
4. Compare the original value with the calculated one, and return true if they are the same.

Go to the full post

Self-descriptive numbers

Write function that check if its input represents a self-descriptive base-10 integer.

A number is said self-descriptive if its digit at the i-th position is the counter for the i-digit in the number itself.
21200 is self-descriptive, since it has 2 zeros, 1 ones, 2 twos, 0 threes, and 0 fours.

Here is a possible C++ implementation:
bool isSelfDescr(const std::string& input)
{
  if(input.empty() || input.size() > 10) // 1
    return false;

  for(unsigned i = 0; i < input.size(); ++i) // 2
    if(std::count(input.begin(), input.end(), '0' + i) != input[i] - '0')
      return false;

  return true;
}
1. I am expecting a 10-based number, that means it can't have more than 10 digits - and it shouldn't be empty.
2. For each digit in the number, I count how many of them are in the string, using the STL algorithm count(), and I compare the result against the number in that position.

Go to the full post

Happy numbers

In the Doctor Who episode "42" (the seventh of the third modern series), the tenth Doctor explains that a (natural positive) number that reduces to one when you sum up the square of its digits and continue iterating it until it yields one is said to be happy. If this description doesn't look so descriptive to you, there is a page about happy numbers on wikipedia that looks interesting.

We can check if a number is happy with a C++ function like this one:
bool isHappy(unsigned value)
{
  std::set<unsigned> numbers; // 1
  numbers.insert(1); // 2
  while(numbers.find(value) == numbers.end()) // 3
  {
    numbers.insert(value); // 4
    int next = 0;
    while(value > 0)
    {
      int digit = value % 10;
      next += std::pow(digit, 2); // 5
      value /= 10;
    }
    value = next;
  }

  return value == 1; // 6
}
1. A sad number would enter in a hopeless infinite loop. To detect it, we should keep memory of the states it has already passed, so that we can check them.
2. We could stop transforming the input number when we get a value that we have already seen (sad), of when we get 1 (happy).
3. If the current value is not in the buffering set, we iterate once again.
4. Add the current value to the "already seen" set, and calculate the next state.
5. Each digit is squared and added.
6. If value has reached 1, we have a happy number.

Go to the full post

Summing up primes

Which is the sum of the first one thousand prime numbers?

This question is (also) a CodeEval problem named Sum of Primes.

Even though it looks similar to the previous CodeEval problem I have seen, there's something that makes it more interesting:
int solution()
{
  std::vector<int> primes; // 1
  primes.reserve(1000);
  primes.push_back(2);
  primes.push_back(3);

  for(int i = 5; primes.size() < 1000; i+=2) // 2
  {
    bool isPrime = true;
    for(unsigned j = 1; j < primes.size() && (std::pow(primes[j], 2) <= i); ++j) // 3
    {
      if(i % primes[j] == 0)
      {
        isPrime = false;
        break;
      }
    }

    if(isPrime)
      primes.push_back(i);
  }

  return std::accumulate(primes.begin(), primes.end(), 0); // 4
}
1. I am going to put the generated primes in this vector.
2. I have already pushed the first two elements by hands, now I push all the other ones. I start checking 5, and then I step to the next odd number.
3. To check if a number is prime, it is enough to ensure that no other prime number is among its divisors. Moreover, we can stop checking when we reach a tentative divisor that, when squared, is bigger than the candidate prime.
4. Finally, just sum all the prime numbers up.

Some time ago, I have written about a similar but more general problem, how to check if a given number is prime.

Go to the full post

Prime and palindrome

Write a program that output the biggest number below 1000 that is prime and palindrome.

You could test your solution on CodeEval, where this very simple problem is named Prime Palindrome.

Its cleanest solution would be, for instance in Python, something like that:
print 929
However, if you are answering this question on an interview, you'd probably better think to a less concise solution.

For instance you could write a for-loop like this (here I used C++, but you could easily adapt it to about any programming language):
for(int i = 989; i > 100; i -= 2) // 1
{
  if(isPalindrome(i) && isPrime(i)) // 2
  {
    std::cout << i << std::endl;
    break;
  }
}
1. I start looping from the highest available palindromic number, after 999 that is obviously not prime, down to 100, since it is easy to see that at least 101 is both a palindrome and prime, stepping by two, given that I don't want to check even numbers.
2. If the current number is both palindrome and prime, print it and break the loop.

Checking our number for its palindromicity is trivial. It is just a matter of comparing its first and last cipher.

A bit more interesting is the check on its primality, please follow the link to a previous post I have written on the matter. Here we could use an even simpler algorithm, since we know that our biggest number to check is less than 1000, still the structure of the algorithm stay the same.

Go to the full post

Triangle triplet

In a triangle, the sum of the catheti is bigger than the hypotenuse. Let's call "triangle triplet" a group of three integer numbers that represents the length sides of a triangle. We want to check if in an array of integers, that could longish (one million elements), there is at least one of such triplets.

You can find this problem in the Codility train page, section Sorting, under the nickname Triangle, where you can find also an extra requirement, the values in input could be also negative (even that doesn't make much sense, accordingly to the definition I gave), and could cover the complete range of signed 32 bit integers in C/C++.

Codility provides also a couple of test cases, described in informal language. I felt that at least a third one was missing. Here they are, written in C++ for the googletest xUnit testing framework:
TEST(Tria, Given) // 1
{
    std::vector<int> input;
    input.push_back(10);
    input.push_back(2);
    input.push_back(5);
    input.push_back(1);
    input.push_back(8);
    input.push_back(20);

    ASSERT_EQ(1, solution(input));
}

TEST(Tria, Given2) // 2
{
    std::vector<int> input;
    input.push_back(10);
    input.push_back(50);
    input.push_back(5);
    input.push_back(1);

    ASSERT_EQ(0, solution(input));
}

TEST(Tria, MaxInt) // 3
{
    std::vector<int> input;
    input.push_back(INT_MAX);
    input.push_back(INT_MAX);
    input.push_back(INT_MAX);

    ASSERT_EQ(1, solution(input));
}
1. Example of a sequence that we should accept.
2. This input sequence does not contain any triangle triplet.
3. The input represents an equilateral triangle. However it is so huge that we could overflow, if our code is not designed carefully.

The idea of the algorithm I implemented is quite simple. Get the three smallest values in input, if the sum of the first two is less than the third one we have got our positive solution. Otherwise we know that the smallest number is too small to be part of any good triplet. Discard it and try again with the new smallest number in the lot. Go on till all the triplets are checked.

This was my implementation at the time of writing this post, in the meantime, codility has upgraded its compiler to get C++11, my code here depends on int type actual definition, and so now it fails in a extreme condition. Please, have a look to the newer post I have written about it for a more robust solution:
int solution(const std::vector<int>& input)
{
    if(input.size() < 3) // 1
        return 0;

    std::vector<int> buffer(input.begin(), input.end()); // 2
    std::sort(buffer.begin(), buffer.end());

    for(unsigned i = 0; i < buffer.size() - 2; ++i) // 3
    {
        if(static_cast<int64_t>(buffer[i]) + buffer[i+1] > buffer[i+2])
            return 1;
    }

    return 0;
}
1. Trivial case.
2. Performance-wise, would make no sense to operate on an unsorted collection. Being the input constant, create a copy and sort it.
3. Apply the above described algorithm. To avoid overflow, we should store the sum of the tentative catheti in a 64 bit integer. The simplest way to do that is casting one of them to int64_t.

Go to the full post

Minimal element in subsequences

We have a non-empty string, that could contain up to 100,000 characters (only the 'A','C','G','T' ones). The user would specify a few ranges, up to 50 thousand of them, in the string, and he expects as output the indices relative to the lowest letter in that ranges.

The problem itself is not complicated, it just asks us to check carefully the requirements. You can found it in the Codility train page, prefix sums section, under the name Genomic-range-query.

We can expect only ACGT letters in input, because the idea is that it represents a DNA sequence. Pay attention to the fact that the user specifies the subsequence ranges as zero-based indices, and he expects the output as one-based indices. If 'A' is the answer, we have to output 1, and so on.

As tradition in these kind of problems, there is no stress at all in error handling. If this function should be used in a real world environment, we should check thoroughly the input. Here we can just assume anything is fine.

There is a test case in the problem description, I added a few more of them to help me understanding better how to design the code. Here are the original one and a couple of new ones, written in C++ for the xUnit GoogleTest framework:
std::vector<int> solution(const std::string& dna, // 0
        const std::vector<int>& begs, const std::vector<int>& ends);

TEST(GeRa, Simple) // 1
{
    std::string input("ACGT");

    std::vector<int> P;
    P.push_back(0);
    P.push_back(1);
    P.push_back(2);
    P.push_back(3);

    std::vector<int> Q;
    Q.push_back(0);
    Q.push_back(1);
    Q.push_back(2);
    Q.push_back(3);

    std::vector<int> output = solution(input, P, Q);
    ASSERT_EQ(4, output.size());

    EXPECT_EQ(1, output[0]);
    EXPECT_EQ(2, output[1]);
    EXPECT_EQ(3, output[2]);
    EXPECT_EQ(4, output[3]);
}

TEST(GeRa, Given) // 2
{
    std::string input("GACACCATA");

    std::vector<int> P;
    P.push_back(0);
    P.push_back(0);
    P.push_back(4);
    P.push_back(7);

    std::vector<int> Q;
    Q.push_back(8);
    Q.push_back(2);
    Q.push_back(5);
    Q.push_back(7);

    std::vector<int> output = solution(input, P, Q);
    ASSERT_EQ(4, output.size());

    ASSERT_EQ(1, output[0]);
    ASSERT_EQ(1, output[1]);
    ASSERT_EQ(2, output[2]);
    ASSERT_EQ(4, output[3]);
}

TEST(GeRa, Huge) // 3
{
    std::string input(100000, 'A');

    std::vector<int> P(50000);

    std::vector<int> Q(50000, input.size() - 1);

    std::vector<int> output = solution(input, P, Q);
    ASSERT_EQ(50000, output.size());

    for(unsigned i = 0; i < output.size(); ++i)
        EXPECT_EQ(1, output[i]);
}
0. Codility asks for a slightly different function interface, no parameter is marked there as const.
1. On a very short sequence ("ACGT"), I want to get the lower element on each single element subsequence, (0, 0), (1, 1), (2, 2), (3, 3). The expected result is a four-sized int vector containing 1, 2, 3, 4 (meaning 'A', 'C', 'G', 'T').
2. The Codility given test. From the input sequence "GACACCATA", we should return 1 for (0, 8), 1 for (0, 2), 2 for (4, 5), 4 for (7, 7).
3. This test case is meant to let the developer know how good is the chosen algorithm in term of time complexity. The input sequence is as long as possible, and we have to check the biggest possible number of subsequences that are all covering the entire range. I don't care much of the actual data, so in the input string I have only 'A', consequently as a result a 50,000 sized vector containing only 1's is expected.

Simple but slow solution

A natural solution would be require to check all the subintervals, looping from begin to end, looking for the lowest element.

Its obvious disadvantage is that it would be implemented with a for-in-a-for loop, that in the worst case would lead to an O(N*M) complexity, where N is the sequence size and M is the number of subsequences we need to check.

Here is a first naive implementation:
std::vector<int> solution(const std::string& dna,
        const std::vector<int>& begs, const std::vector<int>& ends)
{
    assert(begs.size() == ends.size()); // 1

    std::vector<int> result(begs.size()); // 2
    for (unsigned i = 0; i < begs.size(); ++i) // 3
    {
        char nucleotide = 'T'; // 4
        for (int j = begs[i]; j <= ends[i]; ++j) // 5
            if (dna[j] < nucleotide) // 6
                nucleotide = dna[j];

        result[i] = nucleotide == 'A' ? 1 : // 7
                    nucleotide == 'C' ? 2 :
                    nucleotide == 'G' ? 3 : 4;
    }
    return result;
}
1. Even if it is not required, I feel too bad not adding at least this minimal check on the input. If you are less paranoid than me, you can happily skip this line.
2. The output is going to be generated in this vector.
3. Check all the intervals.
4. Worst case, the current subsequence has a minimal nucleotide 'T'.
5. Loop on all the elements in the subsequence.
6. If the current element is less than the previous recorded nucleotide, it becomes the new minimal one.
7. I need to convert the selected nucleotide in its representative code.

There are a few improvements that we could operate on this piece of code, for instance, we can break the loop on (5) if we find that the current nucleotide is an 'A', because we have already found the best solution. However, this won't improve our worst case time complexity, it would only help its best and average cases.

We need to look for an altogether different approach.

Using more space to save time

I would like to get the minimal nucleotide in a subinterval just checking its intervals. To achieve this, I can use the partial sum algorithm, and check the difference between the values before entering and at the end of the interval.

A minor issue is that we have to keep track of four different values (A,C,G,T) and not a single variable. It is easy to overcome it, for example creating a vector for each nucleotide.

This generates a small nuisance, I need to convert the character that represent any nucleotide in its index in the vectors of partial sums. This is done with something similar to what I did at the point 7 above, but here I need a zero-based index. To keep the code readable, I created a tiny function to do this mapping:
int getType(char nucleotide)
{
    switch (nucleotide)
    {
    case 'A':
        return 0;
    case 'C':
        return 1;
    case 'G':
        return 2;
    default:
        return 3;
    }
}
What I am going to do is calculating the partial sum for each nucleotide, and then use them on each passed interval to get which is the minimal one present there.

Here is a possibile solution:
std::vector<int> solution(const std::string& dna, const std::vector<int>& begs,
        const std::vector<int>& ends)
{
    assert(begs.size() == ends.size());

    std::vector<std::vector<int> > psums(4); // 1
    for (int i = 0; i < 4; ++i)
        psums[i].resize(dna.size());

    for (unsigned i = 0; i < dna.size(); ++i) // 2
        psums[getType(dna[i])][i] = 1;

    for (int i = 0; i < 4; ++i) // 3
        std::partial_sum(psums[i].begin(), psums[i].end(), psums[i].begin());

    std::vector<int> result(begs.size());
    for (unsigned i = 0; i < begs.size(); ++i) // 4
    {
        int type = 3; // 5
        for (unsigned j = 0; j < 3; ++j) // 6
        {
            int left = begs[i] > 0 ? psums[j][begs[i] - 1] : 0; // 7
            int right = psums[j][ends[i]]; // 8
            if (right != left) // 9
            {
                type = j;
                break;
            }
        }

        result[i] = type + 1; // 10
    }
    return result;
}
1. I create four int vectors, same size of the input DNA sequence. They are initialized with the default int value, that is zero.
2. Scan the DNA sequence. Detect the nucleotide type (0..3) and put in the relative partial sum vector a 1 to mark its presence there.
3. Calculate the partial sum for each nucleotide.
4. Loop on all the subintervals.
5. As in the previous implementation, we already know that the worst case is 'T'. Let's check if there is any "lower" nucleotide. By the way, this also means that we don't really need the fourth psums vector. We could completely get rid of it and save some space.
6. Check of A, C, G nucleotides in this subinterval.
7. This line is a bit tricky. I need to know how many of the current nucleotide (j) have been already seen in the sequence before entering in the subsequence. This information is stored in the element to the immediate left of begs[i]. With one exception, when begs[i] is zero, meaning we are at the beginning of the full sequence. In that case we should use 0 instead, since obviously there were no j-nucleotide at that point.
8. No problem for the right element, just fetch the j-vector of psums, and fetch its ends[i] component.
9. If there is a variation between the final partial sum and the initial one, at least one j-nucleotide is in that interval. So we can set it as the minimal one and stop looping.
10. Last tweak. I stored the nucleotide type as a zero-based index, I need to increase it to match the user expectations.

Go to the full post

Fizz buzz

You won't believe it, but I had no idea what the fizz buzz game was. According to Wikipedia, it's a popular way in (some) English speaking countries to teach children what division is. And checking on the web, I have got the impression that it is also a not so uncommon problem asked during developer interviews. It is so simple, that I'd say it make some sense just for junior positions.

I bumped into it looking at the CodeEval's problems, where it is presented in a slightly more generalized way. We want to list all the numbers from 1 to a given maximum, but replacing the ones that could be divided by two taboo factors, fizz and buzz, with placeholders.

A couple of test cases (written in C++ for GoogleTest), should clarify the requisites.
std::string solution(int fizz, int buzz, int n);

TEST(FiBu, CaseGiven1) // 1
{
  std::string result = solution(3, 5, 10);

  ASSERT_EQ(result, "1 2 F 4 B F 7 8 F B");
}

TEST(FiBu, CaseGiven2) // 2
{
  std::string result = solution(2, 7, 15);

  ASSERT_EQ(result, "1 F 3 F 5 F B F 9 F 11 F 13 FB 15");
}
1. We want to analyze the numbers in the [1..10] interval, any number that has 3 among its factors should be replaced by a F, and 5 by B. Notice that there is no trailing blank after the last generated element.
2. Here the interval is [1..15], the factor 2 should lead to F, and 7 to B. 14 could be divided by both 2 and 7, so it should be replaced by FB.

There is not much to think about before writing the code. The main issue is how we can check if a given number has fizz (or buzz) among its factors. In C, C++ and related languages we normally use the arithmetic operator % (called "modulus" or "modulo") that returns the remainder of the integer division between the two numbers. When it returns zero, we have an integer divisor.

Here is a possible solution:
std::string solution(int fizz, int buzz, int n)
{
  std::ostringstream oss;
  for(int i = 1; i <= n; ++ i)
  {
    bool fb = false; // 1

    if(i % fizz == 0) // 2
    {
      oss << 'F';
      fb = true;
    }
    if(i % buzz == 0) // 3
    {
      oss << 'B';
      fb = true;
    }

    if(!fb) // 4
      oss << i;

    if(i != n) // 5
      oss << ' ';
  }

  return oss.str();
}
1. Flag for fizz or buzz detection.
2. If the remainder of the division of the current number by fizz is zero, it is one of its factors.
3. Same for buzz.
4. If nor fizz nor buzz has been detected, the current number in used.
5. I don't want a trailing blank at the end of the string, so I ensure I am not in the last iteration.

Go to the full post

Counting couples

We have a vector that contains up to one hundred thousand zeros and ones. We want to count the total number of ones that follows each zero.

This problem is better (?) described in the Passing-cars Codility test, part of their train page, prefix sums section.

In my opinion a few test cases would be a better way to clarify it. They are written for C++ with the Google Test framework, however I guess you can easily adapt to your preferred language/xUnit environment:
TEST(PaCa, Given) // 1
{
    std::vector<int> input;
    input.push_back(0);
    input.push_back(1);
    input.push_back(0);
    input.push_back(1);
    input.push_back(1);

    ASSERT_EQ(5, solution(input));
}

TEST(PaCa, Minimal1) // 2
{
    std::vector<int> input(2);
    input[0] = 1;

    ASSERT_EQ(0, solution(input));
}

TEST(PaCa, Huge3) // 3
{
    std::vector<int> input(50000);
    std::vector<int> more(50000, 1);
    input.insert(input.end(), more.begin(), more.end());

    ASSERT_EQ(-1, solution(input));
}
1. This is the test case provided by Codility. Our input is { 0, 1, 0, 1, 1 }. The first zero is followed by three ones, the second zero by another couple. Expected result is five.
2. A first minimal test case I have written (I spare you the other ones). Having in input { 1, 0 }, there is no one following the only zero available. Expected result is zero.
3. A test case that works on the biggest possible input. The first half of the elements are all set to zero, the second half includes only ones. Each zero is followed by 50,000 ones. Having 50,000 zeros, the expected result is 2,500,000,000. Two billion and an half. A clause in the problems says that if we have an output bigger than one billion we should return a sort of error code, minus one.

Inefficient solution

Anyone should find easily this solution. It works fine for small inputs, but it has a O(N**2) time complexity that makes less usable as the input size grows.
int solution(std::vector<int>& input) // 1
{
    if(input.size() < 2) // 2
        return 0;

    unsigned couples = 0; // 3
    for(unsigned i = 0; i < input.size() - 1; ++i) // 4
    {
        if(input[i]) // 5
            continue;

        for(unsigned j = i + 1; j < input.size(); ++j) // 6
        {
            if(input[j]) // 7
            {
                ++couples;
            }
        }
    }

    return couples > 1000000000 ? -1 : couples; // 8
}
1. Usually we would expect the input parameter to be passed as const reference. And here there is no real reason to to pass it as a non-const one, beside the fact that is a problem requirement. We'll see in the third proposed solution how this could be useful to save space complexity.
2. Trivial cases. In real life code, we should have also checked for size too big than expected - maybe throwing an exception.
3. The worst case tested in Huge3 tells us that a plain 32 bit signed int could be not enough to keep the number of couples. And for Codility compiler "int" means "32 bit int". The unsigned version of int, is more than enough for our purposes.
4. Loop on all the input elements but the last one. We are looking for zeros, and we don't care if the last element is one of them, since it can't be obviously followed by anything.
5. If the element is "not zero", it is not what we are looking for, get to the next iteration.
6. Loop on all the following elements looking for ones. Being an asymptotically O(N) loop in another O(N) loop, this is the weak instruction in this algorithm. We'll have to move it someway out of here.
7. If the current element is "not zero", we have found another couple. I could have put here the test on the one billionth couple. If you expect to have many huge inputs leading to a "-1" solution, that could be a better choice. I assumed instead that it is a relatively rare case, and I decided not to pay the price for this repeated check, and move it to (8). Another effect of having the check here, is that I could have given to couples the "plain int" status.
8. If the number of couples is too big, return the error value, otherwise implicitly cast couples to plain int (and I know I can do it) and return it.

Time (and space) linear solution

We have already seen how in previous problems how to trade time for space complexity. The idea here is creating a temporary buffer, same size of the input vector, where we are going to store the sum of all the ones to the right of each zero. Then it will only be a matter of adding the values we are interested in.

Here it comes handy the C++ STL numeric algorithm partial_sum(), that does exactly what we need, once that we pay attention to the fact that we have to look at the reversed input, starting from its rightmost element up to the leftmost one.

Here is the refactored solution:
int solution(std::vector<int>& input)
{
    if(input.size() < 2)
        return 0;

    std::vector<int> buffer(input.size());
    std::partial_sum(input.rbegin(), input.rend(), buffer.rbegin()); // 1

    unsigned couples = 0;
    for(unsigned i = 0; i < input.size() - 1; ++i) // 2
    {
        if(input[i] == 0)
        {
            couples += buffer[i];
        }
    }

    return couples > 1000000000 ? -1 : couples;
}
1. Scan the input vector in reverse order, and put the calculated partial sum likewise in the local buffer.
2. Having extracted the internal loop to place it in (1), the original eternal loop gets much simpler. If the current input element is a zero, I should add the current partial sum (in buffer) to the value I am going to return.

This is a good solution, and it is going to get an 100% by Codility. Still it shouldn't be accepted, if you read carefully their requirements, where it is stated that a O(1) worst-case space complexity is expected.

Dirtier but space constant

Noticing that we are allowed to modify in-place the input (usually not a good idea, since it could cause unpleasant surprises to the caller), we could think a way to combine input and buffer behavior in a single place. Again, this is usually not a good idea. We are violating the single responsibility principle / separation of concerns, and this is going to make our code less readable, and hence less robust to changes. However, let's assume we are in a case where memory is at a premium, and refactor a second time the code, this time to get rid of the local buffer.

We could think to twist the partial sum algorithm so that we store in-place the calculated prefix sum only if the current value is zero, otherwise we wipe out the value in input. The change in the algorithm is so radical that we can't reuse the STL function, but we have to write an our variation.
int solution(std::vector<int>& input)
{
    if(input.size() < 2)
        return 0;

    int sum = 0; // 1
    for(std::vector<int>::reverse_iterator it = input.rbegin(); it != input.rend(); ++it)
    {
        sum += *it; // 2
        *it = *it == 0 ? sum : 0; // 3
    }

    unsigned couples = std::accumulate(input.begin(), input.end(), static_cast(0)); // 4
    return couples > 1000000000 ? -1 : couples;
}
1. Keep track of the current partial sum value.
2. Add the current sequence value to the partial sum.
3. Here is the tricky bit. If the current value is zero, we put the partial sum in. Otherwise we flag it as uninteresting.
4. We need to sum up all the partial sums stored in the input vector. We are not interested in the uninteresting values, but since we have marked them with a zero, we could just sum all the elements in the vector. I'm using the STL function accumulate(), notice that I have explicitly said to it that it as to use as starting value zero as an unsigned value.

The other way round

As Wen-Kai suggests in his comment to this post, we get the same result counting the zeros instead. Think how each 1-element assumes a different weight accordingly to the number of zeros that are before it, since each of them is going to count it for its own sum.

If we perform a slightly customized version of partial sum on zeros, storing the results where the original one-elements were, we get a specular behavior of the previous solution:
int solution(std::vector<int>& input)
{
  int sum = 0; // 1
  for(std::vector<int>::iterator it = input.begin(); it != input.end(); ++it)
  {
      if(*it == 0) // 2
        ++sum;
      else
        *it = sum; // 3
  }

  unsigned couples = std::accumulate(input.begin(), input.end(), static_cast<unsigned>(0)); // 5
  return couples > 1000000000 ? -1 : couples;
}
1. Now "sum" is the number of zeros that we have already scanned.
2. A new zero detected.
3. The weight of the current element grows to keep track of the zeros that are before it.
4. As before, now is just a matter of summing up the partial results.

You can get a sleeker code combining the partial sum loop with the accumulate one, following the Wen-Kai suggestion here below.

Go to the full post

Partial sum

Given a numeric sequence, its partial summation is another sequence where each element represents the sum of all the elements of the original sequence till that point. So, given the sequence { 1, 1, 1, ... }, its partial sum is { 1, 2, 3, 4, ... }. It is also known as prefix sum, prefix reduction, scan, or cumulative sum.

There is a C++ STL function that implements this concept, std::partial_sum(), available in two overloads. One is a proper partial sum implementation, the other is a generic one, that lets the caller to specify which kind of operation applying to transform the original sequence.

I have written a few test cases (for GoogleTest) that should clarify better its usage.

Typical case

I have an input sequence, I want to get its partial sum in a new container:
TEST(TestParSum, CaseStandard)
{
  std::vector<int> input { 1, 3, 1, 4, 2, 3, 5, 4 }; // 1
  std::vector<int> output(input.size()); // 2
  std::partial_sum(input.begin(), input.end(), output.begin()); // 3

  ASSERT_EQ(8, output.size());
  ASSERT_EQ(1, output[0]);
  ASSERT_EQ(4, output[1]);
  ASSERT_EQ(5, output[2]);
  ASSERT_EQ(9, output[3]);
  ASSERT_EQ(11, output[4]);
  ASSERT_EQ(14, output[5]);
  ASSERT_EQ(19, output[6]);
  ASSERT_EQ(23, output[7]);
}
1. The original container. I have used the handy C++11 list initalizer to set it up on construction.
2. The generated result will be stored in this container. It should have the same size of the input sequence.
3. Calculate the partial sum for the passed sequence, putting the result starting from the beginning of the output container.

In place generation

The standard partial_sum() function is designed in such a way that it could overwrite the original data:
TEST(TestParSum, CaseOverwrite)
{
  std::vector<int> data { 1, 3, 1, 4, 2, 3, 5, 4 };
  std::partial_sum(data.begin(), data.end(), data.begin()); // 1

  ASSERT_EQ(8, data.size());
  ASSERT_EQ(1, data[0]);
  ASSERT_EQ(4, data[1]);
  ASSERT_EQ(5, data[2]);
  ASSERT_EQ(9, data[3]);
  ASSERT_EQ(11, data[4]);
  ASSERT_EQ(14, data[5]);
  ASSERT_EQ(19, data[6]);
  ASSERT_EQ(23, data[7]);
}
1. The output iterator is the same that the input starter iterator. We are about to lose the original data, but we are saving some space in memory.

Not only summations

We could need something similar to a partial sum, with the variation that the operator applied is not an addition:
TEST(TestParSum, CaseMultiply)
{
  std::vector<int> data { 1, 3, 1, 4, 2, 3, 5, 4 };
  std::partial_sum(data.begin(), data.end(), data.begin(),
    std::multiplies<int>()); // 1

  ASSERT_EQ(8, data.size());
  ASSERT_EQ(1, data[0]);
  ASSERT_EQ(3, data[1]);
  ASSERT_EQ(3, data[2]);
  ASSERT_EQ(12, data[3]);
  ASSERT_EQ(24, data[4]);
  ASSERT_EQ(72, data[5]);
  ASSERT_EQ(360, data[6]);
  ASSERT_EQ(1440, data[7]);
}
1. Instead of summing, I want to multiply the values. So I pass the STL multiplies functor as last parameter. Nothing else changes from a "normal" partial_sum() call.

Even more generalized

Obviously, we are not restricted to use STL arithmetic functors as a binary operation. We could use our own specifically tailored functor or, if our compiler is C++11 compliant, lambda function.

Here I just rewrite the previous test:
TEST(TestParSum, CaseMultiplyLambda)
{
  std::vector<int> data { 1, 3, 1, 4, 2, 3, 5, 4 };
  std::partial_sum(data.begin(), data.end(), data.begin(),
    [](int a, int b) { return a*b; });

  ASSERT_EQ(8, data.size());
  ASSERT_EQ(1, data[0]);
  ASSERT_EQ(3, data[1]);
  ASSERT_EQ(3, data[2]);
  ASSERT_EQ(12, data[3]);
  ASSERT_EQ(24, data[4]);
  ASSERT_EQ(72, data[5]);
  ASSERT_EQ(360, data[6]);
  ASSERT_EQ(1440, data[7]);
}

Go to the full post

The missing element

An easy problem, that you can find also in the Codility Time Complexity train section. I have written my solution in C++, you could test and submit your one in your preferred language (when available). Its Codility namecode is Perm-Missing-Elem.

In a few words: we are given in input a vector size N containing all the integers (with no duplicates) but one in [1..(N+1)] range. Our job is returning the missing one. We know that N is 100.000 maximum, we want a linear time and a constant space complexity.

First step, I have written the function prototype and I have tried to figure out a few test cases to help me in its design and development (I use Google Test, but any xUnit framework would do):
int missing(const std::vector<int>& input);

TEST(TestPME, CaseSample) // 1
{
  ASSERT_EQ(4, missing({ 2, 3, 1, 5 }));
}

TEST(TestPME, CaseEmpty) // 2
{
  ASSERT_EQ(1, missing({ }));
}

TEST(TestPME, CaseThree) // 3
{
  ASSERT_EQ(3, missing({ 2, 4, 1 }));
}
1. This is the test case provided by Codility. The vector is sized four, the biggest value contained could be five, it easy to see how the missing element is four. A technicality, I have used the C++11 handy notation to create a vector on the fly by an initialization list.
2. It is better to keep an eye on special cases. Here I check what happens when an empty vector is passed. N is zero, so only 1 could be the missing value.
3. There's not much to speculate on this function behavior. But for reason that would become evident in a little while, it is better to test it for both even and odd input sizes.

Naive solution

We could think of repeatedly scanning the vector looking for the missing value. But we should immediately see that this is not a viable solution. We need to loop for each possible value on all the vector elements, that means we are in the domain of a O(N square) time complexity.

Buying time with space

We can radically improve the time complexity using some more memory. Instead of performing a loop in a loop, we perform one after the other, reducing the time complexity to a mere O(N). Sure we have to pay for it, since we have to store the intermediate result somewhere, increasing the space complexity.

The idea is to scan the input vector, using the value read as index in another vector, to keep track that we have found it.
Then we scan the buffer, as soon as we find an element not set, we know that the original element was not present.

Here is my implementation:
int missing(const std::vector<int>& input)
{
  std::vector<bool> check(input.size()+1); // 1

  for(unsigned i = 0; i < input.size(); ++i) // 2
    check[input[i] - 1] = true;

  for(unsigned i = 0; i < check.size(); ++i) // 3
    if(check[i] == false)
      return i + 1;

  return 0;
}
1. I use as buffer a vector of boolean. Remember that we need one element more of the original vector. This STL vector constructor ensures that all the elements contained are set to its default value, that for boolean is false.
2. Loop on the input vector. Quite frighteningly, I haven't done any error handling, trusting the user to provide good stuff in. This is usually a very bad idea. In any case, I read the current value, I decrease it by one, getting a C-style 0-based index, and set the associated element in the check buffer to true, meaning "yeah, we have got this element".
3. Loop on the check buffer. The first element I find set to false is the one I am interested in (actually, it should be the first and only one). Convert back from zero-based index to actual value, increasing by one, and return it.

This solution is good enough to pass the Codility check, but doesn't look satisfactory to me.

Cheaper and more elegant

We are not so much interested in all the values we have in the input container. The unique value that is missing is what we are really interested in. We can spot it reasoning on the input nature. What we get is basically a scrambled sequence of the first N + 1 natural numbers from which we removed a single value. It is very easy to calculate an arithmetic series, if we don't consider the removal. At least since Gauss explained the trick. His classic formula for arithmetic series is usually written like this:
x = 1/2 * top * (top + 1)
What we do is adding the first and last element, top + 1, and multiply it for half the number of the elements. Think about it. To get the sum of all the integer in [1 .. 10], you can add (1 + 10), (2 + 9), ..., (5 + 6). That is 5 * 11.

Once we get the expected result for the full sequence, and remove from it the result we get summing the actual elements, what we get is the missing value:
int missing(const std::vector<int>& input)
{
  int64_t actual = std::accumulate(input.begin(), input.end(), int64_t(0)); // 1

  int64_t top = input.size() + 1;
  int64_t expected = top * (top + 1) / 2; // 2

  return expected - actual; // 3
}
1. The STL accumulate function sums up all the elements in the passed interval, using the third parameter as initial value. I have used as type an explicit 64 bit integer to get rid of problem related to different platforms on which this code could run. Pay attention to the fact that the size of the container and its biggest element could be 100K, so we could easily reach values in the range of billions.
2. I have rewritten the Gauss formula in this slightly different form to avoid the nuisance of multiplying for a floating number (1/2 = 0.5) when I know for sure that I am actually working with integer numbers only.
3. Implicit conversion from 64 bit integer to a plain (whatever means in your environment) integer. Since I am sure that the result is smaller than 100K, I am playing safely.

Go to the full post

Commuting Engineer CodeEval problem

We have the coordinates of a bunch of places that we want to visit. Being nerds, we are not happy if we don't generate an algorithm to determine our path. But, the nature of the problem is such that we are ready to deal with a loose approximation to a good solution. Frankly speaking, we are aiming to get what could look, at least at first sight, as a not-so-bad solution.

You can get a more detailed description of the problem on the CodeEval blog. There you can even enter your solution that would be used (at least at the time when I am writing this post) as a first screening for some job interview.

You can't use the solution I am proposing here for a few good reason. Firstly, it is not a good idea to use a piece of code written by someone else to represent you. Secondly, I have written and tested my code for C++11 on GCC 4.8, that is a bit too modern stuff for the current CodeEval requirements. And thirdly, come on, you don't want to give away a good chance of having some fun writing your own solution.

As I said, I am not aiming to the best possible solution, and this is not caused by sloppiness, there are good reasons for that. Let's see a couple of them.

NP-hard

If you have some knowledge of theory of computation, you should have recognized the problem as an instance of the well known Traveling Salesman Problem, commonly called just TSP. It is an interesting problem because it can be stated in a few words, it looks very easy indeed, but it comes out to be an NP-hard (Non-deterministic Polynomial-time hard) one. That means, forget about to come out with an elegant solution.

In the real life, what I would do if I had to solve a problem like that, is checking for a library provinding some adequate algorithm. For instance, you could have a look to BGL, the Boost Graph Library.

But here we can't use external libraries, we have to rely just on the standard ones. So, what I'll do, is implementing a greedy algorithm, choosing any time the local best solution. It is easy to show as such a strategy is heavily flawed, but at least it assure us we get a solution that is not the worst one, and it does it in a reasonable time.

Geography

As you should know, Earth is not flat. We usually think to it like a sort of sphere, but also this one is nothing more than a weak approximation. This implies that we shouldn't consider the coordinates of a place as they were on a two-dimensional surface.

Besides, we are going to check the distance as if we could go in a straight line from one point to the other, and this is usually not the case.

Splitting the problem

I have reduced the original problem to something that I can actually solve with a relatively simple piece of code. Now I split it in a few simpler problems, for each of them I could write a function that solve it.

Parsing the input

Our input is a number of strings, each of them like this one:
1 | CodeEval 1355 Market St, SF (37.7768016, -122.4169151)
We are interested in its ordinal number, and in the place longitude and latitude.

I decided to organize my data using STL pair's and a vector, and I gave them names that hopefully help to understand better what going on in the code:
using Position = std::pair<double, double>;
using Location = std::pair<int, Position>;
using Locations = std::vector<Location>;
Given that, what I want is to extract a Location from each input string, that is going to be pushed in a Locations container. This is the declaration of the function I am thinking of:
Location parse(const std::string& input);
This test case (written for Google Test) shows how I expect it to behave:
TEST(CommEng, Parse1)
{
    std::string input("1 | CodeEval 1355 Market St, SF (37.7768016, -122.4169151)");
    Location loc = parse(input);

    EXPECT_EQ(1, loc.first);
    EXPECT_DOUBLE_EQ(37.7768016, loc.second.first);
    EXPECT_DOUBLE_EQ(-122.4169151, loc.second.second);
}
Notice I use the EXPECT_DOUBLE_EQ() gtest macro to check the actual value extracted from the input string. This is to avoid, or at least reducing, rounding problems. What I basically do using this macro is delegating to GoogleTest the job of choosing an appropriate epsilon that determines when the two compared values are considered about equal.

Here is my function implementation:
Location parse(const std::string& input)
{
    int nr = std::stoi(input); // 1

    std::string::size_type bracket = input.find('('); // 2
    if(bracket == std::string::npos)
        return {}; // 3

    std::string::size_type comma = input.find(',', bracket);
    if(comma == std::string::npos)
        return {};

    double lon = std::stod(input.substr(bracket + 1)); // 4
    double lat = std::stod(input.substr(comma + 1));
    return { nr, {lon, lat}}; // 5
}
1. stoi() is the standard C++11 function similar to old atoi() but having as input parameter an STL-string and not a C-string. Here I am extracting the place ordinal number, that is expected to be right at the beginning of the string. Real code should be more robust, and be ready to (probably) throw an exception.
2. Just a minimal error checking, if no open bracket and following comma is found, an empty Location is returned.
3. Maybe is worthy to remember that this C++11 notation means "call the default ctor for the expected object". So, what I am doing here is building an "empty" Location.
4. Extract the input substring from the expected position (again, more error handling required in production code), than convert it to double using the C++11 stod() function.
5. Construct a Location object and return it to the caller.

Approximated distance

Just apply the pythagorean theorem to calculate the distance between to positions. For what I have said above, the result should be considered just an approximation:
double distance(const Position& beg, const Position& end)
{
    return std::sqrt(std::pow(beg.first - end.first, 2) + pow(beg.second - end.second, 2));
}
The closest point

My greedy algorithm needs to identify the closest Location to a specific Position:
Locations::iterator findClosest(Position& beg, Locations& others)
{
    double closest = std::numeric_limits<double>::max(); // 1
    Locations::iterator pos = others.end();
    for(Locations::iterator it = others.begin(); it != others.end(); ++it) // 2
    {
        double current = distance(beg, it->second); // 3
        if(current < closest)
        {
            closest = current;
            pos = it;
        }
    }

    return pos; // 4
}
1. Initially I set as a solution as "nothing sensible", so the closest distance found is set the the biggest double number available, and the found position to invalid - the end() iterator.
2. Loop on all the available other points.
3. Calculate the current distance, if I found a good candidate, mark it as such, and check if there is anything better.
4. Return the iterator to the best solution I found.

Generating a path

The core of my algorithm is a function that gets in input a container of Locations and gives back a vector containing the path, where each step is identified by the Location descriptor.
std::vector<int> getPath(const Locations& input)
{
    if(input.empty()) // 1
        return {};

    Locations locations(input); // 2
    std::vector<int> results;
    Locations::iterator current = locations.begin(); // 3
    do { // 4
        Position curPos = current->second; // 5
        results.push_back(current->first);
        locations.erase(current);

        current = findClosest(curPos, locations); // 6

    } while(!locations.empty());

    return results;
}
1. Trivial case, nothing in input, nothing in output.
2. Create an input local copy, since I am about to modify it.
3. As for requirements, the path should start from the first element in the provided list.
4. Loop until all the input is consumed.
5. Erase the current position from the list of Locations that I haven't visited yet, but before that, push its descriptor in the output vector.
6. Find the next "current" element.

Full C++11 source code, and some more test cases, on github.

Go to the full post

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.

Go to the full post

Minimum Scalar Product

In its small dataset input version, the 2008 Code Jam Round 1A problem A, known as Minimum Scalar Product, was solved by almost all the users. Still, the large dataset one was an harder nut to crack, with less than half the participant getting it right. This probably means that the real issue on this problem is about the time complexity of the solving algorithm, and the involved data type. That makes sense, because the question looks easy to solve, at least in its abstract form, but we need to put some attention on its special cases.

In few words, the problem boils down to this request: we have in input two vectors, we want to reorganize them so to minimize its scalar product.

Some theory

Your mathematical background should tell you what the scalar product of vectors is. It has a couple of other names, dot product and inner product, it takes two vectors having the same size, and gives back a single value (just a "scalar"). The result is calculate summing the products of all the elements in the same place on the two vectors (an "inner" product). If you wonder why its "dot" name, is just a matter of notation, a dot is traditionally used to represent the operation.

Your geometrical background could give you an hint to understand how to reorganize the vector. You should remember that a square is the rectangle with maximum area among the ones having the same perimeter. Here we want to minimize the result, so we'll try to stay away as much as we can from that case. We can easily do it sorting the vectors, one in the ascending order, the other descendingly.

Algorithms and data types

Following the large dataset requirements, we need to be prepared to accept input values up to 100,000 (positive or negative). This doesn't look much, but remember we are talking about multiplying, so we need to be able to work with operations like 100,000 * 100,000 and we know that 10,000,000,000 does not fit in a 32 bit integer. Meaning that we should work with 64 bit integers.

We should also be prepared to work with sequences of hundreds of values, meaning that we can't spend too much time looking for the minimal product among elements. But this point is already covered by the bit of theory I have given above. We'll sort the vectors, and this is costing O(N Log N) for each one, before multiplying, a linear O(N) operation.

Testing

For what I said above, I am going to define a function following this prototype:
int64_t minScalarProduct(std::vector<int64_t> x, std::vector<int64_t> y)
Actually, you could be smarter than me, and use cheaper "naked" int in input and more expensive 64 bit int only in output. But this sloppiness helps me to write code more concise, readable and elegant, as we'll see in a moment.

I used the explicit int64_t to avoid portability issues. I let the compiler to match it to long or long long, accordingly to the actual platform.

Some tests (for googletest) I wrote for my C++11 code:
#include <vector>
#include <stdexcept>
#include <gtest/gtest.h>

TEST(MinScalar, Test1) // 1
{
    std::vector<int64_t> x { 1, 3, -5 };
    std::vector<int64_t> y { -2, 4, 1 };

    EXPECT_EQ(-25, minScalarProduct(x, y));
}

TEST(MinScalar, Test2)
{
    std::vector<int64_t> x { 1, 2, 3, 4, 5 };
    std::vector<int64_t> y { 1, 0, 1, 0, 1 };

    EXPECT_EQ(6, minScalarProduct(x, y));
}

TEST(MinScalar, BiggestNegativeOne) // 2
{
    std::vector<int64_t> x(800, 100000);
    std::vector<int64_t> y(800, -100000);

    EXPECT_EQ(-8000000000000, minScalarProduct(x, y));
}

TEST(MinScalar, BadSized) // 3
{
    std::vector<int64_t> x { 1, 2 };
    std::vector<int64_t> y { 1 };

    EXPECT_THROW(minScalarProduct(x, y), std::range_error);
}
1. A couple of tests are provided in the problem descriptions. I have simply rewritten them here.
2. I wrote a few test for the extreme cases, here is probably the most demanding one. The max size expected is 800, and the biggest value expected is |100,000|. I create one all-positive vector, one all-negative, and then I ask for its minimal scalar product. I expect -8,000,000,000,000 as a result.
3. This check was not required by the problem, but I couldn't stop myself of being a bit paranoid and ask what happens if the input vector have different sizes. I decided to let the function throw a C++ standard range_error exception. It would have been cleaner to create a specific exception type.

Developing

In the end, I came up writing this code:
#include <vector>
#include <algorithm>
#include <numeric>
#include <stdexcept>

int64_t minScalarProduct(std::vector<int64_t> x, std::vector<int64_t> y)
{
    if (x.size() != y.size())
        throw std::range_error("check input sizes"); // 1
 
    std::sort(x.begin(), x.end()); // 2
    std::sort(y.begin(), y.end(), std::greater<int64_t>()); // 3

    return std::inner_product(x.begin(), x.end(), y.begin(), static_cast<int64_t>(0)); // 4
}
1. As specified by the BadSized test case, I throw an exception to signal a weird input.
2. Sort "naturally" (ascendingly) the first vector.
3. Sort the second vector descendingly.
4. The STL provides inner_function to calculate the scalar product, using it makes the code sleeker, still it brings a couple of nuisances. It multiplies the container values accordingly to their type, and this is usually what we want to do. That's way I forced the vector underlying type to be a 64 bit integer. The result of the product is added to the last value passed to the function, so its type is fundamental, too. If I don't cast it to int64_t, I'll still have the overflow issue.

Go to the full post

Triangle trilemma

The problem A of the Code Jam Beta 2008 sports a few interesting points. It could be considered a geometrical question, it boils down to knowing how to determine what kind of a triangle we have knowing its three vertices.

We are asked to say if the passed three points are actually a triangle (alternatively, they could be collinear, lying on the same line); if it is acute (all angles are less than 90 degrees), right (one angle is exactly 90 degrees), or obtuse (one angle is more than 90 degrees); and if it is scalene (all sides have a different length) or isosceles. In case of equilateral triangle, we are allowed to give back an imprecise answer, falling back to isosceles.

Before even start thinking about coding, I think it is better to refresh the underlying theory, clarifying what I want to get.

Collinear points

Let's call our points A, B, and C. They determine three segments, AB, BC, and AC. If two of them are collinear, we get for free that the third one is collinear too. It is easy to figure out that, at least in a Euclidean geometry, it has no other chance.

Our job is to compare the slope of whichever two segments. If it is the same, the three points are collinear.

Given our two points, A = (ax, ay) and B = (bx, by), the slope of the line determined by them is: (by - ay) / (bx - ax).

Similarly goes for the other segment, say BC: (by - cy) / (bx - cx), so we could say that the three points are collinear if and only if:
(by - ay) / (bx - ax) = (by - cy) / (bx - cx)
Cool. But you have to pay attention to a couple of details. Firstly, you don't want to divide by zero, and secondly you don't want to divide at all, if you just can avoid it. A division leads often to rounding problems, with consequent headaches.

So we'd better rewrite the equation above to multiply instead of divide. Also multiplications could give to the programmer their shares of trouble (overflow would probably be its name), but here the problem is designed to let them out of the window, since we deal with tiny numbers. This is the equation I am going to use in my code:
(by - ay)*(bx - cx) = (by - cy)*(bx - ax)
Type by angles

Thanks to the Pythagorean theorem, we can easily detect if a triangle is right. As anyone should know, in a rectangle triangle, the sum of the squares of the lengths of the two catheti is equal to the square of the length of the hypotenuse.

Given the lengths of the three sides, it is just a matter of comparing the square of the biggest (let's call it SQx) against the sum of the square of the other two (SQy and SQz):
SQx < SQy + SQz -> obtuse
SQx > SQy + SQz -> acute
SQx = SQy + SQz -> right
Type by sides

That's pretty easy. Assuming that we have the length of each side, if at least two of them are the same we say our triangle is isosceles. We could be more precise, and checking also if all the three of them have the same length (equilateral triangle), but this is not required, and so we should sadly avoid it.

Side length

Both the previous point require the sides length to work. Given two vertices coordinates, we calculate that side length applying (again) the Pythagorean theorem. Actually, to get the value, we should calculate the square of delta x and delta y, sum them, and then extract the square. But we'd better being lazy, and stop at the second step. Instead of calculating the length, get its squared value. In this way we'll avoid a costly operation, and also the usual rounding problems.

Besides, for determine the angles we are specifically requested for the squared values, and for the sides working with the actual value or its square is a non-issue.

This is what I have to do to calculate the squared length of a segment AB:
SQ(A,B) = square(B.y - A.y) + square(B.x - A.x)
Work on triangles with class

Large part of the job is done. I just have to implement the solution. I choose C++ with gtest for the TDD support. It should be a non issue to adapt my code to other languages.

Firstly, a couple of type defines. We are working in a two-dimensional plane, where point are defined are pairs (abscissa, ordinate). And we'll need to operate to collections of exactly three points:
typedef std::pair<int, int> Point;
typedef std::array<Point, 3> Points;
Pair are a well know citizen of the STL nation, array joined the company with C++11. Letting us specify the number of elements in its declaration, it is more expressive than a vector in this context.

I designed a Triangle class having such private data members:
class Triangle
{
private:
  enum Angle { OBTUSE, ACUTE, RIGHT };

  Points vertices_; // 1
  std::array<int, 3> squaredLengths_; // 2
  bool collinear_; // 3

// ...
1. My triangle is described by its vertices.
2. This data member is not strict necessity, it is just a way of saving some computation time using some more space.
3. Ditto.

The real job described above is done by three private function members:
class Triangle
{
private:
  // ..

  int squaredLength(const Point& a, const Point& b) // 1
  {
    return std::pow(b.second - a.second, 2) + std::pow(b.first - a.first, 2);
  }

  bool scalene() // 2
  {
    if(collinear_)
      return false;

    return !(squaredLengths_[0] == squaredLengths_[1] || squaredLengths_[0] == squaredLengths_[2] || squaredLengths_[1] == squaredLengths_[2]);
  }

  Angle angle() // 3
  {
    int ssq = squaredLengths_[0] + squaredLengths_[1];
    return ssq < squaredLengths_[2] ? OBTUSE : ssq > squaredLengths_[2] ? ACUTE : RIGHT;
  }

// ...
1. Utility function to calculate the squared length of the passed segment using the Pythagorean theorem. It is called by the constructor.
2. Is this triangle scalene? If this is not an actual triangle (the three points are collinear) the question makes no sense. I could have thrown an exception, but I decided for a more forgiving behavior. Otherwise let's check if there is at least a couple of sides with the same length. Actually, for the reason described above, I check the squared lengths instead.
3. To ensure that I correctly apply the Pythagorean theorem, I have sorted the squared lengths (see the constructor). It is very easy now to determine if the triangle is obtuse, acute, or right.

In the public interface I left just the constructor and a method to get the required answer:
class Triangle
{
// ...
public:
  Triangle(const Points& p) : vertices_(p), collinear_(false) // 1
  {
    if((p[1].second - p[0].second) * (p[2].first - p[0].first) == (p[1].first - p[0].first) * (p[2].second - p[0].second))
      collinear_ = true;

    squaredLengths_[0] = squaredLength(p[0], p[1]); // 2
    squaredLengths_[1] = squaredLength(p[0], p[2]);
    squaredLengths_[2] = squaredLength(p[1], p[2]);
    std::sort(squaredLengths_.begin(), squaredLengths_.end());
  }

  std::string description() // 3
  {
    std::string result("triangle");
    if(collinear_)
      return "not a " + result;

    Angle ang = angle();
    result.insert(0, ang == OBTUSE ? "obtuse " : ang == ACUTE ? "acute " : "right ");
    result.insert(0, scalene() ? "scalene " : "isosceles ");
    return result;
  }
};
1. The constructor create a triangle from a collection of three points. The points are stored in the private data member vertices_, the collinear_ flag is set accordingly to what we discussed in the section "Collinear points". A real life class should add more checking on the input parameters. Here I rely on the client fairness.
2. Each side squared length is calculated and stored in the private data member squaredLengths_, then the array is sorted, following the natural sorting function, so that the longest one is last (position 2).
3. Build a string containing a triangle description.

Test cases

As usual, I let the design of my code to be driven by test cases. I'm using here the Google C++ Testing Framework (friendly known as googletest), but you should easily adapt them to any xUnit framework you like.

Firstly I have written the test cases provided by the problem itself. Here are the first and last of them:
#include "gtest/gtest.h"

TEST(TestTrilemma, CaseSample1)
{
  Triangle triangle({{ Point(0, 0), Point(0, 4), Point(1, 2) }}); // 1
  ASSERT_EQ("isosceles obtuse triangle", triangle.description());
}

TEST(TestTrilemma, CaseSample8)
{
  Triangle triangle({{ Point(7, 7), Point(7, 7), Point(7, 7) }});
  ASSERT_EQ("not a triangle", triangle.description());
}
1. Maybe is worthy spend a few words on this line. I am creating an object Triangle, passing to it a brace-enclosed initializer list (C++11 goodies) to initialize on the fly a temporary array object, as required by the constructor. Being this an rvalue, the move flavor for the Triangle vertices_ data member constructor will be called, resulting in sleeker code.
Right. But why the double braces? Wasn't one brace enough? No, it wasn't enough. And this is a compiler, and not a language issue. Currently, the GCC compiler get sometimes confused by a single-braced initializer list. This is one of those cases. If you put just a single brace there, you should get a very confusing diagnostic output. But if you write the same code in a simpler way, like this:
Points ps = { Point(0, 0), Point(0, 4), Point(1, 2) };
Triangle triangle(ps);
You should get a cleaner message, a warning like "missing braces around initializer".

Then I have added a few more test cases, exploring different setting. Here are some of them:
TEST(TestTrilemma, CaseCentered) // 1
{
  Triangle triangle({{ Point(0, -2), Point(0, 2), Point(1, 0) }});
  ASSERT_EQ("isosceles obtuse triangle", triangle.description());
}

TEST(TestTrilemma, CaseNegative) // 2
{
  Triangle triangle({{ Point(-1000, -500), Point(-1000, -1000), Point(-100, -700) }});
  ASSERT_EQ("scalene acute triangle", triangle.description());
}

TEST(TestTrilemma, CaseHuge3) // 3
{
  Triangle triangle({{ Point(-1000, 0), Point(-1000, -1000), Point(1000, 1000) }});
  ASSERT_EQ("scalene obtuse triangle", triangle.description());
}
1. What if the triangle is (sort of) centered on the plane origin?
2. Could we have an issue on a Triangle lying in the plane negative quarter?
3. The problem requirements state that the Triangle points must be in the [-1000, 1000] range. I didn't enforced this constrain in the code, but I ensured with a number of tests that my class works fine with the biggest expected triangles.

Go to the full post

Number of disc intersections - linear solution

I described this Codility problem in previous post. There I took an alluring path that drove me to a weak O(N square) solution. Then I tried to save the day, tweaking that algorithm so that, in the best case, it could lead to an acceptable O(N log N) result. But we could not avoid to acknowledge that we still have a Big Oh N Square time complexity in the worst case.

Thinking a bit more on the problem nature, we should find a much more elegant algorithm, that gives us a shiny O(N) time complexity.

A different approach

Instead of focusing on the discs, let's check how a generic point contributes to the total number of intersections. We should just know how many other discs have started before, and how may are starting in that point. An example should clarify the matter.

The red vertical line in the picture represent the current point.

We have three discs (A, B, C - represented by black lines) that have already started, and a new one (D - the blue line) that starts there.

It is easy to see that we'll have three new intersections, AD, BD, CD. The blue line could be accounted for one intersection for each black line.

Things get a bit more complicated if we have many new discs starting in a point.
Say that we have three running discs (A, B, C - black lines), and three new ones (D, E, F - blue lines) are starting there (the red line).

Similarly to the previous example, we'll have a new bunch of intersections deriving from the contact between the first group and the second, namely, AD, AE, AF; BD, BE, BF; CD, CE, CF. That is 3 * 3.

But this is just part of the story, now we need to consider also of the intersection internal to the second group. In this case they are three: DE, DF, EF.

It is easy to count them by hand, but, what is the rule that determine this number?

Mathematically speaking, we are looking for the k-combinations of n-elements, where k is the number of parts involved in the intersection (in our case it is always 2), and n the number of elements we are dealing to (the new discs, represented by blue lines). This n-choose-k value is formally named binomial coefficient (n k) and is calculated using the formula n! / (k! * (n-k)!).

Being k = 2, we want to get the number of intersection between couple of discs, we have just n, the number of new discs, as variable. And we can simplify the formula to n! / (2! * (n-2)!) = n * (n-1) / 2

Let's get the number of intersections using it.

In the first case, there is just one new disc, so we have 3 intersection, 1 blue against 3 blacks, plus 1-choose-2 for the blue: n * (n - 1) / 2 = 1 * 0 / 2 = 0. That means, in the first case we have just three intersections.

What happens in the case of 2 new discs against 3 already existing? We'll have 6 intersections, 2 blues * 3 blacks, plus 2-choose-2 for the blues: 2 * 1 / 2 = 1. A total of seven intersections.

If we have three blues and three blacks, we'll have 3 * 3 = 9 intersections, and 3-choose-2 for the blues alone: (3 2) = 3 * 2 / 2 = 3. Twelve intersections.

The code
int beta(const std::vector<int>& input)
{
  const SIZE_T SIZE = input.size();

  if(SIZE < 2)
    return 0;
  if(SIZE > MAX_ELEMENTS)
    return -1;

  std::pair<int, int> disks[SIZE]; // 1
  for(SIZE_T i = 0; i < input.size(); ++i)
  {
    ++disks[(int)i < input[i] ? 0 : i - input[i]].first;
    ++disks[i+input[i] >= input.size() ? input.size() - 1 : i + input[i]].second;
  }

  int result = 0;
  int open = 0; // 2
  for(SIZE_T i = 0; i < input.size(); ++i)
  {
    result += open * disks[i].first + (disks[i].first * (disks[i].first - 1)) / 2; // 3
    if(result > MAX_INTERSECTING_PAIRS)
      return -1;

    open += disks[i].first - disks[i].second; // 4
  }

  return result;
}
1. Same data structure as used in the previous implementation, but here it has a different meaning. Each pair represents a point in the interval [0, input size); its first component keep tracks of how may discs start in that point (note that I cut off to zero this value, for the same reason discussed in the previous post); its second component represents the number of discs ending there.
2. Initially we have no "open" discs.
3. This is the core of the algorithm. The first part calculates the intersections between the already existing discs and the number of discs starting in this point. The second part is the binomial coefficient discussed above.
4. Add to "open" the number of discs starting here, and subtract the one that terminates here.

Go to the full post