From 4c48d691c43e6ee2af4f89c690fb228d5ecd8947 Mon Sep 17 00:00:00 2001 From: kevincolyer <> Date: Sat, 9 May 2020 16:49:48 +0100 Subject: ch 2 done. Refactoring ch 1 --- challenge-059/kevin-colyer/raku/ch-1.p6 | 106 ++++++++++++++++++++++++++++++++ challenge-059/kevin-colyer/raku/ch-2.p6 | 51 +++++++++++++++ 2 files changed, 157 insertions(+) create mode 100644 challenge-059/kevin-colyer/raku/ch-1.p6 create mode 100644 challenge-059/kevin-colyer/raku/ch-2.p6 (limited to 'challenge-059') diff --git a/challenge-059/kevin-colyer/raku/ch-1.p6 b/challenge-059/kevin-colyer/raku/ch-1.p6 new file mode 100644 index 0000000000..970770e46d --- /dev/null +++ b/challenge-059/kevin-colyer/raku/ch-1.p6 @@ -0,0 +1,106 @@ +#!perl6 +# Task 1 Challenge 059 Solution by kevincolyer +use Test; +#TASK #1 › Linked List +#Reviewed by Ryan Thompson +#You are given a linked list and a value k. +# Write a script to partition the linked list such that all nodes less than k +# come before nodes greater than or equal to k. +# Make sure you preserve the original relative order of the nodes in each of the two partitions. +# +#For example: +# +#Linked List: 1 → 4 → 3 → 2 → 5 → 2 +# +#k = 3 +# +#Expected Output: 1 → 2 → 2 → 4 → 3 → 5. +# + + + +class LinkedList { + has Int $.value; + has LinkedList $.next is rw; + # has LinkedList $.prev is rw; + method is-tail { + return $!next.defined ?? False !! True; + } + method display { + my $s = " -> " ~ $!value; + if self.is-tail { return $s }; + return $s ~ self.next.display; + } +} + +my $ExampleList = LinkedList.new(value => 1); + +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; +} +say $ExampleList.display; diff --git a/challenge-059/kevin-colyer/raku/ch-2.p6 b/challenge-059/kevin-colyer/raku/ch-2.p6 new file mode 100644 index 0000000000..641a6c11f0 --- /dev/null +++ b/challenge-059/kevin-colyer/raku/ch-2.p6 @@ -0,0 +1,51 @@ +#!perl6 +# Task 2 Challenge 059 Solution by kevincolyer + +#TASK #2 › Bit Sum +#Reviewed by Ryan Thompson +#Helper Function +#For this task, you will most likely need a function f(a,b) which returns the count of different bits of binary representation of a and b. +# +#For example, f(1,3) = 1, since: +# +#Binary representation of 1 = 01 +# +#Binary representation of 3 = 11 +# +#There is only 1 different bit. Therefore the subroutine should return 1. Note that if one number is longer than the other in binary, the most significant bits of the smaller number are padded (i.e., they are assumed to be zeroes). +# +#Script Output +#You script should accept n positive numbers. Your script should sum the result of f(a,b) for every pair of numbers given: +# +#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) { + my Int $count=0; + my Int $bits = $a +^ $b; + while $bits>0 { + $count+= $bits +& 1; + $bits=$bits +> 1; + } + 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) { + +} + +# http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel +# faster solution +# for 32 bits +# c = (v & 0x55555555) + ((v >> 1) & 0x55555555); +# c = (c & 0x33333333) + ((c >> 2) & 0x33333333); +# c = (c & 0x0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F); +# c = (c & 0x00FF00FF) + ((c >> 8) & 0x00FF00FF); +# c = (c & 0x0000FFFF) + ((c >> 16)& 0x0000FFFF); -- cgit From 97eed38d949d36fe7277adcbaddc40e2dc205f56 Mon Sep 17 00:00:00 2001 From: kevincolyer <> Date: Sat, 9 May 2020 17:06:20 +0100 Subject: ch 2 done. Refactoring ch 1 --- challenge-059/kevin-colyer/raku/ch-1.p6 | 182 ++++++++++++++++++-------------- 1 file changed, 105 insertions(+), 77 deletions(-) (limited to 'challenge-059') diff --git a/challenge-059/kevin-colyer/raku/ch-1.p6 b/challenge-059/kevin-colyer/raku/ch-1.p6 index 970770e46d..c13cef6760 100644 --- a/challenge-059/kevin-colyer/raku/ch-1.p6 +++ b/challenge-059/kevin-colyer/raku/ch-1.p6 @@ -17,90 +17,118 @@ use Test; #Expected Output: 1 → 2 → 2 → 4 → 3 → 5. # - +class SLLNode { + has Int $.value is rw; + has SLLNode $.next is rw; + method display { + return " -> " ~ $!value; + } +} class LinkedList { - has Int $.value; - has LinkedList $.next is rw; - # has LinkedList $.prev is rw; - method is-tail { - return $!next.defined ?? False !! True; + has SLLNODE $.head is rw; + has SLLNODE $.tail is rw; + has Int $.items; + + method is-tail(SLLNode $n) { + return $n==$tail; } + method display { - my $s = " -> " ~ $!value; - if self.is-tail { return $s }; - return $s ~ self.next.display; + return "Empty List" if $!items=0; + my $n = $!head; + my $s="($!items)|-> " ~ $n.value; + while not self.is-tail($n) { + $n.=next; + $s~=" -> {$n.display}"; + } + return $s; + + } + method add-to-tail($v) { + my $n= SLLNode.new(value=>$v); + if $!items==0 { + self.head=$n; + self.tail=$n; + $!items++; + return; + } + self.tail.next=$n; + self.tail=$n; + $!items++; } } -my $ExampleList = LinkedList.new(value => 1); - -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; +my $ll = LinkedList.new; +say $ll.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; -} -say $ExampleList.display; +# 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; +# } -- cgit From 9b6de2b84e296d308e08f8be46c015e56961523e Mon Sep 17 00:00:00 2001 From: kevincolyer <> Date: Sun, 10 May 2020 21:36:32 +0100 Subject: completed challenges --- challenge-059/kevin-colyer/raku/ch-1.p6 | 235 ++++++++++++++++++++------------ challenge-059/kevin-colyer/raku/ch-2.p6 | 26 ++-- 2 files changed, 164 insertions(+), 97 deletions(-) (limited to 'challenge-059') 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 -- cgit From 99c837a63be70a11c042b99dc5ed546035593aee Mon Sep 17 00:00:00 2001 From: kevincolyer <> Date: Sun, 10 May 2020 21:37:39 +0100 Subject: Challenge-059 solutions by kevincolyer --- challenge-059/kevincolyer | 1 + 1 file changed, 1 insertion(+) create mode 120000 challenge-059/kevincolyer (limited to 'challenge-059') diff --git a/challenge-059/kevincolyer b/challenge-059/kevincolyer new file mode 120000 index 0000000000..8fc47c15c2 --- /dev/null +++ b/challenge-059/kevincolyer @@ -0,0 +1 @@ +kevin-colyer \ No newline at end of file -- cgit