Codesignal Solution: Complete the Sequence
Jack isn't really good at math, but his sadistic teacher still gave him some math exercises about sequences. He needs to find the next number of the given sequence
, which can be one of the following three types:
 arithmetic progression;
 geometric progression;
 pseudofibonacci sequence (a sequence each element of which is the sum of two preceding elements).
You are given 4
first numbers in the series as a string, in which the numbers are separated by commas. Help Jack to figure out what type of the sequence it is, and return the next number.
Example

For
sequence = "4,6,10,16"
, the output should beCompletetheSequence(sequence) = 26
.The sequence is a pseudofibonacci sequence.

For
sequence = "5,10,20,40"
, the output should beCompletetheSequence(sequence) = 80
.The sequence for a geometric progression with
r = 2
. 
For
sequence = "2,4,6,8"
, the output should beCompletetheSequence(sequence) = 10
.The sequence for a arithmetic progression with
d = 2
.
Input/Output
 [time limit] 4000ms (js)

[input] string sequence
A string containing
4
numbers separated by a comma.Constraints:
7 ≤ sequence.length ≤ 254
. 
[output] integer
The next element of the
sequence
.
Solution
Case 1: Fibonacci Sequence
A Fibonacci sequence is given by
\[x_n = x_{n1} + x_{n2}, x_1 = 1, x_2 = 1\]
As we're given 4 numbers, we can check two times if the difference of two consecutive numbers results in the previous number before them:
\[x_3  x_2 = x_1 \land x_4x_3 = x_2\]
If this is the case, we can return the sum of the last two numbers:
\[S = x_3 + x_4\]
Case 2: Linear recurrence sequence
A linear recurrence sequence is defined as
\[x_1 = a, x_{n+1} = rx_n + d\]
With this generation rule, we can state:
\[\begin{array}{rrl} & x_2&= rx_1 + d\\ & x_3&= rx_2 + d\\ \Rightarrow & r&= \frac{x_2x_3}{x_1  x_2}\\ \Rightarrow& d&= x_2  rx_1\\ \Rightarrow& S&= r * x_4 + d \end{array} \] Implemented in JavaScript the whole thing could look like this:
CompletetheSequence = s => { x = s.split`,` a = +x[0] b = +x[1] c = +x[2] d = +x[3] if (d  c == b) { return d + c } else { R = (b  c) / (a  b) return R * d + b  R * a } }
Or minimized:
CompletetheSequence = s => (c = (x = s.split`,`)[2])  ((d = x[3])  c  (b = x[1]) ? (c  b) * (d  b) / (x[0]  b) : d)
That's quite neat, but too much code for this code golfing task. Let's try to handle the arithmetic and geometric sequence separately as we don't need the general case. Detecting if it's an arithmetic sequence can be done quite easily by checking if \(d\) exists:
\[d = x_3 \bmod x_2\]
Case 2a: Geometric sequence \((d=0)\)
\[S = x_4 * (x_4 / x_3)\]
Case 2b: Arithmetic sequence \((d\neq 0)\)
\[x_4 + (x_4  x_3)\]
As we're given the list as a string instead of an array, we have to do some magic JavaScript foo to lower the code size:
CompletetheSequence = s => { x = s.split`,` b = +x[1] c = +x[2] d = +x[3] if (d  c == b) { return d + c } else if (d % c > 0) { return d + d  c } else { return d * d / c } }
That works fine, even if we only check the upper 3 numbers for the fibonacci detection.
CompletetheSequence = s => { x = s.split`,` b = +x[1] c = +x[2] d = +x[3] return (d  c  b) ? (d % c) ? (d + d  c) : (d * d / c) : (c + d) }
Even smaller:
CompletetheSequence = s => ((d = (x = s.split`,`)[3])  (c = x[2])  x[1]) ? (d % c) ? (2 * d  c) : (d * d / c) : (c  d)
Now remove the brackets:
CompletetheSequence = s => (d = (x = s.split`,`)[3])  (c = x[2])  x[1] ? d % c ? 2 * d  c : d * d / c : c  d