5
\$\begingroup\$

Task

Given a list of integers a1, a2, …, ak (k ≥ 2) and a positive integer m, write a function or a complete program that calculates the next m numbers of the list. Assume that ai = P(i) where

P(x) = bk-1 xk-1 + bk-2 xk-2 + … + b0

is the unique polynomial of minimum order which fits the points.

Description

Input

If the code is a function, input is given by an integer k, an array a1, a2, …, ak and an integer m.

If the code is a program, input (through stdin) is given by space-separated k a1 a2 … ak m.

You can assume that k ≥ 2 and m > 0.

Calculation

(Of course, the code can calculate the result in different way, but the result should be same.)

Find the polynomial P(x) which satisfies ai = P(i) for all 1 ≤ i ≤ k and has a degree of (no more than) k - 1. For example, if a list is 1,2,3,4,5, then P(x) = x. If a list is 1,4,9,16,25, then P(x) = x2.

Then, calculate ak+1 = P(k+1), ak+2 = P(k+2), …, ak+m = P(k+m). These are the results.

Output

If the code is a function, return an array [ak+1, ak+2, …, ak+m].

If the code is a full program, print those numbers to stdout, separated by an any character you want.

\$\endgroup\$
  • \$\begingroup\$ I think you should require some separator for the output: 1 4 9 16 25 is much less ambiguous than 1491625. \$\endgroup\$ – Ilmari Karonen Dec 10 '11 at 2:32
  • \$\begingroup\$ @IlmariKaronen OK then. \$\endgroup\$ – JiminP Dec 10 '11 at 2:34
  • \$\begingroup\$ NB This is almost a duplicate of codegolf.stackexchange.com/questions/1230/… . The differences are that it's over a field of characteristic 0; that the x-coords are implicit; and that it asks for extrapolation to k+1, ... k+m rather than to 0. \$\endgroup\$ – Peter Taylor Dec 11 '11 at 7:36
9
+100
\$\begingroup\$

Golfscript, 46 42 40 38 chars

~])\({[{.@-\}*])\}*;]-1%){0\{+.}/p]}*;

This uses a simple difference table approach, which is described in more detail on my GolfScript blog.

\$\endgroup\$
  • \$\begingroup\$ +100: You beat Ilmari's 40 char-or-less challenge :) \$\endgroup\$ – mellamokb Dec 12 '11 at 16:05
  • \$\begingroup\$ Bounty awarded. Congratulations! Now I just need to learn enough GolfScript to be able to understand your code. :) \$\endgroup\$ – Ilmari Karonen Dec 13 '11 at 16:22
  • \$\begingroup\$ @IlmariKaronen, I might write it up for my GolfScript blog in a few days. The -2% is quite interesting in that it's something I didn't really see much point to before. \$\endgroup\$ – Peter Taylor Dec 13 '11 at 16:55
  • 1
    \$\begingroup\$ @IlmariKaronen, code dissection posted to my blog. \$\endgroup\$ – Peter Taylor Dec 14 '11 at 23:42
4
\$\begingroup\$

Maple, 41 chars

c:=(k,a,m)->interp([$1-k..0],a,x)$x=1..m;

For example, c(3, [1, 2, 4], 4) returns 7, 11, 16, 22.

This function interprets the spec literally, taking both k and a as separate arguments. If the list a does not have exactly k elements, an error occurs. For convenience, here's a 45-char version that omits k from the argument list:

c:=(a,m)->interp([$1-nops(a)..0],a,x)$x=1..m;

I was first thinking of trying this in Perl, but hell, let's use the right tool for the job.

\$\endgroup\$
  • \$\begingroup\$ BTW, since this is code golf, 'the right tool' is golfscript. :P \$\endgroup\$ – JiminP Dec 10 '11 at 9:47
  • 1
    \$\begingroup\$ @JiminP: OK, challenge accepted. The first person to solve this task in 40 or fewer chars in GolfScript gets a 100 rep bounty from me. \$\endgroup\$ – Ilmari Karonen Dec 10 '11 at 16:20
  • \$\begingroup\$ @PeterTaylor When inputs are integers, outputs might always be integers (there's a way to calculate outputs by using only integers), even though I don't have any proofs. \$\endgroup\$ – JiminP Dec 11 '11 at 7:51
  • \$\begingroup\$ Challenge met. Don't feel obliged to give me the bounty, though; I'm doing ok for rep already. \$\endgroup\$ – Peter Taylor Dec 12 '11 at 0:16
  • \$\begingroup\$ @PeterTaylor: I'll give it to you anyway, it's not like I'm starved for rep either. And I did promise. (I assume I have to wait until the question is old enough, though, since I don't see any "start a bounty" link yet.) \$\endgroup\$ – Ilmari Karonen Dec 12 '11 at 0:42
2
\$\begingroup\$

Jelly, 18 bytes, language postdates challenge

Iß;@Ḣ+\øṁ⁹µL?
çUḣU

Try it online!

Jelly's functions only support up to two arguments, so I don't take in k (which is redundant) as an argument. I hope that's acceptable. The program defines a function that obeys the specification in the question.

Explanation

Helper function (takes input λ, ρ, and expands λ by ρ elements):

Iß;@Ḣ+\øṁ⁹µL?
       ø  µ ? If
           L    {λ} is nonempty,
              then:
I               take differences of consecutive elements of {λ};
 ß              call 1ŀ recursively on this value and {ρ};
  ;@            prepend
    Ḣ           the first element of {λ};
     +\         and take the cumulative sum {and return it}.
              Otherwise:
        ṁ⁹      {return} {0} repeated ρ times.

This is fairly magical in the way in which Jelly happens to pick out the exactly values I need it to operate on at every stage. Some of it is the result of me manipulating things; in particular, the unusual choice ø for the separator (rather than the more usual µ) means that all implicit arguments are set to 0, which is fairly handy in this case. However, I have no idea why ;@Ḣ parses the way it does, but it seems to work…

Main function (takes input λ, ρ, and returns the next ρ elements of λ):

çUḣU
ç             Call 1ŀ on {λ} and {ρ};
 U            reverse it;
  ḣ           take the first {ρ} elements;
   U          and reverse it {and return that value}.

This is just massaging the output into the form requested (if we were allowed to return the terms we were already given, that would remove a whole 5 bytes). Jelly doesn't have a "last n elements" function; of the various ways to synthesize it out of other functions, UḣU is convenient here because it happens to pick up ρ as a default argument.

\$\endgroup\$
1
\$\begingroup\$

Golfscript, 51 characters

Similar approach to Peter's one.

~])\-1%[{(.@{.@\-}%\;.,}do;]-1%\[0]\*\{\{+.}%\;}%;p

When run on input

2 3 12 35 78
4

it yields the result

[147 248 387 570]

There are still possible places where the solution might be golfable further.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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