# 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? Sep 11, 2017 at 23:29
• Behavior is undefined for invalid input (I don't care what your code does) Sep 11, 2017 at 23:30
• Shouldn't [1,2,1] give 2? [1,2,1] -> [1,-1] -> [-2] Sep 11, 2017 at 23:35
• @HyperNeutrino, yep, sorry. I had a brain-fart there Sep 11, 2017 at 23:37
• Add this test case [1,3,9,26,66,150,313,610] -> 6 if you like Sep 12, 2017 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. >_< Sep 11, 2017 at 23:50
• Damn, I was gonna post this. Good job though, +1!
– Leo
Sep 11, 2017 at 23:51
• @Leo, test case I didn't see [1,1,1,1], can I use yours? Sep 11, 2017 at 23:57
• @H.PWiz sure, go on!
– Leo
Sep 11, 2017 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)& Sep 12, 2017 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, 2017 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 Sep 12, 2017 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. Sep 12, 2017 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! Sep 12, 2017 at 16:44 • Instead of importing those modules you can just use java.util.stream.IntStream k = java.util.Arrays.stream(a); Sep 13, 2017 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 Sep 13, 2017 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 Sep 13, 2017 at 14:39 • 140 bytes Sep 14, 2017 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. Sep 13, 2017 at 18:33 • @jferard that's very true Sep 13, 2017 at 20:36 # 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! # Kotlin, 77 bytes first post, tried to edit last answer on kotlin 2 times ;D {var z=it;while(z.any{it!=z})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. Sep 14, 2017 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, 2018 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! :) Sep 11, 2017 at 23:41 • IÐĿEÐḟL for seven (I see Miles also found a seven using recursion). Sep 12, 2017 at 1:00 • @JonathanAllan Cool thanks! Sep 12, 2017 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. Sep 11, 2017 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. Sep 12, 2017 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 Sep 12, 2017 at 1:20 • Is it just me or is the switch to a recursive lambda not saving enough bytes? :P Thanks! Sep 12, 2017 at 12:09 • I think this needs a max(...,0) to pass the [1, 1, 1, 1, ...] test cases. Sep 13, 2017 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=≢∪⍵}⊢ Sep 15, 2017 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, 2018 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(/=) Sep 13, 2017 at 13:28 • @ChristianSievers thanks! That was obvious, but I didn't see it... Sep 13, 2017 at 18:29 • You can also use z=(=<<tail).zipWith, one byte shorter Sep 13, 2017 at 20:37 • @proudhaskeller and more elegant, as always with point free definitions. Thanks! Sep 13, 2017 at 20:58 # 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. Sep 12, 2017 at 13:19 • @KevinCruijssen thank you! Also, oops. Sep 12, 2017 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. Sep 13, 2017 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, 2017 at 12:25 • @Dave Even better: WP{Q=hZ=.+Q)Z. Thanks! Sep 12, 2017 at 12:28 # Perl 5, 83 + 1 (-a) = 84 bytes sub c{$r=0;$r||=$_-$Ffor@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}){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 }) { // 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}){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 Sep 12, 2017 at 8:08
• It's lang-kotlin, not simply kotlin, in the highlighter hints. Sep 12, 2017 at 11:56

# Swift 4, 90 bytes

func f(_ a:[Int])->Int{return a.contains{$0 != a} ?f(zip(a, a.dropFirst()).map(-))+1:0}  Alternative, closure-based implementation: var f: ((_ input: [Int]) -> Int)! f = {a in a.contains{$0 != a} ?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!")
}