Perl Weekly Challenge 129.
My solutions (task 1, and task 2 ) to the The Weekly Challenge - 129.
Task 1: Root Distance
Submitted by: Mohammad S Anwar
You are given a tree and a node of the given tree.
Write a script to find out the distance of the given node from
the root.
Example 1:
Tree:
1
/ \
2 3
\
4
/ \
5 6
Node: 6
Output: 3 as the distance of given node 6 from the root (1).
Node: 5
Output: 3
Node: 2
Output: 1
Node: 4
Output: 2
Example 2:
Tree:
1
/ \
2 3
/ \
4 5
\ /
6 7
/ \
8 9
Node: 7
Output: 3 as the distance of given node 6 from the root (1).
Node: 8
Output: 4
Node: 6
Output: 3
Trees are difficult to represent as ordinary text. In previous
challenges I have used perl code for nested array
references. They are easy to process but hard to write and
read for humans. Now, I will use nested emacs org mode lists
to represent the tree. Thus, children are distinguished from
parents by their indentation. I allow value-less nodes to
represent empty trees. I make a routine to build the
internal tree structure, as a hash reference. As I read each
line, it is not known a priori if it corresponds to a
children, a sibling or an uncle. Thus, I may have to keep the
input line and it associated indentation and value until it is
ready for processing. After I build the tree structure, I
could use it to analyze the depth corresponding to each
value. Nevertheless, this could be done on the fly while
building the tree, after which the tree structure could be
discarded. Though I could have avoided building it, I kept it
for debugging.
# Perl weekly challenge 129
# Task 1: root distance
#
# See https://wlmb.github.io/2021/09/06/PWC129/#task-1-root-distance
use warnings;
use strict;
use v5.12;
# use Data::Dumper;
my %root_distance; # hash of depths indexed by the node values.
# my $tree= # Throw away the actual tree, as it is not used
analyze_tree(-1,-1); # initialize indentation and depth.
# say Dumper($tree); # For debugging
say "Value: $_ Depth: ", $root_distance{$_}//"Not defined" for @ARGV;
sub analyze_tree {
my ($previous_indent, $depth)=@_;
++$depth;
my ($current_indent, $value)=analyze_line($previous_indent);
# If I found a node at the correct indentation, build a tree structure
$root_distance{$value}=$depth, #
return {value=>$value,
left=>analyze_tree($current_indent,$depth),
right=>analyze_tree($current_indent,$depth)}
if defined $current_indent && defined $value && $value ne '';
return undef;
}
sub analyze_line {
# Read and analyze lines. Keep them until their turn if outdented
state ($line, $current_indent, $value);
my $previous_indent=shift;
if(!defined $current_indent){
$line=<STDIN>;
return () if !defined $line || $line=~m/^\s*$/;
die "Malformed tree: $line" unless $line=~m/^(\s*)-\s*(\d*)\s*$/;
$current_indent=length $1;
$value=$2;
}
if($current_indent>$previous_indent){
my $result_indent=$current_indent;
$current_indent=undef;
return ($result_indent, $value);
}
return ();
}
Example 1:
./ch-1.pl 6 5 2 4 << 'EOF'
- 1
- 2
- 3
-
- 4
- 5
- 6
EOF
Results:
Value: 6 Depth: 3
Value: 5 Depth: 3
Value: 2 Depth: 1
Value: 4 Depth: 2
Example 2:
./ch-1.pl 7 8 6 << 'EOF'
- 1
- 2
- 4
-
- 6
- 8
- 9
-
- 3
-
- 5
- 7
-
EOF
Results:
Value: 7 Depth: 3
Value: 8 Depth: 4
Value: 6 Depth: 3
Task 2: Add Linked Lists
Submitted by: Mohammad S Anwar
You are given two linked list having single digit positive
numbers.
Write a script to add the two linked list and create a new
linked representing the sum of the two linked list
numbers. The two linked lists may or may not have the same
number of elements.
HINT: Just a suggestion, feel free to come up with your own
unique way to deal with the task. I am expecting a class
representing linked list. It should have methods to create a
linked list given list of single digit positive numbers and a
method to add new member. Also have a method that takes 2
linked list objects and returns a new linked list. Finally a
method to print the linked list object in a user friendly
format.
Example 1:
Input: L1 = 1 -> 2 -> 3
L2 = 3 -> 2 -> 1
Output: 4 -> 4 -> 4
Operation: Pick the first rightmost element of L1 i.e. 3
and adds to the first rightmost element of L2 i.e. 1. Finally
store the result i.e. 3 in the new linked list. Move to the
next one of both linked lists L1 and L2, perform the same
operation. In case the sum >= 10 then you apply the same rule
you would do to regular addition problem i.e. divide the sum
by 10 keep the remainder and push to the new linked
list. Don't forget to carry, 1, to the next operation. In case
one linked list is smaller than the other, you can safely
assume it is 0..
Example 2:
Input: L1 = 1 -> 2 -> 3 -> 4 -> 5
L2 = 6 -> 5 -> 5
Output: 1 -> 3 -> 0 -> 0 -> 0
Operation:
a) 1st member of L1 = 5 and 1st member of L2 = 5
b) 5 + 5 = 10
c) 0 pushed to the new linked list.
d) carry forward 1.
e) 2nd member of L1 = 4 and 2nd member of L2 = 5
f) 4 + 5 + 1 (carry) = 10
h) 0 again pushed to the new linked list.
i) carry forward 1.
j) 3rd member of L1 = 3 and 3rd member of L2 = 6
k) 3 + 6 + 1 (carry) = 10
l) 0 pshed to the new linked list.
m) carry forward 1.
n) 4th member of L1 = 2 and assume 0 as the 4th member of
L2 since there are only 3 members.
o) 2 + 1 (carry) = 3
p) 3 pushed to the new linked list.
q) 5th member of L1 = 1 and assume 0 as the 5th member of
L2 since there are only 3 members.
r) 1 + 0 = 1
s) 1 pushed to the new linked list.
So the new linked list now have: 1 -> 3 -> 0 -> 0 -> 0.
The above suggestion is one way, not necessarily the best
way to deal with it.
There are many ways to describe linked lists. In Perl I
could use a simple array, as splicing allows all operations
that could be done with linked lists. Furthermore, as each
element contains only one digit, I could represent the array by a
string. Finally, strings can represent numbers. This suggest a
trivial one-liner solution. Is it cheating?
Example 1:
perl -E '($A,$B)=map {join "", split /\s*->\s*/, $_} @ARGV;'\
-E 'say join "->", split "", $A+$B;' "1->2->3" "3->2->1"
Results:
4->4->4
Example 2:
perl -E '($A,$B)=map {join "", split /\s*->\s*/, $_} @ARGV;'\
-E 'say join "->", split "", $A+$B;' "1->2->3->4->5" "6->5->5"
Results:
1->3->0->0->0
The longer version:
# Perl weekly challenge 129
# Task 2: add linked lists
#
# See https://wlmb.github.io/2021/09/06/PWC129/#task-2-add-linked-lists
use warnings;
use strict;
use v5.12;
use List::Util qw(all);
use bigint; # to allow large lists
my @A=split /\s*->\s*/, shift @ARGV;
my @B=split /\s*->\s*/, shift @ARGV;
die "Usage: ./ch-2.pl l1 l2 with list arguments of the form \"dN...d2->d1->d0\""
unless all {m/^\d$/} @A, @B;
my $A=join '', @A;
my $B=join '', @B;
my $length=@A-@B;
my $indent_A=$length<0?" "x(-$length):"";
my $indent_B=$length>0?" "x $length :"";
say "Input: L1=$indent_A", join "->", @A;
say " L2=$indent_B", join "->", @B;
say "Output: ", join "->", split '', $A+$B;
Example 1:
./ch-2.pl "1->2->3" "3->2->1"
Results:
Input: L1=1->2->3
L2=3->2->1
Output: 4->4->4
Example 2:
./ch-2.pl "1->2->3->4->5" "6->5->5"
Results:
Input: L1=1->2->3->4->5
L2= 6->5->5
Output: 1->3->0->0->0