Perl Weekly Challenge #79, Task #2

Daniel Mantovani — Thu, 24 Sep 2020 19:43:22 +0000

TASK #2 › Trapped Rain Water
Submitted by: Mohammad S Anwar
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.

Last date to submit the solution 23:59 (UK Time) Sunday 27th September 2020.

Proposed solution:

First of all, we are asked to print the histogram. This is not as trivial as it sounds, specially if the numbers involved have more than 1 digit, because that can misalign your columns.

To make all numbers uniform, we are using a sprintf format string with "%d" to accommodate the biggest number. For example, if the biggest number is 15, we need two digits so the used format will be "%2d" for all the numbers.

Histogram printing as requested

We evaluate each line without any spaces first, then we interpolate spaces between letters just to allow a nicer final view.

The following script would allow to print the histogram in that way:

use strict;
use warnings;
use v5.20;

# get input array from command line

my @N = @ARGV;

die "usage: perl $0 <space separate numbers (at least 3)>" unless @N > 2;

# check that all  numbers are positive, and find max value

my $max = -1;
for my $n (@N) {
  die "$n is not a proper positive number" unless $n && $n =~ /^\d+$/;
  $max = $n if $n > $max;
}

# we need to take care of the amount of decimal places needed
# form $max, so the histogram can look ok

my $places = length $max;

# so the format to print numbers should be:

my $dfmt = "\%${places}d";

for my $r (reverse 1 .. $max) {

  # construct horizontal row, starting from $max
  my $line = join('', map { $_ >= $r ? '#' : ' ' } @N);

  # we will add separating spaces between symbols
  $line = ' ' . join(' ', split('', $line));
  say sprintf($dfmt, $r) . $line;
}

# closing line
say " " x ($places - 1) . '_' . ' _' x @N;

# now print the base rows of the histogram

for my $i (0 .. $places - 1) {
  my $line = join(' ', map { substr(sprintf($dfmt, $_), $i, 1) } @N);
  say " " x ($places + 1) . $line;
}

Count trapped water units

To find how much water we can trap, we can take a look at a typical row of the histogram, before we add the spaces between letters (only the part of '#'s and spaces is important):

...
 2# #  #
...

So we have a '#', then 1 space, another '#', 2 more spaces, and finally another '#'.

In this case, we can trap 1 unit of water in the first space, and 2 more units in the 2 spaces after.

The pattern we are looking for then is something like /#\s+#/. Note also that the '#' in the middle should be matched against the first group (1 space), and also against the second group (2 spaces).

To do that we will replace al spaces in the match with another letter (a "W" for instance), so we can reset the regex and start again and match the following one.

The final expression will be:

while ($line =~ s/#(\s+)#/'#'. 'W' x length($1) . '#'/e) { }

This sentence will look for the first match, then replace the inner spaces by "W"s, and then start again until no more matches are found.

Note the /e modifier at the end of the regex, that means that the second part of the substitution is actually an expression to be evaluated (i.e. '#' . 'W' x length($1) . '#'

The final script proposed is then:

use strict;
use warnings;
use v5.20;

# get input array from command line

my @N = @ARGV;

die "usage: perl $0 <space separate numbers (at least 3)>" unless @N > 2;

# check that all  numbers are positive, and find max value

my $max = -1;
for my $n (@N) {
  die "$n is not a proper positive number" unless $n && $n =~ /^\d+$/;
  $max = $n if $n > $max;
}

# we need to take care of the amount of decimal places needed
# form $max, so the histogram can look ok

my $places = length $max;

# so the format to print numbers should be:

my $dfmt = "\%${places}d";

my $acc_water = 0;

for my $r (reverse 1 .. $max) {

  # construct horizontal row, starting from $max
  my $line = join('', map { $_ >= $r ? '#' : ' ' } @N);

  # we need to identify in this particular line how many units
  # of rain water we can trap. We will replace with a "W" every
  # one of those units.
  #
  # We search for the pattern #< n spaces>#, and as this will
  # allow to trap n units, we will replace the spaces with the
  # letter "W"

  # Note that after replacing one group, we should start over the
  # same line. We cannot continue looking because the last caracter
  # matched ('#') may be necesary for the next match. So we cannot
  # use a /g to repeat the search, we need to start over the
  # matching, but with the spaces changed to "W" so we don't get
  # the same match but the following one, if any.

  # For the regex, we use substitution (s///) and we calculate
  # the replacement with "W" x length(spaces captured), and leave
  # the '#'s in place. /e means we are evaluating the second
  # argument, instead of taking it literally
  #
  while ($line =~ s/#(\s+)#/'#'. 'W' x length($1) . '#'/e) { }

# units this row can trap is the amount of "W"s we have on it
# feel free to change the transliteration operator to tr/W/W/
# to keep an indication of the allocated water units
  $acc_water += $line =~ tr/W/ /;

  # we will add separating spaces between symbols, note we do that after any
  # calculation
  $line = ' ' . join(' ', split('', $line));
  say sprintf($dfmt, $r) . $line;
}

# closing line
say " " x ($places - 1) . '_' . ' _' x @N;

# now print the base rows of the histogram

for my $i (0 .. $places - 1) {
  my $line = join(' ', map { substr(sprintf($dfmt, $_), $i, 1) } @N);
  say " " x ($places + 1) . $line;
}

say "Trapped water: $acc_water";

Perl Weekly Challenge #79,Task #1

Daniel Mantovani — Wed, 23 Sep 2020 19:35:37 +0000

Task: 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.

Proposed Answer:

Note that perl already has the capability to get a binary expression of an integer, just using the sprintf formatter %b, as in

my $binary_string = sprintf("%b", $number);

We need to count how many "1"s are in the binary representation. There are many ways to do that in perl. We will use the return value of the transliteration internal function of perl (tr):

$amount_of_ones = $binary_string =~ tr/1//;

This will efectively remove all "1"s from our string, but most important, will return a scalar with the amount of substitutions done (i.e, number of 1s in the binary representation)

Also we are supposed to truncate to a modulo 1,000,000,007 integer on every addition, probably avoiding any overflows on perl arithmetic for 32 bit perls (that number is a prime number often used for that purpose).

So with all these considerations, our script will just be:

use strict;
use warnings;
use v5.20;

my $big_prime           = 1_000_000_007;
my $total_count_set_bit = 0;

for my $n (1 .. shift) {    # or $ARGV[0]
  $total_count_set_bit += sprintf("%b", $n) =~ tr/1//;
  $total_count_set_bit %= $big_prime;
}

say $total_count_set_bit;

As an example, you can use the script like this:

$> perl ch-1.pl 12345678
143433315
$> _