Perl Weekly Challenge Week 079

The Weekly Challenge - 079

Published 24 September 2020 by Steven Wilson.

My final solutions for week 79 can be found here

Task 2 > Trapped Rain Water

Problem Statement

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.

Solution

My solution is to transform the histogram into an array of arrays where the arrays hold rows in the histogram. Columns will be represented by 0 and whitespace will be represented by 1. This gives me the following array of arrays for the above example:

array[3]: ( 1, 1, 1, 1, 1, 0 )
array[2]: ( 1, 1, 0, 1, 1, 0 )
array[1]: ( 1, 1, 0, 1, 1, 0 )
array[0]: ( 0, 1, 0, 1, 0, 0 )

I can discard arrays from the top if their sum is equal to the size of the input array minus 1, meaning there is only 1 column, which holds no water. Next I will 'trim' each array by removing 1s at the beginning and end of an array, the 1s need to be between 0s to trap rain water. I'm left with:

array[2]: ( 0, 1, 1, 0 )
array[1]: ( 0, 1, 1, 0 )
array[0]: ( 0, 1, 0, 1, 0, 0 )

The total sum of the arrays will then give me the answer to how much water the histogram can trap.

In practice my code doesn't create an array of arrays, instead I discard and trim rows after their creation and keep a running total of the sum.

I wasn't sure whether or not to print out the histogram. I didn't initially and retroactively printing it made the script look messy so the below code is what I'm presenting.

Perl Code

#!/usr/bin/env perl

use strict;
use warnings;
use feature qw/ say /;
use List::Util qw/ sum max /;
use Test::More;

my @N1_t = ( 2, 1, 4, 1, 2, 5 );
my @N2_t = ( 3, 1, 3, 1, 1, 5 );
ok( water_trapped( \@N1_t ) == 6 );
ok( water_trapped( \@N2_t ) == 6 );
done_testing();

sub water_trapped {
    my $input_ref   = shift;
    my @input       = @{$input_ref};
    my $hist_width  = scalar @input;
    my $hist_height = max(@input);
    my $total_water_trapped;

    for my $row ( 2 .. $hist_height ) {
        my @row_array;
        for my $column ( 0 .. $hist_width - 1 ) {
            if ( $input[$column] >= $row ) {
                $row_array[$column] = 0;
            }
            else {
                $row_array[$column] = 1;
            }
        }
        if ( !( sum(@row_array) == $hist_width - 1 ) ) {
            while ( $row_array[0] == 1 ) {
                shift @row_array;
            }
            while ( $row_array[-1] == 1 ) {
                pop @row_array;
            }
            $total_water_trapped += sum(@row_array);
        }
    }
    return $total_water_trapped;
}

Solution on Github