# Nth Differences

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


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 , lowest score in bytes in each language wins for that language. Lowest score overall gets the green checkmark.

• Can the input be "invalid" as in, if the input is to NOT conform to the provided spec, should we error? Provide -1 as the output? – Magic Octopus Urn Sep 11 '17 at 23:29
• Behavior is undefined for invalid input (I don't care what your code does) – Gryphon Sep 11 '17 at 23:30
• Shouldn't [1,2,1] give 2? [1,2,1] -> [1,-1] -> [-2] – HyperNeutrino Sep 11 '17 at 23:35
• @HyperNeutrino, yep, sorry. I had a brain-fart there – Gryphon Sep 11 '17 at 23:37
• Add this test case [1,3,9,26,66,150,313,610] -> 6 if you like – J42161217 Sep 12 '17 at 0:10

# 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

• Whenever someone said Husk is the new Jelly, they were pretty dang right. >_< – Zacharý Sep 11 '17 at 23:50
• Damn, I was gonna post this. Good job though, +1! – Leo Sep 11 '17 at 23:51
• @Leo, test case I didn't see [1,1,1,1], can I use yours? – H.PWiz Sep 11 '17 at 23:57
• @H.PWiz sure, go on! – Leo Sep 11 '17 at 23:58

# 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

# MATL, 8 bytes

dta}x@q


### 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


# 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.

# 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&

• (s=#;t=0;While[UnsameQ@@s,s=Differences@s;t++];t)& – alephalpha Sep 12 '17 at 3:50
• UnsameQ[1,2,1] is False; !SameQ[1,2,1] is True. I don't think the manual loop saves characters either: Length@NestWhileList[Differences,#,!SameQ@@#&]-1& is already the same length as yours after replacing UnsameQ with !SameQ. – hftf Sep 12 '17 at 7:45

# 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  • Non-recursive alternative: IÐĿE€ċ0 – Erik the Outgolfer Sep 12 '17 at 10:05 # 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! # 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. • Changing @(.[] Z- .[1..*]) to [.[] Z-.[1..*]] should save two bytes. – nwellnhof Sep 12 '17 at 15:04 # Java 8, 191 + 58 = 249198 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); }  • Welcome to the site! – DJMcMayhem Sep 12 '17 at 16:44 • Instead of importing those modules you can just use java.util.stream.IntStream k = java.util.Arrays.stream(a); – PunPun1000 Sep 13 '17 at 14:26 • In fact, there are a couple of changes you can make for free. 1) public doesn't need to be included in the byte count. 2) You should not be accepting a second parameter, but removing it can actually save bytes. 3) you can remove some unneeded brackets there – PunPun1000 Sep 13 '17 at 14:38 • 4) Not a saver but you should include a TIO if possible, here is an example with those suggestions at 198 bytes TIO – PunPun1000 Sep 13 '17 at 14:39 • 140 bytes – Nevay Sep 14 '17 at 9:23 # 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. • the recursive solution was the good one. – jferard Sep 13 '17 at 18:33 • @jferard that's very true – proud haskeller Sep 13 '17 at 20:36 # 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 • Welcome to PPCG! Nice first answer, an outgolf too. – H.PWiz Sep 14 '17 at 22:37 # 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) • it's shorter if you sacrifice tail-recursiveness: {1=≢∪⍵:0⋄1+∇2-/⍵} – ngn Jun 15 '18 at 8:21 # 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 • @Gryphon Done! :) – HyperNeutrino Sep 11 '17 at 23:41 • IÐĿEÐḟL for seven (I see Miles also found a seven using recursion). – Jonathan Allan Sep 12 '17 at 1:00 • @JonathanAllan Cool thanks! – HyperNeutrino Sep 12 '17 at 1:17 # 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  ## JavaScript (ES6), 58 bytes f=a=>+(b=a.slice(1).map((e,i)=>e-a[i])).some(e=>e)&&1+f(b)  • +0, not enough Jquery :p. Really though, +1, nice job, I know I would never be able to golf in JS. – Zacharý Sep 11 '17 at 23:57 # 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! • Save a byte initialising c to 1, decrementing and then using print-c. – Jonathan Allan Sep 12 '17 at 1:06 • Save six more by making it into a recursive function: f=lambda l,c=1:any(l)and f([j-i for i,j in zip(l,l[1:])],c-1)or-c – Jonathan Allan Sep 12 '17 at 1:20 • Is it just me or is the switch to a recursive lambda not saving enough bytes? :P Thanks! – totallyhuman Sep 12 '17 at 12:09 • I think this needs a max(...,0) to pass the [1, 1, 1, 1, ...] test cases. – Yonatan N Sep 13 '17 at 1:33 # 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  • Does this work? ≢-1+∘≢2-/⍣{1=≢∪⍵}⊢ – Zacharý Sep 15 '17 at 14:10 # 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  • ~&/1_=': -> 1<#? – ngn Jun 15 '18 at 8:06 # Haskell, 6661 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. • I think you can test for non-equal elements with or.z(/=) – Christian Sievers Sep 13 '17 at 13:28 • @ChristianSievers thanks! That was obvious, but I didn't see it... – jferard Sep 13 '17 at 18:29 • You can also use z=(=<<tail).zipWith, one byte shorter – proud haskeller Sep 13 '17 at 20:37 • @proudhaskeller and more elegant, as always with point free definitions. Thanks! – jferard Sep 13 '17 at 20:58 # 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! # 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. # 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. # 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! • You can remove the redundant space at (y,z)=>y-z. But nice answer, +1 from me. – Kevin Cruijssen Sep 12 '17 at 13:19 • @KevinCruijssen thank you! Also, oops. – Grzegorz Puławski Sep 12 '17 at 13:27 ## 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). • Nice, exactly what I was trying to do but I was struggling for a compact pairwise diffs. That's brilliant, I'll have to remember that for the future. – MattPutnam Sep 13 '17 at 18:43 # 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.  • -1 byte Wtl{Q=hZ=.+Q)Z – Dave Sep 12 '17 at 12:25 • @Dave Even better: WP{Q=hZ=.+Q)Z. Thanks! – Mr. Xcoder Sep 12 '17 at 12:28 # 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.

# Pyke, 11 bytes

W$D}ltoK)Ko  Try it here! # 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.  # 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

• If someone could edit to fix my language hints please, I can't seem to get them working – jrtapsell Sep 12 '17 at 8:08
• It's lang-kotlin, not simply kotlin, in the highlighter hints. – Ruslan Sep 12 '17 at 11:56

# 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!")
}