The Weekly Challenge 079

So after three months of doing The Weekly Challenge, I decided it was also about time to doing blogging properly rather than just write a README.md file. I didn't want to host my own blog, so after reading Dave's Blogging for Perl post mentioning dev.to, I'm using this.

On to the tasks.

TASK #1 › Count Set Bits

Following Perl's TIMTOWTDI philosophy I presented two solutions.

The first solution goes through the numbers, converts each value to a binary value (using sprintf '%b') and counts the number of ones (using tr///) in the string.

The second solution has a binary counter that starts at 1, and doubles each run. I then go though the numbers, and add to the counter if value & binary is true.

It turns out that the first number is significantly faster. In counting to 10 million on my i7 NUC, the first solution took 19s while the second solution took 79s seconds.

I'm not really sure why we needed to calculate the modulus of 1000000007, but I did that anyway.

Examples

» ./ch1a.pl 3
4 % 1000000007 = 4

» ./ch1a.pl 4
5 % 1000000007 = 5

» time ./ch1a.pl 100000000
1314447116 % 1000000007 = 314447109

real    0m19.881s
user    0m19.878s
sys     0m0.000s

» time ./ch1b.pl 100000000
1314447116 % 1000000007 = 314447109

real    1m19.270s
user    1m19.251s
sys     0m0.005s

TASK #2 › Trapped Rain Water

Solution

This is very similar to the second task in Challenge 075 in fact I copied the printing histogram code from that task, and added to it to display the fills with ·s.

The logic is also similar to the previous task too. For this task, I worked through each column, except the first and last ones (any water in those would fall off the side). For each column, I calculated how many units of water it could hold using the following method:

1. Calculate the maximum of the columns to the left.
2. Calculate the maximum of the columns to the right.
3. Take the minimum of the above two values.
4. Subtract the height. The units of water is the solution (if > 0)

Examples

» ./ch2.pl 2 1 4 1 2 5
5           #
4     # · · #
3     # · · #
2 # · # · # #
1 # # # # # #
- - - - - - -
  2 1 4 1 2 5

Result is 6

» ./ch2.pl 3 1 3 1 1 5
5           #
4           #
3 # · # · · #
2 # · # · · #
1 # # # # # #
- - - - - - -
  3 1 3 1 1 5

Result is 6