Make the list Fibonacci-like

Question

Related, but not dupe.

Challenge

A list of integers \$a_1, a_2, a_3, \dots, a_n\$ (\$ n ≥ 1 \$) is Fibonacci-like if \$a_i = a_{i-1} + a_{i-2}\$ for every \$i > 2\$. Note that every list that contains only 1 or 2 integers is Fibonacci-like.

For example, \$[1]\$, \$[6, 9]\$, \$[6, -4, 2, -2, 0, -2, -2, -4, -6, -10]\$, \$[7, -1, 6, 5, 11, 16, 27]\$ are Fibonacci-like lists.

Your task is, given a list, to determine the minimum amount of numbers that you have to remove from the list to make it Fibonacci-like.

For example, in \$[9, 7, -1, 6, 5, 2, 11, 16, 27]\$, you have to remove 2 numbers at minimum (\9ドル\$ and \2ドル\$) to transform the list into \$[7, -1, 6, 5, 11, 16, 27]\$, which is a Fibonacci-like list.

Input/Output

Input/output can be taken in any reasonable format, taking a list of numbers and returning the minimum number to complete the task.

Testcases:

[1, 2] -> 0
[5, 4, 9, 2] -> 1
[9, 7, -1, 6, 5, 2, 11, 16, 27] -> 2
[9, 9, 9, 9, 7, 9, 9, 9, 9, -1, 6, 5, 2, 11, 16, 27] -> 9

This is code-golf, so shortest answer (in bytes) wins!

• Nigel: You should include some more challenging test cases with multiple numbers to remove in a row. For example: [9,9,9,9, 7, 9,9,9,9, -1, 6, 5, 2, 11, 16, 27] => 9

Answer 1

JavaScript (ES6), 63 bytes

f=([v,...a],x,y)=>1/v?Math.min(v-x-y?1/0:f(a,y,v),1+f(a,x,y)):0

Try it online!

Commented

f = ( // f is a recursive function taking:
 [v, // v = next value from the input array
 ...a], // a[] = all remaining values
 x, // x = penultimate value, initially undefined
 y // y = previous value, initially undefined
) => //
1 / v ? // if v is defined:
 Math.min( // return the minimum of:
 v - x - y ? // 1) if both x and y are defined and v is not
 // equal to x + y:
 1 / 0 // force this one to fail by using +infinity
 : // else:
 f(a, y, v), // do a recursive call where v is used
 1 + // 2) increment the final result
 f(a, x, y) // and do a recursive call where v is removed
 ) // end of Math.min()
: // else:
 0 // stop the recursion

Answer 2

R, (削除) 90 (削除ここまで) 88 bytes

Edit: -2 bytes thanks to @Giuseppe.

\(v)max(which(sapply(sum(v|1):1,\(i)all(combn(v,i,\(x)any(diff(x)[-1]-head(x,-2)))))),0)

Attempt This Online!

Checking Fibonacci-likeness borrowed from @Dominic van Essen's answer to related challenge.

• Giuseppe: I had started this with using combn for index lists but this is much cleaner, and you even remembered to use FUN in combn!
• Giuseppe: maybe use all instead of min and you can get rid of the >0?
• pajonk: @Giuseppe, yes, you taught me well about the FUN in combn! And thanks for the golf!

Answer 3

Pip, 36 bytes

#g-MX#*:S H@>_-_=H H_FIFL*CP:GMZgMlg

Try It Online! -6 thanks to DLosc.

#g # Length of input
 - # Minus
 MX # Maximum of
 #*: # Map length over
 FL* # Flatten each of...
 CP: # Cartesian product of...
 MZ # Map over zipped
 gMl # Input filled with empty lists
 g # And input...
 G # Get all arguments (i.e. both)
 FI # Filter by...
 S H # Remove first and last items from
 - # Differences of 
 @>_ _ # Shifted value and value
 = # Equal to...
 H H_ # Remove last two items from value?

• emanresu A: @DLosc Some of that breaks on cases containing zeroes (should be 1)
• DLosc: Whoops--for some reason, I thought the numbers would always be positive even though that's not even true in the test case... Backing that change out and keeping the others gives 37 bytes, but there's something else wrong because that still returns 3, as does your current solution.
• emanresu A: @DLosc That's because I pulled a stupid and pasted unicode hyphens in instead of minuses lol. This works, but your 35 still breaks
• DLosc: It irks me that there doesn't seem to be a short way to get all ordered subsets... I may have to add a builtin. I found a method that's a bit ugly but saves one byte.

Answer 4

Vyxal, 19 bytes

ẏṗ'?ẏ⊍?$İ=ÞS ̄Ḣc;ÞgL

Try it Online!

Long, clunky, and likely to be outgolfed, but it's 1:01am so whatever lol.

Gets all lists of indices where removing the items at those positions gives a Fibonacci list and then gets the length of the smallest indice list.

• Jonathan Allan: There is some kind of bug in it since it returns 0 when given [1, 3, 6].

Answer 5

APL(Dyalog Unicode), ^{(削除) 31 (削除ここまで)} 30 bytes ^SBCS

≢⌊.-∘∊2(×ばつ∘⊃↓⍷+/∘,) ̈ ̈(⊢,, ̈)\

Try it on APLgolf!

(⊢,, ̈)\ gets all non-empty subsequences of the input (taken from Bubbler's tip).

2(×ばつ∘⊃↓⍷+/∘,)x If x is Fibonacci-like, this returns the length of x, otherwise 0.

≢⌊.-∘∊x computes the minimum value of length of input - some number in x.

Answer 6

Jelly, 14 bytes

ŒP+=ƭ3\Ạ$ƇṪLạL

A monadic Link that accepts the list of integers and yields the count of elements to remove.

Try it online! Or see the test-suite.

How?

ŒP+=ƭ3\Ạ$ƇṪLạL - Link: list of integers, A
ŒP - powerset of A -> all subsequences (Note: shortest to longest)
 Ƈ - filter keep those for which:
 $ - last two links as a monad:
 3\ - three-wise overlapping reduction by:
 ƭ - alternate between these two links:
 + - add -> first plus second element of the three-slice
 = - equals -> does that result equal the third element?
 Ạ - all truthy?
 Ṫ - tail -> (one of) the longest one(s)
 L - length
 L - length of A
 ạ - absolute difference

Answer 7

Burlesque, 51 bytes

saJ2.-{jR@f{L[2.>}f{J2CO)++~]j[-[-==}[~L[.-}{0it}IE

Try it online!

sa # Non-destructive length 
J # Dup
2.- # Longer than 2
{
 j # Reorder stack
 R@ # All subsequences
 f{ # Filter
 L[ # Length
 2.> # >2
 }
 f{
 J # Dup
 2CO # Pairwise 2s
 )++ # Map sum
 ~] # Drop last
 j # Reorder stack
 [-[- # Drop first twice
 == # Are equal
 }
 [~ # Last
 L[ # Length
 .- # Difference with original
}
{
 0it # Return 0
}IE # If else

Answer 8

05AB1E, (削除) 14 (削除ここまで) 13 bytes

æʒD\¦Å?}ζ‚€gÆ

-1 byte thanks to @ovs

Try it online or verify all test cases.

Explanation:

æ # Get the powerset of the (implicit) input-list
 ʒ # Filter to check if it's Fibonacci-like:
 D # Duplicate the current list
 \ # Pop one and get its forward differences
 ¦ # Remove the first item
 Å? # Check if the original list starts with this as sublist
 }ζ # After the filter: zip/transpose; swapping rows/columns, with " "
 # as implicit default filler for unequal length lists
 ‚ # Pair the (implicit) input-list with this matrix
 €g # Get the length of both
 Æ # Reduce by subtracting
 # (which is output implicitly as result)

Because we only care about the length, the zip/transpose with filler is used to our advantage to get the length of the longest truthy result of the filter (thanks to @ovs).

• ovs: æéʒ...}θ can be shortened to æʒ...}ζ.

Answer 9

Stax, 14 bytes

ü∞♀ÇjäεîVÖ₧"╥←

Run and debug it

Answer 10

K (ngn/k), 47 bytes

{(#x)-|/{(#x)**/(-2_x)=2_-':x}'(,()){x,x,'y}/x}

Try it online!

Wow this is a long one. I tried to emulate APL's (⊢,, ̈)\ with (,()){x,x,'y}/. Actually the whole code is almost a port of ovs's answer into ngn/k.

Answer 11

Factor + math.combinatorics, 81 bytes

[ dup all-subsets [ dup differences rest head? ] find-last nip [ length ] bi@ - ]

Try it online!