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.
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.
» ./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
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
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:
- Calculate the maximum of the columns to the left.
- Calculate the maximum of the columns to the right.
- Take the minimum of the above two values.
- Subtract the height. The units of water is the solution (if > 0)
» ./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