# Fibonacci distribution validator

Create a program that returns True if a given input meets the following specifications, and False otherwise:

• The count of numeric characters (0-9) in the input matches a Fibonacci number.
• The count of non-numeric characters !(0-9) in the input matches the Fibonacci number immediately preceding the count of numeric characters.

• Your program must use the proper Fibonacci sequence, per OEIS - that is, the Fibonacci sequence must start with 0, 1, 1, 2, ...
• If the numerics or non-numerics count is 1, the following must occur:
• Numerics 1: Non-numeric count of 0 or 1 should be handled as True - all others False.
• Non-Numerics 1: Numerics count of 1 or 2 should be handled as True - all others False.
• Input may be taken however you like, but the program must be capable of handling any arbitrary text.
• True/False are not case-sensitive, and can be substituted with 1/0 or T/F.
• You may only hard-code up to two Fibonacci numbers.
• Output may only be True/False or 1/0 or T/F. Any additional text or visible errors generated is unacceptable.
• give some example IO – Shubanker Jan 19 '14 at 7:13
• @Subhanker See the linked question for some example True cases. – Iszi Jan 19 '14 at 7:13
• Relevant wikipedia article: en.wikipedia.org/wiki/… – Justin Jan 19 '14 at 7:33
• is T/F or T/nil acceptable as well? – John Dvorak Jan 19 '14 at 7:52
• Ugh, you changed the challenge. Now you say that the fibonacci sequence starts at 0 and give specific cases for 0. The other question that you linked to forbids 0, so I assumed the same. – Justin Jan 21 '14 at 4:47

# Golfscript, 36

:?1 2{.@+.?,<}do?,=@{.48<\58<^},,@=*


Explanation:

• :? stores the input into ?.
• 1 2{.@+.?,<}do computes the last two fibonacci numbers until it hits the input length. The block reads: "duplicate the top, rotate the third value to the top, add them, duplicate the top, get the input, get its length, compare".
• ?,= compares the last computed fibonacci number to the input length.
• @ brings the input to the top
• {.48<\58<^}, filters out only digits. The block reads "is the ASCII value below 48 XOR below 58?"
• ,@= compares the filtered string length to the lower fibonacci number (count of digits)
• * merges the two comparisons to provide a single boolean value.

# Javascript, 92 88 86 characters

t=prompt()
for(b=c=1;c<t[l='length'];c=a+b)a=b,b=c


I hope you don't mind I've hard-coded the the first three Fibonacci numbers.

• Does it handle multiple lines of text? – Justin Jan 19 '14 at 8:22
• @Quincunx Chrome lets you copy/paste but not type newlines into the prompt input; haven't tested firefox. – John Dvorak Jan 19 '14 at 8:23
• Guess I learn something new every day. – Justin Jan 19 '14 at 8:24
• According to OEIS, the first three Fibonacci numbers are 0, 1, 1. In any case, you should only need to hard-code the first two - why did you do three? – Iszi Jan 20 '14 at 0:25
• @Iszi you are right - a didn't need initialisation. As for why do I start at 1,2,3 - the poster of the initial challenge didn't accept 1 as immediately preceding 1. – John Dvorak Jan 20 '14 at 4:07

# Python - 128 125

import re
def v(s):
l=len(re.sub("\d","",s));L=len(s)-l;a,b=1,2
while a<L:
if a==l and b==L:
print 1;return
b,a=a+b,b
print 0


Really hope there is no problem with hardcoding the first few fibonacci numbers

• Isn't there... too much whitespace? – John Dvorak Jan 19 '14 at 8:39
• @JanDvorak those four spaces were all tabs, so they were counted as 1 char per four spaces. I could alternate tabs and spaces, doing that now. – Justin Jan 19 '14 at 8:45
• Looks like I should have been a bit more clear about hard-coding the numbers. Of course you'll need to prime the sequence, but you should only need the first two to do it. – Iszi Jan 20 '14 at 0:29

## Perl, 92

$_=join"",<>;@_=1;$d=s/\d//g;push@_,$t=$_[-1]+$_[-2]while$t<$d;print$t==$d&$_[-2]==y///c?1:0


Usage:

cat fib-test
print "Hello world%s"%("!"*int(3.141592653589793238462643383279502884197169399375105820))

perl -e '$_=join"",<>;@_=1;$d=s/\d//g;push@_,$t=$_[-1]+$_[-2]while$t<$d;print$t==$d&$_[-2]==y///c?1:0' fib-test
1


# Python 3

## (105 characters)

Script file name is passed to the program through the command line

import sys
a=[0]*2
a,b=a
while a>0:a,b=b-a,a
print(b==1)


## (87 characters)

Script must be wroted in file with name 's'

a=[0]*2
a,b=a
while a>0:a,b=b-a,a
print(b==1)


# Java - 147 145

boolean v(String s){int l=s.replaceAll("\\d","").length(),L=s.length()-l,a=1,b=2,c;while(a<L){if(a==l&&b==L)return 0<1;c=b;b+=a;a=c;}return 0>1;}


I'd say this is not bad for Java.

Edit: Thanks to Chris Hayes for suggesting 0>1 for false and 0<1 for true.

• As long as we're using 1==0 to save on characters, you could use 0<1 in place of true, and 0>1 for false. – Chris Hayes Jan 19 '14 at 11:55

# APL, 34 chars/bytes*

{n←+/⍵∘.=⍞∊⎕D⋄n≡+\∘⌽⍣{≥/+/⊃⍺n}⍵}⍳2


Expects the input string on standard input and prints either 0 or 1 as required. ⎕IO must be set to 0 (the default is implementation-dependent.)

Ungolfed

s←⍞                ⍝ read input string
d←s∊⎕D             ⍝ vector with 1 for each digit, 0 for each non-digit in s
n←+/0 1∘.=d        ⍝ 2-vector with number of non-digits and number of digits in s
f←+\∘⌽             ⍝ a function that computes a fibonacci step (f 2 3 → 3 5)
t←f⍣{≥/+/⊃⍺n}0 1   ⍝ apply f repeatedly, starting with 0 1, until we get two fibonacci
⍝   terms whose sum is ≥ the length of the input string (sum of n)
n≡t                ⍝ return 1 if the fibonacci terms match the no. of digits and non-digits


Examples

      {n←+/⍵∘.=⍞∊⎕D⋄n≡+\∘⌽⍣{≥/+/⊃⍺n}⍵}⍳2
%~n01234
1
{n←+/⍵∘.=⍞∊⎕D⋄n≡+\∘⌽⍣{≥/+/⊃⍺n}⍵}⍳2
x'48656C6C6F20776F726C642121'||'!'
1
{n←+/⍵∘.=⍞∊⎕D⋄n≡+\∘⌽⍣{≥/+/⊃⍺n}⍵}⍳2
[72 101 108 108 111 32 119 111 114 108 100 33 {.}2*]''+
1
{n←+/⍵∘.=⍞∊⎕D⋄n≡+\∘⌽⍣{≥/+/⊃⍺n}⍵}⍳2
What?12345
0


⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
*: APL can be written in its own (legacy) single-byte charset that maps APL symbols to the upper 128 byte values. Therefore, for the purpose of scoring, a program of N chars that only uses ASCII characters and APL symbols can be considered to be N bytes long.

## Ruby, 85

d=-(n=(i=\$<.read).gsub(/\d/,'').size)+i.size
a=b=1;while b<d;b=a+a=b end;p b==d&&a==n


Takes input either on STDIN or as a filename argument.

Output is either "true" or "false".