Perl Weekly Challenge 130.
My solutions (task 1, and task 2 ) to the The Weekly Challenge - 130 .
Task 1: Odd Number
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[0]:"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[0]:"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
# Task 1: Odd number
#
# See https://wlmb.github.io/2021/09/15/PWC130/#task-1-odd-number
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[0]:"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
#
# See https://wlmb.github.io/2021/09/15/PWC130/#task-2-binary-search-tree
use warnings;
use v5.12;
use YAML::Tiny;
$/=''; #slurp
my $tree=YAML::Tiny->read_string(my $data=<>);
my ($result)=is_bst($tree->[0]);
say "Input:\n$data\nOutput: ", $result->[0];
sub is_bst { # returns [0] 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 [0] unless $left->[0] && $right->[0]; # any children not bst=> not bst
# set default values to $value
my ($left_smallest, $left_largest, $right_smallest, $right_largest)
= map {$_//$value} ($left->[1], $left->[2], $right->[1], $right->[2]);
return [0] 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