# RabbitFarm

### 2023-11-26

The Weekly Challenge 244 (Prolog Solutions)

*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

```
smaller([], _, 0).
smaller([H|Integers], X, Y):-
smaller(Integers, X, Y0),
((X > H, succ(Y0, Y));
(X =< H, Y = Y0)).
count_smaller(Integers, CountSmaller):-
maplist(smaller(Integers), Integers, CountSmaller).
```

### Sample Run

```
% gprolog --consult-file prolog/ch-1.p
| ?- count_smaller([2, 2, 2], CountSmaller).
CountSmaller = [0,0,0]
yes
| ?- count_smaller([6, 5, 4, 8], CountSmaller).
CountSmaller = [2,1,0,3] ?
yes
| ?- count_smaller([8, 1, 2, 2, 3], CountSmaller).
CountSmaller = [4,0,1,1,3] ?
yes
| ?-
```

### Notes

Probably this is the most obvious way to count up smaller elements as
required. In order to cut down on the recursion I call `smaller/3`

via
a `maplist/3`

.

## 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

```
group_hero(Group, GroupHero):-
findall(Hero, (
sublist(SubList, Group),
max_list(SubList, Maximum),
min_list(SubList, Minimum),
Hero #= Maximum**2 * Minimum
), Heroes),
sum_list(Heroes, GroupHero).
```

### Sample Run

```
% gprolog --consult-file prolog/ch-2.p
| ?- group_hero([2, 1, 4], GroupHero).
GroupHero = 141
yes
| ?-
```

### Notes

The core of this problem is to enumerate all the *Power Sets* of the
Group list. In other programming languages enumerating all sublists of a
list is straightforward enough, but requires much more code. Here, with
Prolog, we need only call `sublist/2`

with backtracking. We use a
`findall/3`

to generate all the necessary backtracking and create the
list of intermediate sums, which are then all summed for the final
solution.

## References

posted at: 15:01 by: Adam Russell | path: /prolog | permanent link to this entry

#### 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

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