aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--challenge-079/bob-lied/README4
-rwxr-xr-xchallenge-079/bob-lied/perl/ch-1.pl44
-rwxr-xr-xchallenge-079/bob-lied/perl/ch-2.pl62
-rw-r--r--challenge-079/bob-lied/perl/lib/CountSetBit.pm55
-rw-r--r--challenge-079/bob-lied/perl/lib/TrappedRainWater.pm110
-rw-r--r--challenge-079/bob-lied/perl/t/CountSetBit.t35
-rw-r--r--challenge-079/bob-lied/perl/t/TrappedRainWater.t19
7 files changed, 327 insertions, 2 deletions
diff --git a/challenge-079/bob-lied/README b/challenge-079/bob-lied/README
index ac3ae94c19..026576bd98 100644
--- a/challenge-079/bob-lied/README
+++ b/challenge-079/bob-lied/README
@@ -1,3 +1,3 @@
-Solutions to weekly challenge 78 by Bob Lied.
+Solutions to weekly challenge 79 by Bob Lied.
-https://perlweeklychallenge.org/blog/perl-weekly-challenge-078/
+https://perlweeklychallenge.org/blog/perl-weekly-challenge-079/
diff --git a/challenge-079/bob-lied/perl/ch-1.pl b/challenge-079/bob-lied/perl/ch-1.pl
new file mode 100755
index 0000000000..ba9a661621
--- /dev/null
+++ b/challenge-079/bob-lied/perl/ch-1.pl
@@ -0,0 +1,44 @@
+#!/usr/bin/env perl
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#=============================================================================
+# ch-1.pl
+#=============================================================================
+# Copyright (c) 2020, Bob Lied
+#=============================================================================
+# Perl Weekly Challenge 079 Task #1 > Count Set Bits
+#=============================================================================
+# You are given a positive number $N.
+# Write a script to count the total numbrer of set bits of the binary
+# representations of all numbers from 1 to $N and
+# return $total_count_set_bit % 1000000007.
+# Example 1: Input = 4
+# 1 --> 001 Count = 1
+# 2 --> 010 Count = 1
+# 3 --> 011 Count = 2
+# 4 --> 100 Count = 1
+# TOTAL: 5
+
+use strict;
+use warnings;
+use v5.30;
+
+use feature qw/ signatures /;
+no warnings qw/ experimental::signatures /;
+
+use Getopt::Long;
+
+use lib "lib";
+use CountSetBit;
+
+sub Usage { "Usage: $0 N \t\t# N > 0" };
+
+my $Verbose = 0;
+GetOptions('verbose' => \$Verbose);
+
+my $N = shift;
+
+die Usage() unless $N && $N >= 0;
+
+my $task = CountSetBit->new($N);
+my $result = $task->run();
+say $result;
diff --git a/challenge-079/bob-lied/perl/ch-2.pl b/challenge-079/bob-lied/perl/ch-2.pl
new file mode 100755
index 0000000000..55500582d1
--- /dev/null
+++ b/challenge-079/bob-lied/perl/ch-2.pl
@@ -0,0 +1,62 @@
+#!/usr/bin/env perl
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#=============================================================================
+# ch-2.pl
+#=============================================================================
+# Copyright (c) 2020, Bob Lied
+#=============================================================================
+# Perl Weekly Challenge 079 Task #2 > Trapped Rain Water
+#=============================================================================
+# 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.
+# Example 1: Input: (2, 1, 4, 1, 2, 5)
+# As historgram: 5 #
+# 4 # #
+# 3 # #
+# 2 # # # #
+# 1 # # # # # #
+# _ _ _ _ _ _ _
+# 2 1 4 1 2 5
+# Concave units that can trap water:
+# 5 |
+# 4 | O O |
+# 3 | O O |
+# 2 | O | O _ |
+# 1 | _ | _ | |
+# _ _ _ _ _ _ _
+# 2 1 4 1 2 5
+# Answer: 6
+
+use strict;
+use warnings;
+use v5.30;
+
+use feature qw/ signatures /;
+no warnings qw/ experimental::signatures /;
+
+use Getopt::Long;
+
+use lib "lib";
+use TrappedRainWater;
+
+sub Usage { "Usage: $0 list-of-int-gt-0" };
+
+my $Verbose = 0;
+GetOptions('verbose' => \$Verbose);
+
+my $list = "@ARGV";
+
+die Usage() unless $list;
+
+$list =~ s/[(),]/ /g;
+my @list = split(" ", $list);
+
+die Usage() unless grep /\d+/, @list;
+
+my $task = TrappedRainWater->new(\@list);
+$task->show() if $Verbose;
+
+my $result = $task->run();
+$task->show() if $Verbose;
+say "-----\n", $result;
diff --git a/challenge-079/bob-lied/perl/lib/CountSetBit.pm b/challenge-079/bob-lied/perl/lib/CountSetBit.pm
new file mode 100644
index 0000000000..1733d4e676
--- /dev/null
+++ b/challenge-079/bob-lied/perl/lib/CountSetBit.pm
@@ -0,0 +1,55 @@
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#=============================================================================
+# CountSetBit.pm
+#=============================================================================
+# Copyright (c) 2020, Bob Lied
+#=============================================================================
+# Description:
+#=============================================================================
+
+package CountSetBit;
+
+use strict;
+use warnings;
+use v5.30;
+
+use feature qw/ signatures /;
+no warnings qw/ experimental::signatures /;
+
+require Exporter;
+our @ISA = qw(Exporter);
+our @EXPORT = qw();
+our @EXPORT_OK = qw();
+
+sub new($class, $n)
+{
+ $class = ref($class) || $class;
+ my $self = {
+ _n => $n,
+
+ _sum => 0,
+ };
+ bless $self, $class;
+ return $self;
+}
+
+# https://www.techiedelight.com/brian-kernighans-algorithm-count-set-bits-integer/
+sub run($self)
+{
+ $self->{_sum} += $self->_bitsOf($_) for ( 1 .. $self->{_n} );
+ return ( $self->{_sum} % 1000000007 );
+}
+
+sub _bitsOf($self, $n)a
+{
+ my $count = 0;
+
+ while ( $n > 0 )
+ {
+ $count++;
+ $n = $n & ($n-1);
+ }
+ return $count;
+}
+
+1;
diff --git a/challenge-079/bob-lied/perl/lib/TrappedRainWater.pm b/challenge-079/bob-lied/perl/lib/TrappedRainWater.pm
new file mode 100644
index 0000000000..34285e52b9
--- /dev/null
+++ b/challenge-079/bob-lied/perl/lib/TrappedRainWater.pm
@@ -0,0 +1,110 @@
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#=============================================================================
+# TrappedRainWater.pm
+#=============================================================================
+# Copyright (c) 2020, Bob Lied
+#=============================================================================
+# Description:
+#=============================================================================
+
+package TrappedRainWater;
+
+use strict;
+use warnings;
+use v5.30;
+
+use feature qw/ signatures /;
+no warnings qw/ experimental::signatures /;
+
+use List::Util qw/ max /;
+
+require Exporter;
+our @ISA = qw(Exporter);
+our @EXPORT = qw();
+our @EXPORT_OK = qw();
+
+sub new($class, $listref)
+{
+ $class = ref($class) || $class;
+ my $self = {
+ _list => $listref,
+ _numCol => scalar(@$listref),
+ _numRow => List::Util::max(@$listref),
+
+ _grid => [],
+ _trap => [],
+ };
+ bless $self, $class;
+
+ $self->_setup();
+ return $self;
+}
+
+sub _setup($self)
+{
+ my ($lst, $trap, $g, $numRow, $numCol) = @{$self}{ qw(_list _trap _grid _numRow _numCol) };
+
+ for ( my $r = 0; $r < $numRow ; $r++ )
+ {
+ for ( my $c = 0; $c < $numCol; $c++ )
+ {
+ $g->[$r][$c] = ( $lst->[$c] > $r ? '#' : ' ');
+ $trap->[$r][$c] = 0;
+ }
+ }
+}
+
+sub show($self)
+{
+ my ($g, $numRow, $numCol) = @{$self}{ qw(_trap _numRow _numCol) };
+ print " ";
+ for ( my $c = 0 ; $c < $numCol; $c++ )
+ {
+ print "[$c]";
+ }
+ print "\n";
+ for ( my $r = $numRow - 1; $r >= 0 ; $r-- )
+ {
+ print "[$r] ";
+ say " ", join(' ', @{$g->[$r]}), " ";
+ }
+
+}
+
+sub _hasWall($self)
+{
+ my $sawWall = 0;
+ my $g = $self->{_grid};
+ my $trap = $self->{_trap};
+
+ for (my $r = 0 ; $r < $self->{_numRow} ; $r++ )
+ {
+ # Increment count if there's a wall on the left
+ for (my $c = 0 ; $c < $self->{_numCol} ; $c++ )
+ {
+ if ( $g->[$r][$c] eq '#' ) { $sawWall = 1 }
+ elsif ( $sawWall ) { $trap->[$r][$c]++ }
+ }
+ # Increment count if there's a wall on the right
+ $sawWall = 0;
+ for (my $c = $self->{_numCol}-1 ; $c >= 0 ; $c-- )
+ {
+ if ( $g->[$r][$c] eq '#' ) { $sawWall = 1 }
+ elsif ( $sawWall ) { $trap->[$r][$c]++ }
+ }
+ $sawWall = 0;
+ }
+ # Assume there's a wall on the bottom (all list values are > 0).
+}
+
+sub run($self)
+{
+ $self->_hasWall();
+
+ my @flattrap = map { ref eq 'ARRAY' ? @$_ : $_ } @{$self->{_trap}};
+
+ my $holdsWater = grep { $_ == 2 } @flattrap;
+ return $holdsWater;
+}
+
+1;
diff --git a/challenge-079/bob-lied/perl/t/CountSetBit.t b/challenge-079/bob-lied/perl/t/CountSetBit.t
new file mode 100644
index 0000000000..8652b033d5
--- /dev/null
+++ b/challenge-079/bob-lied/perl/t/CountSetBit.t
@@ -0,0 +1,35 @@
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#
+#===============================================================================
+# FILE: CountSetBit.t
+# DESCRIPTION: Unit test for CountSetBit
+#===============================================================================
+
+use strict;
+use warnings;
+use v5.30;
+
+use Test2::V0;
+use CountSetBit;
+
+my $csb = CountSetBit->new(4);
+isa_ok( $csb, [ qw(CountSetBit) ], "Constructor" );
+
+is( CountSetBit->new( 1)->run(), 1, "1");
+is( CountSetBit->new( 2)->run(), 2, "2");
+is( CountSetBit->new( 3)->run(), 4, "3");
+is( CountSetBit->new( 4)->run(), 5, "4");
+is( CountSetBit->new( 5)->run(), 7, "5");
+is( CountSetBit->new( 6)->run(), 9, "6");
+is( CountSetBit->new( 7)->run(), 12, "7");
+is( CountSetBit->new( 8)->run(), 13, "8");
+is( CountSetBit->new( 9)->run(), 15, "8");
+is( CountSetBit->new(10)->run(), 17, "8");
+is( CountSetBit->new(11)->run(), 20, "8");
+is( CountSetBit->new(12)->run(), 22, "8");
+is( CountSetBit->new(13)->run(), 25, "8");
+is( CountSetBit->new(14)->run(), 28, "8");
+is( CountSetBit->new(15)->run(), 32, "8");
+is( CountSetBit->new(16)->run(), 33, "8");
+
+done_testing();
diff --git a/challenge-079/bob-lied/perl/t/TrappedRainWater.t b/challenge-079/bob-lied/perl/t/TrappedRainWater.t
new file mode 100644
index 0000000000..c3d419b298
--- /dev/null
+++ b/challenge-079/bob-lied/perl/t/TrappedRainWater.t
@@ -0,0 +1,19 @@
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#
+#===============================================================================
+# FILE: TrappedRainWater.t
+# DESCRIPTION: Unit test for TrappedRainWater
+#===============================================================================
+
+use strict;
+use warnings;
+use v5.30;
+
+use Test2::V0;
+use TrappedRainWater;
+
+my $trw = TrappedRainWater->new(2, 1, 4, 1, 2, 5);
+
+isa_ok( $trw, [ qw(TrappedRainWater) ], "Constructor" );
+
+done_testing();
generated by cgit (git 2.34.1) at 2026-07-02 13:57:57 +0000