### Perl Weekly Challenge: Week 79

#### Challenge 1:

Count Set Bits

You are given a positive number `\$N`.

Write a script to count the total numbrer of set bits of the binary representations of all numbers from `1` to `\$N` and return `\$total_count_set_bit % 1000000007`.

##### Example 1:
``````Input: \$N = 4

Explanation: First find out the set bit counts of all numbers i.e. 1, 2, 3 and 4.

Decimal: 1
Binary: 001
Set Bit Counts: 1

Decimal: 2
Binary: 010
Set Bit Counts: 1

Decimal: 3
Binary: 011
Set Bit Counts: 2

Decimal: 4
Binary: 100
Set Bit Counts: 1

Total set bit count: 1 + 1 + 2 + 1 = 5

Output: Your script should print `5` as `5 % 1000000007 = 5`.
``````
##### Example 2:
``````Input: \$N = 3

Explanation: First find out the set bit counts of all numbers i.e. 1, 2 and 3.

Decimal: 1
Binary: 01
Set Bit Count: 1

Decimal: 2
Binary: 10
Set Bit Count: 1

Decimal: 3
Binary: 11
Set Bit Count: 2

Total set bit count: 1 + 1 + 2 = 4

Output: Your script should print `4` as `4 % 1000000007 = 4`.
``````

In Raku this is straightforward; I could even have made it a one-liner but given that `\$total` is used twice it is actually shorter this way. The first step is to take the range of numbers from 1 to `\$N` and then use `.map()` to convert them to binary and get the number of 1's in each via a regex. Then the `[+]` operator is used to sum them up into `\$total`.

``````my \$total = [+] (1 .. \$N).map({ sprintf("%b", \$_) ~~ m:g/ 1 /; });
``````

The second line outputs `\$total` in the required format.

``````say "\$total % 1000000007 = \$total";
``````

(Full code on Github.)

In Perl we don't have `[+]` so I added to `\$total` inside the `map()` block instead. And I used `tr()` instead of matching to get the count of 1's.

``````my \$total = 0;
map { \$total += sprintf("%b", \$_) =~ tr/1/1/; } 1 .. \$N;

say "\$total % 1000000007 = \$total";
``````

(Full code on Github.)

#### Challenge 2:

Trapped Rain Water

You are given an array of positive numbers `@N`.

Write a script to represent it as Histogram Chart and find out how much water it can trap.

##### Example 1:

Input: @N = (2, 1, 4, 1, 2, 5)

The histogram representation of the given array is as below.

`````` 5           #
4     #     #
3     #     #
2 #   #   # #
1 # # # # # #
_ _ _ _ _ _ _
2 1 4 1 2 5
``````

Looking at the above histogram, we can see, it can trap `1 unit` of rain water between 1st and 3rd column. Similary it can trap `5 units` of rain water betweem 3rd and last column.

Therefore your script should print `6`.

##### Example 2:

Input: @N = (3, 1, 3, 1, 1, 5)

The histogram representation of the given array is as below.

`````` 5           #
4           #
3 #   #     #
2 #   #     #
1 # # # # # #
_ _ _ _ _ _ _
3 1 3 1 1 5
``````

Looking at the above histogram, we can see, it can trap `2 units` of rain water between 1st and 3rd column. Also it can trap `4 units` of rain water between 3rd and last column.

Therefore your script should print `6`

My first attempt at a solution (in Raku) was hideously overcomplicated with loops within loops etc. And while it did work, it dawned on me that the task can be made a lot simpler.

First we set up a variable to hold the running total of units of rainwater. my \$rainwater = 0;

And this was my key insight. We only need to keep track of the current tallest column. Initially it is set to the first column.

``````my \$tallest = @N;
``````

Then we go through `\$N` element by element.

``````for 0 ..^ @N.elems -> \$i {
``````

If the size of the column is smaller than `\$tallest`, we can add `(size of the column) - \$tallest` units of rainwater...

``````    if (@N[\$i] < \$tallest) {
\$rainwater += (\$tallest - @N[\$i]);
} else {
``````

...otherwise the size of the column becomes the new value of `\$tallest`.

``````        \$tallest = @N[\$i];
}
}
``````

All that remains once `\$N` has been fully traversed, is to print out the results. The spec is a little ambiguous but it seem to suggest we should print the histogram too.

``````histogram(@N);
say \$rainwater;
``````

As you can see I made a seperate function for the histogram. It is shown below.

``````sub histogram(@N) {
``````

The `.max()` method gives the largest value in an array. We need this to determine the maximum height of the histogram. Then we range backwards from the maximum height to 1 to form the y-axis of the graph.

``````    for @N.max ... 1 -> \$y {
``````

The value of Y is printed and then `@N` is traversed element by element. if the value of the current element is less than the current value of `\$y` a space is returned or if not, a hash symbol. These are all joined together into a string and printed.

``````        say "\$y ",
(0 ..^ @N.elems).map({ @N[\$_] < \$y ?? q{ } !! q{#}; }).join(q{});
}
``````

To make things a little more legible, a row of dashes is printed.

``````    say '-' x @N.elems + 2;
``````

Finally, the values of `@N` are printed.

``````    say q{  }, @N.join(q{});
}
``````

(Full code on Github.)

The Raku code for the main algorithm can be translated into perl straightforwardly.

``````my \$rainwater = 0;
my \$tallest = \$N;

for my \$i (0 .. scalar @N - 1) {

if (\$N[\$i] < \$tallest) {
\$rainwater += (\$tallest - \$N[\$i]);
} else {
\$tallest = \$N[\$i];
}
}

histogram(@N);
say \$rainwater;
``````

Translating `histogram()` is slightly trickier. For one thing, we don't have `.max()` (unless we use CPAN modules which I would in a real life situation but tend not to in these challenges.) This is a quick replacement.

``````sub max {
my (@N) = @_;
my \$maximum = 0;

for my \$i (@N) {
if (\$i > \$maximum) {
\$maximum = \$i;
}
}

return \$maximum;
}
``````

In `histogram()` itself, we can't do reverse ranges with the handy `...` so you have to explicitly use `reverse()` instead.

``````sub histogram {
my (@N) = @_;

for my \$y (reverse 1 .. max(@N)) {
say "\$y ",
(join q{}, map { \$N[\$_] < \$y ? q{ } : q{#}; } (0 .. scalar @N - 1));
}
say '-' x scalar @N + 2;
say q{  }, (join q{}, @N);
}
``````

(Full code on Github.)