
mhx
Enthusiast
/ Moderator
Oct 26, 2001, 2:44 PM
Post #5 of 10
(68047 views)
|
Jim, I'm really sorry if my solution sickens you. I didn't want that. So here's my explanation for the code, I hope that makes it a bit clearer. First of all, I've added some line breaks and whitespace to the code to make it a bit more readable:
sub _ { my $a = shift; local $_ = shift; defined || return print "$a\n"; $_ < 2 ? _( $a.$_, @_ ) : do { $_=3*$_+91; _( $a.chr, @_ ) for $_..$_+2 } } _( '', <> =~ /(\d)/g ) Next, I'm going to give the subroutine a cool name (although I personally find the underscore is really cool as a subroutine name) and replace the ?: section by an if/else section, just to make it even more readable:
sub phone { my $a = shift; local $_ = shift; defined || return print "$a\n"; if( $_ < 2 ) { phone( $a.$_, @_ ) } else { $_=3*$_+91; phone( $a.chr, @_ ) for $_..$_+2 } } phone( '', <> =~ /(\d)/g ) Now, one can almost immediately see that this is a recursive algorithm. It's started in the last line by calling phone() with an empty string and all digits entered by the user. <> reads in one line and the regular expression transforms that line into a list containing all digits. The heart of that algorithm is obviously the phone() subroutine. In that subroutine, $a is always the string that is assembled to contain the phonobulized version of the phone number. In the first call, $a will be the empty string and $_ will be the first of the digits:
my $a = shift; local $_ = shift; I'll explain the next line later and first go to the if/else section:
if( $_ < 2 ) { phone( $a.$_, @_ ) } else { $_=3*$_+91; phone( $a.chr, @_ ) for $_..$_+2 } Depending on whether the first digit is less than 2 or not, two different blocks need to be executed. In case of a 0 or 1, we only need to add the digit to the string and enter the next recursion level by calling the phone() subroutine again with the new string and all remaining digits. (Remember we shifted the string and the first digit off @_, so it holds all remaining digits.) But if the first digit is 2 or greater, we need to replace it by three consecutive letters. Fortunately enough, the characters are sorted in the ASCII set, and since the lowercase letters start at 97 (a) and our digit ($_) is at least 2, the three letters of interest start at (91+3*$_). We now call phone() again recursively from within a loop over the ASCII values of the three letters. The new string passed to the next recursion level is a concatenation of the old string and the character that corresponds to the current ASCII code stored in $_, which is the default argument to the chr function. Now, when does the recursion stop? As we've seen, with each level of recursion there's one digit shifted off the list. So at a certain level, there's no more digits and thus $_ will become undef. That's when the following line becomes interesting:
defined || return print "$a\n"; Since $_ is also the default argument to defined, the return statement will be executed when we've run out of digits. But before returning from the subroutine, we have to print out the string we've assembled, and this string is still stored in $a. As we don't call phone(), the recursion has reached its end. If you're familiar with recursion, this shouln't be too hard to understand. If you're not it may be, uh, quite hard. To answer your other questions: I read your post shortly after I got up. Then I went shopping with my mom and that's where I made up most of the algorithm. It was clear to me from the beginning that it had to be recursive. I also had the idea of using $_=3*$_+91 to get the letters corresponding to a digit while being in town. Back home, coding those ideas took about 15 minutes and compressing the code took another 15 minutes. So, considering that I spent a total of 30 minutes thinking about the solution, you can say that it took me about an hour to come up with the above code. I'm pretty sure there's still room for improvements. I'd guess about 120 characters should be possible. However, I hope you find the above explanations helpful and I also hope you won't be crying to much as you'll see that there's really nothing special about the code. -- Marcus
s$$ab21b8d15c3d97bd6317286d$;$"=547269736;split'i',join$,,map{chr(($*+= ($">>=1)&1?-hex:hex)+0140)}/./g;$"=chr$";s;.;\u$&;for@_[0,2];print"@_,"
|