5
\$\begingroup\$

I programmed a little in java a while back, and now I'm learning C#.
This is the first exercise of "medium" or "respectable" difficulty according to Codility, so I'm pretty pleased of finding out that the approach used by me was the same Sheng followed in codesays.
Writing here and in SO as a mémoire (check this if you'd like) helped me see that sometimes I get in a web of complicated thoughts and things that are very hard to program and are really bad in readability and performance. In the link I just posted I said I was going to talk me out of following futile, complicated ideas from that moment on, and so I did here and found the right solution.
I already asked in three other posts, how my code was in terms of quality this past week, and I'm happy with the results of applying the great contributions I received by members of this amazing community.
This solution, as well as the others (EarliestFrogJump, cyclicRotation & permCheck) pass with a 100% score (time complexity detected O(N+M)).

Task description


You are given N counters, initially set to 0, and you have two possible operations on them:

  1. increase(X) => counter X is increased by 1
  2. max counter => all counters are set to the maximum value of any counter.

A non-empty array A of M integers is given. This array represents consecutive operations:

if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X), if A[K] = N + 1 then operation K is max counter. For example, given integer N = 5 and array A such that:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4 

the values of the counters after each consecutive operation will be:

(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.

Write a function:

class Solution { public int[] solution(int N, int[] A); }

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as an array of integers.

For example, given:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

the function should return [3, 2, 2, 4, 2], as explained above.

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..100,000]; each element of array A is an integer within the range [1..N + 1].

And this is my code

    /// <summary>
    /// Perform operations in a given array, according to another array's values
    /// </summary>
    /// <returns>
    /// The array created of length <paramref name="N"> after applying operations
    /// interpreted by integers found in <paramref name="A"/>
    /// </returns>
    public static int[] GetCountersAfterApplyingOperations(int N, int[] A)
    {
        //array of counters
        int[] countersArr = new int[N];
        //<max> is the largest value found in <countersArr>
        int max = 0;
        int index;
        //when <N> is found in <A[]>, means all counters have to be set to <max>
        int setAllCountersOp = N ;
        //<floor> stores the value of <max> when a <setAllCountersOp> is found in <A[]>
        int floor = 0;
        for ( int i = 0; i < A.Length; i++ )
        {
            //As A[i] = 1, should convert <countersArr>={0} to {1}, then
            index = A[i] - 1;

            //if <index> == <setAllCountersOp> then the new <floor> = <max>
            if ( index == setAllCountersOp )
            {
                floor = max;
            }
            //If 0 <= index < N, then the counterArr[index] should be incremented
            else if ( index < N && index >= 0 )
            {
                //if <setAllCountersOp> was found, no counter can be smaller than <floor>
                if ( countersArr[index] < floor )
                {
                    countersArr[index] = floor + 1;
                }
                else
                {
                    ++countersArr[index];
                }
                if (countersArr[index] > max )
                {
                    ++max ;
                }
            }
        }
        //if counter is smaller than <floor>, it is set to that value.
        for ( int i = 0; i < countersArr.Length; i ++ )
        {
            if ( countersArr[i] < floor)
            {
                countersArr[i] = floor;
            }
        }
        return countersArr;
    }

Thanks in advance.

