From 851399b5d2e46d92aafc22871091dd4ac86f6cf8 Mon Sep 17 00:00:00 2001
From: Roger Bell_West <roger@firedrake.org>
Date: Tue, 10 Aug 2021 23:32:55 +0100
Subject: Answers for challenge #125 (amended Tuesday evening)

---
 challenge-125/roger-bell-west/perl/ch-1.pl       | 44 ++++++++++++++++++++
 challenge-125/roger-bell-west/perl/ch-2.pl       | 34 ++++++++++++++++
 challenge-125/roger-bell-west/postscript/ch-2.ps | 48 ++++++++++++++++++++++
 challenge-125/roger-bell-west/python/ch-1.py     | 45 ++++++++++++++++++++
 challenge-125/roger-bell-west/python/ch-2.py     | 35 ++++++++++++++++
 challenge-125/roger-bell-west/raku/ch-2.p6       | 32 +++++++++++++++
 challenge-125/roger-bell-west/ruby/ch-1.rb       | 51 +++++++++++++++++++++++
 challenge-125/roger-bell-west/ruby/ch-2.rb       | 39 ++++++++++++++++++
 challenge-125/roger-bell-west/rust/ch-1.rs       | 52 ++++++++++++++++++++++++
 challenge-125/roger-bell-west/rust/ch-2.rs       | 35 ++++++++++++++++
 10 files changed, 415 insertions(+)
 create mode 100755 challenge-125/roger-bell-west/perl/ch-1.pl
 create mode 100755 challenge-125/roger-bell-west/perl/ch-2.pl
 create mode 100644 challenge-125/roger-bell-west/postscript/ch-2.ps
 create mode 100755 challenge-125/roger-bell-west/python/ch-1.py
 create mode 100755 challenge-125/roger-bell-west/python/ch-2.py
 create mode 100755 challenge-125/roger-bell-west/raku/ch-2.p6
 create mode 100755 challenge-125/roger-bell-west/ruby/ch-1.rb
 create mode 100755 challenge-125/roger-bell-west/ruby/ch-2.rb
 create mode 100755 challenge-125/roger-bell-west/rust/ch-1.rs
 create mode 100755 challenge-125/roger-bell-west/rust/ch-2.rs

