Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/usr/bin/perl -w
- # This small program solves the following problem:
- # http://programmingpraxis.com/2013/11/15/twitter-puddle/
- #
- # Input is a list of numbers separated by spaces, example: 3 2 3 0 2 6 4 5 2 1 4
- # Output is a single number representing the amount of water accumulated, example: 11
- #
- # Implementation details:
- # In order to do the calculation, this program divides the input list into two pieces,
- # each piece satisfying the condition that the highest value in the piece is located
- # at the right most position. The idea is that this condition makes the calculation
- # much easier.
- #
- # In order to create these two pieces, the maximum value is found first
- # and then the two pieces are [0 .. max] and reverse([max .. length-1]).
- use strict;
- use warnings;
- my $input = <STDIN>;
- chomp($input);
- # Read input list from STDIN
- my $list = [ split /\ /, $input ];
- my $total_water_amount = accumulatedWater($list);
- print "$total_water_amount\n";
- sub accumulatedWater {
- my $list = shift;
- # Find the max value
- my $max_index = 0;
- for(my $i = 1; $i < scalar(@{$list}); $i++) {
- $max_index = $i if $list->[$i] > $list->[$max_index];
- }
- my $total = 0;
- if($max_index > 0) {
- # Sum accumulated water on the first piece
- my @array = @{$list};
- my $list_part1 = [ @array[0 .. $max_index] ];
- $total += accumulatedWaterSimple($list_part1);
- }
- if($max_index < scalar(@{$list}) - 1) {
- # Sum accumulated water on the second piece
- my @array = @{$list};
- my $list_part2 = [ reverse @array[$max_index .. scalar(@array) - 1] ];
- $total += accumulatedWaterSimple($list_part2);
- }
- return $total;
- }
- # This method assumes that the max value in this list is located at the right most position
- sub accumulatedWaterSimple {
- my $list = shift;
- my $total_amount = 0;
- my $current_amount = undef;
- my $current_top = undef;
- my $prev_height = undef;
- foreach my $height (@{$list}) {
- if(!defined $prev_height) {
- $prev_height = $height;
- next;
- }
- if(defined $current_top) { # we are currently counting
- if($height < $current_top) { # just add to the current puddle
- $current_amount += $current_top - $height;
- }
- else { # finished a puddle
- $total_amount += $current_amount;
- $current_top = undef;
- $current_amount = undef;
- }
- }
- else {
- if($height < $prev_height) { # we start counting here
- $current_top = $prev_height;
- $current_amount = $current_top - $height;
- }
- }
- $prev_height = $height;
- }
- return $total_amount;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement