Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Perl Weekly Challenge 079
#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;
}
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.
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";
}
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";
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment