Peter's solutions to week 151

3 files changed, 97 insertions, 0 deletions

diff --git a/challenge-151/peter-campbell-smith/blog.txt b/challenge-151/peter-campbell-smith/blog.txt
new file mode 100644
index 0000000000..3f7dee49be
--- /dev/null
+++ b/challenge-151/peter-campbell-smith/blog.txt
@@ -0,0 +1 @@
+https://pjcs-pwc.blogspot.com/2022/02/locate-leaf-and-rob-road.html
diff --git a/challenge-151/peter-campbell-smith/perl/ch-1.pl b/challenge-151/peter-campbell-smith/perl/ch-1.pl
new file mode 100755
index 0000000000..2b8eef7ff4
--- /dev/null
+++ b/challenge-151/peter-campbell-smith/perl/ch-1.pl
@@ -0,0 +1,49 @@
+#!/usr/bin/perl
+
+# Peter Campbell Smith - 2022-01-31
+# PWC 150 task 1
+
+use v5.28;
+use strict;
+use utf8;
+
+# You are given binary tree. Write a script to find the minimum depth.
+# The minimum depth is the number of nodes from the root to the nearest leaf node 
+# (node without any children).
+
+# Note: this assumes that all occupied nodes contain a single character.  if that
+# were not the case, the same algorithm would work using an array rather than
+# a string to represent the contents of each level.
+
+my (@tests, $test, @levels, $level, $child1, $child2, $j);
+
+@tests = ('1 | 2 3 | 4 5', '1 | 2 3 | 4 *  * 5 | * 6', '1|23|4567|890123456|7');
+
+# loop over tests
+TEST: for $test (@tests) {
+	say qq[\nInput:  $test];
+	$test =~ s/ //g;    # eliminate spaces from test string
+	
+	# split levels into array
+	@levels = split(/\|/, $test);
+	
+	# loop over levels
+	for ($level = 0;; $level ++) {   # loop over levels
+	
+		# loop over nodes within level
+		for $j (0 .. 2 ** $level - 1) {
+
+			# for the jth node in this level the children are in the next level at 2j and 2j+1
+			$child1 = substr($levels[$level + 1], 2 * $j, 1);
+			$child2 = substr($levels[$level + 1], 2 * $j + 1, 1);
+
+			# if neither child exists we have reached the shortest branch
+			if ((! $child1 or $child1 eq '*') and (! $child2 or $child2 eq '*')) {
+				say qq[Output: ] . ($level + 1);
+				next TEST;
+			}
+		}
+	}
+}
+			
+			
diff --git a/challenge-151/peter-campbell-smith/perl/ch-2.pl b/challenge-151/peter-campbell-smith/perl/ch-2.pl
new file mode 100755
index 0000000000..47dfad0dc8
--- /dev/null
+++ b/challenge-151/peter-campbell-smith/perl/ch-2.pl
@@ -0,0 +1,47 @@
+#!/usr/bin/perl
+
+# Peter Campbell Smith - 2022-01-31
+# PWC 150 task 2
+
+use v5.28;
+use strict;
+use utf8;
+
+# You are planning to rob a row of houses, always starting with the first 
+# and moving in the same direction. However, you can’t rob two adjacent houses.
+# Write a script to find the highest possible gain that can be achieved.
+
+my (@tests, $test, @houses, $last, $best);
+
+@tests = ([2, 4, 5], [4, 2, 3, 6, 5, 3],
+	[32, 32, 8, 12, 46, 28, 79, 81, 84, 23, 48, 88, 38, 36, 44, 45, 55, 74, 33, 54, 49, 33, 54, 50, 20, 45, 79, 94, 48,
+	94, 51, 93, 88, 23, 19]);
+
+# loop over tests
+for $test (@tests) {
+	
+	@houses = @$test;	
+	say qq[\nInput: ] . join(' ', @$test);
+	$best = 0;
+	$last = scalar @houses - 1;
+	
+	# start at house 0 and we've got $houses[0] in the swag bag
+	robberies(0, $houses[0]);
+	say qq[Output: $best];
+}
+
+sub robberies {
+	
+	# robberies($number, $swag) updates $best with the best result starting from house $number
+	# with $swag already in the bag
+		
+	my ($number, $swag, $next, $new_swag);
+	
+	($number, $swag) = @_;	
+	# try all the next allowable houses starting from $number
+	for ($next = $number + 2; $next <= $last; $next ++) {
+		$new_swag = $swag + $houses[$next];
+		$best = $new_swag if $new_swag > $best;   # looking good!
+		robberies($next, $new_swag);
+	}
+}
\ No newline at end of file