Fibonacci distribution validator

Question

Related: Hello world!!! Fibonacci distribution

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.

• Shub: give some example IO
• Iszi: @Subhanker See the linked question for some example True cases.
• Justin: Relevant wikipedia article: en.wikipedia.org/wiki/…
• John Dvorak: is T/F or T/nil acceptable as well?
• Justin: 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.

Answer 1

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.

Live demo: http://golfscript.apphb.com/?c=OyIvMDU5OiIKOj8xIDJ7LkArLj8sPH1kbz8sPUB7LjQ4PFw1ODxefSwsQD0q

Answer 2

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.

• Justin: Does it handle multiple lines of text?
• John Dvorak: @Quincunx Chrome lets you copy/paste but not type newlines into the prompt input; haven't tested firefox.
• Justin: Guess I learn something new every day.
• Iszi: 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?
• John Dvorak: @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.

Answer 3

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

• John Dvorak: Isn't there... too much whitespace?
• Justin: @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.
• Iszi: 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.

Answer 4

Python 3, 105 characters

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

import sys
a=[0]*2
for b in open(sys.argv[1]).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=[0]*2
for b in open('s').read():a['/'<b<':']+=1
a,b=a
while a>0:a,b=b-a,a
print(b==1)

Answer 5

Jelly, (削除) 15 (削除ここまで) 14 bytes

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

Try it online!

How it works

ḟ,fɗØDẈẇ8LŻÆḞ¤ - 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:
 8 - 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

• Kevin Cruijssen: 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
• caird coinheringaahing: @KevinCruijssen Well, different builtins are shorter/better in different languages :P
• Kevin Cruijssen: 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. ;)

Answer 6

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

Answer 7

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.

• Chris Hayes: 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.

Answer 8

05AB1E, (削除) 15 (削除ここまで) (削除) 12 (削除ここまで) 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.

Try it online or verify a few more test cases.

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.

• caird coinheringaahing: 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
• Kevin Cruijssen: @cairdcoinheringaahing Woops, forgot to replace the code indeed. Thanks for noticing.
• ovs: You can replace ü2 with Œ (sublists) for -1. And i think d1Ý¢¤ÅFs.kd works as a more efficient 11-byter.
• Kevin Cruijssen: @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.

Answer 9

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

Answer 10

Husk, (削除) 23 (削除ここまで) (削除) 21 (削除ここまで) (削除) 19 (削除ここまで) (削除) 18 (削除ここまで) 16 bytes

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

€↑→L1İfe#€ṁsl·91L

Try it online!

€↑→L1İfe#€ṁsl·91L
€ # index of argument in list, if found, otherwise 0,
 ↑ # list: the first n elements
 →L1 # 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
 € 1 # present in list of
 ṁsl·9 # string from 0 to 9
 L # 2. length of input

• Razetime: -1 byte by changing '0'9
• Dominic van Essen: Great! Thanks! '0'9 did seem very clunky!
• Razetime: Does removing the compositions work correctly? Try it online!
• Dominic van Essen: @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...

Answer 11

K (ngn/k), (削除) 46 (削除ここまで) (削除) 40 (削除ここまで) (削除) 38 (削除ここまで) 32 bytes

• -12 bytes from golfing, -2 from @ngn's improvements

{~^(|+\)\[#x;|!2]?+/'~:\~"0:"'x}

Try it online!

• ~"0:"'x determine which characters in the input are digits
• +/'~:\ count the number of digits and non-digits
• ~^(...)[...]? determine if the above is in...
  • (|+\)\[#x;|!2] the pairs of fibonacci numbers

Answer 12

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

Answer 13

Japt v2.0a0, 20 bytes

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

Try it (Test cases appropriated from caird)