Perl Weekly Challenge: Week 151
Challenge 1:
Binary Tree Depth
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).
Example 1
Input: '1 | 2 3 | 4 5'
1
/ \
2 3
/ \
4 5
Output: 2
Example 2
Input: '1 | 2 3 | 4 * * 5 | * 6'
1
/ \
2 3
/ \
4 5
\
6
Output: 3
To input and create the tree I reused the Node class and makeTree() function I
created in PWC 93.
They require the tree to be input as a series of command-line arguments with -
representing an empty node. So e.g. example 2 would look like this: 1 2 3 4 - - 5 - 6.
The solution traverses the tree from its' root node with a recursive Depth-First Search (DFS) defined in theminimumDepth() function.
sub minimumDepth(Node $root) {
The base case to stop recursion is if the root node (of the tree as a whole or a sub-tree) is non-existent, the tree (or sub-tree) is empty, so we return the depth as 0.
if !$root {
return 0;
}
If the left leaf node is empty, we only have to traverse the sub-tree under the
right leaf node. We add 1 to the depth and recursively call minimumDepth() again.
if !$root.left {
return 1 + minimumDepth($root.right);
}
Similarly, if the right leaf node is empty, we only have to traverse the left sub-tree.
if !$root.right {
return 1 + minimumDepth($root.left);
}
Otherwise we traverse both sub-trees and comparing the answers and taking whichever
is smaller with .min(). 1 is added to this amount and that is the new depth.
return 1 + (minimumDepth($root.left), minimumDepth($root.right)).min;
}
When minimumDepth() has finally stopped all that recursion the final return value will
be the minimum depth of the whole tree.
For the Perl version, as well as Node and makeTree(), we need a replacement min().
Otherwise the code works the same way as in Raku.
sub minimumDepth($root) {
if (!$root) {
return 0;
}
if (!$root->left) {
return 1 + minimumDepth($root->right);
}
if (!$root->right) {
return 1 + minimumDepth($root->left);
}
return 1 + min(minimumDepth($root->left), minimumDepth($root->right));
}
Challenge 2:
Rob the House
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.
Example 1
Input: @valuables = (2, 4, 5);
Output: 7
If we rob house (index=0) we get 2 and then the only house we can rob is house (index=2) where we have 5.
So the total valuables in this case is (2 + 5) = 7.
Example 2
Input: @valuables = (4, 2, 3, 6, 5, 3);
Output: 13
The best choice would be to first rob house (index=0) then rob house (index=3) then finally house (index=5).
This would give us 4 + 6 + 3 =13.
I was worried that this might get complicated but in fact we can solve this easily with dynamic programming techniques.
The array @dp will hold the highest possible gain so far at each house (i.e. index.)
We can initialize it with two values. Zero houses means zero gain so index 0 will always equal 0.
At the first house our choices are the value of the valuables at that house (i.e. @valuables[0])
or 0 from the previous entry so it's always going to be the former.
my @dp = 0, @valuables[0];
Now we go through the houses starting from the second (@valuables[1]) upto the end...
for 1 .. @valuables.end {
...and compare either the last calculated value in @dp or the second to last plus
the value of the valuables in this house. Whichever amount is greater (using max) gets
added to @dp. This way we are not comparing adjacent houses.
@dp.push(@dp[*-1] max (@dp[*-2] + @valuables[$_]));
}
When all houses and their valuables have been checked, the last value in @dp will give us
our answer.
say @dp[*-1];
The Perl version works the same way.
my @dp = (0, $valuables[0]);
for my $v (1 .. scalar @valuables - 1) {
push @dp, max($dp[-1], ($dp[-2]) + $valuables[$v]);
}
say $dp[-1];