Continues from previous week.
Feel free to submit a merge request or open a ticket if you found any issues with this post. We highly appreciate and welcome your feedback.
For a quick overview, go through the original tasks and recap of the weekly challenge.
Task #1
For a good overview on how this recursive formulae works, you can look at this animated calculator.
This seemed like a straight forward question, a direct translation and implementation of the Ackermann function using the definition of the formulae given.
Well, some particpants (Veesh Goldman, Duane Powell, and Daniel Mantovani) discovered that direct formulae implementation will hit the bottleneck of the recursion starting from A(4, 2). Or as Veesh Goldman found out, “good luck getting (4, 2) to print, it’s 2 ** 65533..". Even using caching through storing pre-calculated values in hash or Memoize CPAN module would only help to a certain limit. Nevertheless, Dave Jacoby did some benchmark and found out that Memoize did make the code faster by 15x. Likewise, Yozen Hernandez‘s benchmark result showed a 216% improvement.
As Ackermann function is deeply recursive (more than 100 levels), you will get Deep recursion on anonymous subroutine warning. The workaround was to suppress the warning through no warnings pragma. Surprisingly, not sure why, not all submitted answers which translated the implementation directly hide this warning message.
Only the solution by Veesh Goldman, Michael Hamlin and Joelle Maslak managed to calculate the value of A(4, 2) within the reasonable time.
Some notable solutions that caught our attention. The recursion subroutine of Michael Hamlin direct formulate implementation certainly stand out compare to other participants. The code was short and concise although some will argue about the clarity and readability of the nested ternary operators. There were four techniques or tricks being used here. First, using state variable to cache the calculated value. Second, logical-or was used to check and retrieve cached value or to calculate and cache it. Third, the do block used here was to improve readability and group the ternary operators although the usage was optional here. Note that the do block here may seem like a subroutine but it’s not. And fourth, nested ternary or conditional operators to replace if-else statement.
sub _ack( $m, $n ) {
state @known;
$count++;
return $known[$m][$n] ||= do {
!$m ? $n + 1 :
!$n ? _ack($m - 1, 1) :
_ack($m - 1, _ack($m, $n - 1));
};
}
Another interesting Perl trick we found in Joelle Maslak‘s solution. Note the last two lines of the subroutine which was an implementation of a pure Perl tail call optimization. The goto &NAMED_SUBROUTINE form immediately exits the current subroutine and calls the named subroutine with new values of @_.
sub up_arrow($m, $num_arrows, $n) {
no warnings 'recursion';
return 1 unless $n;
return $m ** $n if $num_arrows == 1;
@_ = ($m, $num_arrows-1, up_arrow($m, $num_arrows, $n-1));
goto &up_arrow;
}
Task #2
In general, three approaches were used by the participants which includes parsing the URL manually, using a CPAN module, or use your own parser.
Most participants (Dave Jacoby, Daniel Mantovani, Ruben Westerberg, Laurent Rosenfeld, Jaldhar H. Vyas, Roger Bell West, Yozen Hernandez, Duncan C White, Feng Chang, Steven Wilson, and Andrezgz) solved this task using the manual way through regex. While there were many coding styles to express your regex, we found Laurent Rosenfeld‘s style short and sweet with all the necessary details.
$url =~ m{
^ # start of string
(\w+ (?: : \w+)?) # scheme, captured in $1
:// # literal ://
(?:(\w+:\w+)@)? # optional user info captured in $2
(\w+ (?: \.\w+)*) # host, captured in $3
(?: : (\d+) )? # optional port captured in $4
(/(?:\w+ (?:/\w+)*)?) # path, captured in $5
(?: \? (\w+=[\s\w]+))? # optional query in $6
(?: \# (\w+))? # optional fragment in $7
$ # end of string
}x;
Some CPAN modules used to parse the URL from the submitted answers includes Mojo::URL, URI, URI::Split, and URI::Fast.
Yozen Hernandez did a benchmark test to compare normal regular expression and Mojo::URL to parse the URL. Theoretically plain regular expression should be faster but the benchmark indicated that it’s way 255% faster than Mojo::URL. We assumed that there must be quite a lot of overhead with Mojo::URL.
Rate mojo from_scratch_regex
mojo 31204/s -- -72%
from_scratch_regex 110892/s 255% --
We believed this was the first time where three participants submitted their solutions through the implementation of a parser. Adam Russell done this through Parse::Yapp. E. Choroba took an alternative way using Marpa::R2. And lastly, Joelle Maslak solved this using Parse::RecDescent.
It may seemed over-engineered, but we love to see creative and alternative solutions and tricks using Perl for every weekly challenge.
If you’re interested in parsing in Perl, Adam Russell recommended that you should start with this book, Pro Perl Parsing.
Task #3
Compare to last week, we’ve more submissions this week for Perl 5 (Adam Russell, Jaldhar H Vyas, and the regular participant for this task, Joelle Maslak) and Perl 6 (Randy Lauen and again, Joelle Maslak).
If you want to learn how to use OAuth with Perl, go through all the submitted answers to learn how it was done.
In our previous challenge, Neil Bowers created a new CPAN module to solve this task. And this week, it was Jaldhar H. Vyas turn to create a whole CPAN module, WWW::Bhagavadgita (he will upload to CPAN later) as part of his solution. Similarly for Perl 6, Randy Lauen have created a Perl 6 package to solve this solution. Comparing Perl 5 with Moo and Perl 6 solution, it made us wonder if Perl 6 would be a good replacement or successor for web development these days?
And for those who haven’t try this optional task, feel free to give it a shot, either in Perl 5 or Perl 6.
Blog Posts
Additional details write-up by some of our regular participants for this week challenge.
(1) Up, up and Away! by Veesh Goldman.
Read how he optimized the Task #1 using different strategies in both Perl 5 and Perl 6.
(2) Ackerman, URL and Perl 6 by Arne Sommer.
The usual step-by-step code in Perl 6. As what he demonstrated, Perl 6 grammar is definitely a better choice than regular expression for parsing.
(3) Perl Weekly Challenge 017 Parsing with Parse::Yapp and using the Bhagavad Gita API by Adam Russell.
If you’re interested in parsing with Perl, read how he solved the Task #2 using a parser. The visualization of the grammar was a nice touch to the submitted solution.
(4) Thoughts on Perl Weekly Challenge 17 by Dave Jacoby.
Dave discovered that using Memoize CPAN module help to speed up Task #1 by 15x.
(5) Perl Weekly Challenge # 17: Ackermann Function and Parsing URLs by Laurent Rosenfeld.
Laurent showed us that you can replace if statement with multi subroutines. His Perl 6 solution on parsing URL was similar but different from Arne Sommer.
(6) Perl Weekly Challenge: Week 17 by Jaldhar H. Vyas.
Jaldhar solved all three tasks for this week challenge and again, his Perl 6 solutions on parsing URL was similar to Laurent‘s approach but slight minor difference.
(7) Multitudinal Uniform Resource Parsing – Perl weekly challenge, week 17 by Francis Whittle.
Similar to Laurent, Francis using multiple dispatch to solve Task #1 in Perl 6. Likewise, he was using the same Grammar approach to parse URL, just like Arne and Laurent.
(8) Perl Weekly Challenge 17: The Ackermann function by Yozen Hernandez.
Another benchmark comparison using Memoize CPAN module for Task #1.
(9) Perl Weekly Challenge 17: Writing Our Own URL Parser in Perl (But Should We?) by Yozen Hernandez.
Yet another benchmark result comparing regular expression against Mojo::URL CPAN module.
(10) Perl Weekly Challenge 017: Ackermann Function and URL Parsing by E. Choroba.
See how he related Erlang pattern matching to Perl 6 multi dispatch. Read his alternative approach on URL parsing compare to Adam Russell.