Pastebin launched a little side project called HostCabi.net, check it out ;-)Don't like ads? PRO users don't see any ads ;-)
Guest

Twitter Puddle - Solution

By: a guest on Jan 7th, 2014  |  syntax: Perl  |  size: 2.80 KB  |  hits: 35  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #!/usr/bin/perl -w
  2.  
  3. # This small program solves the following problem:
  4. # http://programmingpraxis.com/2013/11/15/twitter-puddle/
  5. #
  6. # Input is a list of numbers separated by spaces, example: 3 2 3 0 2 6 4 5 2 1 4
  7. # Output is a single number representing the amount of water accumulated, example: 11
  8. #
  9. # Implementation details:
  10. # In order to do the calculation, this program divides the input list into two pieces,
  11. # each piece satisfying the condition that the highest value in the piece is located
  12. # at the right most position. The idea is that this condition makes the calculation
  13. # much easier.
  14. #
  15. # In order to create these two pieces, the maximum value is found first
  16. # and then the two pieces are [0 .. max] and reverse([max .. length-1]).
  17.  
  18. use strict;
  19. use warnings;
  20.  
  21. my $input = <STDIN>;
  22. chomp($input);
  23.  
  24. # Read input list from STDIN
  25. my $list = [ split /\ /, $input ];
  26. my $total_water_amount = accumulatedWater($list);
  27. print "$total_water_amount\n";
  28.  
  29. sub accumulatedWater {
  30.     my $list = shift;
  31.  
  32.     # Find the max value
  33.     my $max_index = 0;
  34.     for(my $i = 1; $i < scalar(@{$list}); $i++) {
  35.         $max_index = $i if $list->[$i] > $list->[$max_index];
  36.     }
  37.  
  38.     my $total = 0;
  39.     if($max_index > 0) {
  40.         # Sum accumulated water on the first piece
  41.         my @array = @{$list};
  42.         my $list_part1 = [ @array[0 .. $max_index] ];
  43.         $total += accumulatedWaterSimple($list_part1);
  44.     }
  45.     if($max_index < scalar(@{$list}) - 1) {
  46.         # Sum accumulated water on the second piece
  47.         my @array = @{$list};
  48.         my $list_part2 = [ reverse @array[$max_index .. scalar(@array) - 1] ];
  49.         $total += accumulatedWaterSimple($list_part2);
  50.     }
  51.  
  52.     return $total;
  53. }
  54.  
  55. # This method assumes that the max value in this list is located at the right most position
  56. sub accumulatedWaterSimple {
  57.     my $list = shift;
  58.  
  59.     my $total_amount = 0;
  60.  
  61.     my $current_amount = undef;
  62.     my $current_top = undef;
  63.     my $prev_height = undef;
  64.  
  65.     foreach my $height (@{$list}) {
  66.         if(!defined $prev_height) {
  67.             $prev_height = $height;
  68.             next;
  69.         }
  70.  
  71.         if(defined $current_top) { # we are currently counting
  72.             if($height < $current_top) { # just add to the current puddle
  73.                 $current_amount += $current_top - $height;
  74.             }
  75.             else { # finished a puddle
  76.                 $total_amount += $current_amount;
  77.                 $current_top = undef;
  78.                 $current_amount = undef;
  79.             }
  80.         }
  81.         else {
  82.             if($height < $prev_height) { # we start counting here
  83.                 $current_top = $prev_height;
  84.                 $current_amount = $current_top - $height;
  85.             }
  86.         }
  87.  
  88.         $prev_height = $height;
  89.     }
  90.  
  91.     return $total_amount;
  92. }