From 7180e1d1ddc515c9bba7e6083c8d84ca1879117a Mon Sep 17 00:00:00 2001
From: Roger Bell_West <roger@firedrake.org>
Date: Mon, 22 Jul 2019 05:41:25 +0100
Subject: Solutions to #18

---
 challenge-018/roger-bell-west/perl5/1.pl | 51 +++++++++++++++++++++++++++++++
 challenge-018/roger-bell-west/perl5/2.pl | 52 ++++++++++++++++++++++++++++++++
 2 files changed, 103 insertions(+)
 create mode 100755 challenge-018/roger-bell-west/perl5/1.pl
 create mode 100755 challenge-018/roger-bell-west/perl5/2.pl

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..7d6f3a92f5
--- /dev/null
+++ b/challenge-018/roger-bell-west/perl5/1.pl
@@ -0,0 +1,51 @@
+#! /usr/bin/perl
+
+use strict;
+use warnings;
+
+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);
+    }
+    @a=sort 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;
+}
-- 
cgit 


From 4c9f9b62170ec501a27c753b49e0b0f54b732782 Mon Sep 17 00:00:00 2001
From: Roger Bell_West <roger@firedrake.org>
Date: Mon, 22 Jul 2019 06:11:30 +0100
Subject: Oops.

---
 challenge-018/roger-bell-west/perl5/1.pl | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/challenge-018/roger-bell-west/perl5/1.pl b/challenge-018/roger-bell-west/perl5/1.pl
index 7d6f3a92f5..7e952a9cdd 100755
--- a/challenge-018/roger-bell-west/perl5/1.pl
+++ b/challenge-018/roger-bell-west/perl5/1.pl
@@ -3,6 +3,8 @@
 use strict;
 use warnings;
 
+use List::Util qw(max);
+
 print map {"$_\n"} lcsubstr(@ARGV);
 
 sub lcsubstr {
@@ -17,7 +19,8 @@ sub lcsubstr {
     foreach my $a (@a) {
       map {$b{$_}=1} lcsubstr2($a,$c);
     }
-    @a=sort keys %b;
+    my $m=max(map {length($_)} keys %b);
+    @a=sort grep {length($_)==$m} keys %b;
   }
   return @a;
 }
-- 
cgit