Author 
Message 

thornahawk μολών λαβέ
Active Member
Joined: 27 Mar 2005 Posts: 569

Posted: 03 Jun 2009 09:51:30 pm Post subject: 


Here's a twoforone challenge for you guys:
a.) Given a list of xcoordinates in L₁ and ycoordinates 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 brokenline (piecewise linear) interpolant at the value X?
b.) With L₁ and L₂ given as above, write a program that calculates the area under the brokenline 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(L_{1})ΔList(cumSum(L_{2}).5L_{2}[/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 Ycoordinate 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 xvalues 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 xvalues 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(A1))/(L1(A)L1(A1
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)(XL1(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)(XL1(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(...,K1,K)...) construct. I didn't realize the shorter solution posted.
thornahawk
P.S. Personally, I prefer the name "broken line interpolant", maybe even "connectthedots 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 


