# RabbitFarm

### 2023-11-26

#### Counting the Smallest Embiggens the Group Hero

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

## Part 1

You are given an array of integers. Write a script to calculate the number of integers smaller than the integer at each index.

### Solution

``````
use v5.38;
sub count_smaller{
my @integers = @_;
my @integers_sorted = sort {\$a <=> \$b} @integers;
return map {
my \$x = \$_;
(grep { \$integers[\$x] == \$integers_sorted[\$_]} 0 .. @integers_sorted - 1)[0];
} 0 .. @integers - 1;
}

MAIN:{
say join q/, /, count_smaller qw/8 1 2 2 3/;
say join q/, /, count_smaller qw/6 5 4 8/;
say join q/, /, count_smaller qw/2 2 2/;
}
``````

### Sample Run

``````
\$ perl perl/ch-1.pl
4, 0, 1, 1, 3
2, 1, 0, 3
0, 0, 0
``````

### Notes

I'll admit this is a little convoluted. Since we already have a nested loop with the `map` and `grep` this is not any more efficient than if I had just searched and summed the smaller elements.

The idea here is to sort the array of integers and then for each element in the original array find it's position in the sorted array. The number of elements preceding the sought after element in the sorted list are the number of elements which are smaller than it.

This approach may have a performance benefit in the case of extremely large lists coupled with early termination of the inner loop.

## Part 2

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.

### Solution

``````
use v5.38;
sub group_hero{
my @group = @_;
my \$group_hero = 0;
do{
my \$indices = \$_;
my @hero = sort {\$a <=> \$b} @group[grep{vec(\$indices, \$_, 1) == 1} 0 .. @group - 1];
\$group_hero += (\$hero[@hero - 1]**2 * \$hero[0]);
} for 1 .. 2**@group - 1;
return \$group_hero;
}

MAIN:{
say group_hero qw/2 1 4/;
}
``````

### Sample Run

``````
\$ perl perl/ch-2.pl
141
``````

### Notes

A core part of this problem is to compute the Power Set, set of all subsets, of the original array. To do this we use the well known trick of mapping the set bits of the numbers from `1 .. N^2`, where `N` is the size of the array, to the array indices.

`@group[grep{vec(\$indices, \$_, 1) == 1} 0 .. @group - 1]` examines which bit within each number `\$_` in `1 .. 2**@group - 1` are set and then uses them as the indices to `@group`. The elements from within `@group` that are found this way are then sorted to obtain the maximum and minimum needed for the final calculation.

## References

Power Set

Challenge 244

posted at: 14:30 by: Adam Russell | path: /perl | permanent link to this entry