completed challenges

2 files changed, 164 insertions, 97 deletions

diff --git a/challenge-059/kevin-colyer/raku/ch-1.p6 b/challenge-059/kevin-colyer/raku/ch-1.p6
index c13cef6760..525a17b692 100644
--- a/challenge-059/kevin-colyer/raku/ch-1.p6
+++ b/challenge-059/kevin-colyer/raku/ch-1.p6
@@ -1,5 +1,6 @@
 #!perl6
 # Task 1 Challenge 059 Solution by kevincolyer
+
 use Test;
 #TASK #1 › Linked List
 #Reviewed by Ryan Thompson
@@ -17,118 +18,176 @@ use Test;
 #Expected Output: 1 → 2 → 2 → 4 → 3 → 5.
 #
 
-class SLLNode {
+class DLLNode {
     has Int $.value is rw;
-    has SLLNode $.next is rw;
+    has DLLNode $.next is rw;
+    has DLLNode $.prev is rw;
     method display {
-        return " -> " ~ $!value;
+        return " -> " ~ $.value;
     }
 }
 
 class LinkedList {
-    has SLLNODE $.head is rw;
-    has SLLNODE $.tail is rw;
-    has Int $.items;
+    has DLLNode $.head is rw;
+    has DLLNode $.tail is rw;
+    has Int $!items=0;
     
-    method is-tail(SLLNode $n) {
-        return $n==$tail;
+    method is-tail(DLLNode $n) {
+        return $n===$.tail;
     }
-
+    
+    method is-head(DLLNode $n) {
+        return $n===$.head;
+    }
+    
     method display {
-        return "Empty List" if $!items=0;
-        my $n = $!head;
-        my $s="($!items)|-> " ~ $n.value;
+        return "Empty List" if $!items==0;
+        my $n = $.head;
+        my $s="(Items $!items)|-> " ~ $n.value;
         while not self.is-tail($n) {
-            $n.=next;
-            $s~=" -> {$n.display}";
+            $n=$n.next;
+            $s~=$n.display;
         }
         return $s;
-        
     }
+    
     method add-to-tail($v) {
-        my $n= SLLNode.new(value=>$v);
-        if $!items==0 {
+        my $n= DLLNode.new(value=>$v);
+        $!items++;
+        if $!items==1 {
             self.head=$n;
             self.tail=$n;
-            $!items++;
             return;
         } 
-        self.tail.next=$n;
+        $n.prev=self.tail;
+        $n.prev.next=$n;
         self.tail=$n;
+    }
+
+    method add-to-head($v) {
+        my $n=DLLNode.new(value=>$v);
+        $!items++;
+        if $!items==0 {
+            self.head=$n;
+            self.tail=$n;
+            return;
+        }
+        self.head.prev=$n;
+        $n.next=self.head;
+        self.head=$n;
+    }
+
+    method add-after(DLLNode $n, Int $v) {
+        if self.is-tail($n) { self.add-to-tail($v); return };
+        my $i = DLLNode.new(value => $v);
+        $i.prev=$n;
+        $i.next=$n.next;
+        $i.next.prev=$i;
+        $n.next=$i;
         $!items++;
     }
+
+    method remove-node($n) {
+        return if $!items==0;
+        $!items--;
+        if $!items==0 {
+            self.head=Nil;
+            self.tail=Nil;
+            $n.prev=Nil;
+            $n.next=Nil;
+            return $n;
+        }
+        if self.is-head($n) {
+            self.head=$n.next;
+            self.head.prev=Nil;
+            $n.next=Nil;
+            return $n;
+        }
+        if self.is-tail($n) {
+            self.tail=$n.prev;
+            self.tail.next=Nil;
+            $n.prev=Nil;
+            return $n;
+        }
+        $n.prev.next=$n.next;
+        $n.next.prev=$n.prev;
+        $n.next=Nil;
+        $n.prev=Nil;
+        return $n;
+    }
+    
+    method partioned-sort(Int $k) {
+        # search for k
+        # from k onwards
+        # skip if >=
+        # otherwise search from root, place asap
+        my DLLNode $n = self.head;
+        loop {
+            last if $n.value==$k;
+            die "[$k] not found in list" if self.is-tail($n);
+            $n=$n.next;
+        }
+        die "[$k] is end of list already" if self.is-tail($n);
+
+        $n.=next;
+        my $next=$n;
+        loop {
+            $next=$n.next;
+            if $n.value <= $k {
+                $n = self.remove-node($n);
+                my $i=self.head;
+                $i.=next while $i.value < $n.value;
+                self.add-after($i.prev,$n.value);
+            }
+            last unless $next.defined;
+            $n=$next;
+        }
+    }
 }
 
 my  $ll = LinkedList.new;
-say $ll.display;
+is $ll.display,"Empty List","test empty";
+$ll.add-to-tail(1);
+is $ll.display,"(Items 1)|-> 1","test add to tail";
+$ll.add-to-tail(2);
+is $ll.display,"(Items 2)|-> 1 -> 2","test add to tail";
+$ll.add-to-tail(3);
+is $ll.display,"(Items 3)|-> 1 -> 2 -> 3","test add to tail";
+$ll.add-to-head(0);
+is $ll.display,"(Items 4)|-> 0 -> 1 -> 2 -> 3","test add to head";
+
+my $h = $ll.head;
+my $t = $ll.tail;
+$ll.remove-node($t);
+is $ll.display,"(Items 3)|-> 0 -> 1 -> 2","test tail remove";
+$ll.remove-node($h);
+is $ll.display,"(Items 2)|-> 1 -> 2","test head remove";
+
+$h = $ll.head;
+$t = $ll.tail;
+$ll.remove-node($t);
+is $ll.display,"(Items 1)|-> 1","test tail remove";
+$ll.remove-node($h);
+is $ll.display,"Empty List","test head remove";
+
+$ll.add-to-tail(1);
+$ll.add-to-tail(4);
+$h=$ll.head;
+$t=$ll.tail;
+$ll.add-after($h,0);
+is $ll.display,"(Items 3)|-> 1 -> 0 -> 4","test add after";
+$ll.add-after($t,0);
+is $ll.display,"(Items 4)|-> 1 -> 0 -> 4 -> 0","test add after";
+$ll.remove-node($ll.tail);
+$ll.remove-node($ll.tail);
+$ll.remove-node($ll.tail);
+$ll.remove-node($ll.tail);
 
+$ll.add-to-tail($_) for 1, 4, 3, 2, 5, 2;
+is $ll.display,"(Items 6)|-> 1 -> 4 -> 3 -> 2 -> 5 -> 2","before partitioned sort";
 
+diag "partitioning by k=3";
+$ll.partioned-sort(3);
+is $ll.display,"(Items 6)|-> 1 -> 2 -> 2 -> 4 -> 3 -> 5","after partitioned sort";
 
-# is $ExampleList.value, 1, "value is 1";
-# is $ExampleList.is-tail, True, "At end of list";
-# $ExampleList.next = LinkedList.new(value => 4);
-# is $ExampleList.is-tail, False, "Not at end of list";
-# say $ExampleList.display;
-# 
-# $ExampleList.next.next = LinkedList.new(value => 3);
-# $ExampleList.next.next.next = LinkedList.new(value => 2);
-# $ExampleList.next.next.next.next = LinkedList.new(value => 5);
-# $ExampleList.next.next.next.next.next = LinkedList.new(value => 2);
-# $ExampleList.next.next.next.next.next.next = LinkedList.new(value => 0);
-# say $ExampleList.display;
-# 
-# # search for k
-# # from k onwards
-# # skip if >=
-# # otherwise search from root, place asap
-# 
-# my $n = $ExampleList;
-# my $k=3;
-# my $kn= $ExampleList;
-# 
-# loop {
-#     if $n.value==$k {
-#         $kn=$n;
-#         last;
-#     }
-#     die "[$k] not found in list" if $n.is-tail;
-#     $n=$n.next;
-# }
-# die "[$k] is end of list already" if $kn.is-tail;
-# 
-# my $prev=$n;
-# $n=$kn.next;
-# say $n.display;
-# 
-# loop {
-#     my $next=$n.next;
-#     say "n value is {$n.value}";
-#     if $n.value < $k {
-#         $prev.next=$next; # snip $n out of list
-#         say $ExampleList.display;
-#         my $search= $ExampleList; # search from beginning
-#         my $searchPrev= $ExampleList;
-#         if $search.value <= $n.value {
-#             $n.next=$ExampleList;
-#             $ExampleList=$n;
-#             $n=$next;
-#             next;
-#         } 
-#         while  $search.value < $n.value {
-#             say "searching for >={$n.value} got {$search.value}";
-#             $searchPrev=$search;
-#             $search=$searchPrev.next;
-#         }
-#         say "got {$search.value} inserting before {$searchPrev.value}";
-#         $searchPrev.next=$n; # reconnect into list
-#         $n.next=$search;
-#         say $ExampleList.display;
-#         # continue loop
-#         $n=$next;
-#         last if $prev.is-tail;
-#         next;
-#     }
-#     $prev=$n;
-#     $n=$next;
-#     last if $prev.is-tail;
-# }
+done-testing;
diff --git a/challenge-059/kevin-colyer/raku/ch-2.p6 b/challenge-059/kevin-colyer/raku/ch-2.p6
index 641a6c11f0..714aae9d07 100644
--- a/challenge-059/kevin-colyer/raku/ch-2.p6
+++ b/challenge-059/kevin-colyer/raku/ch-2.p6
@@ -20,7 +20,12 @@
 #For example, given 2, 3, 4, the output would be 6, since f(2,3) + f(2,4) + f(3,4) = 1 + 2 + 3 = 6
 
 # F XORs bits then counts them by mask of bit one, shifts left, ends when empty
-sub f(Int $a, Int $b) {
+
+use Test;
+
+subset PosInt of Int where * >=0 ;
+
+sub f(PosInt $a, PosInt $b) {
     my Int $count=0;
     my Int $bits = $a +^ $b;
     while $bits>0 {
@@ -30,15 +35,18 @@ sub f(Int $a, Int $b) {
     return $count;
 }
 
-is f(1,3),1,"example";
-is f(2,3),1,"example 2";
-is f(2,4),2,"example 2";
-is f(4,3),3,"example 2";
-is f(2,3)+f(2,4)+f(3,4),6,"example 2";
-
-# accept n pos ints and add them...
-sub MAIN(+@n) {
+multi MAIN('test') {
+    is f(1,3),1,"example";
+    is f(2,3),1,"example 2";
+    is f(2,4),2,"example 2";
+    is f(4,3),3,"example 2";
+    is f(2,3)+f(2,4)+f(3,4),6,"example 2";
+}
 
+#|Sum the different bits of pairs of positive ints...
+multi MAIN(+@n) {
+    die "Need pairs of numbers, got {@n.elems}" unless @n %% 2 && @n.elems > 0;
+    say [+] gather for @n -> $a,$b { take f($a,$b) };
 }
 
 # http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel