Nth Differences

Question

In math, one way to figure out what the type of a given relation (linear, quadratic, etc) is to calculate the differences. To do so you take a list of y values for which the gap between the correspondent x values is the same, and subtract each one from the number above it, creating a list of numbers one shorter then the previous list. If the resultant list is completely composed of identical numbers, then the relation has a difference of 1 (it is linear). If they are not identical, then you repeat the process on the new list. If they are now identical, the relation has a difference of 2 (it is quadratic). If they are not identical, you simply continue this process until they are. For example, if you have the list of y values [1,6,15,28,45,66] for incrementally increasing x values:

First Differences:

1
6   1-6  =-5
15  6-15 =-9
28  15-28=-13
45  28-45=-17
66  45-66=-21

Second differences:

-5 
-9  -5+9  =4
-13 -9+13 =4
-17 -13+17=4
-21 -17+21=4

As these results are identical, this relation has a difference of 2

Your Task:

Write a program or function that, when given an array of integers as input, returns the difference of the relation described by the array, as explained above.

Input:

An array of integers, which may be of any length>1.

Output:

An integer representing the difference of the relation described by the input.

Test Cases:

Input                            => Output
[1,2,3,4,5,6,7,8,9,10]           => 1
[1,4,9,16,25,36]                 => 2
[1,2,1]                          => 2 (when there is only one value left, all values are automatically identical, so the largest difference an array can have is equal to the length of the array-1)
"Hello World"                    => undefined behavior (invalid input)
[1,1,1,1,1,1,1,1,1]              => 0 (all elements are already identical)
[1, 3, 9, 26, 66, 150, 313, 610] => 6

Scoring:

This is code-golf, lowest score in bytes in each language wins for that language. Lowest score overall gets the green checkmark.

Answer 1

Husk, 6 bytes

Thanks Leo for letting me use his version that works for [1,1,1,1,1,1]

←VE¡Ẋ-

Try it online!

Explanation

   ¡     Repeatedly apply function, collecting results in a list
    Ẋ-     Differences
 VE      Get the index of the first place in the list where all the elements are equal
←        Decrement

Answer 2

MATL, 8 bytes

`dta}x@q

Try it online! Or verify all test cases.

Explanation

This compuntes consecutive differences iteratively until the result is all zeros or empty. The output is the required number of iterations minus 1.

`      % Do... while
  d    %   Consecutive diffferences. Takes input (implicitly) the first time
  t    %   Duplicate
  a    %   True if any element is nonzero. This is the loop condition
}      % Finally (execute before exiting the loop)
  x    %   Delete. This removes the array of all zeros
  @    %   Push iteration index
  q    %   Subtract 1. Implicitly display
       % End (implicit). Proceed with next iteration if top of the stack is true

Answer 3

R, 50 44 bytes

function(l){while(any(l<-diff(l)))F=F+1
F*1}

Try it online!

Takes a diff of l, sets it to l, and checks if the result contains any nonzero values. If it does, increment F (initialized as FALSE implicitly), and returns F*1 to convert FALSE to 0 in the event that all of l is identical already.

Answer 4

JavaScript (ES6), 47 bytes

f=a=>-a.every(x=>i=!x)||1+f(a.map(n=>n-a[++i]))

Test cases

f=a=>-a.every(x=>i=!x)||1+f(a.map(n=>n-a[++i]))

console.log(f([1,2,3,4,5,6,7,8,9,10]))    // 1
console.log(f([1,4,9,16,25,36]))          // 2
console.log(f([1,2,1]))                   // 2
console.log(f([1,1,1,1,1,1,1,1,1]))       // 0
console.log(f([1,3,9,26,66,150,313,610])) // 6

Answer 5

Mathematica, 49 bytes

