12
\$\begingroup\$

For this code golf, you will receive an input of a fibonacci sequence, that is, a normal Fibonacci sequence but with one number incorrect. See, the sequence is fibbing! Get it? :D

Your job is to find out which number is incorrect, and print the index (0-based) of that number.

For example:

Input : 1 1 2 9 5 8 13
Output: 3

Input : 8 13 21 34 55 80
Output: 5

Input : 2 3 5 5 13 21
Output: 3

Specifications:

  • The sequence may start at any number.
  • The first two numbers of the input will always be correct.
  • Shortest code (character count) wins.
\$\endgroup\$
  • 2
    \$\begingroup\$ Does the input have to be space-delimited or can commas be used as well? \$\endgroup\$ – Volatility Jun 23 '13 at 0:26
  • \$\begingroup\$ @Volatility Input is space-delimited. \$\endgroup\$ – Doorknob Jun 23 '13 at 0:33
  • \$\begingroup\$ The job is to find only the first such number, right? For example, if you started from the right in the first sequence you could think that 8 is incorrect because it doesn't equal 9+5 \$\endgroup\$ – Luis Mendo Jan 23 '15 at 16:40
  • \$\begingroup\$ @LuisMendo There will always be only one such number. \$\endgroup\$ – Doorknob Jan 23 '15 at 16:48
  • 1
    \$\begingroup\$ @LuisMendo Okay, let me reword that: There will always be exactly one way to change a single number that causes the sequence to be correct. \$\endgroup\$ – Doorknob Jan 23 '15 at 16:53

20 Answers 20

15
\$\begingroup\$

GolfScript (18 chars)

~]:^,,{^>3<~-+}?2+

The key to keeping this short is ? (find).

\$\endgroup\$
  • 15
    \$\begingroup\$ +1 for the portrait of Fibonacci ~]:^, \$\endgroup\$ – gnibbler Jun 26 '13 at 5:26
5
\$\begingroup\$

J, 30 23

(2+0 i.~2&}.=[:}:}:+}.)
\$\endgroup\$
5
\$\begingroup\$

Golfscript, 31 28 26 25 23

~]-1%~1{)\3$3$-=}do])\;
\$\endgroup\$
5
\$\begingroup\$

APL (19)

1+1⍳⍨(1↓1⌽k)≠2+/k←⎕

Explanation:

  • k←⎕: store user input in k
  • 2+/k: sum each pair of elements in k (i.e. 1 1 2 3 -> 1+1 1+2 2+3 -> 2 3 5)
  • 1↓1⌽k: rotate k to the right by 1 and then drop the first element (i.e. 1 1 2 3 -> 2 3 1)
  • : find the place where these lists are not equal
  • 1⍳⍨: find the location of the first 1 in this list (location of the incorrect number)
  • 1+: add 1 to compensate for the dropped element
\$\endgroup\$
4
\$\begingroup\$

K, 32

{2+*&~(n@n@x)=x+(n:{1_x,x 0})@x}
\$\endgroup\$
4
\$\begingroup\$

dc, 36 32

?zszsasb[lalbdsa+dsb=x]dsxxlzz-p

dc is a reverse-Polish calculator, so obviously you need to input the numbers in reverse order ;)

$ dc fib.dc <<< "999 13 8 5 3 2 1 1"
7
$ dc fib.dc <<< "999 1 1"
2
\$\endgroup\$
3
\$\begingroup\$

Javascript (69 68 61 60 55)

for(s=prompt(i=2).split(' ');s[i]-s[i-1]==s[i-2];i++);i

(60)

s=prompt(i=2).split(' ');for(;s[i]==+s[i-1]+ +s[i++-2];);--i


(61)

s=prompt(i=1).split(' ');for(k=+s[1];k+=+s[i-1],k==s[++i];);i

(68)

s=prompt(i=1).split(' ');for(k=+s[1];k+=+s[i-1],k==s[++i];);alert(i)

(69)

s=prompt(i=1).split(' ');k=+s[1];for(;k+=+s[i-1],k==s[++i];);alert(i)
\$\endgroup\$
2
\$\begingroup\$

JavaScript, 70

for(n=prompt().split(' '),i=n.length;i---2;)if(n[i-2]- -n[i-1]!=n[i])i
\$\endgroup\$
2
\$\begingroup\$

