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
1to$Nand 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 unitof rain water between 1st and 3rd column. Similary it can trap5 unitsof 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 unitsof rain water between 1st and 3rd column. Also it can trap4 unitsof 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);
}