(s=#;t=0;While[!SameQ@@s,s=Differences@s;t++];t)&  

thanx @alephalpa for -6 bytes and @hftf -1 byte

and here is another approach from @hftf

Mathematica, 49 bytes

Length@NestWhileList[Differences,#,!SameQ@@#&]-1&

Answer 6

Jelly, 7 bytes

-Iß$E?‘

Try it online!

Explanation

-Iß$E?‘  Input: array A
     ?   If
    E    All elements are equal
         Then
-          Constant -1
         Else
   $       Monadic chain
 I           Increments
  ß          Recurse
      ‘  Increment

Answer 7

Perl 6, 37 bytes

{($_,{@(.[] Z- .[1..*])}...*.none)-2}

Try it online!

Explanation: The function takes the input as one list. It then builds a recursive sequence like this: the first element is the original list ($_), the next elements are returned by {@(@$_ Z- .[1..*])} being called on the previous element, and that is iterated until the condition *.none is true, which happens only when the list is either empty or contains only zeroes (or, technically, other falsey values). We then grab the list and subtract 2 from it, which forces it first to the numerical context (and lists in numerical context are equal to the number of their elements) and, at the end, returns 2 less than the number of elements in the list.

The weird block {@(@$_ Z- .[1..*])} just takes the given list (.[] — so called Zen slice — indexing with empty brackets yields the whole list), zips it using the minus operator (Z-) with the same list without the first element (.[1..*]) and forces it to a list (@(...) — we need that because zip returns only a Seq, which is basically an one-way list that can be iterated only once. Which is something we don't like.) And that's it.

Answer 8

Japt, 10 7 bytes

è@=ä-)d

Try it online!

Relies on the fact that the result is guaranteed to be within the length of the input array.

Explanation

è@=ä-)d     Implcit input of array U
 @          For each value in U...
  =ä-)      Update U to be equal to its subsections, each reduced by subtraction
      d     Check if any values in that are truthy
è           Count how many items in that mapping are true

By the end, this will map the array
[1, 3, 9, 26, 66, 150, 313, 610] to [true, true, true, true, true, true, false, false],
which contains 6 trues.

Previous 10 byte version

@=ä-)e¥0}a

Try it online!

Answer 9

Java 8, 191 + 58 = 249 198 140 bytes.

Thanks PunPun1000 for 51 bytes.
Thanks Nevay for 58 bytes.

int f(int[]a){int x=a.length-1,b[]=new int[x];for(;x-->0;)b[x]=a[x+1]-a[x];return java.util.Arrays.stream(a).distinct().count()<2?0:1+f(b);}

Try it Online!

Try it Online (198 byte version)

So, this is my first time posting here in PPCG (and the first time ever doing a code golf challenge). Any constructive criticism is welcome and appreciated. I tried to follow the guidelines for posting, if anything's not right feel free to point it out.

Beautified version:

int f(int[] a) {
    int x = a.length - 1, b[] = new int[x];
    for (; x-- > 0;) {
        b[x] = a[x + 1] - a[x];
    }
    return java.util.Arrays.stream(a).distinct().count() < 2 ? 0 : 1 + f(b);
}

Answer 10

APL (Dyalog Classic), 22 17 bytes

{1=≢∪⍵:0⋄1+∇2-/⍵}

Try it online!

Thanks to @ngn for -5 bytes!

How?

• { ... }, the function
• 1=≢∪⍵:0, if every element is equal in the argument, return 0
• 1+∇2-/⍵, otherwise, return 1 + n of the differences (which is n-1, thus adding one to it gives n)

Answer 11

Haskell, 46 bytes

g l|all(==l!!0)l=0|0<1=1+g(zipWith(-)l$tail l)

this simply recurses - zipWith(-)l$last l is the difference list of l. and g is the function that answers the question.

Answer 12

Kotlin, 77 bytes

first post, tried to edit last answer on kotlin 2 times ;D

{var z=it;while(z.any{it!=z[0]})z=z.zip(z.drop(1),{a,b->a-b});it.size-z.size}

took testing part from @jrtapsell

TryItOnline

Answer 13

Jelly, 7 bytes

IÐĿEÐḟL

Try it online!

Explanation

IÐĿEÐḟL  Main link
 ÐĿ      While results are unique (which is never so it stops at [])
I        Take the increments, collecting intermediate values # this computes all n-th differences
    Ðḟ   Filter out
   E     Lists that have all values equal (the first n-th difference list that is all equal will be removed and all difference lists after will be all 0s)
      L  Take the length (this is the number of iterations required before the differences become equal)

