G2A Many GEOs
SHARE
TWEET

Twitter Puddle - Solution

a guest Jan 7th, 2014 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
Ledger Nano X - The secure hardware wallet
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top