Merge pull request #7471 from Firedrake/rogerbw-challenge-201

Solutions for challenge no. 201

19 files changed, 624 insertions, 0 deletions

diff --git a/challenge-201/roger-bell-west/javascript/ch-1.js b/challenge-201/roger-bell-west/javascript/ch-1.js
new file mode 100755
index 0000000000..1ed12562b5
--- /dev/null
+++ b/challenge-201/roger-bell-west/javascript/ch-1.js
@@ -0,0 +1,26 @@
+#! /usr/bin/node
+
+"use strict"
+
+function missingnumber(l) {
+    let v = new Set(l);
+    for (let i = 0; i <= l.length; i++) {
+        if (!v.has(i)) {
+            return i;
+        }
+    }
+    return 0;
+}
+
+if (missingnumber([0, 1, 3]) == 2) {
+  process.stdout.write("Pass");
+} else {
+  process.stdout.write("FAIL");
+}
+process.stdout.write(" ");
+if (missingnumber([0, 1]) == 2) {
+  process.stdout.write("Pass");
+} else {
+  process.stdout.write("FAIL");
+}
+process.stdout.write("\n");
diff --git a/challenge-201/roger-bell-west/javascript/ch-2.js b/challenge-201/roger-bell-west/javascript/ch-2.js
new file mode 100755
index 0000000000..4b7b834ae3
--- /dev/null
+++ b/challenge-201/roger-bell-west/javascript/ch-2.js
@@ -0,0 +1,40 @@
+#! /usr/bin/node
+
+"use strict"
+
+function pennypiles(n) {
+    if (n == 0) {
+        return 1;
+    }
+    let s = 0;
+    let j = n - 1;
+    let k = 2;
+    while (j >= 0) {
+        let t = pennypiles(j);
+        if (Math.floor(k / 2) % 2 == 1) {
+            s += t;
+        } else {
+            s -= t;
+        }
+        if (k % 2 == 1) {
+            j -= k;
+        } else {
+            j -= Math.floor(k / 2)
+        }
+        k++;
+    }
+    return s;
+}
+
+if (pennypiles(5) == 7) {
+  process.stdout.write("Pass");
+} else {
+  process.stdout.write("FAIL");
+}
+process.stdout.write(" ");
+if (pennypiles(10) == 42) {
+  process.stdout.write("Pass");
+} else {
+  process.stdout.write("FAIL");
+}
+process.stdout.write("\n");
diff --git a/challenge-201/roger-bell-west/kotlin/ch-1.kt b/challenge-201/roger-bell-west/kotlin/ch-1.kt
new file mode 100644
index 0000000000..3cae3d322b
--- /dev/null
+++ b/challenge-201/roger-bell-west/kotlin/ch-1.kt
@@ -0,0 +1,26 @@
+fun missingnumber(l: List<Int>): Int {
+    val v = l.toSet()
+    for (i in 0..l.size) {
+        if (!v.contains(i)) {
+            return i
+        }
+    }
+    return 0
+}
+
+fun main() {
+
+    if (missingnumber(listOf(0, 1, 3)) == 2) {
+        print("Pass")
+    } else {
+        print("Fail")
+    }
+    print(" ")
+    if (missingnumber(listOf(0, 1)) == 2) {
+        print("Pass")
+    } else {
+        print("Fail")
+    }
+    println("")
+
+}
diff --git a/challenge-201/roger-bell-west/kotlin/ch-2.kt b/challenge-201/roger-bell-west/kotlin/ch-2.kt
new file mode 100644
index 0000000000..54f7d5f105
--- /dev/null
+++ b/challenge-201/roger-bell-west/kotlin/ch-2.kt
@@ -0,0 +1,40 @@
+fun pennypiles(n: Int): Int {
+    if (n == 0) {
+        return 1
+    }
+    var s = 0
+    var j = n - 1
+    var k = 2
+    while (j >= 0) {
+        val t = pennypiles(j)
+        if ((k / 2) % 2 == 1) {
+            s += t
+        } else {
+            s -= t
+        }
+        if (k % 2 == 1) {
+            j -= k
+        } else {
+            j -= k / 2
+        }
+        k += 1
+    }
+    return s
+}
+
+fun main() {
+
+    if (pennypiles(5) == 7) {
+        print("Pass")
+    } else {
+        print("Fail")
+    }
+    print(" ")
+    if (pennypiles(10) == 42) {
+        print("Pass")
+    } else {
+        print("Fail")
+    }
+    println("")
+
+}
diff --git a/challenge-201/roger-bell-west/lua/ch-1.lua b/challenge-201/roger-bell-west/lua/ch-1.lua
new file mode 100755
index 0000000000..7b01d337b8
--- /dev/null
+++ b/challenge-201/roger-bell-west/lua/ch-1.lua
@@ -0,0 +1,29 @@
+#! /usr/bin/lua
+
+function missingnumber(l)
+   local v = {}
+   for dummy, i in ipairs(l) do
+      v[i] = true
+   end
+   for i = 0,#l do
+      if v[i] == nil then
+         return i
+      end
+   end
+   return 0
+end
+
+if missingnumber({0, 1, 3}) == 2 then
+  io.write("Pass")
+else
+  io.write("FAIL")
+end
+io.write(" ")
+
+if missingnumber({0, 1}) == 2 then
+  io.write("Pass")
+else
+  io.write("FAIL")
+end
+print("")
+
diff --git a/challenge-201/roger-bell-west/lua/ch-2.lua b/challenge-201/roger-bell-west/lua/ch-2.lua
new file mode 100755
index 0000000000..da63ceebf2
--- /dev/null
+++ b/challenge-201/roger-bell-west/lua/ch-2.lua
@@ -0,0 +1,40 @@
+#! /usr/bin/lua
+
+function pennypiles(n)
+   if n == 0 then
+      return 1
+   end
+   local s = 0
+   local j = n - 1
+   local k = 2
+   while j >= 0 do
+      local t = pennypiles(j)
+      if math.floor(k / 2) % 2 == 1 then
+         s = s + t
+      else
+         s = s - t
+      end
+      if k % 2 == 1 then
+         j = j - k
+      else
+         j = j - math.floor(k / 2)
+      end
+      k = k + 1
+   end
+   return s
+end
+
+if pennypiles(5) == 7 then
+  io.write("Pass")
+else
+  io.write("FAIL")
+end
+io.write(" ")
+
+if pennypiles(10) == 42 then
+  io.write("Pass")
+else
+  io.write("FAIL")
+end
+print("")
+
diff --git a/challenge-201/roger-bell-west/perl/ch-1.pl b/challenge-201/roger-bell-west/perl/ch-1.pl
new file mode 100755
index 0000000000..d273482274
--- /dev/null
+++ b/challenge-201/roger-bell-west/perl/ch-1.pl
@@ -0,0 +1,20 @@
+#! /usr/bin/perl
+
+use strict;
+use warnings;
+use experimental 'signatures';
+
+use Test::More tests => 2;
+
+is(missingnumber([0, 1, 3]), 2, 'example 1');
+is(missingnumber([0, 1]), 2, 'example 2');
+
+sub missingnumber($l) {
+  my %v = map {$_ => 1} @{$l};
+  foreach my $i (0..scalar @{$l}) {
+    if (!exists $v{$i}) {
+      return $i;
+    }
+  }
+  return 0;
+}
diff --git a/challenge-201/roger-bell-west/perl/ch-2.pl b/challenge-201/roger-bell-west/perl/ch-2.pl
new file mode 100755
index 0000000000..1ba70f9911
--- /dev/null
+++ b/challenge-201/roger-bell-west/perl/ch-2.pl
@@ -0,0 +1,16 @@
+#! /usr/bin/perl
+
+use strict;
+use warnings;
+use experimental 'signatures';
+
+use Math::Prime::Util qw(partitions);
+
+use Test::More tests => 2;
+
+is(pennypiles(5), 7, 'example 1');
+is(pennypiles(10), 42, 'example 2');
+
+sub pennypiles($n) {
+  return partitions($n);
+}
diff --git a/challenge-201/roger-bell-west/postscript/ch-1.ps b/challenge-201/roger-bell-west/postscript/ch-1.ps
new file mode 100644
index 0000000000..5afd9a9535
--- /dev/null
+++ b/challenge-201/roger-bell-west/postscript/ch-1.ps
@@ -0,0 +1,64 @@
+%!PS
+
+% begin included library code
+% see https://github.com/Firedrake/postscript-libraries/
+/test.end {
+    ( ) print
+    test.count 0 gt {
+        (Passed ) print
+        test.pass (...) cvs print
+        (/) print
+        test.count (...) cvs print
+        ( \() print
+        test.pass 100 mul test.count idiv (...) cvs print
+        (%\)) print
+        (\r\n) print
+    } if
+} bind def
+
+/test.start {
+    print (:) print
+    /test.pass 0 def
+    /test.count 0 def
+} bind def
+
+/toset { % array -> dict of (value, true)
+    << exch
+       {
+           true
+       } forall
+    >>
+} bind def
+
+/test {
+    /test.count test.count 1 add def
+    {
+        /test.pass test.pass 1 add def
+    } {
+        ( ) print
+        test.count (....) cvs print
+        (-fail) print
+    } ifelse
+} bind def
+
+
+% end included library code
+
+/missingnumber {
+    3 dict begin
+    /l exch def
+    /v l toset def
+    0
+    0 1 l length {
+        /i exch def
+        v i known not {
+            pop i
+        } if
+    } for
+    end
+} bind def
+
+(missingnumber) test.start
+[0 1 3] missingnumber 2 eq test
+[0 1] missingnumber 2 eq test
+test.end
diff --git a/challenge-201/roger-bell-west/postscript/ch-2.ps b/challenge-201/roger-bell-west/postscript/ch-2.ps
new file mode 100644
index 0000000000..98e5acf6ae
--- /dev/null
+++ b/challenge-201/roger-bell-west/postscript/ch-2.ps
@@ -0,0 +1,74 @@
+%!PS
+
+% begin included library code
+% see https://github.com/Firedrake/postscript-libraries/
+/test.end {
+    ( ) print
+    test.count 0 gt {
+        (Passed ) print
+        test.pass (...) cvs print
+        (/) print
+        test.count (...) cvs print
+        ( \() print
+        test.pass 100 mul test.count idiv (...) cvs print
+        (%\)) print
+        (\r\n) print
+    } if
+} bind def
+
+/test.start {
+    print (:) print
+    /test.pass 0 def
+    /test.count 0 def
+} bind def
+
+/test {
+    /test.count test.count 1 add def
+    {
+        /test.pass test.pass 1 add def
+    } {
+        ( ) print
+        test.count (....) cvs print
+        (-fail) print
+    } ifelse
+} bind def
+
+
+% end included library code
+
+/pennypiles {
+    dup 0 eq {
+        1 exch pop
+    } {
+        4 dict begin
+        /s 0 def
+        /j exch 1 sub def
+        /k 2 def
+        {
+            j 0 lt {
+                exit
+            } if
+            /t j pennypiles def
+            /s s t
+            k 2 idiv 2 mod 0 eq {
+                neg
+            } if
+            add def
+            /j j
+            k 2 mod 1 eq {
+                k
+            } {
+                k 2 idiv
+            } ifelse
+            sub def
+            /k k 1 add def
+        } loop
+        s
+        end
+    } ifelse
+} bind def
+
+(pennypiles) test.start
+5 pennypiles 7 eq test
+10 pennypiles 42 eq test
+test.end
diff --git a/challenge-201/roger-bell-west/python/ch-1.py b/challenge-201/roger-bell-west/python/ch-1.py
new file mode 100755
index 0000000000..de077ad70b
--- /dev/null
+++ b/challenge-201/roger-bell-west/python/ch-1.py
@@ -0,0 +1,20 @@
+#! /usr/bin/python3
+
+import unittest
+
+def missingnumber(l):
+  v = set(l)
+  for i in range(len(l) + 1):
+    if i not in v:
+      return i
+  return 0
+
+class TestMissingnumber(unittest.TestCase):
+
+  def test_ex1(self):
+    self.assertEqual(missingnumber([0, 1, 3]), 2, 'example 1')
+
+  def test_ex2(self):
+    self.assertEqual(missingnumber([0, 1]), 2, 'example 2')
+
+unittest.main()
diff --git a/challenge-201/roger-bell-west/python/ch-2.py b/challenge-201/roger-bell-west/python/ch-2.py
new file mode 100755
index 0000000000..7594ac74e7
--- /dev/null
+++ b/challenge-201/roger-bell-west/python/ch-2.py
@@ -0,0 +1,32 @@
+#! /usr/bin/python3
+
+import unittest
+
+def pennypiles(n):
+  if n == 0:
+    return 1
+  s = 0
+  j = n - 1
+  k = 2
+  while j >= 0:
+    t = pennypiles(j)
+    if int(k / 2) % 2 == 1:
+      s += t
+    else:
+      s -= t
+    if k % 2 == 1:
+      j -= k
+    else:
+      j -= int(k / 2)
+    k += 1
+  return s
+
+class TestPennypiles(unittest.TestCase):
+
+  def test_ex1(self):
+    self.assertEqual(pennypiles(5), 7, 'example 1')
+
+  def test_ex2(self):
+    self.assertEqual(pennypiles(10), 42, 'example 2')
+
+unittest.main()
diff --git a/challenge-201/roger-bell-west/raku/ch-1.p6 b/challenge-201/roger-bell-west/raku/ch-1.p6
new file mode 100755
index 0000000000..d757b1751f
--- /dev/null
+++ b/challenge-201/roger-bell-west/raku/ch-1.p6
@@ -0,0 +1,18 @@
+#! /usr/bin/raku
+
+use Test;
+
+plan 2;
+
+is(missingnumber([0, 1, 3]), 2, 'example 1');
+is(missingnumber([0, 1]), 2, 'example 2');
+
+sub missingnumber(@l) {
+  my $v = set(@l);
+  for (0..@l.elems) -> $i {
+    unless ($v{$i}:exists) {
+      return $i;
+    }
+  }
+  return 0;
+}
diff --git a/challenge-201/roger-bell-west/raku/ch-2.p6 b/challenge-201/roger-bell-west/raku/ch-2.p6
new file mode 100755
index 0000000000..edf43355ef
--- /dev/null
+++ b/challenge-201/roger-bell-west/raku/ch-2.p6
@@ -0,0 +1,32 @@
+#! /usr/bin/raku
+
+use Test;
+
+plan 2;
+
+is(pennypiles(5), 7, 'example 1');
+is(pennypiles(10), 42, 'example 2');
+
+sub pennypiles($n) {
+    if ($n == 0) {
+        return 1;
+    }
+    my $s = 0;
+    my $j = $n - 1;
+    my $k = 2;
+    while ($j >= 0) {
+        my $t = pennypiles($j);
+        if (($k div 2) % 2 == 1) {
+            $s += $t;
+        } else {
+            $s -= $t;
+        }
+        if ($k % 2 == 1) {
+            $j -= $k;
+        } else {
+            $j -= ($k div 2);
+        }
+        $k++;
+    }
+    return $s;
+}
diff --git a/challenge-201/roger-bell-west/ruby/ch-1.rb b/challenge-201/roger-bell-west/ruby/ch-1.rb
new file mode 100755
index 0000000000..3947d53c31
--- /dev/null
+++ b/challenge-201/roger-bell-west/ruby/ch-1.rb
@@ -0,0 +1,27 @@
+#! /usr/bin/ruby
+
+require 'test/unit'
+
+require 'set'
+
+def missingnumber(l)
+  v = Set.new(l)
+  0.upto(l.length) do |i|
+    if !v.include?(i) then
+      return i
+    end
+  end
+  return 0
+end
+
+class TestMissingnumber < Test::Unit::TestCase
+
+  def test_ex1
+    assert_equal(2, missingnumber([0, 1, 3]))
+  end
+
+  def test_ex2
+    assert_equal(2, missingnumber([0, 1]))
+  end
+
+end
diff --git a/challenge-201/roger-bell-west/ruby/ch-2.rb b/challenge-201/roger-bell-west/ruby/ch-2.rb
new file mode 100755
index 0000000000..e1ce0a8ebe
--- /dev/null
+++ b/challenge-201/roger-bell-west/ruby/ch-2.rb
@@ -0,0 +1,39 @@
+#! /usr/bin/ruby
+
+require 'test/unit'
+
+def pennypiles(n)
+  if n == 0 then
+    return 1
+  end
+  s = 0
+  j = n - 1
+  k = 2
+  while j >= 0 do
+    t = pennypiles(j)
+    if k.div(2) % 2 == 1 then
+      s += t
+    else
+      s -= t
+    end
+    if k % 2 == 1 then
+      j -= k
+    else
+      j -= k.div(2)
+    end
+    k += 1
+  end
+  return s
+end
+
+class TestPennypiles < Test::Unit::TestCase
+
+  def test_ex1
+    assert_equal(7, pennypiles(5))
+  end
+
+  def test_ex2
+    assert_equal(42, pennypiles(10))
+  end
+
+end
diff --git a/challenge-201/roger-bell-west/rust/ch-1.rs b/challenge-201/roger-bell-west/rust/ch-1.rs
new file mode 100755
index 0000000000..3cc8ef3e57
--- /dev/null
+++ b/challenge-201/roger-bell-west/rust/ch-1.rs
@@ -0,0 +1,25 @@
+#! /bin/sh
+//usr/bin/env rustc --test $0 -o ${0}x && ./${0}x --nocapture; rm -f ${0}x ; exit
+
+use std::collections::HashSet;
+
+#[test]
+fn test_ex1() {
+    assert_eq!(missingnumber(vec![0, 1, 3]), 2);
+}
+
+#[test]
+fn test_ex2() {
+    assert_eq!(missingnumber(vec![0, 1]), 2);
+}
+
+
+fn missingnumber(l: Vec<usize>) -> usize {
+    let v: HashSet<&usize> = l.iter().collect();
+    for i in 0..=l.len() {
+        if !v.contains(&i) {
+            return i;
+        }
+    }
+    0
+}
diff --git a/challenge-201/roger-bell-west/rust/ch-2.rs b/challenge-201/roger-bell-west/rust/ch-2.rs
new file mode 100755
index 0000000000..5464d3b2dc
--- /dev/null
+++ b/challenge-201/roger-bell-west/rust/ch-2.rs
@@ -0,0 +1,36 @@
+#! /bin/sh
+//usr/bin/env rustc --test $0 -o ${0}x && ./${0}x --nocapture; rm -f ${0}x ; exit
+
+#[test]
+fn test_ex1() {
+    assert_eq!(pennypiles(5), 7);
+}
+
+#[test]
+fn test_ex2() {
+    assert_eq!(pennypiles(10), 42);
+}
+
+fn pennypiles(n: isize) -> isize {
+    if n == 0 {
+        return 1;
+    }
+    let mut s = 0;
+    let mut j = n - 1;
+    let mut k = 2;
+    while j >= 0 {
+        let t = pennypiles(j);
+        if (k / 2) % 2 == 1 {
+            s += t;
+        } else {
+            s -= t;
+        }
+        if k % 2 == 1 {
+            j -= k;
+        } else {
+            j -= k / 2;
+        }
+        k += 1;
+    }
+    s
+}
diff --git a/challenge-201/roger-bell-west/tests.yaml b/challenge-201/roger-bell-west/tests.yaml
new file mode 100644
index 0000000000..da3e844f64
--- /dev/null
+++ b/challenge-201/roger-bell-west/tests.yaml
@@ -0,0 +1,20 @@
+---
+ch-1:
+  - function: missingnumber
+    arguments:
+      - 0
+      - 1
+      - 3
+    result: 2
+  - function: missingnumber
+    arguments:
+      - 0
+      - 1
+    result: 2
+ch-2:
+  - function: pennypiles
+    arguments: 5
+    result: 7
+  - function: pennypiles
+    arguments: 10
+    result: 42