Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.
share|improve this question
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:… – Justin Jan 19 '14 at 7:33
is T/F or T/nil acceptable as well? – Jan 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<^},,@=*


  • :? 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:

share|improve this answer

Javascript, 92 88 86 characters


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

share|improve this answer
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. – Jan 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. – Jan Dvorak Jan 20 '14 at 4:07

Python - 128 125

import re
def v(s):
 while a<L:
    if a==l and b==L:
     print 1;return
 print 0

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

share|improve this answer
Isn't there... too much whitespace? – Jan 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



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
share|improve this answer

Python 3

(105 characters)

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

import sys
for b in open(sys.argv[1]).read():a['/'<b<':']+=1
while a>0:a,b=b-a,a

(87 characters)

Script must be wroted in file with name 's'

for b in open('s').read():a['/'<b<':']+=1
while a>0:a,b=b-a,a
share|improve this answer

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.

share|improve this answer
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*


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


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


[72 101 108 108 111 32 119 111 114 108 100 33 {.}2*]''+

*: 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.

share|improve this answer

Ruby, 85

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.