15
\$\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\$
7
  • 2
    \$\begingroup\$ Does the input have to be space-delimited or can commas be used as well? \$\endgroup\$
    – Volatility
    Jun 23, 2013 at 0:26
  • \$\begingroup\$ @Volatility Input is space-delimited. \$\endgroup\$
    – Doorknob
    Jun 23, 2013 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, 2015 at 16:40
  • \$\begingroup\$ @LuisMendo There will always be only one such number. \$\endgroup\$
    – Doorknob
    Jan 23, 2015 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, 2015 at 16:53

23 Answers 23

15
\$\begingroup\$

GolfScript (18 chars)

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

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

\$\endgroup\$
1
  • 15
    \$\begingroup\$ +1 for the portrait of Fibonacci ~]:^, \$\endgroup\$
    – gnibbler
    Jun 26, 2013 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, 70

for(n=prompt().split(' '),i=n.length;i---2;)if(n[i-2]- -n[i-1]!=n[i])i
\$\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\$
3
\$\begingroup\$

Awk: 55

{for(i=3;i<=NF;i++)if($i+$(i-1)!=$(i+1)){print i;exit}}
\$\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\$
1
  • \$\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, 2015 at 18:38
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\$

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\$
1
\$\begingroup\$

JS, 52B

for(s=prompt(i=2).split` `;s[i]-s[i-1]==s[i++-2];);i
\$\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
1
\$\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\$
1
\$\begingroup\$

Raku, 45 bytes

{first :k,?*,(@($/=.words)Z-($0,$1,*+*...*))}

Try it online!

$/ = .words stores the words (numbers) of the input string into the pattern-match variable $/. Conveniently, the elements of that variable can be accessed with $0, $1, etc, so $0, $1, * + * ... * forms the Fibonacci sequence starting with the first two input numbers. The input numbers and the Fibonacci sequence are then zipped together using the subtraction operator (Z-), forming a new sequence which is nonzero only at the place where the two series are different. Then first :k, ?*, ... returns the index (thanks to the :k parameter) of that location; ?* is an anonymous predicate function that coerces its argument to a boolean value.

\$\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\$

Haskell, 48

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

Jelly, 11 bytes

ÆḞ€i$€In1i1

Try it online!

\$\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\$
0
\$\begingroup\$

Pxem, 0 bytes (content) + 52 bytes (filename).

  • Filename (escaped): \002._._X.w.c.t.v.m.v.+._.c.t.v.m.v.-\001.r.x.n.d.a\001.+.vX.a

Usage

  • From stdin
  • Must be an actual FIBonacci sequence
  • Each integer are separated with blank characters

With comments

XX.z
# Initial stack: F(i-1), F(i-2), i
# i is initially 2
.a\002._._XX.z
# while :; do
.aX.wXX.z
  # to: (F(i-1)+F(i-2)), i, F(i-1)
  .a.c.t.v.m.v.+XX.z
  # input is F(i)
  # to: F(i), (F(i-1)+F(i-2)), i, F(i-1), F(i)
  .a._.c.t.v.m.vXX.z
  # to 0, abs(F(i)-F(i-1)-F(i-2)), i, F(i-1), F(i)
  # if (pop!=pop); then
  .a.-\001.r.xXX.z
    # print pop; exit; fi
    .a.n.d.aXX.z
  # to F(i), F(i-1), (i+1)
  .a\001.+.vXX.z
# done
.aX.a

Try it online!

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

Husk, 5 bytes

δV≠İf

Try it online!

You know it's a good day when you get to use decorV in an answer.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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