Merge pull request #2390 from adamcrussell/master

solutions for challenge 079

5 files changed, 154 insertions, 0 deletions

diff --git a/challenge-079/adam-russell/blog.txt b/challenge-079/adam-russell/blog.txt
new file mode 100644
index 0000000000..4d2077411c
--- /dev/null
+++ b/challenge-079/adam-russell/blog.txt
@@ -0,0 +1 @@
+http://www.rabbitfarm.com/cgi-bin/blosxom/2020/09/27#pwc079
diff --git a/challenge-079/adam-russell/cxx/ch-1.cxx b/challenge-079/adam-russell/cxx/ch-1.cxx
new file mode 100644
index 0000000000..a1e03c7076
--- /dev/null
+++ b/challenge-079/adam-russell/cxx/ch-1.cxx
@@ -0,0 +1,21 @@
+#include <iostream>
+
+int count_bits(int n){
+    int set_bits = 0;
+    for(int i = 1; i <= n; i++){
+        int x = i;
+        while(x > 0){
+            int b = x & 1;
+            set_bits += b;
+            x = x >> 1;
+        }
+    }
+    return set_bits;
+}
+
+int main(int argc, char** argv){
+    int set_bits = count_bits(3);
+    std::cout << set_bits << " % 1000000007 = " << set_bits % 1000000007 << std::endl;
+    set_bits = count_bits(4);
+    std::cout << set_bits << " % 1000000007 = " << set_bits % 1000000007 << std::endl;
+}
\ No newline at end of file
diff --git a/challenge-079/adam-russell/perl/ch-1.pl b/challenge-079/adam-russell/perl/ch-1.pl
new file mode 100644
index 0000000000..71fd852755
--- /dev/null
+++ b/challenge-079/adam-russell/perl/ch-1.pl
@@ -0,0 +1,28 @@
+use strict;
+use warnings;
+##
+# You are given a positive number $N.
+# Write a script to count the total number of set bits 
+# of the binary representations of all numbers 
+# from 1 to $N and return $total_count_set_bit % 1000000007.
+##
+sub count_bits{
+    my($n) = @_;
+    my $total_count_set_bit = 0;
+    for my $x (1 .. $n){
+        while($x){
+            my $b = $x & 1;
+            $total_count_set_bit++ if $b;
+            $x = $x >> 1;
+        }        
+    }
+    return $total_count_set_bit;
+}
+
+
+MAIN:{
+    my $count = count_bits(4);
+    print "$count % 1000000007 = " . $count % 1000000007 . "\n";
+    $count = count_bits(3);
+    print "$count % 1000000007 = " . $count % 1000000007 . "\n";
+}
\ No newline at end of file
diff --git a/challenge-079/adam-russell/perl/ch-2.pl b/challenge-079/adam-russell/perl/ch-2.pl
new file mode 100644
index 0000000000..d19efc845a
--- /dev/null
+++ b/challenge-079/adam-russell/perl/ch-2.pl
@@ -0,0 +1,78 @@
+use strict;
+use warnings;
+##
+# You are given an array of positive numbers @N.
+# Write a script to represent it as Histogram Chart 
+# and find out how much water it can trap.
+##
+sub print_histogram{
+    my($values) = @_;
+    my @sorted_values = sort @{$values};
+    my $max = $sorted_values[-1];
+    my $x = $max;
+    while($x >= 1){
+        print "$x ";
+        for my $h (@{$values}){
+            print "# " if $h >= $x;
+            print "  " if $h < $x;
+        }
+        print "\n";
+        $x--;
+    }
+    print "- " x (@{$values} + 1);
+    print "\n  " . join(" ", @{$values}) ."\n";
+}
+
+sub get_bucket_end{
+    my($values, $i) = @_;
+    for my $j (($i+1) .. (@{$values} - 1)){
+        if($values->[$j] >= $values->[$i]){
+            return $j;
+        }
+    }
+    return -1;
+}
+
+sub find_buckets{
+    my($values) = @_;
+    my @buckets;
+    for(my $i=0; $i < @{$values}; $i++){
+        my $bucket_start = $i;
+        my $bucket_end = get_bucket_end($values, $i);
+        if($bucket_end > 0 && ($bucket_end - $bucket_start) >=1){
+            push @buckets, [$bucket_start, $bucket_end];
+            $i = $bucket_end - 1;
+        }
+    } 
+    return @buckets; 
+}
+
+sub volume{
+    my($buckets, $values) = @_;
+    my $volume = 0;
+    for my $bucket (@{$buckets}){
+        my $bucket_start = $bucket->[0];
+        my $bucket_end = $bucket->[1];
+        my $min_wall = ($values->[$bucket_start] >= $values->[$bucket_end])? $bucket_end: $bucket_start;
+        for my $i ($bucket_start + 1 .. $bucket_end - 1){
+            $volume += ($values->[$min_wall] - $values->[$i]);
+        }
+    }
+    return $volume;
+}
+
+MAIN:{
+    my @A = (2, 1, 4, 1, 2, 5);
+    my @buckets = find_buckets(\@A);
+    my $volume = volume(\@buckets, \@A);
+    print_histogram(\@A);
+    print "Volume: $volume\n";
+    
+    print "\n";
+    
+    @A = (3, 1, 3, 1, 1, 5);
+    @buckets = find_buckets(\@A);
+    $volume = volume(\@buckets, \@A);
+    print_histogram(\@A);
+    print "Volume: $volume\n";
+}
\ No newline at end of file
diff --git a/challenge-079/adam-russell/prolog/ch-1.p b/challenge-079/adam-russell/prolog/ch-1.p
new file mode 100644
index 0000000000..b5fd8a5c04
--- /dev/null
+++ b/challenge-079/adam-russell/prolog/ch-1.p
@@ -0,0 +1,26 @@
+set_bits(N, X):-
+    set_bits(N, 0, X).
+set_bits(0, X, X).    
+set_bits(N, X_Acc, X):-    
+    B is N /\ 1,
+    X0 is X_Acc + B,
+    N0 is N >> 1,
+    set_bits(N0, X0, X).
+
+count_bits(N, X) :-
+    count_bits(N, 0, X).
+count_bits(0, X, X).  
+count_bits(N, X_Acc, X):-     
+    set_bits(N, X0),
+    X1 is X0 + X_Acc,
+    N0 is N - 1,
+    count_bits(N0, X1, X).
+
+bit_count:-
+    count_bits(4, X),
+    X0 is X mod 1000000007,
+    writef("%d \\% 1000000007 = %d\n", [X, X0]),
+    count_bits(3, Y),
+    Y0 is Y mod 1000000007,
+    writef("%d \\% 1000000007 = %d\n", [Y, Y0]),
+    halt.
\ No newline at end of file