Merge pull request #2402 from drbaggy/master

Week 80 - neat solutions...

4 files changed, 60 insertions, 39 deletions

diff --git a/challenge-079/james-smith/perl/ch-1.pl b/challenge-079/james-smith/perl/ch-1.pl
index 75a2e92922..5b5ad927f1 100755
--- a/challenge-079/james-smith/perl/ch-1.pl
+++ b/challenge-079/james-smith/perl/ch-1.pl
@@ -62,11 +62,10 @@ sub count_set_bits {
   my $t = my $s = 0;
   while (@q) {
     next unless shift @q;
-    $t += ($s + @q/2)*(1<<@q);
-    $t %= 1000000007;
+    $t += ($s + @q/2) * (1<<@q);
     $s++;
   }
-  return $t;
+  return $t % 1000000007;
 }
 
 sub naive_count_set_bits {
diff --git a/challenge-080/james-smith/README.md b/challenge-080/james-smith/README.md
index 96284e7deb..b1f39c934a 100644
--- a/challenge-080/james-smith/README.md
+++ b/challenge-080/james-smith/README.md
@@ -1,45 +1,18 @@
 Solutions by James Smith.
 
-# Challenge 1 - Count Set Bits
+# Challenge 1 - Smallest Positive Number
 
-This is a really interesting challenge - there is a really quick naive solution which is to do the
-counting - but that is an O(n log(n)) problem so as n gets large (to values where the modulus
-calculation is required) then this gets very slow.
+After testing three solutions:
 
-There is an O(log(n)) solution which means breaking the sums into chunks which are easy to sum.
+  * using sort
+  * using hash keys
+  * scanning with the numbers 1, 2, 3 etc
 
-For the numbers 1 .. (2^n-1) you can see that the sum of the bits is n(2^n)/2
+it became obvious the best way of handling this is to sort the +ve numbers and them loop through them to find the first missing one (the first number which has the value in the array not equal to the 1-based index) was the quicksest...
 
-[ There are 2^n numbers (including 0) and you can represent number in n bits, and exactly half of the bits are 1 ]
+# Challenge 2 - Count candies
 
-We can then use this to work out the sums of the bit counts..
+This is a simple sweep approach applying the b) rule multiple times until the counting stops!
 
-First we get a bit representation of "$i+1"
+Note you have to do this repeatedly till you find the right answer - a single pass will not return the right value {especially in more complex environments}
 
-so e.g. for i = 22 - the array is 1 0 1 1 1
-
-Loop through the bits and use the count method above to count the lower bits
-of each group (ignore any where the value in the bit array is 0)
-The higher bits are counted by multiplying the size of the group by the bits
-in the "higher bit" e.g. 16, 20, 22 below... What we note though is that this
-number increases by 1 each time that we loop through the array
-
-So in the example above the chunks become:
-
-```
- 1..15 - split this into 16 x "0"  & 0..15  - total is 2^4 * 0 + 4(2^4)/2 = 32
-16..19 - split this into  4 x "16" & 0..3   - total is 2^2 * 1 + 2(2^2)/2 =  8
-20..21 - split this into  2 x "20" & 0..1   - total is 2^1 * 2 + 1(2^1)/2 =  5
-22     - split this into  1 x "22" & 0      - total is 2^0 * 3 + 0(2^0)/2 =  3
-                                                                            48
-```
-
-# Challenge 2 - trapped rain water
-
-Much simpler challenge this time - we just need to work out how much water is trapped.
-So for any column we need to work out the maximum height of rocks to the left and right
-of the column, if neither of these are higher than the height of the current column no
-water is trapped. Otherwise the amount of water is trapped is the minimum of these two
-values minus the height of the column.
-
-To enhance the image - I've also added "~~"s to indicate where the water is trapped
diff --git a/challenge-080/james-smith/perl/ch-1.pl b/challenge-080/james-smith/perl/ch-1.pl
new file mode 100644
index 0000000000..09526718d6
--- /dev/null
+++ b/challenge-080/james-smith/perl/ch-1.pl
@@ -0,0 +1,18 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use feature qw(say);
+
+say smallest_number_sort(qw(200 1 -2 2 5 1000 -6 3000 ),1e6..1e7,6001..9001,3,4,3401..5900);
+say smallest_number_sort(qw(5 2 -2 0));
+say smallest_number_sort(qw(1 8 -1));
+say smallest_number_sort(qw(2 0 -1));
+
+sub smallest_number_sort {
+  my @q = sort { $a <=> $b } grep {$_>0} @_; ## Need +ve in order!
+  for( $_=1; $_ == shift @q; $_++  ) {}      ## Loop through from 1.. exit loop if the array
+                                             ##   value isn't equal to index (1-based)
+  return $_;                                 ## return value...
+}
diff --git a/challenge-080/james-smith/perl/ch-2.pl b/challenge-080/james-smith/perl/ch-2.pl
new file mode 100644
index 0000000000..9116f85539
--- /dev/null
+++ b/challenge-080/james-smith/perl/ch-2.pl
@@ -0,0 +1,31 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use feature qw(say);
+
+say candies( qw(1 2 2) );
+say candies( qw(1 4 3 2) );
+
+sub candies {
+  my @ranks = @_;
+  my $prev_count = @candies = map { 1 } @ranks; ## First pass we set everything to 1!
+  my $flag;
+  do {
+    my $count = 0;
+    foreach( 0..(@ranks-2) ) {         ## Loop through comparing element to next one - increase as approprite
+
+      $candies[$_]   = $candies[$_+1]+1 if ($ranks[$_] > $ranks[$_+1]) && ($candies[$_] <= $candies[$_+1]);
+      $candies[$_+1] = $candies[$_  ]+1 if ($ranks[$_] < $ranks[$_+1]) && ($candies[$_] => $candies[$_+1]);
+
+      $count        += $candies[$_  ]; ## by the time we get here we would have done both comparisons that
+                                       ## cause this entry to be updated..
+    }
+
+    $count += $candies[-1];            ## Add count for the last element...
+
+    return $count if $count == $prev_count; ## Totals are the same so nothing been update can return
+    $prev_count = $count;
+  } while( 1 ); ## Infinite loop - will hit exit condition in loop...!
+}