Take the 2-minute tour ×
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.

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 –  Subhanker Jan 19 at 7:13
    
@Subhanker See the linked question for some example True cases. –  Iszi Jan 19 at 7:13
    
Relevant wikipedia article: en.wikipedia.org/wiki/… –  Quincunx Jan 19 at 7:33
    
is T/F or T/nil acceptable as well? –  Jan Dvorak Jan 19 at 7:52
2  
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. –  Quincunx Jan 21 at 4:47
show 12 more comments

8 Answers

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

share|improve this answer
add comment

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.

share|improve this answer
    
Does it handle multiple lines of text? –  Quincunx Jan 19 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 at 8:23
    
Guess I learn something new every day. –  Quincunx Jan 19 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 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 at 4:07
show 5 more comments

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

share|improve this answer
    
Isn't there... too much whitespace? –  Jan Dvorak Jan 19 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. –  Quincunx Jan 19 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 at 0:29
add comment

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

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 wroted 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)
share|improve this answer
add comment

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
4  
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 at 11:55
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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.