Merge pull request #7746 from drbaggy/master

208 solutions

4 files changed, 97 insertions, 67 deletions

diff --git a/challenge-208/james-smith/README.md b/challenge-208/james-smith/README.md
index 367b308981..60038de5c3 100644
--- a/challenge-208/james-smith/README.md
+++ b/challenge-208/james-smith/README.md
@@ -1,7 +1,7 @@
-[< Previous 206](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-206/james-smith) |
-[Next 208 >](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-208/james-smith)
+[< Previous 207](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-207/james-smith) |
+[Next 209 >](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-209/james-smith)
 
-# The Weekly Challenge 207
+# The Weekly Challenge 208
 
 You can find more information about this weeks, and previous weeks challenges at:
 
@@ -13,91 +13,64 @@ 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-207/james-smith
+https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-208/james-smith
 
-# Task 1: Keyboard Word
+# Task 1: Minimum Index Sum
 
-***You are given an array of words. Write a script to print all the words in the given array that can be types using alphabet on only one row of the keyboard. (Assuming as English this is a QWERTY keyboard)***
+***You are given two arrays of strings. Write a script to find out all common strings in the given two arrays with minimum index sum. If no common strings found returns an empty list.***
 
 ## Solution
 
-The obvious solution here is to use a regular expression, where each row of the keyboard is separated by a `|` to make them separate clauses.
-
-```perl
-sub keyboard_words { grep { m{^([qwertyuiop]+|[asdfghjkl]+|[zxcvbnm]+)$}i } @_ }
-```
-
-We can loop through a file with the following code to find the longest keyboard words in the dictionary
-
+We proceed to do a pass of each array. 
 ```perl
-m{^([qwertyuiop]+|[asdfghjkl]+|[zxcvbnm]+)$}i && print while <>
-```
-
-**or** as a bash one-liner:
-
-```bash
-perl -ne 'm{^([qwertyuiop]+|[asdfghjkl]+|[zxcvbnm]+)$}i&&print' /usr/share/dict/british-english-huge
+sub min_index_sum {
+  my( $b, %x, $t, $s, @best ) = ( 1e99,                #0
+    map { $_[0][$_] => $_ } reverse ( 0 .. $#{$_[0]} ) #1
+  );
+  exists $x{$t = $_[1][$_]} &&                         #3
+    ( $b > ($s=$x{$t}+$_) ?  ($b,@best) = ( $s,$t )    #4
+    : $b == $s            && push @best, $t )          #5
+    for 0 .. $#{$_[1]};                                #2
+  \@best                                               #6
+}
 ```
 
-This gives us the following for longest words:
+First we start with the first array and find the lowest index for each word in it - and store them in the hash `%x`. Note we work backwards through the list to ensure that it is the lowest index if the word is duplicated. This is the `map` in line 1.
 
-Length 11:
+We then loop through the second list of strings (`#2`) looking for words which are in the first list (`#3`). If it has a lower index sum that the best so far we record this and reset the list of words (`#4`). If it has the same we just push it onto the list. (`#5`)
 
- * rupturewort
+At the end we just return the current list of words (which could be empty if there are no duplicates). (`#6`)
 
-Length 10:
- * peppertree
- * pepperwort
- * perpetuity
- * perruquier
- * pirouetter
- * prerequire
- * proprietor
- * repertoire
- * typewriter
+Note we set the initial best index sum (`#0`) as `10^99` as the index sum will be no where near this and so we can treat this as effectively infinity...
 
-Note these are all on the top row of the keyboard - So no **typewriter** isn't the longest word in the English language you can make from the top row of the keyboard.
+# Task 2: Duplicate and Missing
 
-Using this extreme dictionary - we have:
+Try all combinations and 
+***You are given an array of integers in sequence with one missing and one duplicate. Write a script to find the duplicate and missing integer in the given array. Return `-1` if none found. For the sake of this task, let us assume the array contains no more than one duplicate and missing.***
 
-| Length | Count |
-+--------+-------+
-|     11 |     1 |
-|     10 |     9 |
-|      9 |    27 |
-|      8 |    70 |
-|      7 |   128 |
-|      6 |   224 |
-|      5 |   278 |
-|      4 |   322 |
-|      3 |   285 |
-|      2 |   218 |
-|      1 |    52 |
+## Observation
 
-Note: the definition of a word is a bit vague at times....
-
-Note: there are 5 9-letter words which are not from the top row - these are all of Jewish origin.
-
-# Task 2: H-index
-
-***You are given an array of integers containing citations a researcher has received for each paper. Write a script to compute the researcher’s H-Index. For more information please checkout the wikipedia page.***
-
-***The H-Index is the largest number h such that h articles have at least h citations each. For example, if an author has five publications, with 9, 7, 6, 2, and 1 citations (ordered from greatest to least), then the author’s h-index is 3, because the author has three publications with 3 or more citations. However, the author does not have four publications with 4 or more citations.***
+It is not 100% clear in the desciption - but we have assumed that it means a list of integers from `n` ... `m` with a step of `1`.
 
 ## Solution
 
