The Obfuscated Fibonacci; Or, a Curious Connection in Computation 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

Search: