# Perl Weekly Challenge 130.

My solutions (task 1, and task 2 ) to the The Weekly Challenge - 130 .

``````Submitted by: Mohammad S Anwar
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.

Example 1
Input: @N = (2, 5, 4, 4, 5, 5, 2)
Output: 5 as it appears 3 times in the array where as all
other numbers 2 and 4 appears exactly twice.
Example 2
Input: @N = (1, 2, 3, 4, 3, 2, 1, 4, 4)
Output: 4
``````

I can count the appearances of each number with a hash, choose those elements that have an odd number of repetitions and print the result if there is only one. This fits in a one liner.

``````perl -E 'map {++\$r{\$_}} @ARGV; @o=grep {\$r{\$_}%2} keys %r;\
say "Input: ", join " ", @ARGV;\
say "Output: ", @o==1?\$o:"Wrong input"' 2 5 4 4 5 5 2
perl -E 'map {++\$r{\$_}} @ARGV; @o=grep {\$r{\$_}%2} keys %r;\
say "Input: ", join " ", @ARGV;\
say "Output: ", @o==1?\$o:"Wrong input"' 1 2 3 4 3 2 1 4 4
``````

Results:

``````Input: 2 5 4 4 5 5 2
Output: 5
Input: 1 2 3 4 3 2 1 4 4
Output: 4
``````

The full version would be

``````# Perl weekly challenge 130
#
use warnings;
use v5.12;
my %repetitions_of;
map {++\$repetitions_of{\$_}} @ARGV;
my @output=grep {\$repetitions_of{\$_}%2} keys %repetitions_of;
say "Input: ", join " ", @ARGV;
say "Output: ", @output==1?\$output:"Wrong input";
``````

Examples:

``````./ch-1.pl 2 5 4 4 5 5 2
./ch-1.pl 1 2 3 4 3 2 1 4 4
``````

Results:

``````Input: 2 5 4 4 5 5 2
Output: 5
Input: 1 2 3 4 3 2 1 4 4
Output: 4
``````

Examples with invalid input:

``````./ch-1.pl 2 5 4 4 5 5 2 5 # no odd number of appearances
./ch-1.pl 1 2 3 4 3 2 1 4 4 2 # more than one odd number of appearances
``````

Results:

``````Input: 2 5 4 4 5 5 2 5
Output: Wrong input
Input: 1 2 3 4 3 2 1 4 4 2
Output: Wrong input
``````

# Task 2: Binary Search Tree

``````Submitted by: Mohammad S Anwar
You are given a tree.

Write a script to find out if the given tree is Binary Search
Tree (BST).

According to wikipedia, the definition of BST:

A binary search tree is a rooted binary tree, whose internal
nodes each store a key (and optionally, an associated value),
and each has two distinguished sub-trees, commonly denoted
left and right. The tree additionally satisfies the binary
search property: the key in each node is greater than or equal
to any key stored in the left sub-tree, and less than or equal
to any key stored in the right sub-tree. The leaves (final
nodes) of the tree contain no key and have no structure to
distinguish them from one another.

Example 1
Input:
8
/ \
5   9
/ \
4   6

Output: 1 as the given tree is a BST.
Example 2
Input:
5
/ \
4   7
/ \
3   6

Output: 0 as the given tree is a not BST.
``````

In previous posts (for example, PWC125 and PWC129) I have read the tree either as a `Perl` expresion to be eval’ed, representing an anonymous nested array reference, or using an indented list. This time I solve the input using a `YAML` expression to represent the tree (with keys v for value, l for left and r for right). I recursively check if the tree is a binary search tree with a function `is_bst` that returns an array whose first element is an indicator of bst’ness, and the others are the minimum and largest value of the (sub)tree.

``````# Perl weekly challenge 130
# Task 2:  Binary search tree
#
use warnings;
use v5.12;
use YAML::Tiny;
\$/=''; #slurp
my (\$result)=is_bst(\$tree->);
say "Input:\n\$data\nOutput: ", \$result->;
sub is_bst { # returns  on failure, [1, smallest, largest] on success
my \$tree=shift;
return [1, undef, undef] unless defined \$tree; # I consider empty trees as bst
my \$value=\$tree->{v};
die "Malformed tree" unless defined \$value;
my (\$left, \$right)=map {is_bst(\$tree->{\$_})} qw(l r);
return  unless \$left-> && \$right->; # any children not bst=> not bst
# set default values to \$value
my (\$left_smallest, \$left_largest, \$right_smallest, \$right_largest)
= map {\$_//\$value} (\$left->, \$left->, \$right->, \$right->);
return  if \$left_largest > \$value || \$right_smallest < \$value;
return [1, \$left_smallest, \$right_largest];
}
``````

Example 1:

``````    8
/ \
5   9
/ \
4   6

./ch-2.pl <<END
v: 8
l:
v: 5
l:
v: 4
r:
v: 6
r:
v: 9
END
``````

Results:

``````Input:
v: 8
l:
v: 5
l:
v: 4
r:
v: 6
r:
v: 9

Output: 1
``````

Example 2:

``````Input:
5
/ \
4   7
/ \
3   6

./ch-2.pl <<END
v: 5
l:
v: 4
l:
v: 3
r:
v: 6
r:
v: 7
END
``````

Results:

``````Input:
v: 5
l:
v: 4
l:
v: 3
r:
v: 6
r:
v: 7

Output: 0
``````
Written on September 15, 2021