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.
Go to the full post