Merge pull request #3485 from Firedrake/rogerbw-challenge-099

Solutions for challenge #099

10 files changed, 388 insertions, 0 deletions

diff --git a/challenge-099/roger-bell-west/perl/ch-1.pl b/challenge-099/roger-bell-west/perl/ch-1.pl
new file mode 100755
index 0000000000..e509782c9b
--- /dev/null
+++ b/challenge-099/roger-bell-west/perl/ch-1.pl
@@ -0,0 +1,23 @@
+#! /usr/bin/perl
+
+use strict;
+use warnings;
+
+use Test::More tests => 4;
+
+is(pm('abcde','a*e'),1,'example 1');
+is(pm('abcde','a*d'),0,'example 2');
+is(pm('abcde','?b*d'),0,'example 3');
+is(pm('abcde','a*c?e'),1,'example 4');
+
+sub pm {
+  my $text=shift;
+  my $match=shift;
+  (my $re=$match) =~ s/\?/./g;
+  $re =~ s/\*/.*/g;
+  $re='^'.$re.'$';
+  if ($text =~ /$re/) {
+    return 1;
+  }
+  return 0;
+}
diff --git a/challenge-099/roger-bell-west/perl/ch-2.pl b/challenge-099/roger-bell-west/perl/ch-2.pl
new file mode 100755
index 0000000000..0097d4dcb9
--- /dev/null
+++ b/challenge-099/roger-bell-west/perl/ch-2.pl
@@ -0,0 +1,47 @@
+#! /usr/bin/perl
+
+use strict;
+use warnings;
+
+use Test::More tests => 2;
+
+is(us('littleit','lit'),5,'example 1');
+is(us('london','lon'),3,'example 2');
+
+use List::Util qw(sum);
+
+sub us {
+  my $text=shift;
+  my $match=shift;
+  my %s;
+  {
+    my $i=0;
+    foreach my $c (split '',$text) {
+      push @{$s{$c}},$i;
+      $i++;
+    }
+  }
+  my @j;
+  foreach my $c (split '',$match) {
+    if (exists $s{$c}) {
+      push @j,$s{$c};
+    } else {
+      return 0;
+    }
+  }
+  my @o=(1) x scalar @{$j[0]};
+  foreach my $m (1..$#j) {
+    my @n;
+    foreach my $bi (0..$#{$j[$m]}) {
+      my $t=0;
+      foreach my $ai (0..$#{$j[$m-1]}) {
+        if ($j[$m-1][$ai] < $j[$m][$bi]) {
+          $t+=$o[$ai];
+        }
+      }
+      push @n,$t;
+    }
+    @o=@n;
+  }
+  return sum(@o);
+}
diff --git a/challenge-099/roger-bell-west/python/ch-1.py b/challenge-099/roger-bell-west/python/ch-1.py
new file mode 100755
index 0000000000..8a3140e45e
--- /dev/null
+++ b/challenge-099/roger-bell-west/python/ch-1.py
@@ -0,0 +1,37 @@
+#! /usr/bin/python3
+
+import re
+
+def pm(text,match):
+    rl=list()
+    rl.append("^")
+    for c in match:
+        if c == '?':
+            rl.append(".")
+        elif c == '*':
+            rl.append(".*")
+        else:
+            rl.append(c)
+    rl.append("$")
+    rls=''.join(rl)
+    if re.match(rls,text):
+        return 1
+    return 0
+    
+import unittest
+
+class TestPm(unittest.TestCase):
+
+    def test_ex1(self):
+        self.assertEqual(pm('abcde','a*e'),1,'example 1')
+
+    def test_ex2(self):
+        self.assertEqual(pm('abcde','a*d'),0,'example 2')
+
+    def test_ex3(self):
+        self.assertEqual(pm('abcde','?b*d'),0,'example 3')
+
+    def test_ex4(self):
+        self.assertEqual(pm('abcde','a*c?e'),1,'example 4')
+
+unittest.main()
diff --git a/challenge-099/roger-bell-west/python/ch-2.py b/challenge-099/roger-bell-west/python/ch-2.py
new file mode 100755
index 0000000000..2acef1cb02
--- /dev/null
+++ b/challenge-099/roger-bell-west/python/ch-2.py
@@ -0,0 +1,39 @@
+#! /usr/bin/python3
+
+from collections import defaultdict
+
+def us(text,match):
+    s=defaultdict(list)
+    for i,c in enumerate(text):
+        s[c].append(i)
+    j=list()
+    for c in match:
+        if c in s:
+            j.append(s[c])
+        else:
+            return 0
+    o=list();
+    for i in range(len(j[0])):
+        o.append(1)
+    for m in range(1,len(j)):
+        n=list()
+        for bi in range(len(j[m])):
+            t=0
+            for ai in range(len(j[m-1])):
+                if j[m-1][ai] < j[m][bi]:
+                    t += o[ai]
+            n.append(t)
+        o=n
+    return sum(o)
+
+import unittest
+
+class TestUs(unittest.TestCase):
+
+    def test_ex1(self):
+        self.assertEqual(us('littleit','lit'),5,'example 1')
+
+    def test_ex2(self):
+        self.assertEqual(us('london','lon'),3,'example 2')
+
+unittest.main()
diff --git a/challenge-099/roger-bell-west/raku/ch-1.p6 b/challenge-099/roger-bell-west/raku/ch-1.p6
new file mode 100755
index 0000000000..5f49b4248b
--- /dev/null
+++ b/challenge-099/roger-bell-west/raku/ch-1.p6
@@ -0,0 +1,20 @@
+#! /usr/bin/perl6
+
+use Test;
+
+plan 4;
+
+is(pm('abcde','a*e'),1,'example 1');
+is(pm('abcde','a*d'),0,'example 2');
+is(pm('abcde','?b*d'),0,'example 3');
+is(pm('abcde','a*c?e'),1,'example 4');
+
+sub pm($text,$match) {
+  (my $re=$match) ~~ s:g/\?/./;
+  $re ~~ s:g/\*/.*/;
+  $re='^' ~ $re ~ '$';
+  if ($text ~~ /<$re>/) {
+    return 1;
+  }
+  return 0;
+}
diff --git a/challenge-099/roger-bell-west/raku/ch-2.p6 b/challenge-099/roger-bell-west/raku/ch-2.p6
new file mode 100755
index 0000000000..ed5478ce07
--- /dev/null
+++ b/challenge-099/roger-bell-west/raku/ch-2.p6
@@ -0,0 +1,45 @@
+#! /usr/bin/perl6
+
+use Test;
+
+plan 2;
+
+is(us('littleit','lit'),5,'example 1');
+is(us('london','lon'),3,'example 2');
+
+sub us($text,$match) {
+  my %s;
+  {
+    my $i=0;
+    for $text.comb -> $c {
+      unless %s{$c} {
+        %s{$c}=Array.new;
+      }
+      push %s{$c},$i;
+      $i++;
+    }
+  }
+  my @j;
+  for $match.comb -> $c {
+    if (%s{$c}:exists) {
+      push @j,%s{$c};
+    } else {
+      return 0;
+    }
+  }
+  my @o=(1) xx @j[0].elems;
+  for 1..@j.elems-1 -> $m {
+    my @n;
+    for 0..@j[$m].elems-1 -> $bi {
+      my $t=0;
+      for 0..@j[$m-1].elems-1 -> $ai {
+        if (@j[$m-1][$ai] < @j[$m][$bi]) {
+          $t+=@o[$ai];
+        }
+      }
+      push @n,$t;
+    }
+    @o=@n;
+  }
+  return sum(@o);
+}
diff --git a/challenge-099/roger-bell-west/ruby/ch-1.rb b/challenge-099/roger-bell-west/ruby/ch-1.rb
new file mode 100755
index 0000000000..7f3e75e2d0
--- /dev/null
+++ b/challenge-099/roger-bell-west/ruby/ch-1.rb
@@ -0,0 +1,33 @@
+#! /usr/bin/ruby
+
+def pm(text,match)
+  re='^' + match + '$'
+  re=re.gsub(/\?/,'.')
+  re=re.gsub(/\*/,'.*')
+  if text =~ Regexp.new(re) then
+    return 1
+  end
+  return 0
+end
+
+require 'test/unit'
+
+class TestPm < Test::Unit::TestCase
+
+  def test_ex1
+    assert_equal(1,pm('abcde','a*e'))
+  end
+
+  def test_ex2
+    assert_equal(0,pm('abcde','a*d'))
+  end
+
+  def test_ex3
+    assert_equal(0,pm('abcde','?b*d'))
+  end
+
+  def test_ex4
+    assert_equal(1,pm('abcde','a*c?e'))
+  end
+
+end
diff --git a/challenge-099/roger-bell-west/ruby/ch-2.rb b/challenge-099/roger-bell-west/ruby/ch-2.rb
new file mode 100755
index 0000000000..056e59ba25
--- /dev/null
+++ b/challenge-099/roger-bell-west/ruby/ch-2.rb
@@ -0,0 +1,48 @@
+#! /usr/bin/ruby
+
+def us(text,match)
+  s=Hash.new
+  text.split(//).each_with_index do |c,i|
+    unless s[c] then
+      s[c]=Array.new
+    end
+    s[c].push(i)
+  end
+  j=Array.new;
+  match.split(//).each do |c|
+    if s.has_key?(c) then
+      j.push(s[c])
+    else
+      return 0
+    end
+  end
+  o=Array.new([1] * j[0].length)
+  1.upto(j.length-1) do |m|
+    n=Array.new
+    0.upto(j[m].length-1) do |bi|
+      t=0
+      0.upto(j[m-1].length-1) do |ai|
+        if j[m-1][ai] < j[m][bi] then
+          t += o[ai]
+        end
+      end
+      n.push(t)
+    end
+    o=n
+  end
+  return o.sum
+end
+
+require 'test/unit'
+
+class TestUs < Test::Unit::TestCase
+
+  def test_ex1
+    assert_equal(5,us('littleit','lit'))
+  end
+
+  def test_ex2
+    assert_equal(3,us('london','lon'))
+  end
+
+end
diff --git a/challenge-099/roger-bell-west/rust/ch-1.rs b/challenge-099/roger-bell-west/rust/ch-1.rs
new file mode 100755
index 0000000000..d3fe36b15c
--- /dev/null
+++ b/challenge-099/roger-bell-west/rust/ch-1.rs
@@ -0,0 +1,47 @@
+use regex::Regex;
+
+// Cargo.toml needs:
+// [dependencies]
+// regex = "1"
+
+#[test]
+fn test_ex1() {
+    assert_eq!(pm("abcde","a*e"),1);
+}
+
+#[test]
+fn test_ex2() {
+    assert_eq!(pm("abcde","a*d"),0);
+}
+
+#[test]
+fn test_ex3() {
+    assert_eq!(pm("abcde","?b*d"),0);
+}
+
+#[test]
+fn test_ex4() {
+    assert_eq!(pm("abcde","a*c?e"),1,"example 4");
+}
+
+fn pm(text: &str,mat: &str) -> u8 {
+    let mut rl: Vec<char>=vec![];
+    rl.push('^');
+    for c in mat.chars() {
+        if c == '?' {
+            rl.push('.');
+        } else if c == '*' {
+            rl.push('.');
+            rl.push('*');
+        } else {
+            rl.push(c);
+        }
+    }
+    rl.push('$');
+    let rs=rl.iter().collect::<String>();
+    let rx: Regex=Regex::new(&rs).unwrap();
+    if rx.is_match(&text) {
+        return 1;
+    }
+    return 0;
+}
diff --git a/challenge-099/roger-bell-west/rust/ch-2.rs b/challenge-099/roger-bell-west/rust/ch-2.rs
new file mode 100755
index 0000000000..3b6d74a105
--- /dev/null
+++ b/challenge-099/roger-bell-west/rust/ch-2.rs
@@ -0,0 +1,49 @@
+#! /bin/sh
+//usr/bin/env rustc --test $0 -o ${0}x && ./${0}x; rm -f ${0}x ; exit
+
+use std::collections::HashMap;
+
+#[test]
+fn test_ex1() {
+    assert_eq!(us("littleit","lit"),5);
+}
+
+#[test]
+fn test_ex2() {
+    assert_eq!(us("london","lon"),3);
+}
+
+fn us(text: &str,mat: &str) -> usize {
+    let mut s: HashMap<char,Vec<usize>>=HashMap::new();
+    for (i,c) in text.chars().enumerate() {
+        let mut sc: Vec<usize>=vec![];
+        if s.contains_key(&c) {
+            sc=s.get(&c).unwrap().to_vec();
+        }
+        sc.push(i);
+        s.insert(c,sc);
+    }
+    let mut j: Vec<Vec<usize>>=vec![];
+    for c in mat.chars() {
+        if s.contains_key(&c) {
+            j.push(s.get(&c).unwrap().to_vec());
+        } else {
+            return 0;
+        }
+    }
+    let mut o: Vec<usize>=vec![1; j[0].len()];
+    for m in 1..j.len() {
+        let mut n: Vec<usize>=vec![];
+        for bi in 0..j[m].len() {
+            let mut t: usize=0;
+            for ai in 0..j[m-1].len() {
+                if j[m-1][ai] < j[m][bi] {
+                    t += o[ai];
+                }
+            }
+            n.push(t);
+        }
+        o=n;
+    }
+    return o.iter().sum();
+}