# 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
– Shub
Jan 19, 2014 at 7:13
• @Subhanker See the linked question for some example True cases.
– Iszi
Jan 19, 2014 at 7:13
• Relevant wikipedia article: en.wikipedia.org/wiki/… Jan 19, 2014 at 7:33
• is T/F or T/nil acceptable as well? Jan 19, 2014 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. Jan 21, 2014 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? Jan 19, 2014 at 8:22
• @Quincunx Chrome lets you copy/paste but not type newlines into the prompt input; haven't tested firefox. Jan 19, 2014 at 8:23
• Guess I learn something new every day. Jan 19, 2014 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, 2014 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. Jan 20, 2014 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? Jan 19, 2014 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. Jan 19, 2014 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, 2014 at 0:29

# 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 written in file with name s

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


# Jelly, 15 14 bytes

ḟ,fɗØDẈẇ⁸LŻÆḞ¤


Try it online!

## How it works

ḟ,fɗØDẈẇ⁸LŻÆḞ¤ - Main link. Takes a string S on the left
ØD         - Yield "0123456789"; D
ɗ           - Group the previous three atoms together as a dyad, f(S, D):
ḟ              -   Remove digits from S
f            -   Remove non-digits from S
,             -   Pair these two
Ẉ        - Lengths of each in the pair; [a, b]
⁸      -   Yield S
L     -   Take its length, L
Ż    -   [0, 1, 2, ..., L]
ÆḞ  -   nth Fibonacci number for each
ẇ       - Sublist exists?
This returns 1 if the left argument ([a, b]) is a contiguous sublist
of the right argument (the list of Fib numbers), i.e.
a and b are both Fibonacci numbers, and a immediately precedes b

• It's funny how I've saved a byte by changing the first portion of my program to what you had in your first iteration, yet you saved a byte by changing the first portion of your program to what I had in my first iteration. xD Oct 27, 2020 at 16:10
• @KevinCruijssen Well, different builtins are shorter/better in different languages :P Oct 27, 2020 at 16:11
• Ik, ik. It's just funny how we've basically swapped the implementation of our first parts to both save a byte in our languages. ;) Oct 27, 2020 at 16:12

## 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


# 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. Jan 19, 2014 at 11:55

# 05AB1E, 1512 11 bytes

d1Ý¢¤ÅFs.kd


-3 bytes by taking inspiration from @cairdCoinheringaahing's initial Jelly program
-1 byte thanks to @ovs

Input as a list of characters.

Explanation:

d            # Check for each character in the (implicit) input-list if it's a
# non-negative (>=0) integer (1 if truthy; 0 if falsey)
1Ý          # Push the list [0,1]
¢         # Count them in the list of truthy/falsey results
¤        # Push the last count, without popping the pair itself
ÅF      # Pop and push a list of Fibonacci numbers <= this count
s     # Swap so the pair is at the top of the stack
.k   # Get the index of the pair (as sublist) in the Fibonacci list
# (or -1 if this pair isn't a sublist)
d  # Check that this index is non-negative (>=0), thus that it was found
# (after which the result is output implicitly)


Unfortunately the Fibonacci sequence contains two 1s, otherwise we could have saved two bytes by changing s.kd to sÅ¿ (check whether it ends with the pair), which fails for single-digit inputs.

• You've still got the 15-byter as your code underneath the header. Also, very nice! 05AB1E's ÅF for sure gives it an advantage over Jelly here Oct 27, 2020 at 16:10
• @cairdcoinheringaahing Woops, forgot to replace the code indeed. Thanks for noticing. Oct 27, 2020 at 16:11
• You can replace ü2 with Œ (sublists) for -1. And i think d1Ý¢¤ÅFs.kd works as a more efficient 11-byter.
– ovs
Oct 27, 2020 at 16:36
• @ovs Ah, the ü2 to Œ is indeed an obvious one. As for the second, I didn't even knew the .k worked that way. I thought it was to get the index of a list in a list of lists, but apparently it also works to get the index of a list (as sublist) in a flattened list. TIL, and thanks for the -1. Oct 27, 2020 at 17:38

# 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.

# Husk, 23211918 16 bytes

Edit: -1 byte, then -2 more bytes, thanks to Razetime

€↑→L¹İfe#€ṁsŀ9¹L


Try it online!

€↑→L¹İfe#€ṁsŀ9¹L
€                       # index of argument in list, if found, otherwise 0,
↑                      # list: the first n elements
→L¹                   # n = length of input +1
İf                 # of the list of fibonacci numbers
e                # argument: 2-element list
#               # 1. number of elements in input that are
€    ¹         # present in list of
ṁsŀ9          # string from 0 to 9
L        # 2. length of input

• -1 byte by changing '0'9 Oct 28, 2020 at 9:01
• Great! Thanks! '0'9 did seem very clunky! Oct 28, 2020 at 9:09
• Does removing the compositions work correctly? Try it online! Oct 28, 2020 at 9:38
• @Razetime Indeed, it seems to work fine. Thanks! I'm surprised it works, but I guess that (by luck in this case) the argument types don't allow ambiguous interpretation... Oct 28, 2020 at 9:42

# K (ngn/k), 4640 38 bytes

• -6 bytes from golfing
• -2 bytes from @ngn's improvements
{(+\|:)/[(#x)>+/;!2]~+/'~:\=/"/9"<\:x}


Try it online!

Uses the "while" version of / to generate the next fibonacchi step, comparing it against the length of the input. Checks to see that the largest fibonacchi numbers match the number of non-digits and digits.

## 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".

# Japt v2.0a0, 20 bytes

Êô@MgXÃã de[\D\d]£èX


Try it (Test cases appropriated from caird)