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!

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.

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?

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.

Answer 5

APL(Dyalog Unicode), ³¹ 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).

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!