 a guest
Jan 7th, 2014
120
0
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:
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. }