diff --git a/challenge-125/roger-bell-west/perl/ch-1.pl b/challenge-125/roger-bell-west/perl/ch-1.pl
new file mode 100755
index 0000000000..4c09301883
--- /dev/null
+++ b/challenge-125/roger-bell-west/perl/ch-1.pl
@@ -0,0 +1,44 @@
+#! /usr/bin/perl
+
+use strict;
+
+use List::Util qw(min);
+
+use Test::More tests => 3;
+
+is_deeply(pt(5),[[3,4,5],[5,12,13]],'example 1');
+is_deeply(pt(13),[[5,12,13],[13,84,85]],'example 2');
+is_deeply(pt(1),[],'example 3');
+
+sub pt {
+  my $n=shift;
+  my @out;
+  my @tri=([3,4,5]);
+  while (@tri) {
+    my $t=shift @tri;
+    foreach my $i (0..2) {
+      if ($n % $t->[$i] == 0) {
+        my $k=$n/$t->[$i];
+        push @out,[map {$_*$k} @{$t}];
+      }
+    }
+    unless (min(@{$t}) > $n) {
+      push @tri,[
+        $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],
+          ];
+      push @tri,[
+        $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],
+          ];
+      push @tri,[
+        -$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],
+          ];
+    }
+  }
+  return \@out;
+}
diff --git a/challenge-125/roger-bell-west/perl/ch-2.pl b/challenge-125/roger-bell-west/perl/ch-2.pl
new file mode 100755
index 0000000000..0b7be33985
--- /dev/null
+++ b/challenge-125/roger-bell-west/perl/ch-2.pl
@@ -0,0 +1,34 @@
+#! /usr/bin/perl
+
+use strict;
+
+use Test::More tests => 1;
+use List::Util qw(max);
+
+is(btd([1,
+        2,5,
+        3,4,6,7,
+        0,0,0,0,0,0,8,10,
+        0,0,0,0,0,0,0,0,0,0,0,0,9,0,0,0]),6,'example 1');
+
+sub btd {
+  my $tree=shift;
+  my $st=scalar @{$tree};
+  my @depth=(0) x $st;
+  my @diameter=(0) x $st;
+  for (my $i=$st-1;$i>=0;$i--) {
+    if ($tree->[$i] != 0) {
+      my $a=$i*2+1;
+      my $b=$a+1;
+      if ($b < $st) {
+        $depth[$i]=1+max($depth[$a],$depth[$b]);
+        $diameter[$i]=max($depth[$a]+$depth[$b],
+                          $diameter[$a],
+                          $diameter[$b]);
+      } else {
+        $depth[$i]=1;
+      }
+    }
+  }
+  return $diameter[0];
+}
diff --git a/challenge-125/roger-bell-west/postscript/ch-2.ps b/challenge-125/roger-bell-west/postscript/ch-2.ps
new file mode 100644
index 0000000000..802e5c9dba
--- /dev/null
+++ b/challenge-125/roger-bell-west/postscript/ch-2.ps
@@ -0,0 +1,48 @@
+%! no DSC
+
+/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
+
+/btd {
+    /tree exch def
+    /st tree length def
+    /depth st array def
+    /diameter st array def
+    0 1 st 1 sub {
+        dup
+        depth exch 0 put
+        diameter exch 0 put
+    } for
+    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
+                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
+
+[ 1
+  2 5
+  3 4 6 7
+  0 0 0 0 0 0 8 10
+  0 0 0 0 0 0 0  0 0 0 0 0 9 0 0 0 ]
+btd
+=
diff --git a/challenge-125/roger-bell-west/python/ch-1.py b/challenge-125/roger-bell-west/python/ch-1.py
new file mode 100755
index 0000000000..4fab2618f2
--- /dev/null
+++ b/challenge-125/roger-bell-west/python/ch-1.py
@@ -0,0 +1,45 @@
+#! /usr/bin/python3
+
+import unittest
+from collections import deque
+
+def pt(n):
+  out=[]
+  tri=deque()
+  tri.append([3,4,5])
+  while len(tri)>0:
+    t=tri.popleft()
+    for i in range(3):
+      dm=divmod(n,t[i])
+      if dm[1]==0:
+        out.append([i*dm[0] for i in t])
+    if min(t) <= n:
+      tri.append([
+        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.append([
+        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.append([
+        -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],
+      ])
+  return out
+
+class TestPt(unittest.TestCase):
+
+        def test_ex1(self):
+          self.assertEqual(pt(5),[[3,4,5],[5,12,13]],'example 1')
+
+        def test_ex2(self):
+          self.assertEqual(pt(13),[[5,12,13],[13,84,85]],'example 2')
+
+        def test_ex3(self):
+          self.assertEqual(pt(1),[],'example 3')
+          
+unittest.main()
diff --git a/challenge-125/roger-bell-west/python/ch-2.py b/challenge-125/roger-bell-west/python/ch-2.py
new file mode 100755
index 0000000000..70df3a8337
--- /dev/null
+++ b/challenge-125/roger-bell-west/python/ch-2.py
@@ -0,0 +1,35 @@
+#! /usr/bin/python3
+
+import unittest
+
+from math import degrees,atan2
+
+def btd(tree):
+  st=len(tree)
+  depth=[0]*st
+  diameter=[0]*st
+  for i in range(st-1,-1,-1):
+    if tree[i] != 0:
+      a=i*2+1
+      b=a+1
+      if b < st:
+        depth[i]=1+max(depth[a],depth[b])
+        diameter[i]=max(
+          depth[a]+depth[b],
+          diameter[a],
+          diameter[b]
+          )
+      else:
+        depth[i]=1
+  return diameter[0]
+
+class TestBtd(unittest.TestCase):
+
+        def test_ex1(self):
+          self.assertEqual(btd([1,
+                                2,5,
+                                3,4,6,7,
+                                0,0,0,0,0,0,8,10,
+                                0,0,0,0,0,0,0,0,0,0,0,0,9,0,0,0]),6,'example 1')
+          
+unittest.main()
diff --git a/challenge-125/roger-bell-west/raku/ch-2.p6 b/challenge-125/roger-bell-west/raku/ch-2.p6
new file mode 100755
index 0000000000..ee5673dbc8
--- /dev/null
+++ b/challenge-125/roger-bell-west/raku/ch-2.p6
@@ -0,0 +1,32 @@
+#! /usr/bin/perl6
+
+use Test;
+
+plan 1;
+
+is(btd([1,
+        2,5,
+        3,4,6,7,
+        0,0,0,0,0,0,8,10,
+        0,0,0,0,0,0,0,0,0,0,0,0,9,0,0,0]),6,'example 1');
+
+sub btd(@tree) {
+  my $st=@tree.elems;
+  my @depth=(0) xx $st;
+  my @diameter=(0) xx $st;
+  loop (my $i=$st-1;$i>=0;$i--) {
+    if (@tree[$i] != 0) {
+      my $a=$i*2+1;
+      my $b=$a+1;
+      if ($b < $st) {
+        @depth[$i]=1+max(@depth[$a],@depth[$b]);
+        @diameter[$i]=max(@depth[$a]+@depth[$b],
+                          @diameter[$a],
+                          @diameter[$b]);
+      } else {
+        @depth[$i]=1;
+      }
+    }
+  }
+  return @diameter[0];
+}
diff --git a/challenge-125/roger-bell-west/ruby/ch-1.rb b/challenge-125/roger-bell-west/ruby/ch-1.rb
new file mode 100755
index 0000000000..6ac3537985
--- /dev/null
+++ b/challenge-125/roger-bell-west/ruby/ch-1.rb
@@ -0,0 +1,51 @@
+#! /usr/bin/ruby
+
+def pt(n)
+  out=[]
+  tri=[[3,4,5]]
+  while (tri.length>0) do
+    t=tri.shift
+    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 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
+
+require 'test/unit'
+
+class TestPt < Test::Unit::TestCase
+
+  def test_ex1
+    assert_equal([[3,4,5],[5,12,13]],pt(5))
+  end
+
+  def test_ex2
+    assert_equal([[5,12,13],[13,84,85]],pt(13))
+  end
+
+  def test_ex3
+    assert_equal([],pt(1))
+  end
+  
+end
diff --git a/challenge-125/roger-bell-west/ruby/ch-2.rb b/challenge-125/roger-bell-west/ruby/ch-2.rb
new file mode 100755
index 0000000000..dd58c18578
--- /dev/null
+++ b/challenge-125/roger-bell-west/ruby/ch-2.rb
@@ -0,0 +1,39 @@
+#! /usr/bin/ruby
+
+def btd(tree)
+  st=tree.length
+  depth=Array.new(st,0)
+  diameter=Array.new(st,0)
+  (st-1).downto(0) do |i|
+    if tree[i] != 0 then
+      a=i*2+1
+      b=a+1
+      if b < st then
+        depth[i]=1+[depth[a],depth[b]].max
+        diameter[i]=[
+          depth[a]+depth[b],
+          diameter[a],
+          diameter[b],
+        ].max
+      else
+        depth[i]=1
+      end
+    end
+  end
+  return diameter[0]
+end
+
+require 'test/unit'
+
+class TestBtd < Test::Unit::TestCase
+
+  def test_ex1
+    assert_equal(6,btd([1,
+                        2,5,
+                        3,4,6,7,
+                        0,0,0,0,0,0,8,10,
+                        0,0,0,0,0,0,0,0,0,0,0,0,9,0,0,0
+                       ]))
+  end
+  
+end
diff --git a/challenge-125/roger-bell-west/rust/ch-1.rs b/challenge-125/roger-bell-west/rust/ch-1.rs
new file mode 100755
index 0000000000..f1a6ecb665
--- /dev/null
+++ b/challenge-125/roger-bell-west/rust/ch-1.rs
@@ -0,0 +1,52 @@
+#! /bin/sh
+//usr/bin/env rustc --test $0 -o ${0}x && ./${0}x; rm -f ${0}x ; exit
+
+use std::collections::VecDeque;
+
+#[test]
+fn test_ex1() {
+    assert_eq!(pt(5),vec![vec![3,4,5],vec![5,12,13]]);
+}
+
+#[test]
+fn test_ex2() {
+    assert_eq!(pt(13),vec![vec![5,12,13],vec![13,84,85]]);
+}
+
+#[test]
+fn test_ex3() {
+    assert_eq!(pt(1),Vec::<Vec<i64>>::new());
+}
+
+fn pt(n: i64) -> Vec<Vec<i64>> {
+    let mut out=vec![];
+    let mut tri: VecDeque<Vec<i64>>=VecDeque::new();
+    tri.push_back(vec![3,4,5]);
+    while tri.len()>0 {
+        let t=tri.pop_front().unwrap();
+        for i in 0..=2 {
+            if n % t[i] == 0 {
+                let k=n/t[i];
+                out.push(t.iter().map(|j| j*k).collect());
+            }
+        }
+        if t.iter().min().unwrap() <= &n {
+            tri.push_back(vec![
+                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_back(vec![
+                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_back(vec![
+                -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],
+            ]);
+        }
+    }
+    return out;
+}
diff --git a/challenge-125/roger-bell-west/rust/ch-2.rs b/challenge-125/roger-bell-west/rust/ch-2.rs
new file mode 100755
index 0000000000..b03513c684
--- /dev/null
+++ b/challenge-125/roger-bell-west/rust/ch-2.rs
@@ -0,0 +1,35 @@
+#! /bin/sh
+//usr/bin/env rustc --test $0 -o ${0}x && ./${0}x; rm -f ${0}x ; exit
+
+#[test]
+fn test_ex1() {
+    assert_eq!(btd(vec![1,
+                        2,5,
+                        3,4,6,7,
+                        0,0,0,0,0,0,8,10,
+                        0,0,0,0,0,0,0,0,0,0,0,0,9,0,0,0
+    ]),6);
+}
+
+fn btd(tree: Vec<u64>) -> u64 {
+    let st=tree.len();
+    let mut depth: Vec<u64>=vec![0;st];
+    let mut diameter: Vec<u64>=vec![0;st];
+    for i in (0..st).rev() {
+        if tree[i]!=0 {
+            let a=i*2+1;
+            let b=a+1;
+            if b < st {
+                depth[i]=1+[depth[a],depth[b]].iter().max().unwrap();
+                diameter[i]=*[
+                    depth[a]+depth[b],
+                    diameter[a],
+                    diameter[b]
+                    ].iter().max().unwrap();
+            } else {
+                depth[i]=1;
+            }
+        }
+    }
+    return diameter[0]
+}
-- 
cgit