-1 byte thanks to Jonathan Allan

Answer 14

JavaScript (ES6), 58 bytes

f=a=>+(b=a.slice(1).map((e,i)=>e-a[i])).some(e=>e)&&1+f(b)

Answer 15

Python 2, 65 bytes

-7 bytes thanks to Jonathan Allan.

f=lambda l,c=1:any(l)and f([j-i for i,j in zip(l,l[1:])],c-1)or-c

Try it online!

Answer 16

05AB1E, 7 bytes

[DË#¥]N

Try it online!

Explanation

[         # start loop
 D        # duplicate current list
  Ë       # are all elements equal?
   #      # if so, break
    ¥     # calculate delta's
     ]    # end loop
      N   # push iteration counter

Answer 17

Haskell, 66 61 60 bytes

z=(=<<tail).zipWith
f=length.takeWhile(or.z(/=)).iterate(z(-))

Try it online!

Saved 5 bytes thanks to Christian Sievers

Saved 1 byte thanks to proud-haskeller

iterate(z(-)) computes the differences lists.

or.z(/=) tests if there are non equal elements in those lists.

length.takeWhile counts the differences lists with non equal elements.

Answer 18

Dyalog APL, 19 bytes

≢-1+(≢2-/⍣{1=≢∪⍵}⊢)

Explanation:

≢                      length of input
 -1+(             )    minus 1+
     ≢                 length of
      2-/              differences between elements
         ⍣             while
          {1=≢∪⍵}      there is more than 1 unique element
                 ⊢     starting with the input

Answer 19

Java (OpenJDK 8), 98 94 bytes

a->{int o=0,i,z=1;for(;z!=0;o++)for(i=a.length-1,z=0;i>o;a[i]-=a[--i])z|=a[o]^a[i];return~-o;}

Try it online!

Answer 20

k, 21 bytes

#1_(~&/1_=':)(1_-':)\

This works in k, but not in oK, because oK's while loop runs before checking the condition (as opposed to first checking the condition, and then running the code). Therefore, in oK, the 1 1 1 1 1 example will not work properly.

Try oK online!

Explanation:

   (        )       \ /while(
    ~&/               /      not(min(
       1_=':          /              check equality of all pairs))) {
             (1_-':)  /    generate difference list
                      /    append to output }
#1_                   /(length of output) - 1

Answer 21

Japt, 7 bytes

Same approach (but independently derived) as Justin with a different implementation.

£=äaÃèx

Test it

---

Explanation

Implicit input of array U.

£   Ã

Map over each element.

äa

Take each sequential pair (ä) of elements in U and reduce it by absolute difference (a).

=

Reassign that array to U.

èx

Count (è) the number of sub-arrays that return truthy (i.e., non-zero) when reduced by addition.

Answer 22

TI-Basic, 19 bytes

While max(abs(ΔList(Ans
ΔList(Ans
IS>(A,9
End
A

By default, variables start at zero. Also, never thought I'd be using IS>( for anything useful.

Answer 23

Pyth, 15 bytes

W.E.+Q=.+Q=hZ)Z

Verify all the test cases.

How?

Explanation #1

W.E.+Q=hZ=.+Q)Z   ~ Full program.

W                 ~ While...
 .E.+Q            ~ ... The deltas of Q contain a truthy element.
      =hZ         ~ Increment a variable Z, which has the initial value of 0.
         =        ~ Transform the variable to the result of a function applied to itself...
          .+Q     ~ ... Operate on the current list and deltas.
             )Z   ~ Close the loop and output Z.

Answer 24

C# (.NET Core), 70 69 + 18 bytes

-1 byte thanks to Kevin Cruijssen

g=a=>i=>a.Distinct().Count()>1?g(a.Zip(a.Skip(1),(y,z)=>y-z))(i+1):i;

Must be given 0 when calling to operate correctly. Also included in byte count:

using System.Linq;

Try it online!

Explanation:

g = a => i =>                      // Function taking two arguments (collection of ints and an int)
    a.Distinct()                   // Filter to unique elements
    .Count() > 1 ?                 // If there's more than one element
        g(                         //     Then recursively call the function with
            a.Zip(                 //     Take the collection and perform an action on corresponding elements with another one
                a.Skip(1),         //         Take our collection starting at second element
                (y, z) => y - z    //         Perform the subtraction
            )
        )(i + 1)                   //     With added counter
        : i;                       // Otherwise return counter

Iterative version 84 + 18 bytes:

a=>{int i=0;for(;a.Distinct().Count()>1;i++)a=a.Zip(a.Skip(1),(y,z)=>y-z);return i;}

Try it online!

Answer 25

Clojure, 62 bytes

#(loop[c % i 0](if(apply = c)i(recur(map -(rest c)c)(inc i))))

Nicely = can take any number of arguments, and a single argument is identical to "itself". (apply = [1 2 3]) gets executed as (= 1 2 3).

Answer 26

Perl 5, 83 + 1 (-a) = 84 bytes

sub c{$r=0;$r||=$_-$F[0]for@F;$r}for(;c;$i=0){$_-=$F[++$i]for@F;$#F--}say y/ //-$#F

Try it online!

Input as a list of numbers separated by one space.

Answer 27

Pyke, 11 bytes

W$D}ltoK)Ko

Try it here!

Answer 28

Kotlin, 83 bytes

{var z=it
var c=0
while(z.any{it!=z[0]}){c++
z=(0..z.size-2).map{z[it+1]-z[it]}}
c}

Beautified

{
    // Make input mutable
    var z=it
    // Count for returning
    var c=0
    // While the array is not identical
    while (z.any { it != z[0] }) {
        // Increment count
        c++
        // Update list to differences
        z = (0..z.size-2).map { z[it+1] - z[it] }
    }
    // Return count
    c
}

Test

var n:(List<Int>)->Int =
{var z=it
var c=0
while(z.any{it!=z[0]}){c++
z=(0..z.size-2).map{z[it+1]-z[it]}}
c}

data class TestData(var input: List<Int>, var output: Int)

fun main(args: Array<String>) {
    val items = listOf(
        TestData(listOf(1,2,3,4,5,6,7,8,9,10), 1),
        TestData(listOf(1,4,9,16,25,36), 2),
        TestData(listOf(1,2,1), 2),
        TestData(listOf(1,1,1,1,1,1,1,1,1), 0),
        TestData(listOf(1, 3, 9, 26, 66, 150, 313, 610), 6)
    )

    val fails = items.map { it to n(it.input) }.filter { it.first.output != it.second }

    if (fails.isEmpty()) {
        println("Test passed")
    } else {
        fails.forEach {println("FAILED: $it")}
    }
}

TryItOnline

Answer 29

Pyth, 10 bytes

tf!t{.+FQt

If we can index from 1, we can save a byte by removing the leading t.

Try it Online

Explanation

tf!t{.+FQt
 f        T  Find the first (1-indexed) value T...
     .+FQt   ... such that taking the difference T - 1 times...
  !t{        ... gives a set with more than one value in it.
t            0-index.

Answer 30

Swift 4, 90 bytes

func f(_ a:[Int])->Int{return a.contains{$0 != a[0]} ?f(zip(a, a.dropFirst()).map(-))+1:0}

Alternative, closure-based implementation:

var f: ((_ input: [Int]) -> Int)!
f = {a in a.contains{$0 != a[0]} ?f(zip(a, a.dropFirst()).map(-))+1:0}

test cases:

let testcases: [(input: [Int], expected: Int)] = [
    (input: [1,2,3,4,5,6,7,8,9,10],           expected: 1),
    (input: [1,4,9,16,25,36],                 expected: 2),
    (input: [1,2,1],                          expected: 2),
    (input: [1,1,1,1,1,1,1,1,1],              expected: 0),
    (input: [1, 3, 9, 26, 66, 150, 313, 610], expected: 6),
]

for (caseNumber, testcase) in testcases.enumerated() {
    let actual = f(testcase.input)
    assert(actual == testcase.expected,
        "Testcase #\(caseNumber) \(testcase.input) failed. Got \(actual), but expected \(testcase.expected)!")
    print("Testcase #\(caseNumber) passed!")
}