Minichallenge: HHC2012 RPL programming contest with larger input  Printable Version + HP Forums (https://archived.hpcalc.org/museumforum) + Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum1.html) + Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum2.html) + Thread: Minichallenge: HHC2012 RPL programming contest with larger input (/thread232136.html) 
Minichallenge: HHC2012 RPL programming contest with larger input  David Hayden  09292012 The HHC 2012 RPL programming contest specified a maximum of 10 points in the input. This challenge is for the same problem, but with a list of 1,000 random numbers between 0 and 99,999 as the input. Here is the original contest description and thread. The same rules apply: minimize speed times time. Since the input is large, the trick to this challenge is to find an algorithm that will run quickly. Dave
Re: Minichallenge: HHC2012 RPL programming contest with larger input  Gilles Carpentier  09292012 I suppose 1000 random numbers means 500 points ?
Re: Minichallenge: HHC2012 RPL programming contest with larger input  David Hayden  09292012 Yes. 1,000 numbers, 500 points.
Re: Minichallenge: HHC2012 RPL programming contest with larger input  C.Ret  09292012 Hi, My ansver to this new challenge will be exactly the same code as the original one, since the number of points is only limited by memory available on my HP28S. The original code I propose is able to treat a 1000 elements list since it fit into the 28ko available (with UNDO backup option disable), but may need about 741 min (estimated time)to compute the diameter in this case.
« LIST> 2 / > n
Edited: 29 Sept 2012, 6:11 p.m.
Re: Minichallenge: HHC2012 RPL programming contest with larger input  Gilles Carpentier  09292012 I change nothing to my original code :
« @ SEE 1 Input list You can do little better for _exactly_ 1000 mumber (few bytes and seconds), but I prefer a generic code Time is ~ 20 mn for a 50G
Re: Minichallenge: HHC2012 RPL programming contest with larger input  David Hayden  09302012 I have a program that will solve it in 109 seconds on a 50g. At 689.5 bytes, it's big, but I've made no attempt to reduce the size yet.
Re: Minichallenge: HHC2012 RPL programming contest with larger input  Gilles Carpentier  10012012 Hi David ! Interesting !Wich algorithm did you use ?
PS : I tried to use "processing list" in the inner loop, but with no significiant improvment in term of speed.
Edited: 1 Oct 2012, 8:18 a.m.
Re: Minichallenge: HHC2012 RPL programming contest with larger input  David Hayden  10012012 Here's my algorithm. Many thanks to Eric Smith who gave me the idea to do "furthest point from my furthest point."
The test case I used was perhaps overfriendly to the algorithm. I used 1000 random numbers from 0 to 99,999. So plotting them filled a square area. p1 and p2 were thus two points near diagonal corners and the set of points outside the circle was very small. For my list, there were only 3 points out of the 500 total. One could certainly repeat the process of finding the set of candidates each time you get a better p1 & p2, but there comes a point where the returns diminish, and certainly with only three points to check, it wasn't worth doing.
Dave
Re: Minichallenge: HHC2012 RPL programming contest with larger input  C.Ret  10012012 Ah!Ah! That's a much clever algorithm! As soon as P1 and P2 point are established, a large majority of points in the middle of the circle area will be discarded from the processing list, making the further steps much more efficient.
Following is just illustrations of the algorithm: since 1000 elements is a big bunch of points, I will represent this among as an array of dots:
1.2  Take the first point on the list and find the point furthest from it. Call this point p1. This is a point "near the outside"
1.3  Now find the point furthest from P1. Call this P2 and note the distance from P1 to P2.
1.4  Now comes the important part. Draw a circle with p1 and p2 as the diameter.
1.5  For each point outside the circle, find the furthest point from it.
1.6  If the distance between them is greater than the distance between P1 and P2, then replace P1, P2 and dist with the new values.
2.5  For each point outside the circle, find the furthest point from it.
2.6  If the distance between them is greater than the distance between P1 and P2, then replace P1, P2 and dist with the new values.
3.6  If the distance between them is greater than the distance between P1 and P2, then replace P1, P2 and dist with the new values.
3.7  When you're done, P1 and P2 are the furthest points and dist is the distance between them.
Yeh! Now I have to find a way to implement this into an HP28S !
Re: Minichallenge: HHC2012 RPL programming contest with larger input  David Hayden  10022012 Thanks for the diagrams! They really make the algorithm clearer. However, you've missed a step in the process. Using your example, you start with the point (6,5). Finding the point furthest from it, you get the point (1,1). This point (1,1) becomes p1. The next step is to find the point furthest from p1, so that would be (9,6) in your diagram. At this point, you're done.
Also, your diagrams seem to imply that when you examine the candidates, as soon as you find *some* pair that is more distant than the current p1 & p2, you draw the circle for the new candidate set. I envisioned finding the pair that is *most* distant from a candidate so you get the largest circle possible. Thus in your step 1.5, you start with point (2,6) and find that (7,1) is more distant that the current p1 and p2. Rather that drawing the circle for (2,6) and (7,1), I think it's better to continue the search and find (9,1) is most distant from (2,6).
Re: Minichallenge: HHC2012 RPL programming contest with larger input  Gilles Carpentier  10022012 Hi have you some 'test cases' ? I'm not sure at all that this prog is ok here but here it is in 307 Bytes. In fact i would be suprise if there are no problems here because i'm not sure to understand the algorthim ;) btw the smalls tests I do seems OK I tooks ~ 30sec for a 500 points input at real speed emulator (probably less on the real calc)
The input must be like : but it's easy to change this as we saw before. PS : Could I insert a << UNTIL ... _'lp' STO_... END >> sequence at the end ?...This will delete all the points inside the circle for the next loop. With my small tests, this change nothing and I got the right answer in both case :O PS2 : I realize that in simple cases (see the previous one of C.ret and the example of the chalenge) the d max is find directly :
1/ take a 'random' point (the first)And i get d from P1 to P2.... I need an example where this so simple approach don't work but... it seems not so easy lol
About point 1, I think it could be better to take for first (and virtual)point the 'barycentre' (english word ?) of all the points.
1/ Where is the 'center' of the figure
Edited: 3 Oct 2012, 2:30 a.m.
Re: Minichallenge: HHC2012 RPL programming contest with larger input  Gilles Carpentier  10032012 And what do you think of this very simple algorithm :
1/ Take the first point of the list ( a random point will work) Distance from P1 to P2 seems to be the result... If you have a counter example, i'm interested
« 185 Bytes ~ 20 sec for 500 points Input must be in the form { ( 1 2) (4 5) (7 8) }
Edited: 3 Oct 2012, 11:56 a.m.
Re: Minichallenge: HHC2012 RPL programming contest with larger input  Paul Dale  10032012 Quote:
(0, 0) First point is (0, 0). Furthest from that is (1, 1). Furthest from that is (0, 0). The result is sqrt(2). Actual longest is sqrt(2.42). This is the pseudodiameter algorithm. It is fast but doesn't guarantee the correct result  I believe a guaranteed correct result requires an O(n^{2}) worst case algorithm. Even so, it usually gives the correct answer or something very close.  Pauli
Edited: 5 Oct 2012, 5:45 p.m. after one or more responses were posted
Re: Minichallenge: HHC2012 RPL programming contest with larger input  Gilles Carpentier  10052012 I understand now the David Hayden idea and algortithm !
Re: Minichallenge: HHC2012 RPL programming contest with larger input  David Hayden  10052012 Quote:I've been trying to think of an algorithm that is provably faster that O(n^{2}) in the worst case, but so far no luck. The torture case for my algorithm would be points around a circle where some are just inside and others are just outside. It's an interesting problem.
Dave
