26
2
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.
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 – 2017-09-11T23:29:41.897
Behavior is undefined for invalid input (I don't care what your code does) – Gryphon – 2017-09-11T23:30:53.557
Shouldn't
[1,2,1]
give 2?[1,2,1] -> [1,-1] -> [-2]
– HyperNeutrino – 2017-09-11T23:35:33.460@HyperNeutrino, yep, sorry. I had a brain-fart there – Gryphon – 2017-09-11T23:37:00.353
Add this test case
[1,3,9,26,66,150,313,610]
->6
if you like – J42161217 – 2017-09-12T00:10:18.303Related, potential dupe targets: https://codegolf.stackexchange.com/questions/q/4229/194 , https://codegolf.stackexchange.com/q/47005/194 , https://codegolf.stackexchange.com/q/65409/194 , https://codegolf.stackexchange.com/q/119301/194
– Peter Taylor – 2017-09-12T07:20:02.357@PeterTaylor the third one you suggested is really similar, so I don't know if this counts as a good question. – Michthan – 2017-09-12T08:12:08.077
The description talks about an array with any number of integers, but all the test cases are arrays of at least 2 positive integers. Do solutions need to handle 0s, negative numbers, empty arrays, and arrays of a single element? – Patrick Stephansen – 2017-09-12T11:28:22.123
@PatrickStephansen, yes, yes, no, and yes. – Gryphon – 2017-09-12T21:42:13.650