I’ve been doing the Weekly
Challenges. The
latest
involved a return to binary trees and an optimisation puzzle. (Note that this is
open until 13 February 2022.)
Task 1: Binary Tree Depth
You are given a 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).
Yes, it's a return to binary trees after a bit of a break. This time
there were effectively two parts, though: parse a string input into an
internal tree representation (I used my standard array-based model),
and then use that representation to find the first leaf node.
The string representation is a space-separated list of "*" for an
empty node, "|" for a new row, or a number, with trailing empty nodes
omitted. Thus:
1 | 2 3 | * 4
will become
1
/ \
2 3
\
4
and in the flattened array form
[1, 2, 3, 0, 4, 0. 0]
In order to make sure I have a reliable number of array entries I fill
it with zeroes at each greater depth, then place each entry into its
location.
sub str2tree {
my $st=shift;
my @o;
my $d=0;
my $p=0;
foreach my $e (split ' ',$st) {
if ($e eq '|') {
$d++;
$p=0;
my $m=(1<<($d+1))-1;
if (scalar @o < $m) {
push @o,(0) x ($m - scalar @o);
}
} else {
my $y=0;
if ($e ne '*') {
$y=0+$e;
}
my $i=(1<<$d) -1 +$p;
$o[$i]=$y;
$p++;
}
}
return \@o;
}
To do the actual depth calculation, I walk the tree breadth-first to
find the index of the first leaf node:
sub mindepth {
my $tree = shift;
my $firstleaf=scalar @{$tree};
foreach my $i (0..$#{$tree}) {
If this node is empty, it can't be a leaf.
if ($tree->[$i]==0) {
next;
If its children would run off the length of the array, it's
definitely a leaf.
} elsif (($i+1) << 1 >= scalar @{$tree}) {
$firstleaf=$i;
last;
And if both its children are empty nodes, it's a leaf.
} else {
my $ni=(($i+1) << 1)-1;
if ($tree->[$ni]==0 && $tree->[$ni+1]==0) {
$firstleaf=$i;
last;
}
}
}
Then take log2 of the index value to find the depth of that node.
my $t=$firstleaf+1;
my $d=0;
while ($t > 0) {
$t >>= 1;
$d++;
}
return $d;
}
The other languages all work quite similarly. In PostScript I had to
write a string tokeniser using repeated search
functions; Lua's
1-based arrays turn out to be quite useful for this specific
representation.
Task 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.
And the problem, given a list of reward levels from different houses,
is to determine the maximum possible reward.
I did an exhaustive search, with some optimisations. If I've just
looked at house number 3, I can't include 4, but I can include 5 or 6.
No point jumping ahead to 7, because I can go from 5 to 7, which will
necessarily produce a higher reward (there are no negative rewards in
this setup).
Rust:
fn plan(houses: Vec<u32>) -> u32 {
let terminal = houses.len() - 2;
b
is my buffer for the breadth-first search. (I could do depth-first
by shifting off the front rather than popping off the back, but it's
an exhaustive search anyway, and not every language can efficiently
shift off the front of a list.)
let mut b = vec![vec![0]];
let mut reward = 0;
while b.len() > 0 {
let c = b.pop().unwrap();
let c1 = c[c.len() - 1];
If the last house was one of the last two in the row, we can't add any
more. So add up the values for this sequence, and store it if it's
higher than a previous maximum reward value.
if c1 >= terminal {
let r = c.iter().map(|i| houses[*i]).sum();
if r > reward {
reward = r;
}
} else {
Otherwise, push on new lists with the old list plus each of the next
two valid house indices.
for n in (c1 + 2)..=(c1 + 3) {
if n >= houses.len() {
break;
}
let mut j = c.clone();
j.push(n);
b.push(j);
}
}
}
return reward;
}
An optimisation for larger data would store the value of the row at
each point, but it doesn't seem worth it at this scale.
The ways of doing this kind of shallow copy of a list get quite
abstruse. Python has a copy()
that does basically the same job as
clone()
above. In Ruby (and similarly Kotlin):
j=Array.new(c)
etc.
In Perl, the whole thing is very simple (if you know the syntax):
push @b,[@{$c},$n];
and similarly in PostScript:
b [ c aload pop n ] apush /b exch def
JavaScript:
let j=[...c];
and in Lua I just build another table apparently.
In Raku, that's not the hard bit, and this is something that gave me
great difficulties when I was first learning it. When I push something
onto a list and later pop it off again, I expect to get the same thing
back. But here's a minimal example case of that not happening:
my @c=(1,2,3);
my @d;
@d.push(@c);
my @e=@d.pop;
say @c.perl;
say @e.perl;
produces an array of arrays:
[1, 2, 3]
[[1, 2, 3],]
"Oh, silly Roger," you say, "you should have used $e
not @e
.
[1, 2, 3]
$[1, 2, 3]
OK then.
In practice what I do is:
my @c=(pop @b).flat;
Full code on
github.
Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.