-This is actually relatively straight forward (we will assume that the reference counts are in order).
+We loop through looking for a duplicate `$p[n+1]==$p[$n]` or gap `$p[n+1]!=$p[$n]+1`.
+
+We have two special cases - if there are no duplicates return -1 
 
 ```perl
-sub h_index   { ( $_[$_]>$_) && return $_+1 for reverse 0..$#_ }
-sub h_index_2 { pop @_ while $_[-1] < @_; 0 + @_               }
-sub h_index_3 { ( $_[$_]>$_) || return $_ for 0..$#_; 0+@_     }
-```
+sub dup_missing {
+  my($p,$d,$m) = shift;
+  ($_==$p ? ($d=$_) : $_ == $p+2 && ($m=$_-1)), $p=$_ for @_;
+  defined $d ? ( defined $m ? [ $d, $m ] : [ $d,$p+1  ] ): [-1]
+}
 
-We can either start at the beginning of the list and count backwards *OR* from the start.
+```
+We note that if the two neighbouring values are the same we have found the duplicate, and if the difference is `2` we've found the missing value.
 
-`h_index_3` starts from the beginning of the list. We assume if we are not past the threshold then the `h-index` is the previous index - as in the real world our list is 1-based and in the perl world 0-based - then this is just `$_`. We short cut the loop and return the value. If we don't short cut the loop then the index must be the length of the list.
+At the end of the loop we have 3 cases:
 
-`h_index` is slightly longer! But we start from the end of the list (we `reverse` the indicies). Again we use the same criteria but switch the *logic* to `&&` which is the equivalent of `if`. And loop until we match the criteria. In this case we return `$_+1` as it is the current one we are interested in. **Note** in this case we will always short cut the loop so need no additional `return` state - definitely a one-liner!
+ 1) We have not found the duplicate (`$d` is undefined) - so we return `[-1]`;
+ 2) We have found the duplicate and we've found the missing value as well so we return `[$d,$m]`;
+ 3) We have found the duplicate BUT we haven't found the missing value - there is no solution here - the missing value is at one end or other of the list. As at this point we know what the last value of the list is (but not the first - we threw that away) we just return last value + 1.
 
-`h_index_2` is effectively the same as 1, but removes the nasty use of `&&`/`||` to replace and `if`/`unless` - by putting the logic in the `while` statement and `pop`ping off values..
diff --git a/challenge-208/james-smith/blog.txt b/challenge-208/james-smith/blog.txt
new file mode 100644
index 0000000000..267fb7ddbf
--- /dev/null
+++ b/challenge-208/james-smith/blog.txt
@@ -0,0 +1 @@
+https://github.com/manwar/perlweeklychallenge-club/blob/master/challenge-208/james-smith/blog.txt
diff --git a/challenge-208/james-smith/perl/ch-1.pl b/challenge-208/james-smith/perl/ch-1.pl
new file mode 100644
index 0000000000..e18a1d1f61
--- /dev/null
+++ b/challenge-208/james-smith/perl/ch-1.pl
@@ -0,0 +1,32 @@
+#!/usr/local/bin/perl
+
+use strict;
+use warnings;
+use feature qw(say);
+use Test::More;
+
+my @TESTS = (
+ [ [qw(Perl Raku Love)], [qw(Raku Perl Hate)], 'Perl Raku' ],
+ [ [qw(A B C)],          [qw(D E F)         ], ''             ],
+ [ [qw(A B C)],          [qw(C A B)         ], 'A' ],
+ [ [qw(A B C D E F)],    [qw(A B C)         ], 'A' ],
+ [ [qw(A B C)],          [qw(D E F G H C)   ], 'C' ],
+ [ ['A'..'Z'],           [reverse('A'..'Z')],  "@{[ 'A'..'Z' ]}" ],
+ [ ['A'..'Z'],           ['A'..'Z'],           'A' ],
+ [ ['A'..'Z'],           ['a'..'z'],           '' ],
+);
+
+is( min_index_sum(       @{$_->[0]} ), $_->[1] ) for @TESTS;
+done_testing();
+
+sub min_index_sum {
+  my( $b, %x, $t, $s, @best ) = ( 1e99,                #0
+    map { $_[0][$_] => $_ } reverse ( 0 .. $#{$_[0]} ) #1
+  );
+  exists $x{$t = $_[1][$_]} &&                         #3
+    ( $b > ($s=$x{$t}+$_) ?  ($b,@best) = ( $s,$t )    #4
+    : $b == $s            && push @best, $t )          #5
+    for 0 .. $#{$_[1]};                                #2
+  \@best                                               #6
+}
+
diff --git a/challenge-208/james-smith/perl/ch-2.pl b/challenge-208/james-smith/perl/ch-2.pl
new file mode 100644
index 0000000000..bf3c5f0ed7
--- /dev/null
+++ b/challenge-208/james-smith/perl/ch-2.pl
@@ -0,0 +1,24 @@
+#!/usr/local/bin/perl
+
+use strict;
+use warnings;
+use feature qw(say);
+use Test::More;
+
+my @TESTS = (
+ [ [1,2,2,4], [2,3] ],
+ [ [1,2,3,4], [-1]  ],
+ [ [1,2,3,3], [3,4] ],
+ [ [1,2,2,3,5], [2,4] ],
+ [ [5,5],       [5,6] ],
+);
+
+is( dup_missing( @{$_->[0]} ), $_->[1] ) for @TESTS;
+
+done_testing();
+
+sub dup_missing {
+  my($p,$s,$d) = (shift,0);
+  ($p==$_ && ($d=$_)),($p=$_,$s+=$_-$f) for @_;
+  defined $d ? [ $d, $s2-$s+$d ] : [ -1 ];
+}