Perl 주간 챌린지 #79, 작업 #2

작업 #2 › 갇힌 빗물
제출자: Mohammad S Anwar
양수 배열 @N이 제공됩니다.

히스토그램 차트로 표현하는 스크립트를 작성하고 얼마나 많은 물을 가둘 수 있는지 알아내십시오.

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.

솔루션 제출 마감일은 2020년 9월 27일 일요일 23:59(영국 시간)입니다.

제안 된 해법:

먼저 히스토그램을 인쇄하라는 요청을 받았습니다. 특히 관련된 숫자에 1자리 이상의 숫자가 있는 경우 열이 잘못 정렬될 수 있기 때문에 이것은 들리는 것처럼 사소하지 않습니다.

모든 숫자를 균일하게 만들기 위해 "%d"가 있는 sprintf 형식 문자열을 사용하여 가장 큰 숫자를 수용합니다. 예를 들어, 가장 큰 숫자가 15인 경우 사용되는 형식은 모든 숫자에 대해 "%2d"가 되도록 두 자리 숫자가 필요합니다.

요청에 따라 히스토그램 인쇄

먼저 공백 없이 각 줄을 평가한 다음 더 나은 최종 보기를 허용하기 위해 문자 사이에 공백을 삽입합니다.

다음 스크립트를 사용하면 히스토그램을 그런 방식으로 인쇄할 수 있습니다.

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;
}

갇힌 물 단위 계산

얼마나 많은 물을 가둘 수 있는지 알아보기 위해 문자 사이에 공백을 추가하기 전에 히스토그램의 일반적인 행을 살펴볼 수 있습니다('#'과 공백의 일부만 중요).

...
 2# #  #
...

그래서 우리는 '#', 그 다음 1개의 공백, 또 다른 '#', 2개의 추가 공백, 그리고 마지막으로 또 다른 '#'이 있습니다.

이 경우 첫 번째 공간에 1단위의 물을 가둘 수 있고 이후 2칸에 2단위를 더 가둘 수 있습니다.

우리가 찾고 있는 패턴은/#\s+#/와 같은 것입니다. 또한 중간에 있는 '#'은 첫 번째 그룹(공백 1개)과 일치해야 하고 두 번째 그룹(공백 2개)과도 일치해야 합니다.

이를 위해 일치 항목의 모든 공백을 다른 문자(예: "W")로 대체하여 정규식을 재설정하고 다시 시작하여 다음 문자와 일치시킬 수 있습니다.

최종 표현식은 다음과 같습니다.

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

이 문장은 첫 번째 일치 항목을 찾은 다음 내부 공백을 "W"로 바꾸고 더 이상 일치 항목을 찾을 수 없을 때까지 다시 시작합니다.

정규식 끝에 있는/e 수정자를 주목하십시오. 이는 대체의 두 번째 부분이 실제로 평가될 표현식임을 의미합니다(즉, '#' . 'W' x length($1) . '#'

제안된 최종 스크립트는 다음과 같습니다.

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