Codility FrogRiverOne

This problem is described in the Codility web site, Counting Elements section.
We are asked to check if the integer vector passed in input contains all the values in the natural sequence from 1 up to a passed number.

I have already given a couple of C++ solutions (a Big-Oh-Squared and a linear one) in a previous post. Here I give the C++ solution that jumped now to my mind, and it sort of look cleaner to me.

First of all, a couple of test cases (based on the GTest framework) that should clarify the problem:
TEST(FrogRiverOne, Given)
{
    std::vector<int> input { 1, 3, 1, 4, 2, 3, 5, 4 }; // 1
    ASSERT_EQ(6, solution(5, input));
}

TEST(FrogRiverOne, Cannot)
{
    std::vector<int> input { 1, 3, 1, 4, 2, 3, 5, 4 }; // 2
    ASSERT_EQ(-1, solution(6, input));
}
1. The Codility given test case. Given this vector, we want to get the index of the first element so that any value in [1 .. 5] is available. That means 6, given that 1 is at position 0 (and 2), 2 at 4, 3 at 1 (and 5), 4 at 3, and finally 5 at 6.
2. A negative case, 6 is not in the passed vector, so we should return -1.

Here is my latest solution:
int solution(int x, std::vector<int>& input)
{
    assert(x > 0); // 1
    assert(!input.empty());

    std::vector<bool> flags(x-1); // 2
    for(unsigned i = 0; i < input.size(); ++i) // 3
    {
        unsigned index = input[i] - 1; // 4
        if(!flags[index]) // 5
        {
            flags[index] = true;
            if(--x == 0)
                return i; // 6
        }
    }

    return -1; // 7
}
1. Enforce the most sensitive problem requisite. This is not requested by Codility, that ensures only "clean" input data are provided.
2. When I see a number in [1..x] I mark it as found. Here I store the flags for this purpose.
3. Loop on all the vector input elements.
4. Convert the current input value so that I can use it as an index for the flags vector. Production code should ensure that index is not outside the range of valid values.
5. If I see this value for the first time, I mark it as found, and I decrease the number of missing value that I am looking for.
6. When I have found all the expected elements, I return the current index in the input vector.
7. Otherwise not-found is returned.

No comments:

Post a Comment