- Added solutions by Peter Campbell Smith.

2 files changed, 135 insertions, 0 deletions

diff --git a/challenge-130/peter-campbell-smith/perl/ch-1.pl b/challenge-130/peter-campbell-smith/perl/ch-1.pl
new file mode 100755
index 0000000000..d5ea4cead5
--- /dev/null
+++ b/challenge-130/peter-campbell-smith/perl/ch-1.pl
@@ -0,0 +1,34 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+# PWC 130 task 1 - Peter Campbell Smith - 2021-09-14
+
+# You are given an array of positive integers, such that all 
+# the numbers appear even number of times except one number.
+# Write a script to find that integer.
+
+# There is no way to solve this without inspecting every element
+# of the array. One approach would be to sort the array
+# and look for the first odd-length sequence, but it is
+# unlikely that the sort can be done more cheaply than the
+# simple algorithm shown below.
+
+my (@N, $j, %count);
+
+# sample data (3 is the answer)
+@N = (1, 2, 3, 4, 3, 2, 1, 4, 4, 3, 4);
+
+# get $count{$j} == number of instances of $j
+for $j (@N) {
+	$count{$j}++;
+}
+
+# look for the first instance of $count{$j} being odd                                                                 
+for $j (keys %count) {
+	if ($count{$j} & 1) {
+		print qq[The answer is $j\n];
+		last;
+	}
+}
diff --git a/challenge-130/peter-campbell-smith/perl/ch-2.pl b/challenge-130/peter-campbell-smith/perl/ch-2.pl
new file mode 100755
index 0000000000..859e24235a
--- /dev/null
+++ b/challenge-130/peter-campbell-smith/perl/ch-2.pl
@@ -0,0 +1,101 @@
+#!/usr/bin/perl
+use strict;
+use warnings;
+
+# PWC 130 task 2 - Peter Campbell Smith - 2021-09-14
+
+# You are given a tree. Write a script to find out if the given tree is a Binary 
+# Search Tree (BST).
+
+# The solution shown below expects the input to be a
+# file with one line per node, containing
+#      node_id, node_key, node side, node_id_of_parent
+# 'node_id' is a sequential number (starting from 0),
+# 'node_side' is L or R and 'node_parent' is the node_id of the parent
+# of the parent node. The first line is the node_id and key of the root node.
+
+# Here is the sample tree (in __DATA__) shown as node_id->key
+#
+#                          0->50
+#                 _____/           \_____
+#           1->25                        2->75
+#         /      \                     /       \ 
+#    3->12        4->36          5->63           6->88
+#   /    \       /     \        /      \       /       \
+# 7->6  8->18  9->30 10->42  11->57  12->69  13->82  14->94
+
+# The nodes in this code are not strictly the same as the nodes in
+# the BST as defined by Wikipedia, as the Wikipedia nodes contain L and R
+# downward pointers to the child level, whereas the nodes here contain upward 
+# pointers to the parent level.
+
+# To demonstrate a lowest leaf conflicting with the root, change the
+# key of node 10 from 42 to 51.
+
+our @nodes;
+
+read_nodes();
+check_nodes();
+
+print qq[This is a valid binary search tree\n];
+
+sub read_nodes {
+	
+	my ($n, $line, @keys, $junk);
+	
+	# read in tree
+	$n = 0;
+	while ($line = <DATA>) {
+		@keys = split /[\s,]+/, $line;
+		($nodes[$n]->{id}, $nodes[$n]->{key}, $nodes[$n]->{side}, $nodes[$n++]->{parent}) = @keys;
+	}	
+}
+
+sub check_nodes {
+	
+	my ($node_id, $node, $key, $this_node, $parent);
+
+	# loop over nodes
+	for $node_id (1 .. $#nodes) {
+		$node = $nodes[$node_id];
+		$key = $node->{key};
+		
+		# need to check against every node back up to the root
+		$this_node = $node;
+		while (1) {
+			$parent = $this_node->{parent};
+			if ($this_node->{side} eq 'L') {
+				is_bad(qq[node $node_id->$key > node $nodes[$parent]->{id}->$nodes[$parent]->{key}]) 
+					if $key > $nodes[$parent]->{key};
+			} elsif ($this_node->{side} eq 'R') {
+				is_bad(qq[node $node_id->$key < node $nodes[$parent]->{id}->$nodes[$parent]->{key}]) 
+					if $key < $nodes[$parent]->{key};
+			} 
+			last if $parent == 0;
+			$this_node = $nodes[$parent];
+		}
+	}
+}
+
+sub is_bad {
+	
+	print qq[This is not a valid binary search tree as $_[0]\n];
+	exit;
+}
+
+__DATA__
+0, 50
+1, 25,L,0
+2, 75,R,0
+3, 12,L,1
+4, 36,R,1
+5, 63,L,2
+6, 88,R,2
+7,  6,L,3
+8, 18,R,3
+9, 26,L,4
+10,42,R,4
+11,57,L,5
+12,69,R,5
+13,82,L,6
+14,94,R,6