Solutions for challenge #89.

10 files changed, 503 insertions, 0 deletions

diff --git a/challenge-089/roger-bell-west/perl/ch-1.pl b/challenge-089/roger-bell-west/perl/ch-1.pl
new file mode 100755
index 0000000000..64e65cb4e3
--- /dev/null
+++ b/challenge-089/roger-bell-west/perl/ch-1.pl
@@ -0,0 +1,51 @@
+#! /usr/bin/perl
+
+use strict;
+use warnings;
+
+use Test::More tests => 2;
+
+is(gs(3),3,'example 1');
+is(gs(4),7,'example 2');
+
+use List::Util qw(min sum);
+
+sub gs {
+  my $n=shift;
+  my $tot=$n-1; # gcd(1,2)+gcd(1,3)+...+gcd(1,n)
+  foreach my $a (2..$n-1) {
+    $tot+=sum(map {gcd($a,$_)} ($a+1..$n));
+  }
+  return $tot;
+}
+
+sub gcd {
+  my ($a,$b)=@_;
+  if ($a==0) {
+    return $b;
+  }
+  if ($b==0) {
+    return $a;
+  }
+  my $d=0;
+  while (1) {
+    if ($a == $b) {
+      return $a << $d;
+    }
+    my $aa=($a % 2 == 0);
+    my $bb=($b % 2 == 0);
+    if ($aa && $bb) {
+      $a >>= 1;
+      $b >>= 1;
+      $d++;
+    } elsif ($aa) {
+      $a >>= 1;
+    } elsif ($bb) {
+      $b >>= 1;
+    } else {
+      my $c=abs($a-$b);
+      $a=min($a,$b);
+      $b=$c >> 1;
+    }
+  }
+}
diff --git a/challenge-089/roger-bell-west/perl/ch-2.pl b/challenge-089/roger-bell-west/perl/ch-2.pl
new file mode 100755
index 0000000000..b52969c9ee
--- /dev/null
+++ b/challenge-089/roger-bell-west/perl/ch-2.pl
@@ -0,0 +1,65 @@
+#! /usr/bin/perl
+
+use strict;
+use warnings;
+
+use Test::More tests => 8;
+
+use List::Util qw(sum);
+
+my $ms=ms(3,1,1);
+
+{
+  is(sum(@{$ms->[0]}),15,'row 1');
+  is(sum(@{$ms->[1]}),15,'row 2');
+  is(sum(@{$ms->[2]}),15,'row 3');
+  is(sum(map {$ms->[$_][0]} (0..$#{$ms})),15,'col 1');
+  is(sum(map {$ms->[$_][1]} (0..$#{$ms})),15,'col 2');
+  is(sum(map {$ms->[$_][2]} (0..$#{$ms})),15,'col 3');
+  is(sum(map {$ms->[$_][$_]} (0..$#{$ms})),15,'dia 1');
+  is(sum(map {$ms->[$_][2-$_]} (0..$#{$ms})),15,'dia 2');
+}
+
+print tabular($ms);
+
+sub ms {
+  my ($order,$start,$inc)=@_;
+  my $m;
+  foreach (1..$order) {
+    push @{$m},[(0) x $order];
+  }
+  my ($x,$y)=(int($order/2)+1,int($order/2));
+  my $n=$start;
+  while (1) {
+    $m->[$x][$y]=$n;
+    $n+=$inc;
+    my ($xa,$ya)=(($x+1) % $order,($y+1) % $order);
+    if ($m->[$xa][$ya]>0) {
+      ($xa,$ya)=(($x+2) % $order,$y);
+      if ($m->[$xa][$ya]>0) {
+        last;
+      }
+    }
+    ($x,$y)=($xa,$ya);
+  }
+  return $m;
+}
+
+sub tabular {
+  my $d=shift;
+  my @columnlength;
+  foreach my $row (@{$d}) {
+    foreach my $colno (0..$#{$row}) {
+      if (!defined($columnlength[$colno]) ||
+          $columnlength[$colno] < length($row->[$colno])) {
+        $columnlength[$colno]=length($row->[$colno]);
+      }
+    }
+  }
+  my $format=join('  ',map {"%${_}s"} @columnlength);
+  my $result='';
+  foreach my $row (@{$d}) {
+    $result .= sprintf($format,@{$row})."\n";
+  }
+  return $result;
+}
diff --git a/challenge-089/roger-bell-west/python/ch-1.py b/challenge-089/roger-bell-west/python/ch-1.py
new file mode 100755
index 0000000000..f1922a6e34
--- /dev/null
+++ b/challenge-089/roger-bell-west/python/ch-1.py
@@ -0,0 +1,21 @@
+#! /usr/bin/python3
+
+from math import gcd
+
+def gs(n):
+    tot=n-1;
+    for a in range(2,n):
+        tot += sum(gcd(a,x) for x in range(a+1,n+1))
+    return tot
+
+import unittest
+
+class TestGs(unittest.TestCase):
+
+    def test_ex1(self):
+        self.assertEqual(gs(3),3,'example 1')
+
+    def test_ex2(self):
+        self.assertEqual(gs(4),7,'example 2')
+
+unittest.main()
diff --git a/challenge-089/roger-bell-west/python/ch-2.py b/challenge-089/roger-bell-west/python/ch-2.py
new file mode 100755
index 0000000000..b53d20cd50
--- /dev/null
+++ b/challenge-089/roger-bell-west/python/ch-2.py
@@ -0,0 +1,55 @@
+#! /usr/bin/python3
+ 
+def ms(order,start,inc):
+    m=list()
+    for i in range(order):
+        m.append([0] * order)
+    x=int(order/2)+1
+    y=int(order/2)
+    n=start
+    while 1:
+        m[x][y]=n
+        n+=inc
+        xa=(x+1) % order
+        ya=(y+1) % order
+        if (m[xa][ya]>0):
+            xa=(x+2) % order
+            ya=y
+            if (m[xa][ya]>0):
+                break
+        x=xa
+        y=ya
+    return m
+            
+import unittest
+
+class TestMs(unittest.TestCase):
+
+    def setUp(self):
+        self.ms=ms(3,1,1)
+    
+    def test_ex1(self):
+        self.assertEqual(sum(self.ms[0]),15,'row 1')
+
+    def test_ex2(self):
+        self.assertEqual(sum(self.ms[1]),15,'row 2')
+
+    def test_ex3(self):
+        self.assertEqual(sum(self.ms[2]),15,'row 3')
+    
+    def test_ex4(self):
+        self.assertEqual(sum(x[0] for x in self.ms),15,'col 1')
+    
+    def test_ex5(self):
+        self.assertEqual(sum(x[1] for x in self.ms),15,'col 2')
+    
+    def test_ex6(self):
+        self.assertEqual(sum(x[2] for x in self.ms),15,'col 3')
+    
+    def test_ex7(self):
+        self.assertEqual(sum(self.ms[x][x] for x in range(3)),15,'dia 1')
+    
+    def test_ex8(self):
+        self.assertEqual(sum(self.ms[x][2-x] for x in range(3)),15,'dia 2')
+
+unittest.main()
diff --git a/challenge-089/roger-bell-west/raku/ch-1.p6 b/challenge-089/roger-bell-west/raku/ch-1.p6
new file mode 100755
index 0000000000..8e8c2a57e5
--- /dev/null
+++ b/challenge-089/roger-bell-west/raku/ch-1.p6
@@ -0,0 +1,46 @@
+#! /usr/bin/perl6
+
+use Test;
+plan 2;
+
+is(gs(3),3,'example 1');
+is(gs(4),7,'example 2');
+
+sub gs($n) {
+  my $tot=$n-1; # gcd(1,2)+gcd(1,3)+...+gcd(1,n)
+  for (2..$n-1) -> $a {
+    $tot+=sum(map {gcd($a,$_)},($a+1..$n));
+  }
+  return $tot;
+}
+
+sub gcd($ai,$bi) {
+  my ($a,$b)=($ai,$bi);
+  if ($a==0) {
+    return $b;
+  }
+  if ($b==0) {
+    return $a;
+  }
+  my $d=0;
+  while (1) {
+    if ($a == $b) {
+      return $a +< $d;
+    }
+    my $aa=($a % 2 == 0);
+    my $bb=($b % 2 == 0);
+    if ($aa ?& $bb) {
+      $a +>= 1;
+      $b +>= 1;
+      $d++;
+    } elsif ($aa) {
+      $a +>= 1;
+    } elsif ($bb) {
+      $b +>= 1;
+    } else {
+      my $c=abs($a-$b);
+      $a=min($a,$b);
+      $b=$c +> 1;
+    }
+  }
+}
diff --git a/challenge-089/roger-bell-west/raku/ch-2.p6 b/challenge-089/roger-bell-west/raku/ch-2.p6
new file mode 100755
index 0000000000..6ac7d596d7
--- /dev/null
+++ b/challenge-089/roger-bell-west/raku/ch-2.p6
@@ -0,0 +1,39 @@
+#! /usr/bin/perl6
+
+use Test;
+plan 8;
+
+my $ms=ms(3,1,1);
+
+{
+  is(sum(@($ms[0])),15,'row 1');
+  is(sum(@($ms[1])),15,'row 2');
+  is(sum(@($ms[2])),15,'row 3');
+  is(sum(map {$ms[$_][0]}, (0..$ms.end)),15,'col 1');
+  is(sum(map {$ms[$_][1]}, (0..$ms.end)),15,'col 2');
+  is(sum(map {$ms[$_][2]}, (0..$ms.end)),15,'col 3');
+  is(sum(map {$ms[$_][$_]}, (0..$ms.end)),15,'dia 1');
+  is(sum(map {$ms[$_][2-$_]}, (0..$ms.end)),15,'dia 2');
+}
+
+sub ms($order,$start,$inc) {
+  my $m=Array.new;
+  for (1..$order) {
+    push @($m),(0 xx $order).Array;
+  }
+  my ($x,$y)=(floor($order/2)+1,floor($order/2));
+  my $n=$start;
+  while (1) {
+    $m[$x][$y]=$n;
+    $n+=$inc;
+    my ($xa,$ya)=(($x+1) % $order,($y+1) % $order);
+    if ($m[$xa][$ya]>0) {
+      ($xa,$ya)=(($x+2) % $order,$y);
+      if ($m[$xa][$ya]>0) {
+        last;
+      }
+    }
+    ($x,$y)=($xa,$ya);
+  }
+  return $m;
+}
diff --git a/challenge-089/roger-bell-west/ruby/ch-1.rb b/challenge-089/roger-bell-west/ruby/ch-1.rb
new file mode 100755
index 0000000000..88f5f5b2a1
--- /dev/null
+++ b/challenge-089/roger-bell-west/ruby/ch-1.rb
@@ -0,0 +1,23 @@
+#! /usr/bin/ruby
+
+def gs(n)
+  tot=n-1
+  2.upto(n-1) do |a|
+    tot+=(a+1).upto(n).map{|x| a.gcd(x)}.reduce(:+)
+  end
+  return tot
+end
+
+require 'test/unit'
+
+class TestGs < Test::Unit::TestCase
+
+  def test_ex1
+    assert_equal(3,gs(3))
+  end
+
+  def test_ex2
+    assert_equal(7,gs(4))
+  end
+
+end
diff --git a/challenge-089/roger-bell-west/ruby/ch-2.rb b/challenge-089/roger-bell-west/ruby/ch-2.rb
new file mode 100755
index 0000000000..cd524db842
--- /dev/null
+++ b/challenge-089/roger-bell-west/ruby/ch-2.rb
@@ -0,0 +1,70 @@
+#! /usr/bin/ruby
+
+def ms(order,start,inc)
+  m=Array.new
+  1.upto(order) do
+    m.push([0] * order)
+  end
+  x=((order/2)+1).floor
+  y=(order/2).floor
+  n=start
+  while (true) do
+    m[x][y]=n
+    n+=inc
+    xa=(x+1) % order
+    ya=(y+1) % order
+    if (m[xa][ya]>0)
+      xa=(x+2) % order
+      ya=y
+      if (m[xa][ya]>0)
+        break
+      end
+    end
+    x=xa
+    y=ya
+  end
+  return m
+end
+
+require 'test/unit'
+
+class TestMs < Test::Unit::TestCase
+
+  def setup
+    @ms=ms(3,1,1)
+  end
+
+  def test_row1
+    assert_equal(15,@ms[0].reduce(:+))
+  end
+
+  def test_row2
+    assert_equal(15,@ms[1].reduce(:+))
+  end
+
+  def test_row3
+    assert_equal(15,@ms[2].reduce(:+))
+  end
+
+  def test_col1
+    assert_equal(15,@ms.each.map {|x| x[0]}.reduce(:+))
+  end
+
+  def test_col2
+    assert_equal(15,@ms.each.map {|x| x[1]}.reduce(:+))
+  end
+
+  def test_col3
+    assert_equal(15,@ms.each.map {|x| x[2]}.reduce(:+))
+  end
+
+  def test_dia1
+    assert_equal(15,0.upto(2).each.map {|x| @ms[x][x]}.reduce(:+))
+  end
+
+  def test_dia2
+    assert_equal(15,0.upto(2).each.map {|x| @ms[x][2-x]}.reduce(:+))
+  end
+
+end
+
diff --git a/challenge-089/roger-bell-west/rust/ch-1.rs b/challenge-089/roger-bell-west/rust/ch-1.rs
new file mode 100755
index 0000000000..2699b4ce6d
--- /dev/null
+++ b/challenge-089/roger-bell-west/rust/ch-1.rs
@@ -0,0 +1,60 @@
+#! /bin/sh
+//usr/bin/env rustc --test $0 -o ${0}x && ./${0}x; rm -f ${0}x ; exit
+
+#[test]
+fn test_ex1() {
+    assert_eq!(gs(3),3);
+}
+
+#[test]
+fn test_ex2() {
+    assert_eq!(gs(4),7);
+}
+
+fn gs(n: i32) -> i32 {
+    let mut tot=n-1;
+    for a in 2..n {
+        for x in a+1..n+1 {
+            tot+=gcd(a,x);
+        }
+    }
+    return tot;
+}
+
+fn gcd(mut a: i32,mut b: i32) -> i32 {
+    if a==0 {
+        return b;
+    }
+    if b==0 {
+        return a;
+    }
+    let mut d=0;
+    loop {
+        if a == b {
+            return a << d;
+        }
+        let aa=a % 2 == 0;
+        let bb=b % 2 == 0;
+        if aa && bb {
+            a >>= 1;
+            b >>= 1;
+            d+=1;
+        } else if aa {
+            a >>= 1;
+        } else if bb {
+            b >>= 1;
+        } else {
+            let c=(a-b).abs();
+            a=min(a,b);
+            b=c >> 1;
+        }
+    }
+}
+
+fn min<T: Ord>(value1: T, value2: T) -> T {
+    if value1 <= value2 {
+        value1
+    } else {
+        value2
+    }
+}
diff --git a/challenge-089/roger-bell-west/rust/ch-2.rs b/challenge-089/roger-bell-west/rust/ch-2.rs
new file mode 100755
index 0000000000..c74dd96609
--- /dev/null
+++ b/challenge-089/roger-bell-west/rust/ch-2.rs
@@ -0,0 +1,73 @@
+#! /bin/sh
+//usr/bin/env rustc --test $0 -o ${0}x && ./${0}x; rm -f ${0}x ; exit
+
+#[test]
+fn test_row1() {
+    let ms=ms(3,1,1);
+    assert_eq!(ms[0].iter().sum::<i64>(),15);
+}
+
+#[test]
+fn test_row2() {
+    let ms=ms(3,1,1);
+    assert_eq!(ms[1].iter().sum::<i64>(),15);
+}
+
+#[test]
+fn test_row3() {
+    let ms=ms(3,1,1);
+    assert_eq!(ms[2].iter().sum::<i64>(),15);
+}
+
+#[test]
+fn test_col1() {
+    let ms=ms(3,1,1);
+    assert_eq!((0..ms.len()).map(|i| ms[i][0]).sum::<i64>(),15);
+}
+
+#[test]
+fn test_col2() {
+    let ms=ms(3,1,1);
+    assert_eq!((0..ms.len()).map(|i| ms[i][1]).sum::<i64>(),15);
+}
+
+#[test]
+fn test_col3() {
+    let ms=ms(3,1,1);
+    assert_eq!((0..ms.len()).map(|i| ms[i][2]).sum::<i64>(),15);
+}
+
+#[test]
+fn test_dia1() {
+    let ms=ms(3,1,1);
+    assert_eq!((0..ms.len()).map(|i| ms[i][i]).sum::<i64>(),15);
+}
+
+#[test]
+fn test_dia2() {
+    let ms=ms(3,1,1);
+    assert_eq!((0..ms.len()).map(|i| ms[i][2-i]).sum::<i64>(),15);
+}
+
+fn ms(order: usize, start: i64, inc: i64) -> Vec<Vec<i64>> {
+    let mut m=vec![vec![0; order]; order];
+    let mut x: usize=(order/2)+1;
+    let mut y: usize=order/2;
+    let mut n=start;
+    loop {
+        m[x][y]=n;
+        n += inc;
+        let mut xa=(x+1) % order;
+        let mut ya=(y+1) % order;
+        if m[xa][ya] > 0 {
+            xa=(x+2) % order;
+            ya=y;
+            if m[xa][ya] > 0 {
+                break;
+            }
+        }
+        x=xa;
+        y=ya;
+    }
+    return m;
+}