RogerBW's Blog

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.