Merge pull request #2356 from polettix/polettix/pwc079

Add PWC079 for polettix

4 files changed, 80 insertions, 0 deletions

diff --git a/challenge-079/polettix/blog.txt b/challenge-079/polettix/blog.txt
new file mode 100644
index 0000000000..5046b4445a
--- /dev/null
+++ b/challenge-079/polettix/blog.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2020/09/22/pwc079-count-set-bits/
diff --git a/challenge-079/polettix/blog1.txt b/challenge-079/polettix/blog1.txt
new file mode 100644
index 0000000000..a322894db3
--- /dev/null
+++ b/challenge-079/polettix/blog1.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2020/09/23/pwc079-trapped-rain-water/
diff --git a/challenge-079/polettix/perl/ch-1.pl b/challenge-079/polettix/perl/ch-1.pl
new file mode 100644
index 0000000000..7a8169700e
--- /dev/null
+++ b/challenge-079/polettix/perl/ch-1.pl
@@ -0,0 +1,36 @@
+#!/usr/bin/env perl
+use 5.024;
+use warnings;
+use experimental qw< postderef signatures >;
+no warnings qw< experimental::postderef experimental::signatures >;
+
+sub count_bits ($n, $m = 1000000007) {
+   my $mask     = 1;
+   my $mask_bit = 0;
+   while (($n & ~$mask) > $mask) { # scan for highest set bit
+      $mask <<= 1;
+      $mask_bit++;
+   }
+   my $n_bits = 0;
+   while ($n) {
+      while (($n & $mask) == 0) {    # scan for next high bit
+         $mask_bit--;
+         $mask >>= 1;
+      }
+      $n &= ~$mask;    # this makes $n less than half of itself
+      $n_bits = ($n_bits + 1 + $n + $mask_bit * ($mask >> 1) % $m) % $m;
+   } ## end while ($n)
+   return $n_bits;
+} ## end sub count_bits
+
+sub count_bits_brute_force ($n, $m = 1000000007) {
+   my $n_bits = 0;
+   $n_bits = ($n_bits + (sprintf('%b', $_) =~ tr/1/1/)) % $m
+      for 1 .. $n;
+   return $n_bits;
+}
+
+my $n = shift || 42;
+$n = hex($n) if $n =~ m{\A 0x}imxs;
+say count_bits($n);
+say {*STDERR} count_bits_brute_force($n) if @ARGV > 0;
diff --git a/challenge-079/polettix/perl/ch-2.pl b/challenge-079/polettix/perl/ch-2.pl
new file mode 100644
index 0000000000..b400221493
--- /dev/null
+++ b/challenge-079/polettix/perl/ch-2.pl
@@ -0,0 +1,42 @@
+#!/usr/bin/env perl
+use 5.024;
+use warnings;
+use experimental qw< postderef signatures >;
+no warnings qw< experimental::postderef experimental::signatures >;
+use List::Util qw< min max >;
+
+sub trapped_rain_water (@N) {
+   my $max = 0;
+   my @maxes;
+
+   # first pass, left to right
+   for my $v (@N) {
+      $max = max($max, $v);
+      push @maxes, $max;
+   }
+
+   # second pass, right to left
+   my $retval = 0;
+   $max = 0;
+   for my $v (reverse @N) {
+      $max = max($max, $v);
+      my $w = min($max, shift @maxes);
+      $retval += $w - $v;
+   }
+   return $retval;
+}
+
+sub trapped_rain_water_dumb (@N) {
+   my $retval = 0;
+   for my $i (1 .. $#N - 1) {
+      my $max_left  = max(@N[0 .. $i]);
+      my $max_right = max(@N[$i .. $#N]);
+      my $min_max   = min($max_left, $max_right);
+      $retval += $min_max - $N[$i];
+   }
+   return $retval;
+}
+
+
+say trapped_rain_water_dumb(2, 1, 4, 1, 2, 5);
+say trapped_rain_water_dumb(3, 1, 3, 1, 1, 5);