RogerBW's Blog

The Weekly Challenge 151: Robbing Depth 10 February 2022

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.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action aeronautics aikakirja anecdote animation anime army astronomy audio audio tech aviation base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 cycling dead of winter doctor who documentary drama driving drone ecchi economics espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1