Perl Weekly Challenge 079

ch-1.cxx

#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;
}

ch-1.p

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.

ch-1.pl

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";
}

ch-2.pl

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";
}