Contents
raw puzzle

Original Problem

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:

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

Input/Output

Solution

Case 1: Fibonacci Sequence

A Fibonacci sequence is given by

\[x_n = x_{n-1} + x_{n-2}, 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_4-x_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_2-x_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