 "be consistent" PerlMonks

### (Golf) Fibonacci Strings

by danger (Priest)
 on Jul 19, 2001 at 22:23 UTC 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:

```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
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\$_=~/^|(.)\1*/g;{@_>3?pop==\$_[-1]+\$_[-2]?redo
+:0:pop==1}
}
```   MeowChow
s aamecha.s a..a\u\$&owag.print```
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
}

_____________________________________________________
Jeff japhy Pinyan: Perl, regex, and perl hacker.
s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;

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
+,}\$/
}

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 :-)

In the name of Golf, shave out the ?:
```pop=~/^(?{\$x=\$y=0})((.)(??{"\Q\$2"x\$y})(?!\2)(?{\$y=(\$x+=++\$y)-\$y})){3,}
+\$/

_____________________________________________________
Jeff japhy Pinyan: Perl, regex, and perl hacker.
s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;

(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\$-})(?!\2)){3,}\$/
```   MeowChow
s aamecha.s a..a\u\$&owag.print```
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;
}
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
```
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/;!\$_

This will fail for strings like: abaa0. That's why the length test was needed.
```   MeowChow
s aamecha.s a..a\u\$&owag.print```
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}
}
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}
}
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}
}
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,}\$/
}
```   MeowChow
s aamecha.s a..a\u\$&owag.print```
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.

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.

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.

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlmeditation [id://98178]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (5)
As of 2023-03-24 05:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Which type of climate do you prefer to live in?

Results (60 votes). Check out past polls.

Notices?