Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Explain one liner for fibonacci

by suhailck (Friar)
on Dec 22, 2009 at 09:27 UTC ( #813835=perlquestion: print w/ replies, xml ) Need Help??
suhailck has asked for the wisdom of the Perl Monks concerning the following question:

Hi All,

Anyone please explain this one liner to generate 20 fibonacci number series.

perl -le'$==1,(1x$_)=~/(^)(1|11\1)*(?{$=++})^/,print$=for 0..20'

Thanks in Advance~

Comment on Explain one liner for fibonacci
Download Code
Re: Explain one liner for fibonacci
by JavaFan (Canon) on Dec 22, 2009 at 09:41 UTC
    It exploits the fact the regexp will always fail. Note that the (?{$=++}) always succeeds, adding 1 to $= each time it's executed. The trailing ^ cause the pattern to fail. The (^)(1|11\1)* will always succeed, but in such a way the optimizer doesn't spoil things.

    Now, because (1|11\1) eats either 1 or 2 characters, and then tries the trick on the rest of the pattern, the number of ways a string of length n can fail is:

    F(n) = F(n-1) + F(n-2)
    which is the formula for Fibonacci numbers.

    Also note that $==1 just means $= = 1.

Re: Explain one liner for fibonacci
by ambrus (Abbot) on Dec 22, 2009 at 12:07 UTC

    Code is from Re^2: The Oldest Plays the Piano. As this is the second time someone challenges my fibonacci number generators, I'm starting to suspect I'm secretly writing these questions (under alternate names) to drive attention to my obfus and gain me more XP, and then forget about them so they don't weigh my conscience.

    JavaFan already gave a good explanation about how the code works. The (?{$=++}) part in the regular expression counts how many times the part of the regular expression before that can match. Then the ^ anchor after that forces the expression to fail and backtrack trying another way to match the string.

    There's one more thing to detail, and that's why the backreference is needed. If you just try this simple variant, you'll see it won't work.

    perl -le'$==1,(1x$_)=~/^(1|11)*(?{$=++})^/,print$=for 0..20'
    That's because the regular expression engine somehow memoizes where the (1|11)* subpattern could match, so it won't try to backtrack endlessly. The easiest way to fool the regular expression engine and make it do exponential amount of work would be to use a (??{}) or (?(?{})) expression. Because these features can run arbitary perl code and change whether the regular expression matches or not, there's no way the regex engine can correctly optimize them. Thus, this works.
    perl -le'$==1,(1x$_)=~/^(1|11(??{}))*(?{$=++})^/,print$=for 0..20'

    The \1 backreference (which matches the empty string here) is just a different way to do the same.

    Update: Allow me some more explanation.

    One more trick I didn't mention is that the regex is not anchored to the end of the string, so it counts matches to a prefix of the string only. It might be easier to understand the code if the match was anchored with a $ like this.

    perl -le'$==0,(1x$_)=~/^(1|11(??{}))*$(?{$=++})^/,print$=for 0..20'
    Note that in the original code, the $==1 is needed to add one to the number of matches so we get Fibonacci numbers, here it's not needed. As an example, the following shows all the ways /^(1|11)*$/ could match the string "111111".
    1 (1)(1)(1)(1)(1)(1) 2 (1)(1)(1)(1)(1 1) 3 (1)(1)(1)(1 1)(1) 4 (1)(1)(1 1)(1)(1) 5 (1)(1)(1 1)(1 1) 6 (1)(1 1)(1)(1)(1) 7 (1)(1 1)(1)(1 1) 8 (1)(1 1)(1 1)(1) 9 (1 1)(1)(1)(1)(1) 10 (1 1)(1)(1)(1 1) 11 (1 1)(1)(1 1)(1) 12 (1 1)(1 1)(1)(1) 13 (1 1)(1 1)(1 1)
    And here's how we get one less if the end of the regex is not anchored, so it can match only a prefix of the string.
    1 (1)(1)(1)(1) 2 (1)(1)(1) 1 3 (1)(1)(1 1) 4 (1)(1) 1 1 5 (1)(1 1)(1) 6 (1)(1 1) 1 7 (1) 1 1 1 8 (1 1)(1)(1) 9 (1 1)(1) 1 10 (1 1)(1 1) 11 (1 1) 1 1 12 1 1 1 1

    Update: see also Explain Fibonacci one-liner ?? for a duplicate of the same question and more answers.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://813835]
Approved by SilasTheMonk
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (11)
As of 2014-12-18 13:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (51 votes), past polls