Codility MaxCounters

This problem, that you can find in the Codility test Counting Elements section, tagged as "respectable", requires us to implement a simple finite state automaton. We are going to pass to our function the number of elements we want to work with, and a series of operation we want to apply to them. We should get back the elements final state.

There are just two operation, increase-a-specified-value, and level-to-the-top. To invoke the first one we specify the 1-based index for the element we want to modify, the second one is invoked when N+1 is found. We can safely assume that no other integer would be passed, or we can consider them as no-op.

Here is a C++11 GTest test case, based on a case provided by codility:

TEST(MaxCounters, Given)
{
    const int size = 5; // 1
    std::vector<int> input { 3, 4, 4, 6, 1, 4, 4 }; // 2
    std::vector<int> output = solution(size, input);

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

1. We want to operate on a five integer vector.
2. This list of operations translate as:
- increase the third element (from 0 to 1)
- increase the fourth element (to 1)
- increase the fourth element (to 2)
- equalize all the elements to the top value (2)
- increase the first element (to 3)
- increase the fourth element (to 3)
- increase the fourth element (to 4)
The resulting vector should be { 3, 2, 2, 4, 2 }.

I have already solved this problem some time ago, please have a look to that post if you want more information and also a first inefficient solution. This time I have aimed directly to the 100% solution, and I have written C++11 code - at that time codility did not support it.

As I found out comparing the results afterward, differences are minimal. Basically, just the use of a couple of lambda functions in for_each() loops, instead of old plain for loops:

std::vector<int> solution(int n, std::vector<int>& input)
{
    std::vector<int> result(n); // 1
    int highest = 0; // 2
    int lowest = 0;

    std::for_each(input.begin(), input.end(), [&](int cur){ // 3
        if(static_cast<unsigned>(cur) > result.size()) // 4
        {
            lowest = highest;
        }
        else // 5
        {
            int index = cur - 1; // 6
            result[index] = std::max(result[index], lowest) + 1; // 7
            if(result[index] > highest) // 8
                highest = result[index];
        }
    });

    std::for_each(result.begin(), result.end(), [lowest](int& cur){ // 9
        if(cur < lowest)
            cur = lowest;
    });

    return result;
}

1. This is what the caller wants me to generate.
2. Cache the current highest and lowest values in the output vector. This is going to save a lot of computation time. And it comes quite cheap too.
3. Loop on all the operations specified by the caller.
4. I rely on the input data correctness, guaranteed by codility. In my previous implementation I have been more paranoid, and implemented a no-op strategy in case of unexpected values. Anyway. If the current value is not a valid 1-based index, I assume a top leveling is required. Instead of applying the variation to the actual data, I simply state that the current lowest value is just like the highest one.
5. I have been requested to increase a specific value.
6. For sake of readability, I introduced this local variable, representing the actual 0-based index in my vector.
7. Remember about (4). Possibly the current value in that index is not the real one, I have to compare it against the lowest variable to ensure that I get it right. Then increase it.
8. I should ensure the highest cached value is still valid, so that next time I could do the (4) trick.
9. Before returning to the caller, I should ensure any value in the vector is not less than the lowest cached value.