Merge pull request #412 from Firedrake/rogerbw-challenge-018

Solutions to #18

2 files changed, 106 insertions, 0 deletions

diff --git a/challenge-018/roger-bell-west/perl5/1.pl b/challenge-018/roger-bell-west/perl5/1.pl
new file mode 100755
index 0000000000..7e952a9cdd
--- /dev/null
+++ b/challenge-018/roger-bell-west/perl5/1.pl
@@ -0,0 +1,54 @@
+#! /usr/bin/perl
+
+use strict;
+use warnings;
+
+use List::Util qw(max);
+
+print map {"$_\n"} lcsubstr(@ARGV);
+
+sub lcsubstr {
+  my @str=@_;
+  if (scalar @str < 2) {
+    return @str;
+  }
+  my @a=lcsubstr2(shift @str,shift @str);
+  while (@str) {
+    my %b;
+    my $c=shift @str;
+    foreach my $a (@a) {
+      map {$b{$_}=1} lcsubstr2($a,$c);
+    }
+    my $m=max(map {length($_)} keys %b);
+    @a=sort grep {length($_)==$m} keys %b;
+  }
+  return @a;
+}
+
+# don't use this, use String::LCSS_XS instead
+sub lcsubstr2 { # https://en.wikipedia.org/wiki/Longest_common_substring_problem#Pseudocode
+  my @s=split '',shift;
+  my @t=split '',shift;
+  my %l;
+  my $z=0;
+  my @ret;
+  foreach my $si (0..$#s) {
+    foreach my $ti (0..$#t) {
+      if ($s[$si] eq $t[$ti]) {
+        if ($si==0 || $ti==0) {
+          $l{$si}{$ti}=1;
+        } else {
+          $l{$si}{$ti}=($l{$si-1}{$ti-1} || 0)+1;
+        }
+        if ($l{$si}{$ti} > $z) {
+          $z=$l{$si}{$ti};
+          @ret=();
+        }
+        if ($l{$si}{$ti} == $z) {
+          push @ret,join('',@s[$si-$z+1..$si]);
+        }
+      }
+    }
+  }
+  return @ret;
+}
diff --git a/challenge-018/roger-bell-west/perl5/2.pl b/challenge-018/roger-bell-west/perl5/2.pl
new file mode 100755
index 0000000000..59aae2cd5a
--- /dev/null
+++ b/challenge-018/roger-bell-west/perl5/2.pl
@@ -0,0 +1,52 @@
+#! /usr/bin/perl
+
+use strict;
+use warnings;
+
+my $q=Local::PriorityQueue->new;
+$q->insert_with_priority(4,1);
+$q->insert_with_priority(3,2);
+$q->insert_with_priority(1,3);
+$q->insert_with_priority(2,3);
+$q->insert_with_priority(5,0);
+while (!$q->is_empty) {
+  print $q->pull_highest_priority_element,"\n";
+}
+
+package Local::PriorityQueue;
+use List::Util qw(max);
+
+sub new {
+  my $class = shift;
+  my $self={};
+  bless $self,$class;
+  return $self;
+}
+
+sub is_empty {
+  my $self=shift;
+  if (scalar keys %{$self}) {
+    return 0;
+  }
+  return 1;
+}
+
+sub insert_with_priority {
+  my $self=shift;
+  my $element=shift;
+  my $priority=shift;
+  push @{$self->{$priority}},$element;
+}
+
+sub pull_highest_priority_element {
+  my $self=shift;
+  if ($self->is_empty) {
+    return undef;
+  }
+  my $prio=max(keys %{$self});
+  my $element=shift @{$self->{$prio}};
+  if (scalar @{$self->{$prio}}==0) {
+    delete $self->{$prio};
+  }
+  return $element;
+}