### 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";
```

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";
```

#### 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[0];
```

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{});
}
```

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

```
my $rainwater = 0;
my $tallest = $N[0];
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);
}
```