| Author |
Message |
|
Ed H
Member
Joined: 30 Nov 2007
Posts: 138
|
 Posted: 03 Dec 2008 12:12:48 am Post subject: |
|
|
Two polynomials f(x) and g(x) are represented as lists in L1 and L2, such that the coefficient of xk in f(x) is L1(k+1), and the coefficient of xk in g(x) is L2(k+1), with no trailing zeros at the end of L1 or L2.
Challenge: Write the shortest program that returns f(x)g(x) as a list, to Ans. The list should not have any trailing zeros. Preserving the original lists L1 and L2 is not required.
Example: With {1 1 1 1} in L1 and {1 2 3 4} in L2, the program should return {1 3 6 10 9 7 4}. This is like multiplying the polynomials f(x) = 1 + 1x + 1x2 + 1x3 and g(x) = 1 + 2x + 3x2 + 4x3 to get f(x)g(x) = 1 + 3x + 6x2 + 10x3 + 9x4 + 7x5 + 4x6.
A different challenge: Optimize for speed.
Right now my smallest program is at 66 bytes.
Last edited by Guest on 12 Jul 2010 01:30:53 am; edited 1 time in total |
|
| Back to top |
|
|
cjgone
Aw3s0m3
Active Member
Joined: 24 May 2006
Posts: 693
|
| Posted: 03 Dec 2008 02:03:44 am Post subject: |
|
|
| Wow, sad, mine takes like 100 bytes.. For loop fail :S |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 03 Dec 2008 04:17:46 am Post subject: |
|
|
If you need to preserve L₁ and L₂...
Quote:
0→dim(L₃
For(I,1,dim(L₁
For(J,1,dim(L₂
I+J−1→K
0:If K≤dim(L₃
L₃(K
Ans+L₁(I)L₂(J→L₃(K
End:End
L₃
with the result stored in L₃ .
Otherwise, let me get back to you...
thornahawk |
|
| Back to top |
|
|
Ed H
Member
Joined: 30 Nov 2007
Posts: 138
|
| Posted: 03 Dec 2008 09:39:46 pm Post subject: |
|
|
Hmm, thornahawk, I didn't catch that post when I searched for any previous polynomial multiplication programs.
There is a slight optimization you could make to your code: you can replace :0:If K≤dim(L₃:L₃(K with :L₃(K)(K≤dim(L₃, which saves 2 bytes. |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 11 Dec 2008 09:48:51 pm Post subject: |
|
|
The solution I posted seems to cease to work if I incorporate your suggested change.
thornahawk |
|
| Back to top |
|
|
Ed H
Member
Joined: 30 Nov 2007
Posts: 138
|
| Posted: 12 Dec 2008 10:38:46 pm Post subject: |
|
|
Oh, my mistake. I didn't realize that L3(K does not always exist; otherwise, it would be a simple application of piecewise expressions.
Anyway, if no one posts their solution in a week, I will post mine. Hint: my solution uses no For loops.
Edit: Or any loops, actually.
Last edited by Guest on 12 Jul 2010 01:31:17 am; edited 1 time in total |
|
| Back to top |
|
|
GloryMXE7
Puzzleman 3000
Active Member
Joined: 02 Nov 2008
Posts: 604
|
| Posted: 12 Dec 2008 10:47:55 pm Post subject: |
|
|
| so it either does it with/out loops at all or it uses repeat or while but probanly repeat |
|
| Back to top |
|
|
Ed H
Member
Joined: 30 Nov 2007
Posts: 138
|
| Posted: 15 Dec 2008 08:00:47 pm Post subject: |
|
|
Here is my solution:
Quote: [font="Courier new"]:dim(L1)-1+dim(L2→dim(L1
:Ans→dim(L2
:"sum(seq(L1(A)L2(X+1-A),A,1,X→Y0
:Y0(cumSum(L1 or 1
I used functions to overcome the fact that you can't use a seq( command inside a seq( command. Also, I looped based on the power in the multiplied product, rather than the power of the terms in the multiplicands.
In total, 66 bytes. It's a good size, but it isn't very fast - if one were to use a calculator to find coefficients of generating functions, you'd probably need a faster routine.
Thanks for that catch, Baruch and DarkerLine. I did intend to store to dim(L1.
Last edited by Guest on 30 Dec 2008 06:11:44 pm; edited 1 time in total |
|
| Back to top |
|
|
Baruch
Newbie
Joined: 24 Dec 2008
Posts: 5
|
| Posted: 28 Dec 2008 09:30:15 am Post subject: |
|
|
First line : how can you stock a number into a list ?
cumSum(L1 or 1 is the same as dim(L1 , no ? |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 28 Dec 2008 06:21:29 pm Post subject: |
|
|
You're thinking of sum(. cumSum( of a list returns the cumulative sums, as a list: the first element is the same, the second element is the sum of the first two, the third is the sum of the first three, and so on. cumSum(L1 or 1 gives a list like {1,2,3,4,5,...}.
As for the first line, I suspect he meant to store to dim(L1 instead.
Last edited by Guest on 12 Jul 2010 01:30:23 am; edited 1 time in total |
|
| Back to top |
|
|
Baruch
Newbie
Joined: 24 Dec 2008
Posts: 5
|
| Posted: 29 Dec 2008 07:53:24 am Post subject: |
|
|
| Yep sorry ^^. I didn't know that Y0({list}) was possible. |
|
| Back to top |
|
|
|
TI-Basic Brain Teasers => TI-BASIC
