Merge branch 'master' of github.com:drbaggy/perlweeklychallenge-club

2 files changed, 61 insertions, 29 deletions

diff --git a/challenge-145/james-smith/README.md b/challenge-145/james-smith/README.md
index d479af154d..affd6c3cd4 100644
--- a/challenge-145/james-smith/README.md
+++ b/challenge-145/james-smith/README.md
@@ -1,6 +1,6 @@
-[< Previous 143](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-143/james-smith) |
-[Next 145 >](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-145/james-smith)
-# Perl Weekly Challenge #144
+[< Previous 144](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-144/james-smith) |
+[Next 146 >](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-146/james-smith)
+# Perl Weekly Challenge #145
 
 You can find more information about this weeks, and previous weeks challenges at:
 
@@ -12,48 +12,79 @@ submit solutions in whichever language you feel comfortable with.
 
 You can find the solutions here on github at:
 
-https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-144/james-smith
+https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-145/james-smith
 
-# Challenge 1 - Semiprimes
+# Challenge 1 - Dot product
 
-***Write a script to generate all Semiprime number <= 100. (A semiprime is a number which is a multiple of two primes)***`
+***You are given 2 arrays of same size, `@a` and `@b`. Write a script to implement Dot Product.***
 
 ## The solution
 
-Rather than looping through each number to find if it is a semiprime - instead we find all the primes and multiply these together.
-We realise we need the primes up to $N/2, and so compute them. Then for each prime we push all multiples of the prime with all
-the previous primes (filtering for values less than or equal to $N)
+This challenge is simple - Relatively simple one to start with this week. We keep a running total of the product of corresponding entries in each of the arrays.
+
+In this case we use one array as the basis of the loop, and shift off elements of the other array.
 
-This method is faster than the loop method about 9x faster than the loop method for `$N = 10,000`.
 ```perl
-my $N = 1000;
-my @primes      = (2);
-my @semi_primes = (4);
-
-foreach my $p ( map { 1+2*$_ } 1..($N/4) ) {
-  map { ($p%$_)||(next) } @primes;
-  push @primes,$p;
-  push @semi_primes,grep {$_<=$N} map{$p*$_} @primes;
+sub dot_product {
+  my ($t,@y) = (0,@{$_[1]});
+  $t += $_ * shift @y foreach @{$_[0]};
+  $t;
 }
-
-say for sort {$a<=>$b} @semi_primes;
 ```
 
-# Challenge 2 - Ulam Sequence
+# Challenge 2 - Palindromic Tree
 
-***You are given two positive numbers, `$u` and `$v`. Write a script to generate Ulam Sequence having at least 10 Ulam numbers where `$u` and `$v` are the first 2 Ulam numbers.
-The standard Ulam sequence (the (1, 2)-Ulam sequence) starts with U1 = 1 and U2 = 2. Then for n > 2, Un is defined to be the smallest integer that is the sum of two distinct earlier terms in exactly one way and larger than all earlier terms.***
+***You are given a string `$s`. Write a script to create a Palindromic Tree for the given string.***
 
 ## The solution
 
-For ulam numbers - we use an array and a hash to store previous ulam numbers. That allows us to quickly find those which have 1 unique partition. We do this with the grep in the 3rd line of the function. We then continue until the the array has the appropriate size. (We know there will be at least one solution the sum of the last two ulam numbers)
+This was one of the hardest challenges over recent weeks - not the implementation but understanding how/what this does.
+
+Creating the tree is relatively straight forward. We start with the two "empty" nodes, and for each letter or pair of
+adjacent letters which are the same we add the node as children (connected by edges), and also a back link to the
+first/last letter.
 
 ```perl
-sub ulam {
-  my%seq_hash=map{$_,$_}my@seq=($_[0],my$n=$_[1]);
-  for(;scalar @seq<$_[2];++$n){
-    push@seq,$seq_hash{$n}=$n if 1==grep{2*$_<$n&&$seq_hash{$n-$_}}@seq;
+sub eertree {
+  my $str = [ split //, $_[0] ];
+  my $tree = {
+    -1  => { 'start' => undef, 'edges' => {}, 'suff' => -1 },
+    q() => { 'start' => undef, 'edges' => {}, 'suff' => -1 },
+  };
+  add_str( $tree, $str, -1, $_, $_   ),
+  add_str( $tree, $str, q(), $_, $_+1 ) for 0.. @{$str}-1;
+  $tree;
+}
+```
+
+In `add_str` we:
+
+ * check that we are still in bounds and that the first and last letters are the same;
+ * we create a link from the current node to the new node;
+ * we create the new node if it didn't already exist;
+ * we then expand the palindrome by a character at the front/end and repeat until we
+   are out of bounds or we don't have a palindrome.
+
+```perl
+sub add_str {
+  my( $tr, $c, $node, $st, $en ) = @_;
+  while( $st >=0 && $en < @{$c} && $c->[$st] eq $c->[$en] ) {
+    $tr->{$node}{'edges'}{my $s = join q(), @{$c}[$st..$en] } ||= keys %{$tr->{$node}{'edges'}};
+    $tr->{$node=$s} ||= { 'start' => $st, 'edges' => {}, 'suff' => $st==$en ? -1 : $en==$st+1 ? q() : $c->[$st] };
+    $st--;
+    $en++;
   }
-  @seq;
+}
+```
+
+To generate the output required in the tests we flatten the string by sorting the nodes into the order of their first appearance (and length)
+```perl
+sub stringify {
+  my $tree = shift;
+  return join q( ),
+         sort { $tree->{$a}{'start'} <=> $tree->{$b}{'start'} ||
+                length $a <=> length $b }
+         grep { defined $tree->{$_}{'start'} }
+         keys %{$tree};
 }
 ```
diff --git a/challenge-145/james-smith/blog.txt b/challenge-145/james-smith/blog.txt
new file mode 100644
index 0000000000..873b1773df
--- /dev/null
+++ b/challenge-145/james-smith/blog.txt
@@ -0,0 +1 @@
+https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-145/james-smith