Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

(Golf) Fibonacci Strings

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

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$_[0]=~/^|(.)\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$-[1]})(?!\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.