Implement the Method of Finite Differences

Question

The Method of Finite Differences is a technique used to find the next term in a sequence of numbers, given that the sequence is governed by consecutive values of a certain polynomial. Given a list of n terms, the Method will be able to determine the degree of the polynomial, which is a maximum of n+1.

The Method works by arranging the numbers in order, like so.

4 8 15 16 23 42

Then the difference between any number and its neighbor to the right (given that it has a neighbor to the right) is written in the row below. Note that entries must be written one space (ASCII 20) to the right of the longest entry in the previous column.

4 8 15 16 23 42
4 7 1  7  19

The process is repeated until there is one entry left in the bottom row.

4   8  15 16 23 42
4   7  1  7  19
3   -6 6  12
-9  12 6
21  -6
-27

Then the bottom row's entry is duplicated.

4   8   15 16 23 42
4   7   1  7  19
3   -6  6  12
-9  12  6
21  -6
-27 -27

Then the above process for finding differences is reversed until there is a new entry in the first row, which is separated from the other entries by |

4   8   15  16  23  42 | 46
4   7   1   7   19  4
3   -6  6   12  -15
-9  12  6   -27
21  -6  -33
-27 -27

The Method moves down rows until all of the entries in a row are equal. Take the starting numbers 2 5 10 17 26. This is the finished table.

2 5 10 17 26 | 37
3 5 7  9  11
2 2 2  2

The degree of the polynomial is the number of rows minus 1. As you might tell from the previous example, the polynomial is x^2+1.

---

Your program will take as its input a list of integers separated by whitespace. You may assume that the list contains only integers and has at least 2 elements (they need not be distinct; the resulting chart would have only 1 row). The program will output the entire table generated by the Method of Finite Differences, as defined above.

---

This is code golf. Standard rules apply. Shortest code in bytes wins.

Answer 1

CJam, 74 73 71 68 bytes

q~]{_2ew::-Wf*_)-}g0]W%{_W=@W=++_}*;)"|"\++]W%z{:s_:,$W=)f{Se]}}%zN*

Try it online

The latest version uses the middle section of @MartinBüttner's proposed solution, which is 3 bytes shorter than what I had. The first part for calculating the difference rows was identical. The part for the final formatting was the same length, so I kept my original version. Martin's savings came from making the sum part of the list while the new values are calculated, and using a * instead of a % loop. That also simplified the insertion of the "|".

Explanation:

l       Get one line of input.
~]      Interpret input and wrap in list.
{       While loop to construct additional lines.
  _2ew    Copy and build pairs of subsequent numbers.
  ::-     Reduce all number pairs by subtraction.
  Wf*     Multiply all of them by -1, since the reduction calculated 1st minus 2nd,
          but we need 2nd minus 1st.
  _)-     Check if all numbers in list are equal by popping off last and removing
          value from the list. This is truthy if all numbers are not equal.
}g      End of while loop to construct additional lines.
0       Add a 0 at the end, which will be the starting point of the sum for
        calculating the new values.
]       Wrap all lines in a list.
W%      Revert order of list, since adding the additional numbers in each row
        goes in bottom-up order.
{       Start of loop over rows.
  _W=     Get last value of row.
  @       Rotate previous row to top.
  W=      Extract last value as new increment. For the 0 that was added as an
          additional row, this is a comparison with -1, which gives the desired
          value of 0.
  +       Add increment to last value.
  +       Append value to list.
  _       Copy row for use in next loop iteration.
}*      End of loop over rows.
;       Remove extra copy of last row.
)       Pop off last value of last row.
"|"     Push the vertical bar.
\       Swap vertical bar and last value.
++      Concatenate the 3 parts.
W%      Revert order of list, to get the rows back in original order.
z       Transpose list for handling column alignment.
{       Loop over columns.
  :s      Convert values to strings.
  _:,     Copy and calculate the length of all values.
  $W=     Get maximum length by sorting and getting last value.
  )       Increment to add space between columns.
  f{      Apply to all values.
    Se]     Right pad to column width with spaces.
  }       End apply to all values.
}%      End loop over columns.
z       Transpose back to row order.
N*      Join rows with newlines.