Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's TI-BASIC subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.

This forum is locked: you cannot post, reply to, or edit topics. TI-Basic Brain Teasers => TI-BASIC
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
Display posts from previous:   
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
    »
» View previous topic :: View next topic  
Page 1 of 1 » All times are GMT - 5 Hours

 

Advertisement