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 x^{k} in f(x) is L1(k+1), and the coefficient of x^{k} 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 + 1x^{2} + 1x^{3} and g(x) = 1 + 2x + 3x^{2} + 4x^{3} to get f(x)g(x) = 1 + 3x + 6x^{2} + 10x^{3} + 9x^{4} + 7x^{5} + 4x^{6}.
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(L_{1})1+dim(L_{2}→dim(L_{1}
:Ans→dim(L_{2}
:"sum(seq(L_{1}(A)L_{2}(X+1A),A,1,X→Y_{0}
:Y_{0}(cumSum(L_{1} 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 