Ruby, 66

My first attempt at an (somewhat) complicated Ruby program:

p gets.split.map(&:to_i).each_cons(3).find_index{|a,b,c|a+b!=c}+2
\$\endgroup\$
  • \$\begingroup\$ You can save quite a few characters if you replace gets.split with $* (ARGV) to take input as command line arguments instead of on the standard input stream. The space between p and $* can then also be safely removed. \$\endgroup\$ – britishtea Jan 23 '15 at 18:38
2
\$\begingroup\$

Awk: 55

{for(i=3;i<=NF;i++)if($i+$(i-1)!=$(i+1)){print i;exit}}
\$\endgroup\$
1
\$\begingroup\$

Python, 74

a=map(int,raw_input().split())
i=2
while a[i-2]+a[i-1]==a[i]:i+=1
print i

I had this solution first, but Doorknob answered the question about the format of input right before I had time to post it:

Python, 66

a,b=input(),input()
i=2
while input()==a+b:a,b=b,a+b;i+=1
print i

Assumes newline separated input.

\$\endgroup\$
1
\$\begingroup\$

Matlab / Octave, 39 bytes

Thanks to Stewie Griffin for saving a byte! (- instread of ~=)

@(x)find(diff(x(2:end))-x(1:end-2),1)+1

This is an anonymous function that inputs an array and outputs a number.

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Python (90)

a=map(int,raw_input().split())
print min(i for i in range(2,len(a))if a[i-2]+a[i-1]!=a[i])
\$\endgroup\$
0
\$\begingroup\$

Mathematica 59

Because space-delimited input is required, StringSplit needs to be employed. The following assumes that the input is in the form of a string i.

s = StringSplit@i;
p = 3; While[s[[p - 1]] + s[[p - 2]] == s[[p]], p++]; p - 1
\$\endgroup\$
0
\$\begingroup\$

VB.net (77)

Assuming the numbers are already in a IEnumerable(Of Integer).

 Dim p = xs.Skip(2).TakeWhile(Function(c, i) c = xs.Skip(i).Take(2).Sum).Count + 2
\$\endgroup\$
0
\$\begingroup\$

Haskell, 48

f l=length$fst$span id$zipWith(==)l$1:scanl(+)1l
\$\endgroup\$
0
\$\begingroup\$

JS, 52B

for(s=prompt(i=2).split` `;s[i]-s[i-1]==s[i++-2];);i
\$\endgroup\$
0
\$\begingroup\$

Jelly, 11 bytes

ÆḞ€i$€In1i1

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Kotlin, 77 bytes

{val r=it.split(' ').map{it.toInt()}
var i=2
while(r[i]==r[i-1]+r[i-2])i++
i}

Beautified

{
    val r = it.split(' ').map { it.toInt() }
    var i=2
    while(r[i] == r[i-1] + r[i-2]) i++
    i
}

Test

var f:(String)->Int =
{val r=it.split(' ').map{it.toInt()}
var i=2
while(r[i]==r[i-1]+r[i-2])i++
i}

data class Test(val input: String, val output: Int)

val TESTS = listOf(
        Test("1 1 2 9 5 8 13", 3),
        Test("8 13 21 34 55 80", 5),
        Test("2 3 5 5 13 21", 3)
)
fun main(args: Array<String>) {
    val fails = TESTS
        .asSequence()
        .map { it to f(it.input) }
        .filter { (test, res) -> test.output != res }
        .toList()

    if (fails.isEmpty()) {
        println("Test Passed")
    } else {
        fails.forEach{ println(it)}
    }
}
\$\endgroup\$
0
\$\begingroup\$

QBIC, 31 bytes

_!_!{_!~a+b=c|a=b┘b=c┘s=s+1\_Xs

Explanation

_!_!           Ask the user for two umbers, assign them to 'a' and 'b'
{              DO
 _!            Ask for a third number (this will be assigned to 'c' on every iteration)
 ~a+b=c        IF the previous two terms add up to the third
 |a=b          THEN shift b into a, 
   ┘b=c            and c into b
   ┘s=s+1          increment s (starts as 3 in QBIC)
 \_Xs          ELSE quit, printing the step counter

I'm not quite sure if this is allowed; the sequence is entered one term at a time, and the program aborts on error, not after entering the entire sequence.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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