current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 1 down vote favorite

This question already has an answer here:

Given a set of space-delimited integers, you've gotta either return a function that can generate that sequence, or return "There isn't any such function".

Sample input:

"1 11 41 79"
 - x^3+x^2-1

"12 38 78"
 - 7x^2 + 5x

The operations that the functions can contain are: +-/* and exponentiation.

If anyone has any other ideas LMK. As this is a code-golf, the shortest code will win.

share|improve this question

marked as duplicate by Peter Taylor, Paul R, Howard, grc, M42 Apr 11 '13 at 7:09

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
3  
This is a generalized form of codegolf.stackexchange.com/questions/1729/…, but I don't blame you for missing that (who knows what polynomial interpolation even is?) –  beary605 Apr 10 '13 at 13:21
3  
Also, why is this a popularity contest? –  jdstankosky Apr 10 '13 at 13:59
    
In fact there are at least three other questions asking for polynomial interpolation in addition to the one @beary605 mentions. –  Peter Taylor Apr 10 '13 at 14:31
    
The answer to the first sequence should read -2x^3+22x^2-42x+23. The generator function you have will produce 1 11 35 79. –  primo Apr 10 '13 at 15:21
    
Also, the title is somewhat misleading. Generating functions generate sequences in the coefficients. –  hammar Apr 11 '13 at 2:00
show 1 more comment

2 Answers

up vote 2 down vote accepted

Python 256 bytes

a=raw_input().split();r=range(len(a));m=[[(i+1.)**p for p in r]+[int(a[i])]for i in r]
for j in r:s=m[j];m=[map(lambda a,b:a-b*(i[j]-(i==s))/s[j],i,s)for i in m]
while~j:
 c=m[j][-1]
 if c:print('%+.15g'%c)[s>c>0:j>=c*c==1or 18]+('x^%d'%j)[:j*j],;s=0
 j-=1

Sets up a system of linear equations, matrix style, and then uses Gaussian elimination to solve. Quite a few bytes are spent pretty-printing the output. Non-integer solutions are displayed to 15 digits of accuracy.

As every sequence of n real numbers can be generated by a polynomial of order no more than n-1, the "function does not exist" case is not handled.

Sample usage:

$ echo 1 11 41 79 | python find-poly.py
-2x^3 +22x^2 -42x +23

$ echo 1 11 35 79 | python find-poly.py
x^3 +x^2 -1

$ echo 12 38 78 | python find-poly.py
7x^2 +5x

$ echo 43 12 -5 19 57 | python find-poly.py
-2.25x^4 +27x^3 -98.75x^2 +110x +7
share|improve this answer
add comment
up vote 1 down vote

There was no restriction in using any specific library, so here is a solution in Python using Sympy

Python 2.x: 71 Characters

from sympy import*
print interpolate(map(int,raw_input().split()),abc.x)
share|improve this answer
    
That is quite nice, althought I did need to explicitly import sympy.abc to get it to work. –  primo Apr 10 '13 at 17:53
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.