RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved Pythagorean triples and binary trees. (Note that this is open until 15 August 2021.)

TASK #1 › Pythagorean Triples

You are given a positive integer $N.

Write a script to print all Pythagorean Triples containing $N as a member. Print -1 if it can’t be a member of any.

Triples with the same set of elements are considered the same, i.e. if your script has already printed (3, 4, 5), (4, 3, 5) should not be printed.

A Pythagorean triple refers to the triple of three integers whose lengths can compose a right-angled triangle.

I don't like polymorphic return types, so if there are no valid triangles containing the number I just return an empty list.

My first approach to this used an exhaustive search based on Dickson's method, but while s can be scanned from 1 to n, t might become arbitrarily large.

So instead I use Barning's matrices to generate all primitive triples where at least one value is not greater than n, and see if they fit. This could be done recursively but I used my standard BFS pattern. I'll show this in the Ruby version for maximum clarity.

def pt(n)

out is my output list. tri is the rolling buffer onto which candidate triangles will be pushed.

  out=[]
  tri=[[3,4,5]]
  while (tri.length>0) do

Pull the first candidate off the buffer. (If there's nothing left, return it.)

    t=tri.shift

For each of its three sides, see if that one is an even divisor of n. (The matrices generate only the primitive, i.e. smallest integral, triplets.) If it is, scale it up appropriately, and put that on the output.

    0.upto(2) do |i|
      dm=n.divmod(t[i])
      if dm[1]==0 then
        out.push(t.map{|i| i*dm[0]})
      end
    end

If any of the sides is not greater than n, use Barning's matrices to make three new candidate triangles and push them onto the buffer. (I think, but have not proved, that the minimum value in an output will always be no smaller than the minimum in the corresponding input.)

    if t.min <= n then
      tri.push([
                 t[0]-2*t[1]+2*t[2],
                 2*t[0]-1*t[1]+2*t[2],
                 2*t[0]-2*t[1]+3*t[2],
               ])
      tri.push([
                 t[0]+2*t[1]+2*t[2],
                 2*t[0]+1*t[1]+2*t[2],
                 2*t[0]+2*t[1]+3*t[2],
               ])
      tri.push([
                 -t[0]+2*t[1]+2*t[2],
                 -2*t[0]+1*t[1]+2*t[2],
                 -2*t[0]+2*t[1]+3*t[2],
               ])
    end
  end
  return out
end

I didn't do this one in Raku (it's painfully hard to get a list of lists), or in PostScript (I'm working on helper functions to give me variable-length arrays with push, pop, etc.). But at least there is no floating-point arithmetic.

TASK #2 › Binary Tree Diameter

You are given binary tree as below:

Write a script to find the diameter of the given binary tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. It doesn’t have to pass through the root.

(This was modified to make it clear that the path length is the number of edges, not the number of nodes.)

Well, if you're going to make it easy…

The example gives the actual path, but all that the question asks for is the length, and I find binary trees fairly uninteresting.

Again, this could be done recursively: the diameter of a node is the maximum of (the sum of the depths of both subnodes), (the diameter of the left subnode) and (the diameter of the right subnode), where the depth is the length of the path from this node to the bottommost (in turn that's the larger of the depths of the subnodes, + 1). But since each of those calculations only refers to subnodes of the current node, I took an iterative approach instead.

I'm using the same array notation for the tree that I've used before. Because the tree is sparse, I use value 0 to represent an empty node.

sub btd {
  my $tree=shift;
  my $st=scalar @{$tree};

Build depth and diameter arrays for each node, initialised to 0.

  my @depth=(0) x $st;
  my @diameter=(0) x $st;

Walk backwards through the array. (When one's used to the convenience of the simple for-form, having to remember this one can be a bit of a stretch, for all it's basically the same syntax as C.)

  for (my $i=$st-1;$i>=0;$i--) {

If there's a node here at all (if there isn't, depth and diameter remain at 0)…

    if ($tree->[$i] != 0) {

Subnode indices are cached to save repeated multiplications.

      my $a=$i*2+1;
      my $b=$a+1;

If we potentially have subnodes, i.e. we're not running off the end of the array…

      if ($b < $st) {

Then calculate depth and diameter based on those subnodes.

        $depth[$i]=1+max($depth[$a],$depth[$b]);
        $diameter[$i]=max($depth[$a]+$depth[$b],
                          $diameter[$a],
                          $diameter[$b]);

Otherwise this is a node with no subnodes, so its depth is 1.

      } else {
        $depth[$i]=1;
      }
    }
  }

And that's all there is to it. So I get the straightforwardness of the individual calculation that might go in a recursive approach, and the speed of iterative coding.

  return $diameter[0];
}

It does rely on my having a simple iterator that addresses all nodes; if I had to start at a root node and search for each child in a normal pattern of descent, it might well make more sense to use a different approach.

This one did come together nicely in PostScript. Of course I do need to define a max function, since that isn't in the PostScript v3 standard (though it seems to exist in the GhostScript interpreter). (Yeah, when I get into roll-level stack manipulation I like to work it out in detail…)

/max2 {
    dup % a b b
    3 2 roll % b b a
    dup % b b a a
    3 1 roll % b a b a
    lt { exch} if
    pop
} def

Then it's pretty much the routine as before.

/btd {
    /tree exch def
    /st tree length def

Build two zero-filled arrays of length st.

    /depth st array def
    /diameter st array def
    0 1 st 1 sub {
        dup
        depth exch 0 put
        diameter exch 0 put
    } for

Downward loops are easy.

    st 1 sub 1 neg 0 {
        /i exch def
        tree i get 0 ne {
            /a i 2 mul 1 add def
            /b a 1 add def
            b st lt {
                depth i depth a get depth b get max2 1 add put

We get rhetorical here – this line links up with the put four lines down.

                diameter i
                depth a get depth b get add
                diameter a get
                diameter b get
                max2 max2 put
            } {
                depth i 1 put
            } ifelse
        } if
    } for
    diameter 0 get
} def

Full code on github.