Solutions for challenge #125

9 files changed, 372 insertions, 0 deletions

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..684604b182
--- /dev/null
+++ b/challenge-125/roger-bell-west/perl/ch-2.pl
@@ -0,0 +1,35 @@
+#! /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]),7,'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(1+$depth[$a]+$depth[$b],
+                          $diameter[$a],
+                          $diameter[$b]);
+      } else {
+        $depth[$i]=1;
+        $diameter[$i]=1;
+      }
+    }
+  }
+  return $diameter[0];
+}
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..b03a09c4e0
--- /dev/null
+++ b/challenge-125/roger-bell-west/python/ch-2.py
@@ -0,0 +1,36 @@
+#! /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(
+          1+depth[a]+depth[b],
+          diameter[a],
+          diameter[b]
+          )
+      else:
+        depth[i]=1
+        diameter[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]),7,'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..0014033351
--- /dev/null
+++ b/challenge-125/roger-bell-west/raku/ch-2.p6
@@ -0,0 +1,33 @@
+#! /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]),7,'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(1+@depth[$a]+@depth[$b],
+                          @diameter[$a],
+                          @diameter[$b]);
+      } else {
+        @depth[$i]=1;
+        @diameter[$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..36bd3ce90c
--- /dev/null
+++ b/challenge-125/roger-bell-west/ruby/ch-2.rb
@@ -0,0 +1,40 @@
+#! /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]=[
+          1+depth[a]+depth[b],
+          diameter[a],
+          diameter[b],
+        ].max
+      else
+        depth[i]=1
+        diameter[i]=1
+      end
+    end
+  end
+  return diameter[0]
+end
+
+require 'test/unit'
+
+class TestBtd < Test::Unit::TestCase
+
+  def test_ex1
+    assert_equal(7,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..ddd67a4a27
--- /dev/null
+++ b/challenge-125/roger-bell-west/rust/ch-2.rs
@@ -0,0 +1,36 @@
+#! /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
+    ]),7);
+}
+
+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]=*[
+                    1+depth[a]+depth[b],
+                    diameter[a],
+                    diameter[b]
+                    ].iter().max().unwrap();
+            } else {
+                depth[i]=1;
+                diameter[i]=1;
+            }
+        }
+    }
+    return diameter[0]
+}