Perl Weekly Challenge 002
Below is my take on each of the two parts to challenge 002. The problem statements are short and are included in the first comment of the code. The code blocks shown link to GitHub Gists.
As described this can be done using sprintf(). I was slightly conflicted at first to simply use sprintf() but it's a core function of the language! Probably it's not in the spirit of these challenges to simply import a CPAN module but a core function should be fair game.
If I needed to do a base conversion for real project work I probably wouldn't write my own function, several modules already exist that provide this functionality, and I definitely wouldn't use recursion! This being a programming challenge and an opportunity to try out things for fun I took the approach of (1) using recursion to loop over the number being converted and (2) use chr() and ord(). chr() and ord() are convenient little functions that are the opposites of each other. ord() will return the numeric value of a character and chr() will return the character represented by a number. What these characters and numbers represent is determined by the "character set". W3.org has a comprehensive article on the subject for anyone that wants to dive deeper into the details of character sets. For our purposes we really just need to know that ord('a') is 97 and it follows then that chr(97) is 'a'. [Note: this information has only ever been useful to me in computer science class homework, programming challenges, and job interviews! I believe these sorts of tricks were more commonly used in practice back in the days when statically typed languages such as C made frequent use of char primitives.]
I've always had a strong distaste for string literals and numeric literals appearing in code out without any context. Although this code is short enough to not really need them I stick to having some use constants to define some sample values for testing purposes as well as the base in the challenge. Also, to make practical use of the knowledge that ord('a') is 97 we define an offset of 87. Why is that? Well, we want 'a' to represent 10 and so ord('a') — 87 is 10, ord('b') — 87 is 11, ..., ord('y') is 34. In this way we are able to use the letters a — y as needed in the challenge statement.
The two conversion functions use recursion and are described next.
- given a number return a string representing that number
In this function we check to see if we've reached our base case of the number being 0. In this case we return an empty string. Otherwise we calculate the number mod 35, the base we are converting from. If the result of that calculation is a digit 0-9 then we are done, otherwise we use chr() to find the right representation a-y. The recursive step is to reduce the number by doing an integer division by 35 (in Perl we need to use the int() function to achieve this otherwise we would get a floating point result) and calling the function itself again. This repeats, with each successive digit added to the accumulating result until the division result is 0. This procedure is working from right to left and that is why the line return $r .= $value; builds by adding the return string on the left and not the right, to show the resulting digits in the correct left to right order. The uc() function is used to return everything in upper case, even though we work in lower case, by way of lc(). I just thought upper case looks better when printed in the terminal window. :)
Here the number is split into an array of individual digits. We shift off and inspect each digit. This means that we are now working left to right. If the digit is a numerical digit 0-9 then we can leave it alone but if it is a letter then we use ord() to convert it to a number. We then take this and build up our return value via recursion. Since we used shift() the array of digits is shorted at each step, the recursion terminates when we only have a single number left. The line
return $value * (BASE ** ($length-1)) + base35_to_base10($digits);
takes the value and multiples it by the appropriate power of 35 and adds up the result recursively. $length is the length of the array of remaining digits and since we are working left to right it corresponds to the correct power of 35 to use with the shifted digit.
Recursion In Perl
Using recursion like this in Perl is kind of fun but in practice it is generally frowned upon. Why is that? Mostly because for each recursive call the perl interpreter needs to keep track of the previous state of the program and that can become very memory intensive. By default Perl will warn about recursive loops that repeat more than a fixed limit. That limit is, the last I checked, 100 which is pretty conservative. On modern hardware it should take much more than than to exhaust Perl's memory and crash. If you want to play around with recursion in Perl and not get warned about it you can set the following:
no warnings 'recursion';
I found out a while back that I saw Perl start to fall apart around 5000 recursive calls when running this code: https://github.com/adamcrussell/n-link .
Finally, there are ways to compile a perl interpreter with a higher fixed limit but I've never heard of anyone needing or wanting to do that.