# One out of Infinity: Interpolating polynomials [duplicate]

For this challenge, when given a list of (x,y) points your submission needs to output a polynomial function that goes through all of them.

For example, if your points were [(0,0), (2,5)], you could return y = 2.5*x or y = x + 1/4x^2.

• All points passed in will consist only of integers
• Two points will never have the same y value
• Your function be of the form y = a*x^n + ... b*x^m. Reducing of terms is allowed.
• Constants (the exponent and coefficient) can either be in decimal or fractional form. Decimals should be accurate to at least 3 decimal places
• You should be able to handle an arbitrary number of points
• Output must be a string starting with "y=". Whitespace anywhere in the string is fine.

# Test cases

Note, the given output is not the only valid output, just one of the possibilities.

(1,4)                                                    -> y=x+3
(0,0), (1,8)                                             -> y=8x
(0,6), (-1,90)                                           -> y=-84x+6
(6,4), (70,4), (-1,-6)                                   -> y=−10/497x^2+760/497x−316/71
(4,5), (5,6), (6,7)                                      -> y=x+1
(20,1), (-20,1), (0,5), (10, 4), (11,12), (17,4), (2,4)  -> y=488137/10424165400x^6−643187/473825700x^5−87561839/10424165400x^4+550999039/1042416540x^3−21590713027/5212082700x^2+300110420/52120827x+5


• Your title says something about plotting but the challenge about outputting polynomials. Having the corresponding results for your test cases would probably help clear this up (and make the test cases a lot more useful). Aug 14 '16 at 21:42
• Also how about built-ins? (Mathematica's is InterpolatingPolynomial so it's probably not at risk of winning.) Aug 14 '16 at 21:47
• Builtins are fine. Aug 14 '16 at 21:49
• The output needs to be a string. The input is flexible Aug 14 '16 at 22:01
• Can coefficients in the output be (string representations of) floats instead of fractions? Say with 4 decimals? Aug 14 '16 at 22:02

# MATL, 38 bytes

ynq3$ZQ'y=' '%+fx^%i'btn:qP&vYDh1J3-h)  Inputs are an array with the x values and an array with the y values. Try it online! y % Inplicitly take the two inputs, and push another copy of the first nq % Get its length minus 1. This is the required polynomial degree. 3$ZQ       % Coefficients of polynomial fitted to those data (polyfit)
'y='       % Push this string
'%+fx^%i'  % Push format string for sprintf
b          % Bubble up the polynomial coefficients to the top of the stack
tn:qP      % Duplicate and produce [n n-1  ... 0] where n is the polynomial degree.
% These are the exponents
&v         % Concatenate vertically. This gives a 2D array with the coefficients in
% the first row and the exponents in the second
YD         % Apply sprintf to this array with previous format string. The array
% is read in column-major order: down, then across
h          % Concatenate 'y=' and formatted string representing the polynomial
1J3-h)     % The string ends in '...x^0'. Remove last three chars to delete this.
% Implicitly display


# Python2 + sympy, 61 58 bytes

from sympy import*;print interpolate(input("y="),var("x"))

• You can use var instead of Symbol. Also, not that it matters, but input("y=") gets rid of that unbalanced spacing around =. Aug 14 '16 at 22:56

# Matlab (with Symbolic Toolbox), 52 bytes

Using builtins for calculating an interpolation polynomial, and then converting it to a symbolc expression for pretty printing and back to a string for the actual output. This function takes two lists of coordinates, e.g. [6,70,-1] and [4,4,-6] for the fourth test case.

 @(x,y)['y=',char(poly2sym(polyfit(x,y,numel(x)-1)))]

• I think this should be titled "Matlab with Symbolic Toolbox". Good job! Aug 14 '16 at 22:29
• Here it was kinda obvious, but many times I don't even know whether I'm using one of those toolboxes. =) Aug 14 '16 at 22:46