#!/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;
}