Merge pull request #4849 from Firedrake/rogerbw-challenge-129

Solutions for challenge #129

7 files changed, 586 insertions, 0 deletions

diff --git a/challenge-129/roger-bell-west/perl/ch-1.pl b/challenge-129/roger-bell-west/perl/ch-1.pl
new file mode 100755
index 0000000000..a7422f9933
--- /dev/null
+++ b/challenge-129/roger-bell-west/perl/ch-1.pl
@@ -0,0 +1,71 @@
+#! /usr/bin/perl
+
+use strict;
+
+use Test::More tests => 7;
+use List::Util qw(max);
+
+is(rd([
+               1,
+           2,      3,
+         0,  0,  0,  4,
+        0,0,0,0,0,0,5,6
+          ],6),3,'example 1a');
+is(rd([
+               1,
+           2,      3,
+         0,  0,  0,  4,
+        0,0,0,0,0,0,5,6
+          ],5),3,'example 1b');
+is(rd([
+               1,
+           2,      3,
+         0,  0,  0,  4,
+        0,0,0,0,0,0,5,6
+          ],2),1,'example 1c');
+is(rd([
+               1,
+           2,      3,
+         0,  0,  0,  4,
+        0,0,0,0,0,0,5,6
+          ],4),2,'example 1d');
+is(rd([
+                       1,
+               2,              3,
+           4,      0,      0,      5,
+         0,  6,  0,  0,  0,  0,  7,  0,
+        0,0,8,9,0,0,0,0,0,0,0,0,0,0,0,0
+          ],7),3,'example 2a');
+is(rd([
+                       1,
+               2,              3,
+           4,      0,      0,      5,
+         0,  6,  0,  0,  0,  0,  7,  0,
+        0,0,8,9,0,0,0,0,0,0,0,0,0,0,0,0
+          ],8),4,'example 2b');
+is(rd([
+                       1,
+               2,              3,
+           4,      0,      0,      5,
+         0,  6,  0,  0,  0,  0,  7,  0,
+        0,0,8,9,0,0,0,0,0,0,0,0,0,0,0,0
+          ],6),3,'example 2c');
+
+sub rd {
+  my ($tree,$content)=@_;
+  my $depth=0;
+  my $dl=1;
+  my $db=1;
+  foreach my $i (0..$#{$tree}) {
+    if ($tree->[$i] == $content) {
+      return $depth;
+    }
+    $dl--;
+    if ($dl==0) {
+      $db*=2;
+      $dl=$db;
+      $depth++;
+    }
+  }
+  return -1;
+}
diff --git a/challenge-129/roger-bell-west/perl/ch-2.pl b/challenge-129/roger-bell-west/perl/ch-2.pl
new file mode 100755
index 0000000000..ce5f20524d
--- /dev/null
+++ b/challenge-129/roger-bell-west/perl/ch-2.pl
@@ -0,0 +1,106 @@
+#! /usr/bin/perl
+
+use strict;
+use warnings;
+
+use Test::More tests => 4;
+
+{
+  my $ta=Local::LinkedList->new;
+  $ta->append([1,2,3]);
+  is_deeply($ta->as_arrayref,[1,2,3],'basics 1');
+  $ta->append(4);
+  is_deeply($ta->as_arrayref,[1,2,3,4],'basics 2');
+}
+
+{
+  my $ta=Local::LinkedList->new;
+  $ta->append([1,2,3]);
+  my $tb=Local::LinkedList->new;
+  $tb->append([3,2,1]);
+  my $tc=$ta->piecewise_add($tb);
+  is_deeply($tc->as_arrayref,[4,4,4],'example 1');
+}
+
+{
+  my $ta=Local::LinkedList->new;
+  $ta->append([1,2,3,4,5]);
+  my $tb=Local::LinkedList->new;
+  $tb->append([6,5,5]);
+  my $tc=$ta->piecewise_add($tb);
+  is_deeply($tc->as_arrayref,[1,3,0,0,0],'example 2');
+}
+
+package Local::LinkedList;
+
+sub new {
+  my $class=shift;
+  my $self=[];
+  bless $self,$class;
+}
+
+sub lastused {
+  my $self=shift;
+  if ($#{$self}==-1) {
+    return -1;
+  }
+  my $i=0;
+  while ($self->[$i]{next} != -1) {
+    $i=$self->[$i]{next};
+  }
+  return $i;
+}
+
+sub append {
+  my $self=shift;
+  my $elem=shift;
+  if (ref $elem eq 'ARRAY') {
+    map {$self->append($_)} @{$elem};
+  } else {
+    my $i=$self->lastused;
+    push @{$self},{value => $elem,next => -1};
+    if ($i > -1) {
+      $self->[$i]{next}=$#{$self};
+    }
+  }
+}
+
+sub as_arrayref {
+  my $self=shift;
+  my @a;
+  my $i=0;
+  while (defined $self->[$i]) {
+    push @a,$self->[$i]{value};
+    $i=$self->[$i]{next};
+    if ($i == -1) {
+      last;
+    }
+  }
+  return \@a;
+}
+
+sub piecewise_add {
+  my $self=shift;
+  my $other=shift;
+  my @a=reverse @{$self->as_arrayref};
+  my @b=reverse @{$other->as_arrayref};
+  while (scalar @a < scalar @b) {
+    push @a,0;
+  }
+  while (scalar @b < scalar @a) {
+    push @b,0;
+  }
+  my @c;
+  my $carry=0;
+  foreach my $i (0..$#a) {
+    my $d=$a[$i]+$b[$i]+$carry;
+    push @c,$d % 10;
+    $carry=int($d/10);
+  }
+  if ($carry) {
+    push @c,1;
+  }
+  my $out=Local::LinkedList->new;
+  $out->append([reverse @c]);
+  return $out;
+}
diff --git a/challenge-129/roger-bell-west/postscript/ch-1.ps b/challenge-129/roger-bell-west/postscript/ch-1.ps
new file mode 100644
index 0000000000..6af8726eea
--- /dev/null
+++ b/challenge-129/roger-bell-west/postscript/ch-1.ps
@@ -0,0 +1,72 @@
+%! no DSC
+
+/rd {
+    /content exch def
+    /tree exch def
+    /ret -1 def
+    /depth 0 def
+    /dl 1 def
+    /db 1 def
+    tree {
+        content eq { /ret depth def exit } if
+        /dl dl 1 sub def
+        dl 0 eq {
+            /db db 2 mul def
+            /dl db def
+            /depth depth 1 add def
+        } if
+    } forall
+    ret
+} def
+
+[
+               1 
+           2       3 
+         0   0   0   4 
+        0 0 0 0 0 0 5 6
+] 6 rd 3 eq { (Pass) } { (Fail) } ifelse =
+
+[
+               1 
+           2       3 
+         0   0   0   4 
+        0 0 0 0 0 0 5 6
+] 5 rd 3 eq { (Pass) } { (Fail) } ifelse =
+
+[
+               1 
+           2       3 
+         0   0   0   4 
+        0 0 0 0 0 0 5 6
+] 2 rd 1 eq { (Pass) } { (Fail) } ifelse =
+
+[
+               1 
+           2       3 
+         0   0   0   4 
+        0 0 0 0 0 0 5 6
+] 4 rd 2 eq { (Pass) } { (Fail) } ifelse =
+
+[
+                       1
+               2               3 
+           4       0       0       5 
+         0   6   0   0   0   0   7   0 
+        0 0 8 9 0 0 0 0 0 0 0 0 0 0 0 0
+] 7 rd 3 eq { (Pass) } { (Fail) } ifelse =
+
+[
+                       1
+               2               3 
+           4       0       0       5 
+         0   6   0   0   0   0   7   0 
+        0 0 8 9 0 0 0 0 0 0 0 0 0 0 0 0
+] 8 rd 4 eq { (Pass) } { (Fail) } ifelse =
+
+[
+                       1
+               2               3 
+           4       0       0       5 
+         0   6   0   0   0   0   7   0 
+        0 0 8 9 0 0 0 0 0 0 0 0 0 0 0 0
+] 6 rd 3 eq { (Pass) } { (Fail) } ifelse =
diff --git a/challenge-129/roger-bell-west/python/ch-1.py b/challenge-129/roger-bell-west/python/ch-1.py
new file mode 100755
index 0000000000..aa79103127
--- /dev/null
+++ b/challenge-129/roger-bell-west/python/ch-1.py
@@ -0,0 +1,82 @@
+#! /usr/bin/python3
+
+import unittest
+
+from math import degrees,atan2
+
+def rd(tree,content):
+  depth=0
+  dl=1
+  db=1
+  for i in range(len(tree)):
+    if tree[i]==content:
+      return depth
+    dl -= 1
+    if dl==0:
+      db *= 2
+      dl=db
+      depth += 1
+  return -1
+
+class TestRd(unittest.TestCase):
+
+        def test_ex1a(self):
+          self.assertEqual(rd([
+            1,
+            2,      3,
+            0,  0,  0,  4,
+            0,0,0,0,0,0,5,6
+          ],6),3,'example 1a')
+
+        def test_ex1b(self):
+          self.assertEqual(rd([
+            1,
+            2,      3,
+            0,  0,  0,  4,
+            0,0,0,0,0,0,5,6
+          ],5),3,'example 1b')
+
+        def test_ex1c(self):
+          self.assertEqual(rd([
+            1,
+            2,      3,
+            0,  0,  0,  4,
+            0,0,0,0,0,0,5,6
+          ],2),1,'example 1c')
+          
+        def test_ex1d(self):
+          self.assertEqual(rd([
+            1,
+            2,      3,
+            0,  0,  0,  4,
+            0,0,0,0,0,0,5,6
+          ],4),2,'example 1d')
+          
+        def test_ex2a(self):
+          self.assertEqual(rd([
+            1,
+            2,              3,
+            4,      0,      0,      5,
+            0,  6,  0,  0,  0,  0,  7,  0,
+            0,0,8,9,0,0,0,0,0,0,0,0,0,0,0,0
+          ],7),3,'example 2a')
+          
+        def test_ex2b(self):
+          self.assertEqual(rd([
+            1,
+            2,              3,
+            4,      0,      0,      5,
+            0,  6,  0,  0,  0,  0,  7,  0,
+            0,0,8,9,0,0,0,0,0,0,0,0,0,0,0,0
+          ],8),4,'example 2b')
+          
+        def test_ex2c(self):
+          self.assertEqual(rd([
+            1,
+            2,              3,
+            4,      0,      0,      5,
+            0,  6,  0,  0,  0,  0,  7,  0,
+            0,0,8,9,0,0,0,0,0,0,0,0,0,0,0,0
+          ],6),3,'example 2c')
+
+unittest.main()
diff --git a/challenge-129/roger-bell-west/raku/ch-1.p6 b/challenge-129/roger-bell-west/raku/ch-1.p6
new file mode 100755
index 0000000000..633c6281d3
--- /dev/null
+++ b/challenge-129/roger-bell-west/raku/ch-1.p6
@@ -0,0 +1,70 @@
+#! /usr/bin/perl6
+
+use Test;
+
+plan 7;
+
+
+is(rd([
+               1,
+           2,      3,
+         0,  0,  0,  4,
+        0,0,0,0,0,0,5,6
+          ],6),3,'example 1a');
+is(rd([
+               1,
+           2,      3,
+         0,  0,  0,  4,
+        0,0,0,0,0,0,5,6
+          ],5),3,'example 1b');
+is(rd([
+               1,
+           2,      3,
+         0,  0,  0,  4,
+        0,0,0,0,0,0,5,6
+          ],2),1,'example 1c');
+is(rd([
+               1,
+           2,      3,
+         0,  0,  0,  4,
+        0,0,0,0,0,0,5,6
+          ],4),2,'example 1d');
+is(rd([
+                       1,
+               2,              3,
+           4,      0,      0,      5,
+         0,  6,  0,  0,  0,  0,  7,  0,
+        0,0,8,9,0,0,0,0,0,0,0,0,0,0,0,0
+          ],7),3,'example 2a');
+is(rd([
+                       1,
+               2,              3,
+           4,      0,      0,      5,
+         0,  6,  0,  0,  0,  0,  7,  0,
+        0,0,8,9,0,0,0,0,0,0,0,0,0,0,0,0
+          ],8),4,'example 2b');
+is(rd([
+                       1,
+               2,              3,
+           4,      0,      0,      5,
+         0,  6,  0,  0,  0,  0,  7,  0,
+        0,0,8,9,0,0,0,0,0,0,0,0,0,0,0,0
+          ],6),3,'example 2c');
+
+sub rd(@tree,$content) {
+  my $depth=0;
+  my $dl=1;
+  my $db=1;
+  for (0..@tree.end) -> $i {
+    if (@tree[$i] == $content) {
+      return $depth;
+    }
+    $dl--;
+    if ($dl==0) {
+      $db *= 2;
+      $dl=$db;
+      $depth++;
+    }
+  }
+  return -1;
+}
diff --git a/challenge-129/roger-bell-west/ruby/ch-1.rb b/challenge-129/roger-bell-west/ruby/ch-1.rb
new file mode 100755
index 0000000000..9240d9def5
--- /dev/null
+++ b/challenge-129/roger-bell-west/ruby/ch-1.rb
@@ -0,0 +1,92 @@
+#! /usr/bin/ruby
+
+def rd(tree,content)
+  st=tree.length
+  depth=0
+  dl=1
+  db=1
+  0.upto(tree.length()-1) do |i|
+    if tree[i] == content then
+      return depth
+    end
+    dl -= 1
+    if dl==0 then
+      db *= 2
+      dl=db
+      depth += 1
+    end
+  end
+  return -1
+end
+
+require 'test/unit'
+
+class TestRd < Test::Unit::TestCase
+
+  def test_ex1a
+    assert_equal(3,rd([
+                       1,
+                       2,      3,
+                       0,  0,  0,  4,
+                       0,0,0,0,0,0,5,6
+                     ],6))
+  end
+
+  def test_ex1b
+    assert_equal(3,rd([
+                       1,
+                       2,      3,
+                       0,  0,  0,  4,
+                       0,0,0,0,0,0,5,6
+                     ],5))
+  end
+
+  def test_ex1c
+    assert_equal(1,rd([
+                       1,
+                       2,      3,
+                       0,  0,  0,  4,
+                       0,0,0,0,0,0,5,6
+                     ],2))
+  end
+
+  def test_ex1d
+    assert_equal(2,rd([
+                       1,
+                       2,      3,
+                       0,  0,  0,  4,
+                       0,0,0,0,0,0,5,6
+                     ],4))
+  end
+
+  def test_ex2a
+    assert_equal(3,rd([
+                        1,
+                        2,              3,
+                        4,      0,      0,      5,
+                        0,  6,  0,  0,  0,  0,  7,  0,
+                        0,0,8,9,0,0,0,0,0,0,0,0,0,0,0,0
+                     ],7))
+  end
+
+  def test_ex2b
+    assert_equal(4,rd([
+                        1,
+                        2,              3,
+                        4,      0,      0,      5,
+                        0,  6,  0,  0,  0,  0,  7,  0,
+                        0,0,8,9,0,0,0,0,0,0,0,0,0,0,0,0
+                     ],8))
+  end
+
+  def test_ex2c
+    assert_equal(3,rd([
+                        1,
+                        2,              3,
+                        4,      0,      0,      5,
+                        0,  6,  0,  0,  0,  0,  7,  0,
+                        0,0,8,9,0,0,0,0,0,0,0,0,0,0,0,0
+                     ],6))
+  end
+  
+end
diff --git a/challenge-129/roger-bell-west/rust/ch-1.rs b/challenge-129/roger-bell-west/rust/ch-1.rs
new file mode 100755
index 0000000000..508de0cfd4
--- /dev/null
+++ b/challenge-129/roger-bell-west/rust/ch-1.rs
@@ -0,0 +1,93 @@
+#! /bin/sh
+//usr/bin/env rustc --test $0 -o ${0}x && ./${0}x; rm -f ${0}x ; exit
+
+#[test]
+fn test_ex1a() {
+    assert_eq!(rd(vec![
+        1,
+        2,      3,
+        0,  0,  0,  4,
+        0,0,0,0,0,0,5,6
+    ],6),3);
+}
+
+#[test]
+fn test_ex1b() {
+    assert_eq!(rd(vec![
+        1,
+        2,      3,
+        0,  0,  0,  4,
+        0,0,0,0,0,0,5,6
+    ],5),3);
+}
+
+#[test]
+fn test_ex1c() {
+    assert_eq!(rd(vec![
+        1,
+        2,      3,
+        0,  0,  0,  4,
+        0,0,0,0,0,0,5,6
+    ],2),1);
+}
+
+#[test]
+fn test_ex1d() {
+    assert_eq!(rd(vec![
+        1,
+        2,      3,
+        0,  0,  0,  4,
+        0,0,0,0,0,0,5,6
+    ],4),2);
+}
+
+#[test]
+fn test_ex2a() {
+    assert_eq!(rd(vec![
+        1,
+        2,              3,
+        4,      0,      0,      5,
+        0,  6,  0,  0,  0,  0,  7,  0,
+        0,0,8,9,0,0,0,0,0,0,0,0,0,0,0,0
+    ],7),3);
+}
+
+#[test]
+fn test_ex2b() {
+    assert_eq!(rd(vec![
+        1,
+        2,              3,
+        4,      0,      0,      5,
+        0,  6,  0,  0,  0,  0,  7,  0,
+        0,0,8,9,0,0,0,0,0,0,0,0,0,0,0,0
+    ],8),4);
+}
+
+#[test]
+fn test_ex2c() {
+    assert_eq!(rd(vec![
+        1,
+        2,              3,
+        4,      0,      0,      5,
+        0,  6,  0,  0,  0,  0,  7,  0,
+        0,0,8,9,0,0,0,0,0,0,0,0,0,0,0,0
+    ],6),3);
+}
+
+fn rd(tree: Vec<u64>,content: u64) -> i64 {
+    let mut depth: i64=0;
+    let mut dl: u64=1;
+    let mut db: u64=1;
+    for i in 0..tree.len() {
+        if tree[i]==content {
+            return depth;
+        }
+        dl -= 1;
+        if dl==0 {
+            db *= 2;
+            dl = db;
+            depth += 1;
+        }
+    }
+    return -1;
+}