Don't ask to ask, just ask  
PerlMonks 
(Golf) Fibonacci Stringsby danger (Priest) 
on Jul 19, 2001 at 22:23 UTC ( [id://98178] : perlmeditation . print w/replies, xml )  Need Help?? 
The challenge is produce a routine that returns true if a given string consists entirely of groups of repeating characters such that the number of repititions in each successive group increases in a Fibonacci sequence. What does that mean? Well, with a couple of caveats to follow, it means that strings like the following are so called fibonacci strings:
The Fibonacci series is defined as a sequence of numbers, starting with 0,1 and the next number in the series is obtained by adding the last two existing numbers. So a short series is: 0,1,1,2,3,5,8,13,21,34. (to any mathematicians out there, sorry if I'm playing a little fast and/or loose with the definition). What we are looking for, are strings that contain repeated characters in groups  and the lengths of these groups form such a series. In the first example above we have: a(1), b(1), c(2), d(3), a(5); and the sequence 1,1,2,3,5 is a fibonacci series (we can even say that we have an implied leading zero, ie, say, zero 'x' characters at the start of the string). Caveats: For the purposes of this exercise we assume a simple single line string (no newlines). The leading zero is assumed for any series. Each group of repeating characters *must* be distinct from its neighbors (even though we can break down: 'aaaaaaa' into 'a', 'a', 'aa', 'aaa', this does not count as a fibonacci string. Since any two different characters trivially represents such a series, we will only count strings that have a minumum of 3 groups (at least 4 characters). The routine should return true only if the string represents such a fibonacci series from beginning to end, otherwise it should return a false value. The series must start with 0,1,1 (0 is implied). An example test script (and its output) follows (sans any actual is_fibo() code):
Have the appropriate amount of fun.
Back to
Meditations
