Robbie Hatley's Solutions To The Weekly Challenge #244

For those not familiar with "The Weekly Challenge", it is a weekly programming puzzle with two parts, cycling every Sunday. You can find it here:

The Weekly Challenge

This week (2023-11-19 through 2023-11-25) is weekly challenge #244:

Task 244-1: Count Smaller
Submitted by: Mohammad S Anwar
You are given an array of integers. Write a script to calculate
the number of integers smaller than the integer at each index.

Example 1:
Input: @int = (8, 1, 2, 2, 3)
Output: (4, 0, 1, 1, 3)
For index = 0, count of elements less 8 is 4.
For index = 1, count of elements less 1 is 0.
For index = 2, count of elements less 2 is 1.
For index = 3, count of elements less 2 is 1.
For index = 4, count of elements less 3 is 3.

Example 2:
Input: @int = (6, 5, 4, 8)
Output: (2, 1, 0, 3)

Example 3:
Input: @int = (2, 2, 2)
Output: (0, 0, 0)

Well, the obvious (mundane, prosaic) way is: for each element, riffle through the array and count smaller elements. But let's not do that. Instead, let's make a copy of the array sorted in increasing order. Then for each element of the sorted array which is greater than the element to its left, store its index as "count" in a hash (as suggested to me by Jason Mills in the "Perl Programmers" Facebook group):

Robbie Hatley's Solution to The Weekly Challenge 244-1

Task 244-2: Group Hero
Submitted by: Mohammad S Anwar
You are given an array of integers representing the strength.
Write a script to return the sum of the powers of all possible
combinations; power is defined as the square of the largest
number in a sequence, multiplied by the smallest.

Example 1:
Input: @nums = (2, 1, 4)
Output: 141
Group 1: (2) => square(max(2)) * min(2) => 4 * 2 => 8
Group 2: (1) => square(max(1)) * min(1) => 1 * 1 => 1
Group 3: (4) => square(max(4)) * min(4) => 16 * 4 => 64
Group 4: (2,1) => square(max(2,1)) * min(2,1) => 4 * 1 => 4
Group 5: (2,4) => square(max(2,4)) * min(2,4) => 16 * 2 => 32
Group 6: (1,4) => square(max(1,4)) * min(1,4) => 16 * 1 => 16
Group 7: (2,1,4) => square(max(2,1,4)) * min(2,1,4) => 16 * 1 => 16
Sum: 8 + 1 + 64 + 4 + 32 + 16 + 16 => 141

I was going to use CPAN module "Math::Combinatorics" on this, but then I realized, we're only looking at the minimum and maximum elements (exactly two elements) of each combination, so we should be able to "elide the middle" and look at pairs only, by first sorting the array in descending numeric order, then calculating the "power" for each (max,min) pair, then multiply by the total number of combinations having that (max,min) (which should be 2^(j-i-1) but not less than 1), then tally the results:

Robbie Hatley's FAST Solution to The Weekly Challenge 244-2

I also did this the obvious, mundane, prosaic way (using combinations), and it consistently gives the same results, just 4 times slower:

Robbie Hatley's SLOW Solution to The Weekly Challenge 244-2

That's it for 244; see you on 245!