Author |
Message |
|
thornahawk μολών λαβέ
Active Member
Joined: 27 Mar 2005 Posts: 569
|
Posted: 03 Jun 2009 09:51:30 pm Post subject: |
|
|
Here's a two-for-one challenge for you guys:
a.) Given a list of x-coordinates in L₁ and y-coordinates in L₂, sorted such that L₁(K)<L₁(K+1), K=1..dim(L₁)-1, and a number stored in X anywhere in between the bounds of L₁, what is the shortest program that evaluates the broken-line (piecewise linear) interpolant at the value X?
b.) With L₁ and L₂ given as above, write a program that calculates the area under the broken-line interpolant (a.k.a. the trapezoidal rule) from L₁(1) to L₁(dim(L₁)).
thornahawk |
|
Back to top |
|
|
DarkerLine ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328
|
Posted: 04 Jun 2009 01:14:32 am Post subject: |
|
|
I can't think of anything clever for the first one at 2 in the morning, but [whiteout]sum(ΔList(L1)ΔList(cumSum(L2)-.5L2[/whiteout] solves the second one in 27 bytes.
Last edited by Guest on 12 Jul 2010 01:12:50 am; edited 1 time in total |
|
Back to top |
|
|
ztrumpet
Active Member
Joined: 06 May 2009 Posts: 555
|
Posted: 04 Jun 2009 09:15:41 am Post subject: |
|
|
Off topic:
When I read your posts instead of L1 or L2 I get L= (not =, but it's the closest symbol I could find). Edit: It's kinda like a box.
How do I make it read L1 and L2?
Last edited by Guest on 04 Jun 2009 09:16:21 am; edited 1 time in total |
|
Back to top |
|
|
ticalcnoah
Member
Joined: 28 Oct 2007 Posts: 153
|
Posted: 04 Jun 2009 09:43:34 am Post subject: |
|
|
Lemme guess your using ie6? Switch to firefox or at least update ie. |
|
Back to top |
|
|
ztrumpet
Active Member
Joined: 06 May 2009 Posts: 555
|
Posted: 04 Jun 2009 09:49:45 am Post subject: |
|
|
How do I tell what version of internet explorer I have? |
|
Back to top |
|
|
ticalcnoah
Member
Joined: 28 Oct 2007 Posts: 153
|
Posted: 04 Jun 2009 09:57:09 am Post subject: |
|
|
Do you have tabs? If not google ie7 and download it. Better yet would be to download firefox.
Last edited by Guest on 04 Jun 2009 09:58:09 am; edited 1 time in total |
|
Back to top |
|
|
ztrumpet
Active Member
Joined: 06 May 2009 Posts: 555
|
Posted: 04 Jun 2009 09:58:16 am Post subject: |
|
|
I have tabs. |
|
Back to top |
|
|
ticalcnoah
Member
Joined: 28 Oct 2007 Posts: 153
|
Posted: 04 Jun 2009 10:00:48 am Post subject: |
|
|
Well it should be rendering properly then I'd sugggest trying again with firefox. |
|
Back to top |
|
|
ztrumpet
Active Member
Joined: 06 May 2009 Posts: 555
|
Posted: 04 Jun 2009 10:10:03 am Post subject: |
|
|
Back on topic:
What is a sample input (and result) for part A? |
|
Back to top |
|
|
DarkerLine ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328
|
Posted: 04 Jun 2009 12:47:32 pm Post subject: |
|
|
Say L1 is {1,3,4,6} and L2 is {2,1,3,2}. Then the "piecewise linear interpolant", as thornahawk seems to enjoy calling it, is a function made up of a line from (1,2) to (3,1), then from (3,1) to (4,3), then from (4,3) to (6,2): The points are L1(N), L2(N) for different values of N.
Now if the value of X is 3.5, then the corresponding point on the function is going to be on the line from (3,1) to (4,3), because 3.5 is between 3 and 4. In fact it's halfway between 3 and 4, so the Y-coordinate is halfway between 1 and 3, and the result should be 2.
If the value of X is 1.5, then this is 1/4 the way along the line from (1,2) to (3,1), which is the point (1.5,1.75), so the result should be 1.75.
I could probably have picked nicer numbers for the example, but you get the idea. |
|
Back to top |
|
|
ztrumpet
Active Member
Joined: 06 May 2009 Posts: 555
|
Posted: 04 Jun 2009 02:08:00 pm Post subject: |
|
|
DarkerLine wrote: If the value of X is 1.5, then this is 1/4 the way along the line from (1,2) to (3,1), which is the point (1.5,1.75), so the result should be 1.75. I think you mean X=1.25
Does this work? Edit:No
int(X
L2(Ans)+L2(Ans+1
AnsfPart(X
Edit x2:
I think this works (35 bytes with 1 letter name):
L2(int(X->A
L2(int(X)+1)-Ans
A+AnsfPart(X
Last edited by Guest on 04 Jun 2009 03:43:24 pm; edited 1 time in total |
|
Back to top |
|
|
DarkerLine ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328
|
Posted: 04 Jun 2009 07:24:44 pm Post subject: |
|
|
ztrumpet wrote: DarkerLine wrote: If the value of X is 1.5, then this is 1/4 the way along the line from (1,2) to (3,1), which is the point (1.5,1.75), so the result should be 1.75. I think you mean X=1.25
No, I meant what I said. 1.5 is 1/4 of the way from 1 to 3 (remember that the x-values of the points don't have to be in even increments). Which means your code isn't quite correct either: it works for the special case where L1 is {1,2,3,...}. You're on the right track, though. |
|
Back to top |
|
|
ztrumpet
Active Member
Joined: 06 May 2009 Posts: 555
|
Posted: 04 Jun 2009 07:42:13 pm Post subject: |
|
|
DarkerLine wrote: No, I meant what I said. 1.5 is 1/4 of the way from 1 to 3 (remember that the x-values of the points don't have to be in even increments). Which means your code isn't quite correct either: it works for the special case where L1 is {1,2,3,...}. You're on the right track, though.
You are right. I will keep trying. |
|
Back to top |
|
|
ztrumpet
Active Member
Joined: 06 May 2009 Posts: 555
|
Posted: 05 Jun 2009 07:13:14 am Post subject: |
|
|
Sorry for the double post, but I've got it!
It's 74 bytes with a one letter name.
Code: 1->A
While X>L1(A
A+1->A
End
(L2(A)-L2(A-1))/(L1(A)-L1(A-1
AnsX+L2(A)-AnsL1(A
There's probably a smaller way to do this, but I haven't found one yet. |
|
Back to top |
|
|
woodswolf
Advanced Newbie
Joined: 26 Feb 2009 Posts: 53
|
Posted: 05 Jun 2009 09:35:00 am Post subject: |
|
|
could probably be optimised, but here it is:
Code: :For(A,1,dim(L1)-1
:If not(X≥L1(A) and X≤L1(A+1
:End
:ΔList(L2)/ΔList(L1→L3
:L2(A)+L3(A)(X-L1(A
Thats 75 bytes including the name "A"
dammit, got beaten!
EDIT: nvm, ztrumpet's way is almost the same, however, if you put an X like 100, the program ends with an error, which doesn't happen at mine xP.
However, in both our programs, we get an error at X=0
Last edited by Guest on 05 Jun 2009 09:42:01 am; edited 1 time in total |
|
Back to top |
|
|
DarkerLine ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328
|
Posted: 05 Jun 2009 10:55:38 am Post subject: |
|
|
48 bytes:
[whiteout]max(1,sum(L1<X→N
ΔList(L2)/ΔList(L1
L2(N)+Ans(N)(X-L1(N[/whiteout]
Also doesn't crash at the boundaries.
Last edited by Guest on 12 Jul 2010 01:12:32 am; edited 1 time in total |
|
Back to top |
|
|
woodswolf
Advanced Newbie
Joined: 26 Feb 2009 Posts: 53
|
Posted: 05 Jun 2009 11:33:58 am Post subject: |
|
|
wonderfull, it's the equation I was looking for, I totally forgot about sum in that context. |
|
Back to top |
|
|
thornahawk μολών λαβέ
Active Member
Joined: 27 Mar 2005 Posts: 569
|
Posted: 05 Jun 2009 11:46:42 am Post subject: |
|
|
DarkerLine got the same solution as I did for the first part of the challenge... It's sum( that indeed helps you find the correct interval.
For the second one, my solution was slightly longer, involving a seq(sum(...,K-1,K)...) construct. I didn't realize the shorter solution posted.
thornahawk
P.S. Personally, I prefer the name "broken line interpolant", maybe even "connect-the-dots interpolant"; "piecewise linear interpolant" just happens to be the textbook terminology... ;P |
|
Back to top |
|
|
DarkerLine ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328
|
Posted: 05 Jun 2009 06:55:59 pm Post subject: |
|
|
Personally, the word "interpolant" scares me. Though apparently not enough.
Last edited by Guest on 05 Jun 2009 06:56:23 pm; edited 1 time in total |
|
Back to top |
|
|
|