Perl 6 solutions for task 1 and 2 of challenge 018 by Noud

2 files changed, 109 insertions, 0 deletions

diff --git a/challenge-018/noud/perl6/ch-1.p6 b/challenge-018/noud/perl6/ch-1.p6
new file mode 100644
index 0000000000..aefb42523d
--- /dev/null
+++ b/challenge-018/noud/perl6/ch-1.p6
@@ -0,0 +1,44 @@
+# Write a script that takes 2 or more strings as command line parameters and
+# print the longest common substring. For example, the longest common substring
+# of the strings “ABABC”, “BABCA” and “ABCBA” is string “ABC” of length 3.
+# Other common substrings are “A”, “AB”, “B”, “BA”, “BC” and “C”. Please check
+# this wiki page for details.
+
+
+# The subroutine finds the longest common substrings (could be more than one)
+# with dynamical programming. The algorithm runs in O(ij) time.
+sub lcs($s1, $s2) {
+    my $z = 0;
+    my @ret = ();
+    my @l[$s1.chars, $s2.chars];
+
+    for 0..($s1.chars - 1) -> $i {
+        for 0..($s2.chars - 1) -> $j {
+            @l[$i; $j] = 0;
+            if ($s1.comb[$i] === $s2.comb[$j]) {
+                if ($i == 0 || $j == 0) {
+                    @l[$i; $j] = 1;
+                } else {
+                    @l[$i; $j] = @l[$i-1; $j-1] + 1;
+                }
+
+                if (@l[$i; $j] > $z) {
+                    $z = @l[$i; $j];
+                    @ret = ($s1.substr($i - $z + 1, $z));
+                } elsif (@l[$i; $j] == $z) {
+                    @ret.append($s1.substr($i - $z + 1, $z));
+                }
+
+            }
+        }
+    }
+
+    return @ret;
+}
+
+
+multi MAIN('test') {
+    use Test;
+    is lcs("ababc", "babca"), <babc>;
+    is lcs("abac", "acab"), <ab ac>;
+}
diff --git a/challenge-018/noud/perl6/ch-2.p6 b/challenge-018/noud/perl6/ch-2.p6
new file mode 100644
index 0000000000..e86e866c3c
--- /dev/null
+++ b/challenge-018/noud/perl6/ch-2.p6
@@ -0,0 +1,65 @@
+# Write a script to implement Priority Queue. It is like regular queue except
+# each element has a priority associated with it. In a priority queue, an
+# element with high priority is served before an element with low priority.
+# Please check this wiki page for more informations. It should serve the
+# following operations:
+#
+#   1) is_empty: check whether the queue has no elements.
+#   2) insert_with_priority: add an element to the queue with an associated
+#      priority.
+#   3) pull_highest_priority_element: remove the element from the queue that
+#      has the highest priority, and return it. If two elements have the same
+#      priority, then return element added first.
+
+
+class PriorityQueue {
+    # The last element in the queue is always the element with the highest
+    # priority.
+    has @queue = [];
+
+    method is_empty {
+        return @queue.elems == 0;
+    }
+
+    method insert_with_priority($elm, $priority) {
+        # Find the priority index for the element in the queue. If no index
+        # can be found, the element has the lowest priority in the queue.
+        my @idx = @queue.grep(-> ($i, $j) { $i >= $priority }, :k);
+        if (@idx.elems == 0) {
+            @queue.push([$priority, $elm]);
+        } else {
+            my $i = @idx[0];
+            @queue = [|(@queue[^$i]), [$priority, $elm], |(@queue[$i..*-1])];
+        }
+    }
+
+    submethod pull_highest_priority_element() {
+        return @queue.pop()[1];
+    }
+}
+
+
+multi MAIN('test') {
+    use Test;
+
+    my $pqueue = PriorityQueue.new();
+    is $pqueue.is_empty(), True;
+
+    $pqueue.insert_with_priority(1, 1);
+    $pqueue.insert_with_priority(2, 2);
+    $pqueue.insert_with_priority(3, 2);
+    $pqueue.insert_with_priority(4, 1);
+    $pqueue.insert_with_priority(5, 0);
+    $pqueue.insert_with_priority(6, 2);
+    $pqueue.insert_with_priority(7, 0);
+
+    is $pqueue.is_empty(), False;
+    is $pqueue.pull_highest_priority_element(), 2;
+    is $pqueue.pull_highest_priority_element(), 3;
+    is $pqueue.pull_highest_priority_element(), 6;
+    is $pqueue.pull_highest_priority_element(), 1;
+    is $pqueue.pull_highest_priority_element(), 4;
+    is $pqueue.pull_highest_priority_element(), 5;
+    is $pqueue.pull_highest_priority_element(), 7;
+    is $pqueue.is_empty(), True;
+}