\$\endgroup\$
  • 2
    \$\begingroup\$ Do you mean Thanks in advance or Thanks for advise? \$\endgroup\$ – dfhwze Sep 25 at 15:12
  • 1
    \$\begingroup\$ I mean thanks in advance. Looks like english.stackexchange is merging with codereview lol. \$\endgroup\$ – newbie Sep 25 at 15:13
  • 2
    \$\begingroup\$ Since you're posting multiple posts with the same format, I'd like to say that you always put the same example twice (everything that follow For example, given: is useless, it's already explained above). I think it adds no value to your post. Apart from that, though, your posts are well written, good job. \$\endgroup\$ – IEatBagels Sep 25 at 15:16
  • 1
    \$\begingroup\$ Thanks @IEatBagels as you probably see I followed the valuables advices you gave me yesterday \$\endgroup\$ – newbie Sep 25 at 15:19
4
\$\begingroup\$

Most things have already been addressed by IEatBagels in his answer.

Compactness

I believe readability could be increased by writing more succinct code.

Starting from this if-else block:

if (countersArr[index] < floor)
{
    countersArr[index] = floor + 1;
}
else
{
    ++countersArr[index];
}

We can see that we want to assign x + 1 to countersArr[index] with x depending on the condition countersArr[index] < floor. Written more clearly:

if (countersArr[index] < floor)
{
    countersArr[index] = floor + 1;   // x = floor
}
else
{
    countersArr[index] = countersArr[index] + 1;  // x = countersArr[index] 
}

Written in compact form using Math.Max, because we want x to be countersArr[index] with a bottom limit of floor:

countersArr[index] = Math.Max(countersArr[index], floor) + 1;
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks. I will have this in mind from now on. I really like that last line \$\endgroup\$ – newbie Sep 25 at 20:37
  • \$\begingroup\$ The intermediate code is to get from the initial code to that last line :) Just a thought process \$\endgroup\$ – dfhwze Sep 26 at 4:19
4
\$\begingroup\$

(It's me, once again, same review format)

Readability

  • There are way too many comments in your code. Comments should explain why you do something when it's not already clear in the code. In my opinion, the less comments some code needs, the better it is. Also, considering your comments are formatted almost exactly as your code is, it is veerryyy confusing. So, you comments only when absolutely necessary. For example : If a variable declaration needs a comment, your variable isn't well named. max could be renamed maxValueInCounters or... something like that. You get the vibe.
  • Your variables should have better names. index doesn't mean much in this context. You could rename it counterIndex, for example.
  • I'm not a big fan of this format : if ( blablabla ), I think the standard is if (blablabla). At least, you should try to be consistent in your style, because you sometimes have extra space sometimes not.

Algorithm

  • When can this happen index < N && index >= 0? We already checked the scenario where index == setAllCountersOp, so in that case the if doesn't do anything.

Apart from that, I think your algorithm is fine.

public static int[] GetCountersAfterApplyingOperations(int N, int[] A)
{
    int[] countersArr = new int[N];
    int max = 0;
    int index;
    int setAllCountersOp = N ;
    int floor = 0;

    for (int i = 0; i < A.Length; i++)
    {
        index = A[i] - 1;

        if (index == setAllCountersOp)
        {
            floor = max;
            continue;
        }

        if (countersArr[index] < floor)
        {
            countersArr[index] = floor + 1;
        }
        else
        {
            ++countersArr[index];
        }

        if (countersArr[index] > max)
        {
            ++max ;
        }
    }

    for (int i = 0; i < countersArr.Length; i ++)
    {
        if (countersArr[i] < floor)
        {
            countersArr[i] = floor;
        }
    }

    return countersArr;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ @dfhwze That's up to you but OP might learn a thing or two! \$\endgroup\$ – IEatBagels Sep 25 at 15:49
  • 1
    \$\begingroup\$ @dfhwze If you want to start from my answer I wouldn't be mad about it, if this changes your mind. \$\endgroup\$ – IEatBagels Sep 25 at 15:52
  • 1
    \$\begingroup\$ @newbie Then you should find the cause of those IndexOutOfBoundExceptions, because, reading your problem description, I don't see how they can happen! \$\endgroup\$ – IEatBagels Sep 25 at 20:33
  • 1
    \$\begingroup\$ @ieatbagels as I said, I agree with you in the fact that the problem's description says numbers will go from 1 to N + 1, but as you also said, in real life scenarios it could happen. Still, I've done every exercise in codility in order till this one, and every time test cases try negative numbers and larger number that the exercise's range describes. I don't know if it's by chance or they intend that who solves the problem think of every case but they accomplished that on me. Now I analyze empty lists, negative numbers, huge numbers, 1 element list, etc, before compiling \$\endgroup\$ – newbie Sep 26 at 17:18
  • 1
    \$\begingroup\$ @newbie I understand then! \$\endgroup\$ – IEatBagels Sep 26 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.