Merge pull request #2366 from jo-37/contrib

Solutions to challenge 079

2 files changed, 109 insertions, 0 deletions

diff --git a/challenge-079/jo-37/perl/ch-1.pl b/challenge-079/jo-37/perl/ch-1.pl
new file mode 100755
index 0000000000..c44f5c75b4
--- /dev/null
+++ b/challenge-079/jo-37/perl/ch-1.pl
@@ -0,0 +1,39 @@
+#!/usr/bin/perl
+
+use Test2::V0;
+no warnings 'recursion';
+use bigint;
+
+# Calculate the sum of 1-bits in all numbers from 0 to n.  Going from 0
+# to n instead of 1 to n does not change the result, but simplifies the
+# calculation.  The modulus to 1000000007 is ignored as a number with
+# that many bits is far beyond anything manageable.
+sub bitsum {
+	my $n = shift;
+
+	# Break recursion.
+	return 0 unless $n;
+
+	# Get the largest number of the form 2^k - 1 that is (strictly) less
+	# than n.
+	my $allone = 2**(($n + 0)->blog(2)) - 1;
+
+	# Get the offset from the above number to n.
+	my $offset = $n - $allone;
+
+	# Split the numbers from 0 to n into two parts:
+	# - a maximum power-of-two block having zero as the highest bit.
+	#   Recursing into this part to get the bit sum.
+	# - a remaining block having one as the highest bit.  These leading
+	#   bits are added to the bit sum.  The bit-sum of the second part
+	#   with the leading bit set to zero is calculated by recursion.
+	# When splitting a full power-of-two part, both sub-parts to be
+	# recursed into are the same.  This leads to a shortcut for at least
+	# half of the calculations.
+	$offset + ($allone == $offset - 1 ? 2 * bitsum($allone) : bitsum($allone) + bitsum($offset - 1));
+}
+
+is bitsum(4), 5, 'first example';
+is bitsum(3), 4, 'second example';
+
+done_testing;
diff --git a/challenge-079/jo-37/perl/ch-2.pl b/challenge-079/jo-37/perl/ch-2.pl
new file mode 100644
index 0000000000..40f585a472
--- /dev/null
+++ b/challenge-079/jo-37/perl/ch-2.pl
@@ -0,0 +1,70 @@
+#!/usr/bin/perl
+
+use 5.014;
+use Test2::V0;
+no warnings 'experimental::smartmatch';
+use List::Util qw(uniqnum);
+
+# Count the trapped rain volume.
+sub trapped_rain_water {
+	my @hist = @_;
+
+	my $vol = 0;
+	my $prev_y;
+
+	# Iterate over the histogram at all distinct heights, increasingly.
+	for my $y (uniqnum sort {$a <=> $b} @hist) {
+		# At the floor.
+		unless (defined $prev_y) {
+			$prev_y = $y;
+			next;
+		}
+		# Get step size.
+		my $stepsize = $y - $prev_y;
+		$prev_y = $y;
+
+		my $length = 0;
+		my $leftwall = '';
+
+		# Iterate at the current height.
+		for my $x (0 .. $#hist) {
+			# Build a string representing the current position in the
+			# histogram.  Depicts the walls.
+			for ($leftwall . '_' . ($hist[$x] >= $y)) {
+
+				# At first wall.
+				when ('_1') {
+					$leftwall = 1;
+				};
+
+				# After left wall: increment the length of the temporary
+				# rectangle.
+				when ('1_') {
+					$length++;
+				};
+
+				# At right wall: The temporary volume after the left
+				# wall (if any) is now trapped by a right wall.  The
+				# right wall becomes the new left wall.
+				when ('1_1') {
+					$vol += $length * $stepsize;
+					$length = 0;
+				};
+			}
+		}
+	}
+
+	$vol;
+}
+
+is trapped_rain_water(2, 1, 4, 1, 2, 5), 6, 'first example';
+is trapped_rain_water(3, 1, 3, 1, 1, 5), 6, 'second example';
+# Other tests:
+is trapped_rain_water(7, 1, 1, 1, 7), 18, 'bucket';
+is trapped_rain_water(3, 2, 1, 2, 3), 4, 'gorge';
+is trapped_rain_water(1, 2, 3, 2, 1), 0, 'hill';
+is trapped_rain_water(1, 2, 3, 4, 5), 0, 'uphill';
+is trapped_rain_water(5, 4, 3, 2, 1), 0, 'downhill';
+is trapped_rain_water(1, 1, 1, 1, 1), 0, 'plain';
+
+done_testing;