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

Additional Rules:

• 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
alert(c==t[l]&b==t.match(/\d/g)[l])


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

# Python 3, 105 characters

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

import sys
a=*2
for b in open(sys.argv).read():a['/'<b<':']+=1
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=*2
for b in open('s').read():a['/'<b<':']+=1
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]
¤ - Create a nilad:
⁸      -   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 – Kevin Cruijssen Oct 27 '20 at 16:10
• @KevinCruijssen Well, different builtins are shorter/better in different languages :P – caird coinheringaahing Oct 27 '20 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. ;) – Kevin Cruijssen Oct 27 '20 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. – Chris Hayes Jan 19 '14 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 – caird coinheringaahing Oct 27 '20 at 16:10
• @cairdcoinheringaahing Woops, forgot to replace the code indeed. Thanks for noticing. – Kevin Cruijssen Oct 27 '20 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 '20 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. – Kevin Cruijssen Oct 27 '20 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 – Razetime Oct 28 '20 at 9:01
• Great! Thanks! '0'9 did seem very clunky! – Dominic van Essen Oct 28 '20 at 9:09
• Does removing the compositions work correctly? Try it online! – Razetime Oct 28 '20 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... – Dominic van Essen Oct 28 '20 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)