aboutsummaryrefslogtreecommitdiff
path: root/challenge-145
diff options
context:
space:
mode:
Diffstat (limited to 'challenge-145')
-rw-r--r--challenge-145/roger-bell-west/kotlin/ch-1.kt15
-rw-r--r--challenge-145/roger-bell-west/kotlin/ch-2.kt173
-rwxr-xr-xchallenge-145/roger-bell-west/lua/ch-1.lua16
-rwxr-xr-xchallenge-145/roger-bell-west/lua/ch-2.lua87
-rwxr-xr-xchallenge-145/roger-bell-west/perl/ch-1.pl18
-rwxr-xr-xchallenge-145/roger-bell-west/perl/ch-2.pl143
-rw-r--r--challenge-145/roger-bell-west/postscript/ch-1.ps13
-rw-r--r--challenge-145/roger-bell-west/postscript/ch-2.ps124
-rwxr-xr-xchallenge-145/roger-bell-west/python/ch-1.py16
-rwxr-xr-xchallenge-145/roger-bell-west/python/ch-2.py133
-rwxr-xr-xchallenge-145/roger-bell-west/raku/ch-1.p614
-rwxr-xr-xchallenge-145/roger-bell-west/raku/ch-2.p6136
-rwxr-xr-xchallenge-145/roger-bell-west/ruby/ch-1.rb19
-rwxr-xr-xchallenge-145/roger-bell-west/ruby/ch-2.rb140
-rwxr-xr-xchallenge-145/roger-bell-west/rust/ch-1.rs16
-rwxr-xr-xchallenge-145/roger-bell-west/rust/ch-2.rs58
16 files changed, 1121 insertions, 0 deletions
diff --git a/challenge-145/roger-bell-west/kotlin/ch-1.kt b/challenge-145/roger-bell-west/kotlin/ch-1.kt
new file mode 100644
index 0000000000..db7c547160
--- /dev/null
+++ b/challenge-145/roger-bell-west/kotlin/ch-1.kt
@@ -0,0 +1,15 @@
+fun dotproduct(a: List<Int>,b: List<Int>): Int {
+ var p: Int=0
+ for ((i,v) in a.withIndex()) {
+ p += v * b[i]
+ }
+ return p
+}
+
+fun main() {
+ if (dotproduct(listOf<Int>(1,2,3),listOf<Int>(4,5,6)) == 32) {
+ println("Pass")
+ } else {
+ println("FAIL")
+ }
+}
diff --git a/challenge-145/roger-bell-west/kotlin/ch-2.kt b/challenge-145/roger-bell-west/kotlin/ch-2.kt
new file mode 100644
index 0000000000..4f5debdae3
--- /dev/null
+++ b/challenge-145/roger-bell-west/kotlin/ch-2.kt
@@ -0,0 +1,173 @@
+// Very lightly modified from https://rosettacode.org/wiki/Eertree#Kotlin
+// by "PureFox"
+
+class Eernode {
+ val edges = mutableMapOf<Char, Eernode>() // edges (or forward links)
+ var link: Eernode? = null // suffix link (backward links)
+ var len = 0 // the length of the node
+}
+
+class Eertree(str: String) {
+ val nodes = mutableListOf<Eernode>()
+
+ private val rto = Eernode() // odd length root node, or node -1
+ private val rte = Eernode() // even length root node, or node 0
+ private val s = StringBuilder("0") // accumulated input string, T = S[1..i]
+ private var maxSufT = rte // maximum suffix of tree T
+
+ init {
+ // Initialize and build the tree
+ rte.link = rto
+ rto.link = rte
+ rto.len = -1
+ rte.len = 0
+ for (ch in str) add(ch)
+ }
+
+ private fun getMaxSuffixPal(startEernode: Eernode, a: Char): Eernode {
+ // We traverse the suffix-palindromes of T in the order of decreasing length.
+ // For each palindrome we read its length k and compare T[i-k] against a
+ // until we get an equality or arrive at the -1 node.
+ var u = startEernode
+ val i = s.length
+ var k = u.len
+ while (u !== rto && s[i - k - 1] != a) {
+ if (u === u.link!!) throw RuntimeException("Infinite loop detected")
+ u = u.link!!
+ k = u.len
+ }
+ return u
+ }
+
+ private fun add(a: Char): Boolean {
+ // We need to find the maximum suffix-palindrome P of Ta
+ // Start by finding maximum suffix-palindrome Q of T.
+ // To do this, we traverse the suffix-palindromes of T
+ // in the order of decreasing length, starting with maxSuf(T)
+ val q = getMaxSuffixPal(maxSufT, a)
+
+ // We check Q to see whether it has an outgoing edge labeled by a.
+ val createANewEernode = a !in q.edges.keys
+
+ if (createANewEernode) {
+ // We create the node P of length Q + 2
+ val p = Eernode()
+ nodes.add(p)
+ p.len = q.len + 2
+ if (p.len == 1) {
+ // if P = a, create the suffix link (P, 0)
+ p.link = rte
+ }
+ else {
+ // It remains to create the suffix link from P if |P|>1. Just
+ // continue traversing suffix-palindromes of T starting with the
+ // the suffix link of Q.
+ p.link = getMaxSuffixPal(q.link!!, a).edges[a]
+ }
+
+ // create the edge (Q, P)
+ q.edges[a] = p
+ }
+
+ // P becomes the new maxSufT
+ maxSufT = q.edges[a]!!
+
+ // Store accumulated input string
+ s.append(a)
+
+ return createANewEernode
+ }
+
+ fun getSubPalindromes(): List<String> {
+ // Traverse tree to find sub-palindromes
+ val result = mutableListOf<String>()
+ // Odd length words
+ getSubPalindromes(rto, listOf(rto), "", result)
+ // Even length words
+ getSubPalindromes(rte, listOf(rte), "", result)
+ return result
+ }
+
+ private fun getSubPalindromes(nd: Eernode, nodesToHere: List<Eernode>,
+ charsToHere: String, result: MutableList<String>) {
+ // Each node represents a palindrome, which can be reconstructed
+ // by the path from the root node to each non-root node.
+
+ // Traverse all edges, since they represent other palindromes
+ for ((lnkName, nd2) in nd.edges) {
+ getSubPalindromes(nd2, nodesToHere + nd2, charsToHere + lnkName, result)
+ }
+
+ // Reconstruct based on charsToHere characters.
+ if (nd !== rto && nd !== rte) { // Don't print for root nodes
+ val assembled = charsToHere.reversed() +
+ if (nodesToHere[0] === rte) // Even string
+ charsToHere
+ else // Odd string
+ charsToHere.drop(1)
+ result.add(assembled)
+ }
+ }
+}
+
+fun eertree(st: String): ArrayList<String> {
+ val eertree=Eertree(st)
+ val result = eertree.getSubPalindromes()
+ var q=result.toMutableSet()
+ var res=ArrayList<String>()
+ for (i in 0..st.length-1) {
+ for (j in i..st.length-1) {
+ val k=st.slice(i..j)
+ if (q.contains(k)) {
+ res.add(k)
+ q.remove(k)
+ }
+ }
+ }
+ return res
+}
+
+fun main() {
+ if(eertree("redivider") == listOf("r","redivider","e","edivide","d","divid","i","ivi","v")) {
+ print("Pass")
+ } else {
+ print("FAIL")
+ }
+ print(" ")
+
+ if(eertree("deific") == listOf("d","e","i","ifi","f","c")) {
+ print("Pass")
+ } else {
+ print("FAIL")
+ }
+ print(" ")
+
+ if(eertree("rotors") == listOf("r","rotor","o","oto","t","s")) {
+ print("Pass")
+ } else {
+ print("FAIL")
+ }
+ print(" ")
+
+ if(eertree("challenge") == listOf("c","h","a","l","ll","e","n","g")) {
+ print("Pass")
+ } else {
+ print("FAIL")
+ }
+ print(" ")
+
+ if(eertree("champion") == listOf("c","h","a","m","p","i","o","n")) {
+ print("Pass")
+ } else {
+ print("FAIL")
+ }
+ print(" ")
+
+ if(eertree("christmas") == listOf("c","h","r","i","s","t","m","a")) {
+ print("Pass")
+ } else {
+ print("FAIL")
+ }
+ println("")
+
+}
diff --git a/challenge-145/roger-bell-west/lua/ch-1.lua b/challenge-145/roger-bell-west/lua/ch-1.lua
new file mode 100755
index 0000000000..e6ce731c02
--- /dev/null
+++ b/challenge-145/roger-bell-west/lua/ch-1.lua
@@ -0,0 +1,16 @@
+#! /usr/bin/lua
+
+function dotproduct(a,b)
+ p=0
+ for k1,v1 in pairs(a) do
+ p = p + v1 * b[k1]
+ end
+ return p
+end
+
+if (dotproduct({1,2,3},{4,5,6}) == 32) then
+ io.write("Pass")
+else
+ io.write("FAIL")
+end
+print("")
diff --git a/challenge-145/roger-bell-west/lua/ch-2.lua b/challenge-145/roger-bell-west/lua/ch-2.lua
new file mode 100755
index 0000000000..f12b3797a2
--- /dev/null
+++ b/challenge-145/roger-bell-west/lua/ch-2.lua
@@ -0,0 +1,87 @@
+#! /usr/bin/lua
+
+-- by Michael Anderson at
+-- https://stackoverflow.com/questions/8722620/comparing-two-index-tables-by-index-value-in-lua
+function recursive_compare(t1,t2)
+ -- Use usual comparison first.
+ if t1==t2 then return true end
+ -- We only support non-default behavior for tables
+ if (type(t1)~="table") then return false end
+ -- They better have the same metatables
+ local mt1 = getmetatable(t1)
+ local mt2 = getmetatable(t2)
+ if( not recursive_compare(mt1,mt2) ) then return false end
+
+ -- Check each key-value pair
+ -- We have to do this both ways in case we miss some.
+ -- TODO: Could probably be smarter and not check those we've
+ -- already checked though!
+ for k1,v1 in pairs(t1) do
+ local v2 = t2[k1]
+ if( not recursive_compare(v1,v2) ) then return false end
+ end
+ for k2,v2 in pairs(t2) do
+ local v1 = t1[k2]
+ if( not recursive_compare(v1,v2) ) then return false end
+ end
+
+ return true
+end
+
+function eertree(str)
+ pal={}
+ q={}
+ for i = 1,#str do
+ for j = i,#str do
+ strpal=string.sub(str,i,j)
+ strrev=string.reverse(strpal)
+ if strpal == strrev and q[strpal] == nil then
+ table.insert(pal,strpal)
+ q[strpal]=true
+ end
+ end
+ end
+ return pal
+end
+
+if recursive_compare(eertree("redivider"),{"r","redivider","e","edivide","d","divid","i","ivi","v"}) then
+ io.write("Pass")
+else
+ io.write("FAIL")
+end
+io.write(" ")
+
+if recursive_compare(eertree("deific"),{"d","e","i","ifi","f","c"}) then
+ io.write("Pass")
+else
+ io.write("FAIL")
+end
+io.write(" ")
+
+if recursive_compare(eertree("rotors"),{"r","rotor","o","oto","t","s"}) then
+ io.write("Pass")
+else
+ io.write("FAIL")
+end
+io.write(" ")
+
+if recursive_compare(eertree("challenge"),{"c","h","a","l","ll","e","n","g"}) then
+ io.write("Pass")
+else
+ io.write("FAIL")
+end
+io.write(" ")
+
+if recursive_compare(eertree("champion"),{"c","h","a","m","p","i","o","n"}) then
+ io.write("Pass")
+else
+ io.write("FAIL")
+end
+io.write(" ")
+
+if recursive_compare(eertree("christmas"),{"c","h","r","i","s","t","m","a"}) then
+ io.write("Pass")
+else
+ io.write("FAIL")
+end
+print("")
diff --git a/challenge-145/roger-bell-west/perl/ch-1.pl b/challenge-145/roger-bell-west/perl/ch-1.pl
new file mode 100755
index 0000000000..7c200af188
--- /dev/null
+++ b/challenge-145/roger-bell-west/perl/ch-1.pl
@@ -0,0 +1,18 @@
+#! /usr/bin/perl
+
+use strict;
+use warnings;
+
+use Test::More tests => 1;
+
+is(dotproduct([1,2,3],[4,5,6]),32,'example 1');
+
+sub dotproduct {
+ my $a=shift;
+ my $b=shift;
+ my $p=0;
+ foreach my $i (0..$#{$a}) {
+ $p += $a->[$i]*$b->[$i];
+ }
+ return $p;
+}
diff --git a/challenge-145/roger-bell-west/perl/ch-2.pl b/challenge-145/roger-bell-west/perl/ch-2.pl
new file mode 100755
index 0000000000..472dac313e
--- /dev/null
+++ b/challenge-145/roger-bell-west/perl/ch-2.pl
@@ -0,0 +1,143 @@
+#! /usr/bin/perl
+
+use strict;
+use warnings;
+
+use Test::More tests => 6;
+
+is_deeply(eertree('redivider'),[qw(r redivider e edivide d divid i ivi v)],'example 1');
+is_deeply(eertree('deific'),[qw(d e i ifi f c)],'example 2');
+is_deeply(eertree('rotors'),[qw(r rotor o oto t s)],'example 3');
+is_deeply(eertree('challenge'),[qw(c h a l ll e n g)],'example 4');
+is_deeply(eertree('champion'),[qw(c h a m p i o n)],'example 5');
+is_deeply(eertree('christmas'),[qw(c h r i s t m a)],'example 6');
+
+sub eertree {
+ my $st=shift;
+ my $eertree=Local::Eertree->new();
+ $eertree->add_str($st);
+ my $result=[];
+ $eertree->get_sub_palindromes($eertree->{rto},
+ [$eertree->{rto}],
+ [],
+ $result);
+ $eertree->get_sub_palindromes($eertree->{rte},
+ [$eertree->{rte}],
+ [],
+ $result);
+ my %q=map {$_ => 1} @{$result};
+ my @res;
+ foreach my $i (0..length($st)-1) {
+ foreach my $j ($i..length($st)-1) {
+ my $k=substr($st,$i,$j-$i+1);
+ if (exists $q{$k}) {
+ delete $q{$k};
+ push @res,$k;
+ }
+ }
+ }
+ return \@res;
+}
+
+package Local::Eernode;
+
+sub new {
+ my $class=shift;
+ my $self={
+ edges => {},
+ link => undef,
+ len => 0,
+ id => rand(),
+ };
+ bless $self,$class;
+ return $self;
+}
+
+package Local::Eertree;
+
+sub new {
+ my $class=shift;
+ my $self={
+ nodes => [],
+ rto => Local::Eernode->new(),
+ rte => Local::Eernode->new(),
+ S => ['0'],
+ };
+ $self->{rte}{link}=$self->{rto};
+ $self->{rte}{id}='rte';
+ $self->{rto}{link}=$self->{rto};
+ $self->{rto}{len}=-1;
+ $self->{rto}{id}='rto';
+ $self->{maxSufT}=$self->{rte};
+ bless $self,$class;
+ return $self;
+}
+
+sub get_max_suffix_pal {
+ my $self=shift;
+ my $startnode=shift;
+ my $a=shift;
+ my $u=$startnode;
+ my $i=scalar @{$self->{S}};
+ my $k=$u->{len};
+ while ($u->{id} ne 'rto' && $self->{S}[$i-$k-1] ne $a) {
+ if ($u->{id} eq $u->{link}{id}) {
+ last;
+ }
+ $u=$u->{link};
+ $k=$u->{len};
+ }
+ return $u;
+}
+
+sub add {
+ my $self=shift;
+ my $a=shift;
+ my $q=$self->get_max_suffix_pal($self->{maxSufT},$a);
+ my $newnode=!(exists $q->{edges}{$a});
+ if ($newnode) {
+ my $p=Local::Eernode->new();
+ push @{$self->{nodes}},$p;
+ $p->{len}=$q->{len}+2;
+ if ($p->{len}==1) {
+ $p->{link}=$self->{rte};
+ } else {
+ $p->{link}=$self->get_max_suffix_pal($q->{link},$a)->{edges}{$a} or die "bad link";
+ }
+ $q->{edges}{$a}=$p;
+ $self->{maxSufT}=$q->{edges}{$a};
+ push @{$self->{S}},$a;
+ }
+ return $newnode;
+}
+
+sub add_str {
+ my $self=shift;
+ my $st=shift;
+ foreach my $a (split '',$st) {
+ $self->add($a);
+ }
+}
+
+sub get_sub_palindromes {
+ my $self=shift;
+ my $nd=shift;
+ my $nodestohere=shift;
+ my $charstohere=shift;
+ my $result=shift;
+ foreach my $lnkName (keys %{$nd->{edges}}) {
+ my $nd2=$nd->{edges}{$lnkName};
+ $self->get_sub_palindromes($nd2,[@{$nodestohere},$nd2],[@{$charstohere},$lnkName],$result);
+ }
+ if ($nd->{id} ne 'rto' && $nd->{id} ne 'rte') {
+ my $temp=join('',@{$charstohere});
+ my $revtemp=join('',reverse(@{$charstohere}));
+ my $assembled='';
+ if ($nodestohere->[0]{id} eq 'rte') {
+ $assembled = $revtemp . $temp;
+ } else {
+ $assembled = $revtemp . substr($temp,1);
+ }
+ push @{$result},$assembled;
+ }
+}
diff --git a/challenge-145/roger-bell-west/postscript/ch-1.ps b/challenge-145/roger-bell-west/postscript/ch-1.ps
new file mode 100644
index 0000000000..7f6f861102
--- /dev/null
+++ b/challenge-145/roger-bell-west/postscript/ch-1.ps
@@ -0,0 +1,13 @@
+%!PS
+
+/dotproduct {
+ /b exch def
+ /a exch def
+ /p 0 def
+ 0 1 a length 1 sub {
+ dup a exch get exch b exch get mul p add /p exch def
+ } for
+ p
+} bind def
+
+[ 1 2 3 ] [ 4 5 6 ] dotproduct 32 eq { (Pass) } { (FAIL) } ifelse =
diff --git a/challenge-145/roger-bell-west/postscript/ch-2.ps b/challenge-145/roger-bell-west/postscript/ch-2.ps
new file mode 100644
index 0000000000..7d387d6a2a
--- /dev/null
+++ b/challenge-145/roger-bell-west/postscript/ch-2.ps
@@ -0,0 +1,124 @@
+%!PS
+
+/aeq {
+ 2 dict begin
+ /a exch def
+ /b exch def
+ a length b length eq {
+ /e true def
+ 0 1 a length 1 sub {
+ dup a exch get
+ exch b exch get ne {
+ /e false def
+ exit
+ } if
+ } for
+ e
+ } {
+ false
+ } ifelse
+ end
+} bind def
+
+/apush { % [a b] c -> [a b c]
+ /t exch def
+ [ exch aload pop t ]
+} bind def
+
+/spush { % (ab) c -> (abc)
+ 3 dict begin
+ /t exch 0 get def
+ /a exch def
+ a length 1 add string /b exch def
+ a b copy pop
+ b b length 1 sub t put
+ b
+ end
+} bind def
+
+/sreverse { % (abc) -> (cba)
+ 3 dict begin
+ /a exch def
+ /l a length 1 sub def
+ /b l 1 add string def
+ l -1 0 {
+ dup
+ l exch sub
+ a exch get
+ b 3 1 roll put
+ } for
+ b
+ end
+} bind def
+
+/eertree {
+ 8 dict begin
+ /str exch def
+ /pal 0 array def
+ /l str length def
+ 0 1 l 1 sub {
+ /i exch def
+ 1 1 l i sub {
+ /j exch def
+ /strpal str i j getinterval def
+ strpal strpal sreverse eq {
+ /pal pal strpal apush def
+ } if
+ } for
+ } for
+ /res 0 array def
+ /rd pal length dict def
+ pal {
+ dup
+ rd exch known not {
+ dup rd exch 1 put
+ res exch apush /res exch def
+ } if
+ } forall
+ res
+ end
+} bind def
+
+(redivider) eertree
+[ (r) (redivider) (e) (edivide) (d) (divid) (i) (ivi) (v) ] aeq {
+ (Pass)
+} {
+ (FAIL)
+} ifelse print ( ) print
+
+(deific) eertree
+[ (d) (e) (i) (ifi) (f) (c) ] aeq {
+ (Pass)
+} {
+ (FAIL)
+} ifelse print ( ) print
+
+(rotors) eertree
+[ (r) (rotor) (o) (oto) (t) (s) ] aeq {
+ (Pass)
+} {
+ (FAIL)
+} ifelse print ( ) print
+
+(challenge) eertree
+[ (c) (h) (a) (l) (ll) (e) (n) (g) ] aeq {
+ (Pass)
+} {
+ (FAIL)
+} ifelse print ( ) print
+
+(champion) eertree
+[ (c) (h) (a) (m) (p) (i) (o) (n) ] aeq {
+ (Pass)
+} {
+ (FAIL)
+} ifelse print ( ) print
+
+(christmas) eertree
+[ (c) (h) (r) (i) (s) (t) (m) (a) ] aeq {
+ (Pass)
+} {
+ (FAIL)
+} ifelse =
+
+
diff --git a/challenge-145/roger-bell-west/python/ch-1.py b/challenge-145/roger-bell-west/python/ch-1.py
new file mode 100755
index 0000000000..83464b868f
--- /dev/null
+++ b/challenge-145/roger-bell-west/python/ch-1.py
@@ -0,0 +1,16 @@
+#! /usr/bin/python3
+
+import unittest
+
+def dotproduct(a,b):
+ p=0
+ for i,v in enumerate(a):
+ p+=v*b[i]
+ return p
+
+class TestDotproduct(unittest.TestCase):
+
+ def test_ex1(self):
+ self.assertEqual(dotproduct([1,2,3],[4,5,6]),32,'example 1')
+
+unittest.main()
diff --git a/challenge-145/roger-bell-west/python/ch-2.py b/challenge-145/roger-bell-west/python/ch-2.py
new file mode 100755
index 0000000000..0a3aabbb70
--- /dev/null
+++ b/challenge-145/roger-bell-west/python/ch-2.py
@@ -0,0 +1,133 @@
+#! /usr/bin/python3
+
+# Very lightly modified from https://rosettacode.org/wiki/Eertree#Python
+# by "TimSC"
+
+import unittest
+
+def eertree(st):
+ eertree=Eertree()
+ for ch in st:
+ eertree.add(ch)
+ result = []
+ eertree.get_sub_palindromes(eertree.rto, [eertree.rto], [], result)
+ eertree.get_sub_palindromes(eertree.rte, [eertree.rte], [], result)
+ q=set(result)
+ res=[]
+ for i in range(len(st)):
+ for j in range(i,len(st)):
+ k=st[i:j+1]
+ if k in q:
+ res.append(k)
+ q.discard(k)
+ return res
+
+class Eernode(object):
+ def __init__(self):
+ self.edges = {} # edges (or forward links)
+ self.link = None # suffix link (backward links)
+ self.len = 0 # the length of the node
+
+class Eertree(object):
+ def __init__(self):
+ self.nodes = []
+ # two initial root nodes
+ self.rto = Eernode() #odd length root node, or node -1
+ self.rte = Eernode() #even length root node, or node 0
+
+ # Initialize empty tree
+ self.rto.link = self.rte.link = self.rto;
+ self.rto.len = -1
+ self.rte.len = 0
+ self.S = [0] # accumulated input string, T=S[1..i]
+ self.maxSufT = self.rte # maximum suffix of tree T
+
+ def get_max_suffix_pal(self, startNode, a):
+ # We traverse the suffix-palindromes of T in the order of decreasing length.
+ # For each palindrome we read its length k and compare T[i-k] against a
+ # until we get an equality or arrive at the -1 node.
+ u = startNode
+ i = len(self.S)
+ k = u.len
+ while id(u) != id(self.rto) and self.S[i - k - 1] != a:
+ assert id(u) != id(u.link) #Prevent infinte loop
+ u = u.link
+ k = u.len
+
+ return u
+
+ def add(self, a):
+
+ # We need to find the maximum suffix-palindrome P of Ta
+ # Start by finding maximum suffix-palindrome Q of T.
+ # To do this, we traverse the suffix-palindromes of T
+ # in the order of decreasing length, starting with maxSuf(T)
+ Q = self.get_max_suffix_pal(self.maxSufT, a)
+
+ # We check Q to see whether it has an outgoing edge labeled by a.
+ createANewNode = not a in Q.edges
+
+ if createANewNode:
+ # We create the node P of length Q+2
+ P = Eernode()
+ self.nodes.append(P)
+ P.len = Q.len + 2
+ if P.len == 1:
+ # if P = a, create the suffix link (P,0)
+ P.link = self.rte
+ else:
+ # It remains to create the suffix link from P if |P|>1. Just
+ # continue traversing suffix-palindromes of T starting with the suffix
+ # link of Q.
+ P.link = self.get_max_suffix_pal(Q.link, a).edges[a]
+
+ # create the edge (Q,P)
+ Q.edges[a] = P
+
+ #P becomes the new maxSufT
+ self.maxSufT = Q.edges[a]
+
+ #Store accumulated input string
+ self.S.append(a)
+
+ return createANewNode
+
+ def get_sub_palindromes(self, nd, nodesToHere, charsToHere, result):
+ #Each node represents a palindrome, which can be reconstructed
+ #by the path from the root node to each non-root node.
+
+ #Traverse all edges, since they represent other palindromes
+ for lnkName in nd.edges:
+ nd2 = nd.edges[lnkName] #The lnkName is the character used for this edge
+ self.get_sub_palindromes(nd2, nodesToHere+[nd2], charsToHere+[lnkName], result)
+
+ #Reconstruct based on charsToHere characters.
+ if id(nd) != id(self.rto) and id(nd) != id(self.rte): #Don't print for root nodes
+ tmp = "".join(charsToHere)
+ if id(nodesToHere[0]) == id(self.rte): #Even string
+ assembled = tmp[::-1] + tmp
+ else: #Odd string
+ assembled = tmp[::-1] + tmp[1:]
+ result.append(assembled)
+
+class TestEertree(unittest.TestCase):
+
+ def test_ex1(self):
+ self.assertEqual(eertree("redivider"),["r","redivider","e","edivide","d","divid","i","ivi","v"],'example 1')
+
+ def test_ex2(self):
+ self.assertEqual(eertree("deific"),["d","e","i","ifi","f","c"],'example 2')
+
+ def test_ex3(self):
+ self.assertEqual(eertree("rotors"),["r","rotor","o","oto","t","s"],'example 3')
+
+ def test_ex4(self):
+ self.assertEqual(eertree("challenge"),["c","h","a","l","ll","e","n","g"],'example 4')
+
+ def test_ex5(self):
+ self.assertEqual(eertree("champion"),["c","h","a","m","p","i","o","n"],'example 5')
+
+ def test_ex6(self):
+ self.assertEqual(eertree("christmas"),["c","h","r","i","s","t","m","a"],'example 6')
+
+unittest.main()
diff --git a/challenge-145/roger-bell-west/raku/ch-1.p6 b/challenge-145/roger-bell-west/raku/ch-1.p6
new file mode 100755
index 0000000000..8adde1bc97
--- /dev/null
+++ b/challenge-145/roger-bell-west/raku/ch-1.p6
@@ -0,0 +1,14 @@
+#! /usr/bin/perl6
+
+use Test;
+plan 1;
+
+is(dotproduct((1,2,3),(4,5,6)),32,'example 1');
+
+sub dotproduct(@a,@b) {
+ my $p=0;
+ for 0..@a.end -> $i {
+ $p += @a[$i]*@b[$i];
+ }
+ return $p;
+}
diff --git a/challenge-145/roger-bell-west/raku/ch-2.p6 b/challenge-145/roger-bell-west/raku/ch-2.p6
new file mode 100755
index 0000000000..4d28ff9529
--- /dev/null
+++ b/challenge-145/roger-bell-west/raku/ch-2.p6
@@ -0,0 +1,136 @@
+#! /usr/bin/perl6
+
+use Test;
+plan 6;
+
+is-deeply(eertree('redivider'),[<r redivider e edivide d divid i ivi v>],'example 1');
+is-deeply(eertree('deific'),[<d e i ifi f c>],'example 2');
+is-deeply(eertree('rotors'),[<r rotor o oto t s>],'example 3');
+is-deeply(eertree('challenge'),[<c h a l ll e n g>],'example 4');
+is-deeply(eertree('champion'),[<c h a m p i o n>],'example 5');
+is-deeply(eertree('christmas'),[<c h r i s t m a>],'example 6');
+
+
+class Eernode {
+ has %.edges is rw;
+ has $.link is rw;
+ has $.len is rw;
+ has $.id is rw;
+
+ method init {
+ self.len=0;
+ self.edges={};
+ self.id=rand;
+ return self;
+ }
+}
+
+class Eertree {
+ has @.nodes is rw;
+ has $.rto is rw;
+ has $.rte is rw;
+ has @.S is rw;
+ has $.maxSufT is rw;
+
+ method init {
+ self.nodes=[];
+ self.rto=Eernode.new.init;
+ self.rte=Eernode.new.init;
+ self.rte.link=self.rto;
+ self.rte.id="rte";
+ self.rto.link=self.rto;
+ self.rto.len=-1;
+ self.rto.id="rto";
+ self.S=["0"];
+ self.maxSufT=self.rte;
+ return self;
+ }
+
+ method get_max_suffix_pal($startnode,$a) {
+ my $u=$startnode;
+ my $i=self.S.elems;
+ my $k=$u.len;
+ while ($u.id ne 'rto' && self.S[$i-$k-1] ne $a) {
+ if ($u.id eq $u.link.id) {
+ last;
+ }
+ $u=$u.link;
+ $k=$u.len;
+ }
+ return $u;
+ }
+
+ method add($a) {
+ my $q=self.get_max_suffix_pal(self.maxSufT,$a);
+ my $newnode=!($q.edges{$a}:exists);
+ if ($newnode) {
+ my $p=Eernode.new.init;
+ self.nodes.push($p);
+ $p.len=$q.len+2;
+ if ($p.len==1) {
+ $p.link=self.rte;
+ } else {
+ $p.link=self.get_max_suffix_pal($q.link,$a).edges{$a} or die "bad link";
+ }
+ $q.edges{$a}=$p;
+ self.maxSufT=$q.edges{$a};
+ self.S.push($a);
+ }
+ return $newnode;
+ }
+
+ method add_str($st) {
+ for $st.comb() -> $a {
+ self.add($a);
+ }
+ }
+
+ method get_sub_palindromes($nd,@nodestohere,@charstohere,$result) {
+ for $nd.edges.keys -> $lnkName {
+ my $nd2=$nd.edges{$lnkName};
+ my @nh=@nodestohere;
+ @nh.push($nd2);
+ my @ch=@charstohere;
+ @ch.push($lnkName);
+ self.get_sub_palindromes($nd2,@nh,@ch,$result);
+ }
+ if ($nd.id ne 'rto' && $nd.id ne 'rte') {
+ my $temp=@charstohere.join('');
+ my $revtemp=$temp.flip;
+ my $assembled='';
+ if (@nodestohere[0].id eq 'rte') {
+ $assembled = $revtemp ~ $temp;
+ } else {
+ $assembled = $revtemp ~ substr($temp,1);
+ }
+ $result.push($assembled);
+ }
+ }
+
+}
+
+sub eertree($st) {
+ my $eertree=Eertree.new.init;
+ $eertree.add_str($st);
+ my $result=[];
+ $eertree.get_sub_palindromes($eertree.rto,
+ [$eertree.rto],
+ [],
+ $result);
+ $eertree.get_sub_palindromes($eertree.rte,
+ [$eertree.rte],
+ [],
+ $result);
+ my $q=$result.SetHash;
+ my @res;
+ for 0..chars($st)-1 -> $i {
+ for $i..chars($st)-1 -> $j {
+ my $k=substr($st,$i,$j-$i+1);
+ if ($q{$k}:exists) {
+ $q{$k}:delete;
+ push @res,$k;
+ }
+ }
+ }
+ return @res;
+}
diff --git a/challenge-145/roger-bell-west/ruby/ch-1.rb b/challenge-145/roger-bell-west/ruby/ch-1.rb
new file mode 100755
index 0000000000..eecd7a173c
--- /dev/null
+++ b/challenge-145/roger-bell-west/ruby/ch-1.rb
@@ -0,0 +1,19 @@
+#! /usr/bin/ruby
+
+def dotproduct(a,b)
+ p=0
+ a.each_with_index do |v,i|
+ p += v * b[i]
+ end
+ return p
+end
+
+require 'test/unit'
+
+class TestDotproduct < Test::Unit::TestCase
+
+ def test_ex1
+ assert_equal(32,dotproduct([1,2,3],[4,5,6]))
+ end
+
+end
diff --git a/challenge-145/roger-bell-west/ruby/ch-2.rb b/challenge-145/roger-bell-west/ruby/ch-2.rb
new file mode 100755
index 0000000000..f493e6f36b
--- /dev/null
+++ b/challenge-145/roger-bell-west/ruby/ch-2.rb
@@ -0,0 +1,140 @@
+#! /usr/bin/ruby
+
+require 'set'
+
+class Eernode
+ attr_accessor :edges, :link, :len, :id
+ def initialize
+ @edges=Hash.new
+ @len=0
+ @id=rand
+ end
+end
+
+class Eertree
+ attr_accessor :nodes,:rto,:rte,:S,:maxSufT
+ def initialize
+ @nodes=[]
+ @rto=Eernode.new
+ @rte=Eernode.new
+ @rte.link=@rto
+ @rte.id="rte"
+ @rto.link=rto
+ @rto.len=-1
+ @rto.id="rto"
+ @S=["0"]
+ @maxSufT=@rte
+ end
+
+ def get_max_suffix_pal(startnode,a)
+ u=startnode
+ i=@S.length
+ k=u.len
+ while u.id != "rto" && @S[i-k-1] != a do
+ if u.id == u.link.id then
+ break
+ end
+ u=u.link
+ k=u.len
+ end
+ return u
+ end
+
+ def add(a)
+ q=get_max_suffix_pal(@maxSufT,a)
+ newnode=!q.edges.has_key?(a)
+ if newnode then
+ p=Eernode.new
+ @nodes.push(p)
+ p.len=q.len+2
+ if p.len==1 then
+ p.link=@rte
+ else
+ p.link=get_max_suffix_pal(q.link,a).edges[a]
+ end
+ q.edges[a]=p
+ @maxSufT=q.edges[a]