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:
abccdddaaaaa 01001110000011111111
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):
#!/usr/bin/perl -w use strict; while(<DATA>){ chomp; print "$_\n" if is_fibo($_); } sub is_fibo { # deleted } __DATA__ Pass abaabbbaaaaabbbbbbbbaaaaaaaaaaaaa a aa aaaaa @!%%+++***** Isee Fail aaaaaaaaaaaa abbcccddddd ab OUTPUT: Pass abaabbbaaaaabbbbbbbbaaaaaaaaaaaaa a aa aaaaa @!%%+++***** Isee
Have the appropriate amount of fun.
|
---|
Replies are listed 'Best First'. | |
---|---|
Re: (Golf) Fibonacci Strings
by MeowChow (Vicar) on Jul 20, 2001 at 01:18 UTC | |
Re: (Golf) Fibonacci Strings
by japhy (Canon) on Jul 20, 2001 at 02:12 UTC | |
Re: (Golf) Fibonacci Strings
by danger (Priest) on Jul 20, 2001 at 09:29 UTC | |
by japhy (Canon) on Jul 20, 2001 at 16:07 UTC | |
(MeowChow - holy $#!@) Re: (Golf) Fibonacci Strings
by MeowChow (Vicar) on Jul 21, 2001 at 23:17 UTC | |
Re: (Golf) Fibonacci Strings
by chipmunk (Parson) on Jul 20, 2001 at 02:19 UTC | |
Re: (Golf) Fibonacci Strings
by abstracts (Hermit) on Jul 20, 2001 at 00:35 UTC | |
by dragonchild (Archbishop) on Jul 20, 2001 at 01:43 UTC | |
by MeowChow (Vicar) on Jul 20, 2001 at 01:55 UTC | |
Re: (Golf) Fibonacci Strings
by MeowChow (Vicar) on Jul 21, 2001 at 01:38 UTC | |
Re: (Golf) Fibonacci Strings
by lhoward (Vicar) on Jul 19, 2001 at 23:09 UTC | |
by danger (Priest) on Jul 19, 2001 at 23:17 UTC | |
Re: (Golf) Fibonacci Strings
by dragonchild (Archbishop) on Jul 20, 2001 at 16:38 UTC |