The Tree House with Raku
[169] Published 13. February 2022.This is my response to the Perl Weekly Challenge #151.
Challenge #151.1: Binary Tree Depth
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
Input: '1 | 2 3 | 4 * * 5 | * 6'
1
/ \
2 3
/ \
4 5
\
6
Output: 3
The first part of the program is an exact copy of my «binary-tree-diameter» - except the default tree - from my answer to Challenge #125.2: Binary Tree Diameter. I even used stars to indicate dead ends in a tree, as done here.
File: binary-tree-depth
#! /usr/bin/env raku
unit sub MAIN (Str $tree = "1 | 2 3 | 4 * * 5 | * 6", :v(:$verbose));
class BinaryNode
{
has Int $.value;
has BinaryNode $.left;
has BinaryNode $.right;
}
my @btree = $tree.split("|")>>.words;
my @old-nodes;
my @new-nodes;
for @btree.reverse -> $row
{
my @current = @$row;
@old-nodes = @new-nodes;
@new-nodes = ();
for @current -> $value
{
if $value eq "*"
{
@new-nodes.push("*");
next;
}
my $left = @old-nodes.shift // "*"; $left = Nil if $left eq "*";
my $right = @old-nodes.shift // "*"; $right = Nil if $right eq "*";
@new-nodes.push(BinaryNode.new(value => $value.Int,
left => $left // Nil,
right => $right // Nil));
}
}
my $btree = @new-nodes[0]; # [1]
my @paths; # [2]
traverse2($btree, ()); # [3]
sub traverse2 ($current, @path is copy) # [3]
{
@path.push: $current.value; # [4]
if ($current.left or $current.right) # [5]
{
traverse2($current.left, @path) if $current.left; # [5a]
traverse2($current.right, @path) if $current.right; # [5b]
}
else # [6]
{
say ": Path: [{ @path.join(", ") }] with length { @path.elems }"
if $verbose;
@paths.push: @path; # [6a]
return; # [6b]
}
}
say @paths>>.elems.min; # [7]
[1] The top of the tree.
[2] We are going to collect the different paths from the top to each leaf node here.
[3] Off we go, recursively, from the top.
[4] Add the current node value.
[5] Do we have any child nodes? If so, traverse them [5a and 5b].
[6] If not; this is leaf node. We have a path [6a], and are done here
[7] For each of the paths, get the number of elements, then get the lowest one and print it.
Running it:
$ ./binary-tree-depth "1 | 2 3 | 4 5"
2
$ ./binary-tree-depth -v
3
With verbose mode:
$ ./binary-tree-depth -v "1 | 2 3 | 4 5"
: Path: [1, 2, 4] with length 3
: Path: [1, 2, 5] with length 3
: Path: [1, 3] with length 2
2
$ ./binary-tree-depth -v
: Path: [1, 2, 4, 6] with length 4
: Path: [1, 3, 5] with length 3
3
Some more. just for fun:
$ ./binary-tree-depth "1"
1
$ ./binary-tree-depth "1 | *"
1
$ ./binary-tree-depth "1 | * *"
1
The tree from challenge #125.2:
$ ./binary-tree-depth -v "1 | 2 5 | 3 4 6 7 | * * * * * * 8 10 | 9"
: Path: [1, 2, 3] with length 3
: Path: [1, 2, 4] with length 3
: Path: [1, 5, 6] with length 3
: Path: [1, 5, 7, 8, 9] with length 5
: Path: [1, 5, 7, 10] with length 4
3
Challenge #151.2: Rob The House
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.
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.
The morality of this task is dubious, so let us say that we are painting houses instead. The point of not painting two adjacent houses is that the paint job is done to impress the neighbours. This will not work out if all the houses are painted, so we make a point of promising not to paint the house on either side.
We can do this by creating lists of indices. The first house (with index 0) is always selected, as specified in the challenge. (So the "value" of the second house does not matter at all, as we cannot choose it.) The jump (so to speak), as we cannot visit adjacent houses, turns out to be quite easy:
The first row shows an example with 9 houses. The second row shows what happens if we choose every second house (a jump with value 2), and the third row has every third house chosen. The fourth and last row shows what happens if we do every fourth house, but this is the same as two jumps with value 2, except that we get a smaller total sum (as we have skipped the house with index 2), so we can disregard it. The only relevant jump values are 2 and 3, as long as we are in for maximising the sum.
File: rob-the-house
#! /usr/bin/env raku
unit sub MAIN (*@valuables where @valuables.elems &&
all(@valuables) ~~ Numeric, :v(:$verbose)); # [1]
my $seq := gather { recurse( (0,), 0, @valuables.elems -1); } # [2]
sub recurse(@done is copy, $index, $todo is copy) # [2a]
{
if $todo < 2 # [3]
{
say ": Added candidate: @done[]" if $verbose;
take @done; # [3a]
return; # [3b]
}
for 2, 3 -> $add # [4]
{
if $todo >= $add # [5]
{
my @done1 = @done.clone; # [6]
@done1.push: $index + $add; # [6a]
recurse(@done1, $index + $add, $todo - $add); # [7]
}
}
}
my @candidates = $seq; # [8]
if $verbose
{
for @candidates -> @list
{
say ": Candidate indices: [{ @list.join(",") }] with sum: \
{ @valuables[@list].sum }";
}
}
say @candidates.map({ @valuables[@$_].sum }).max; # [9]
[1] All the house values must be numeric. Note that I do not exclude negative values.
[2] Setting up the sequence of indices with
gather/take is ideal here. I have hidden the take
calls in a procedure, which works quite well. The first argument to the recursive procedure
is a list of indices so far (i.e. houses to visit). The second is the current index, and
the third is the number of houses left (i.e. remaining after the current one).
See my Raku Gather,
I Take article or
docs.raku.org/syntax/gather take for more information about
gather/take.
[3] Less than 2 houses left? If so, return the list of indices (with take
[3a]) and finish the recursion (with return [3b]).
[4] For each jump value,
[5] Do we have enough houses left to do the jump?
[6] If so, add the new house to the list of indices. Note the use of
clone to get a copy of the array - as we modify it twice (in the loop)
See
docs.raku.org/routine/clone for
more information about the clone method.
[7] Off we go, recurively, with the upfawtes list of indices, current position, and remaining number of houses.
[8] Get the sequence as an array.
[9] Iterate over the candidates (with map), use the candidate indices as an array
slice into the valuables array to get those values, and get the sum of each (with sum.
The result is a list of values, one for each candidate list of indices. Then we get the largest
one (with max) and print it.
Running it:
$ ./rob-the-house 4 2 3 6 5 3
13
$ ./rob-the-house -v 4 2 3 6 5 3
: Added candidate: 0 2 4
: Added candidate: 0 2 5
: Added candidate: 0 3 5
: Candidate indices: [0,2,4] with sum: 12
: Candidate indices: [0,2,5] with sum: 10
: Candidate indices: [0,3,5] with sum: 13
13
Looking good.
And that's it.
P.S. Do not rob houses.