Hacker News new | past | comments | ask | show | jobs | submit login
The Obfuscated Fibonacci; Or, a Curious Connection in Computation (statusfailed.com)
30 points by lelf on Feb 10, 2015 | hide | past | web | favorite | 4 comments



I wish they would mention L-systems in highschools instead of just labeling the Fibonacci sequence as "magic" that happens to occur in nature. It could spare young students a lot of numerological woo.


I think the obfuscation is in the order of application of the rules. My uninformed procedure would be:

    a
    ab (rule 1)
    aa (rule 2 - we have to apply rule 2 before rule 1 again, or we'll never get past rule 1, just a followed by arbitrarily many b's)
    abab (rule 1 - applies to all instances of a)
    aaaa (rule 2 - applies to all instances)
    abababab (rule 1)
    aaaaaaaa (rule 2)
So since that doesn't generate what the article does, lets try applying each rule only once to the string per round:

    a
    ab (rule 1)
    aa (rule 2)
    aba (rule 1)
    aaa (rule 2)
    abaa (rule 1)
    aaaa (rule 2)
    abaaa (rule 1)
    aaaaa (rule 2)
That's not getting me to the article sequence either. Let's try anchoring the single substitution on the right hand side of the string:

    a
    ab (rule 1)
    aa (rule 2)
    aab (rule 1)
    aaa (rule 2)
    aaab (rule 1)
    aaaa (rule 2)
Nope, doesn't help. Hmph. Please send me a clue.


Apply both rules at the same time. a - > (a)(b) -> (ab)(a), etc


I actually did a related proof of sorts for a @1haskelladay puzzle a while ago. http://rextester.com/BQA14775




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: