PWC 237 Maximise Greatness

“Be not afraid of greatness. Some are born great, some
achieve greatness, and others have greatness thrust upon them.”
― William Shakespeare, Twelfth Night

PWC 237 Task 2, Maximise Greatness

You are given an array of integers.
Write a script to permute the given array such that
you get the maximum possible greatness.
To determine greatness, add up the number of
indices for which nums[i] < perm[i]
where 0 <= i < nums.length

Example 1

Example 1 Input: @nums = (1, 3, 5, 2, 1, 3, 1)
Output: 4
One possible permutation: (2, 5, 1, 3, 3, 1, 1)
which returns 4 greatness as below:

      [1] [3] 5 [2] [1] 3  1
       <   <  .  <   <  .  .
      [2] [5] 1 [3] [3] 1  1

Example 2

Example 2 Input: @ints = (1, 2, 3, 4)
Output: 3
One possible permutation: (2, 3, 4, 1)
which returns 3 greatness as below:

       [1] [2] [3]  4
        <   <   <   .
       [2] [3] [4]  1

Great Thoughts

It's always worth considering, however briefly, taking a problem literally and applying brute force. If it's only going to be done rarely and with small sets of data, and if the statement of the problem lends itself to an obvious algorithm, it might be the most direct way to get a problem solved.

In this case, we could literally enumerate the permutations and check each one for its greatness value. Permuting an array is an FAQ and Algorithm::Permute is readily available. Still, factorials, amirite? An array of size 10 has 3,628,800 permutations. Doing three million iterations on modern hardware is not all that painful, but what a waste of electrons.

In the other direction, we can go for complicated. Is this a search problem? We could do a recursive depth-first search: for the first element, find the other elements that could be greater, then stack that choice and repeat with the remaining elements until we run out of possibilities.

But recursive search makes my brain hurt, and if I'm going to experience brain-throb, I might as well use it to think a little deeper. First of all, example 2 shows that the upper bound is going to be n-1, achieved by rotating a sorted list with no duplicate values. Also, any list containing only one value will have a greatness of 0. So that establishes bounds, and suggests that the maximum might be some function of how many repeated values are in the list. Interesting, but I don't see a path to a program from here.

Thinking about the ordering of the original list, we realize that the random order of the input is a red herring. To count the number of "greatness" pairs, we could just as easily start with a sorted list. And that illuminates an approach.

If we start with the smallest element, which other element should we pair it with to achieve greatness? If we pair it with the lowest value that works, that leaves the most possible range for other pairs. Moving from left to right then, we can continue finding pairs until we run out of choices.

Let's call a pair of indices $small and $big, starting with $small=0 and $big=1. As we increment them, we will have the invariant condition that $small < $big, and we are looking for the greatness condition, $num[$small] < $num[$big]. Begin by incrementing $big until we find greatness:

      1   1   1   2   3   3   5
     [0] [1] [2] [3] [4] [5] [6]
      |-----------^
   $small       $big

That's the first pair (0,3); increment $small to look for the next pair ($small=1 and $big=4). We find another great pair immediately:

      -   1   1   2   3   3   5
     [0] [1] [2] [3] [4] [5] [6]
          |-------+---^
         $small       $big

You can see that we're going to do this twice more before $big runs out of possible values, with the pairs (2,5) and (3,6)

      -   -   1   2   3   3   5
     [0] [1] [2] [3] [4] [5] [6]
              |---+---+---^
                  |---+---+---^
              $small       $big

It's pretty obvious that it's going to work for the case where all the values are the same ($big will run out before finding any pairs to match), but we're going to put that into additional test cases, just to be sure.

From this, the code should be not too hard to write, but I got it wrong on my first attempt. I wanted to put a loop over incrementing $small, but really the condition we're testing is that we have enough $big.

sub maximizeGreatness(@nums)
{
    my $greatness = 0;

    # Work in a sorted array.
    my @num = sort { $a <=> $b } @nums;

    my $small = 0;
    my $big = 0; # Not 1, because of pre-increment below

    while ( ++$big <= $#num )
    {
        # Advance until we find a bigger number to pair with
        if ( $num[$big] > $num[$small] )
        {
            $greatness++;
            $small++;   # Move on to next smaller number
        }
    }
    return $greatness;
}

Perl Notes

Sorting the list has to be done numerically (the <=> comparison operator); the default sort in Perl is by string values. Default sort would coincidentally work for the single-digit values in the examples. A robust test plan would be sure to include some sets like (3,20,100) to find this flaw.

The length of an array is always readily available to us, either by evaluating the scalar value of an array (scalar(@num)) or through the $#num special variable. The difference of course, is that $#num is the zero-based last index into the array, while the scalar value is the ordinal count (one-based, if you will). When I was new to Perl, I confused myself more than once by trying to find a length function to apply to arrays, like other languages had. There is a prideful myth that once you know one language, the rest are mostly the same. Mostly. Sometimes. The road to developer hell is paved with bad assumptions.

And speaking of bad assumptions, let's close out the assignment by adding a few test cases other than the given examples.

sub runTest
{
    use Test2::V0;

    is( maximizeGreatness(1,3,5,2,1,3,1), 4, "Example 1");
    is( maximizeGreatness(1,2,3,4      ), 3, "Example 2");

    is( maximizeGreatness(             ), 0, "Empty array");
    is( maximizeGreatness( 20          ), 0, "One element");
    is( maximizeGreatness( 1,1,1,1     ), 0, "Opposite of great");
    is( maximizeGreatness( 3,20,100    ), 2, "Bigger numbers, sort check");

    done_testing;
}