challeng 018 perl6 solutions

2 files changed, 113 insertions, 0 deletions

diff --git a/challenge-018/feng-chang/perl6/ch-1.p6 b/challenge-018/feng-chang/perl6/ch-1.p6
new file mode 100755
index 0000000000..6fd9fa9280
--- /dev/null
+++ b/challenge-018/feng-chang/perl6/ch-1.p6
@@ -0,0 +1,40 @@
+#!/bin/env perl6
+
+use Test;
+plan 3;
+
+# Longest Common String
+sub infix:<LCS>(Str:D $s, Str:D $t --> Str) {
+    my Str @S = $s.comb;
+    my Str @T = $t.comb;
+    my UInt @L[$s.chars, $t.chars];
+    my UInt $z = 0;
+    my Str @ret = ();
+
+    for 0..^$s.chars -> $i {
+        for 0..^$t.chars -> $j {
+            if @S[$i] eq @T[$j] {
+                if $i == 0 or $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 = @S[$i-$z+1 .. $i].join;
+                } elsif @L[$i; $j] == $z {
+                    @ret.push(@S[$i-$z+1 .. $i].join);
+                }
+            } else {
+                @L[$i; $j] = 0;
+            }
+        }
+    }
+
+    return @ret.join;
+}
+
+is 'BABC', 'ABABC' LCS 'BABCA', "LCS('ABABC', 'BABCA') => 'BABC'";
+is 'ABC',  'BABCA' LCS 'ABCBA', "LCS('BABCA', 'ABCBA') => 'ABC'";
+is 'ABC',  ([LCS] <ABABC BABCA ABCBA>.flat), "LCS('ABABC', 'BABCA', 'ABCBA') => 'ABC'";
diff --git a/challenge-018/feng-chang/perl6/ch-2.p6 b/challenge-018/feng-chang/perl6/ch-2.p6
new file mode 100755
index 0000000000..f8fcc687ac
--- /dev/null
+++ b/challenge-018/feng-chang/perl6/ch-2.p6
@@ -0,0 +1,73 @@
+#!/bin/env perl6
+
+class task {
+    has UInt $.priority;
+    has Str  $.id;
+}
+
+class PriorityQueue {
+    has UInt @!priorities;      # keep sorted
+    has      %!queue{ UInt };   # UInt => task array
+
+    submethod BUILD() {
+        @!priorities = ();
+        %!queue      = %();
+    }
+
+    method is_empty(--> Bool) { %!queue.elems == 0 }
+
+    method add-new-task(UInt:D $priority, task:D $task) {
+        my UInt $start = 0;
+        my UInt $end   = max(0, @!priorities.elems - 1);
+
+        while ($end - $start > 1) {
+            my UInt $index = ($start + $end) / 2;
+
+            if $priority < @!priorities[$index] {
+                $start = $index;
+            } elsif $priority > @!priorities[$index] {
+                $end = $index;
+            } else { # $priority == @!priorities[$index]
+                %!queue{ $priority }.push($task);
+            }
+        }
+
+        put("end - start should be 0 or 1: { $end - $start }");
+        @!priorities.splice($start, 0, [$priority]);
+        %!queue{ $priority } = [$task];
+    }
+
+    method insert-with-priority(UInt:D $priority, Str:D $task-id) {
+        my $new-task = task.new(priority => $priority, id => $task-id);
+        self.add-new-task($priority, $new-task);
+    }
+
+    method pull-highest-priority-element() {
+        return Nil if %!queue.elems == 0;
+
+        my $t = %!queue{ @!priorities[0] }.pop;
+        if %!queue{ @!priorities[0] }.elems == 0 {
+            %!queue{ @!priorities[0] }:delete;
+            @!priorities.pop;
+        }
+        return $t;
+    }
+
+    method elems { [@!priorities.elems, %!queue.elems] }
+}
+
+use Test;
+plan 5;
+
+my PriorityQueue $que = PriorityQueue.new;
+
+is True, $que.is_empty, 'default queue is empty';
+
+$que.insert-with-priority(3, 'task one');
+is [1, 1], $que.elems, 'task queue length is 1 after 1 insertion';
+
+my $t = $que.pull-highest-priority-element;
+is 3, $t.priority, 'task priority is 3';
+is 'task one', $t.id, 'task is correct';
+
+is [0, 0], $que.elems, 'task queue length is 0 after element is pulled';