(Golf) Fibonacci Strings

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
[download]

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
[download]

Have the appropriate amount of fun.

Comment on (Golf) Fibonacci Strings Select or Download Code

Replies are listed 'Best First'.
Re: (Golf) Fibonacci Strings by MeowChow (Vicar) on Jul 20, 2001 at 01:18 UTC
I really enjoyed this golf - there are so many unique approaches one could take. Here's one at 78: `sub is_fibo { push@_,length$&while$_[0]=~/^\|(.)\1*/g;{@_>3?pop==$_[-1]+$_[-2]?redo +:0:pop==1} }` [download] MeowChow s aamecha.s a..a\u$&owag.print	[reply] [d/l]
Re: (Golf) Fibonacci Strings by japhy (Canon) on Jul 20, 2001 at 02:12 UTC
Here's my solution. It doesn't run your exact test program, because it uses `$_`. It's 74 chars. Oh, I also obfuscated it. `sub fib { $_=pop;$==$}=0;{s&^(.)\1{$=}(?!\1)&&&&($==($}+=++$=)-$=,redo)}''eq$_&& +$=>1 }` [download] _____________________________________________________ Jeff `japhy` Pinyan: Perl, regex, and perl hacker. `s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;`	[reply] [d/l]
Re: (Golf) Fibonacci Strings by danger (Priest) on Jul 20, 2001 at 09:29 UTC
I found all the solutions interesting (even those that let 'ab' slide through). For my own entry, I wanted to do it all in one regex and succeeded but the initial cost was nearly 90 characters. After a dinner and beer break I managed to simplify it out (I was using an extra grouping that wasn't needed), and was then able to use a bit of japhy's techniques to squeeze down to tie at 74: `sub is_fibo { pop=~/^(?{$x=$y=0})(?:(.)(??{"\Q$1"x$y})(?!\1)(?{$y=($x+=++$y)-$y})){3 +,}$/ }` [download] Even passes 'strict' in 5.6.1, but not in 5.00503. Of course, there is the distinct possibility that my brain is mushier than I think from the beer and I'm missing some obvious failure mode with this one. Update: Doh! And along comes japhy to casually make a putt I completely missed for a 2 stroke savings ... probably only used one hand too :-)	[reply] [d/l]
Re: Re: (Golf) Fibonacci Strings by japhy (Canon) on Jul 20, 2001 at 16:07 UTC
In the name of Golf, shave out the `?:` `pop=~/^(?{$x=$y=0})((.)(??{"\Q$2"x$y})(?!\2)(?{$y=($x+=++$y)-$y})){3,} +$/` [download] _____________________________________________________ Jeff `japhy` Pinyan: Perl, regex, and perl hacker. `s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;`	[reply] [d/l]
(MeowChow - holy $#!@) Re: (Golf) Fibonacci Strings by MeowChow (Vicar) on Jul 21, 2001 at 23:17 UTC
Fourty-two chars. One regex. I'm stunned. `pop=~/^((.)(??{"\Q$2"x$-[1]})(?!\2)){3,}$/` [download] MeowChow s aamecha.s a..a\u$&owag.print	[reply] [d/l]
Re: (Golf) Fibonacci Strings by chipmunk (Parson) on Jul 20, 2001 at 02:19 UTC
This isn't close to the shortest solution, but I think it's interesting so I'm posting it anyway. :) `sub is_fibo { my$m=pop;$_=$m=~s/^(.)(?!\1)//for$x,$y; $m=~s/\G(.)\1*/($z=length$&)==$x+$y\|\|return;$x=$y;$y=$z/ge; }` [download]	[reply] [d/l]
Re: (Golf) Fibonacci Strings by abstracts (Hermit) on Jul 20, 2001 at 00:35 UTC
Hello, Do I need to explain how it works? Aziz,,, #!/usr/bin/perl -w use strict; print `cat $0`; print "\nOUTPUT:\n"; while(<DATA>){ chomp; print "$_\n" if is_fibo($_); } sub is_fibo { my ($str,$r,$s) = (shift, -1, 0); ($r,$s) = ($s,$r+$s+1) while $str =~ s#^((.)\2{$s})## and $str !~ /^\Q$2\E/; return not length $str; } __DATA__ Pass abaabbbaaaaabbbbbbbbaaaaaaaaaaaaa a aa aaaaa @!%%+++*** Isee Fail aaaaaaaaaaaa abbcccddddd ab OUTPUT: Pass abaabbbaaaaabbbbbbbbaaaaaaaaaaaaa a aa aaaaa @!%%+++*** Isee ab	[reply]
Re: Re: (Golf) Fibonacci Strings by dragonchild (Archbishop) on Jul 20, 2001 at 01:43 UTC
This is just a golfing of abstract's neat concept. It comes in at 80 chars. Unfortunately, it allows 'ab' to pass, which it shouldn't. I tried to fix it, but couldn't find a way around the s/^((.)\2{$s})// quotemeta thing. `($_,$r,$s)=(pop,-1,0);($r,$s)=($s,$r+$s+1)while s#^((.)\2{$s})##&&!/^\Q$2\E/;!$_`	[reply] [d/l]
Re: Re: Re: (Golf) Fibonacci Strings by MeowChow (Vicar) on Jul 20, 2001 at 01:55 UTC
This will fail for strings like: `abaa0`. That's why the length test was needed. MeowChow s aamecha.s a..a\u$&owag.print	[reply]
Re: (Golf) Fibonacci Strings by MeowChow (Vicar) on Jul 21, 2001 at 01:38 UTC
68 chars, "ab"-compliant too... `sub is_fibo { $_=pop;$n=0;{/^\|(.)\1/g?$n^($c=length$&)?0:($n=1-$c+pos,redo):$n>2} }` [download] update: 66 chars after deleting an artifact from my previous solution `sub is_fibo { $_=pop;$n=1;{/(.)\1/g?$n^($c=length$&)?0:($n=1-$c+pos,redo):$n>2} }` [download] update2: 65 chars, and no more ugly `$&` usage... `sub is_fibo { $_=pop;$n=0;$p=1;{/(.)\1/g?pos^$n?0:($n+=$p+1,$p=pos,redo):$p>2} }` [download] update3*: 61 chars, after incorporating ideas from danger's regex and a new method of counting fibonacci's: `sub is_fibo { $n=0;pop=~/^((.)(??{"\Q$2"x$n})(?!\2)(?{$n=-++$n+pos})){3,}$/ }` [download] MeowChow s aamecha.s a..a\u$&owag.print	[reply] [d/l] [select]
Re: (Golf) Fibonacci Strings by lhoward (Vicar) on Jul 19, 2001 at 23:09 UTC
Shouldn't "ab" pass? I see your sample is_fibo function failing it (based on the output you give above). Also, I recomend adding the following string: "abaabbbaaaaabbbbbbbbaaaaaaaaaaaa" to the test which should be not fibo.	[reply]
Re: Re: (Golf) Fibonacci Strings by danger (Priest) on Jul 19, 2001 at 23:17 UTC
Note, the caveats section of my post where I explicitly rule out any two character sequences as being trivial sequences. So 'ab' fails. As for 'abaabbbaaaaabbbbbbbbaaaaaaaaaaaa', yes it should fail and could be added, but I wasn't going for an exhaustive test suite, merely a few examples to get started with.	[reply]
Re: (Golf) Fibonacci Strings by dragonchild (Archbishop) on Jul 20, 2001 at 16:38 UTC
I really hope people will post explanations for their code. I don't understand a lot of the regex's, but really would.	[reply]


"be consistent"
	PerlMonks