▼
Posts: 528
Threads: 40
Joined: Dec 2008
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
▼
Posts: 468
Threads: 17
Joined: May 2011
I suppose 1000 random numbers means 500 points ?
▼
Posts: 528
Threads: 40
Joined: Dec 2008
Yes. 1,000 numbers, 500 points.
▼
Posts: 260
Threads: 0
Joined: Oct 2008
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
« { n 2 } >ARRY [1,(0,1)] * > D
« 0
1 n 2 / FOR i
D DUP DUP i GET CON  RNRM MAX
NEXT
» » »
Edited: 29 Sept 2012, 6:11 p.m.
Posts: 468
Threads: 17
Joined: May 2011
I change nothing to my original code :
« @ SEE 1 Input list
LIST 2. / 1. + s @ SEE 2 Put the list on the stack and size/2+1 in 's'
«
DUP2 @ SEE 3 Trick for one point only input
1. s FOR n RC s 2. * n  ROLLD NEXT @ SEE 4 Transform in complex number on the stack
@ and put each result in top of the stack
@ SEE 5 : result at the end of the loop
0. @ Init the max distance
s 2. + 4. FOR n
n 1. DISP
4. n FOR m
OVER m PICK @ SEE 6
 @ SEE 7
ABS @ SEE 8
MAX @ SEE 9
NEXT
@ The idea is to compare each element to each other
NIP @ NIP is shortcut for OVER SWAP (delete item 2 on the stack)
1 STEP
NIP
»
»
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
▼
Posts: 528
Threads: 40
Joined: Dec 2008
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.
▼
Posts: 468
Threads: 17
Joined: May 2011
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.
In 'C' or other compiled language (or on a 39Gii), this will run in quite no time( perhaps few seconds with the embedded 39gii language). In RPL the idea may be to avoid the 2 imbricated loop or delete some points to avoid unnecessary calculations ( near the central point 'barycenter' ? \GSLIST 5000. / ). A smarter approach is needed but not obvious. Probably it exists some mathematical study about this
Edited: 1 Oct 2012, 8:18 a.m.
▼
Posts: 528
Threads: 40
Joined: Dec 2008
Here's my algorithm. Many thanks to Eric Smith who gave me the idea to do "furthest point from my furthest point."
 Convert the list to a list of complex numbers.
 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"
 Now find the point furthest from p1. Call this p2 and note the distance from p1 to p2.
 Now comes the important part. Draw a circle with p1 and p2 as the diameter. The distance between any two points inside the circle must be less than the diameter. Therefore, if two points exist that are further apart than p1 and p2, then at least one of them must lie outside this circle. See here for an example.
 For each point outside the circle, find the furthest point from it. If the distance between them is greater than the distance between p1 and p2, then replace p1, p2 and dist with the new values.
 When you're done, p1 and p2 are the furthest points and dist is the distance between them.
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
▼
Posts: 260
Threads: 0
Joined: Oct 2008
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.1  Convert the list to a list of complex numbers.
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.4  Draw a circle with p1 and p2 as the diameter.
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.4  Now comes the important part. Draw a circle with p1 and p2 as the diameter.
3.5  For each point outside the circle, find the furthest point from it.
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 !
▼
Posts: 528
Threads: 40
Joined: Dec 2008
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).
▼
Posts: 468
Threads: 17
Joined: May 2011
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)
«
0. 0. > lp p d @ list of points, point, distance
«
DO
'lp' 1. GET @ Get the first point of the list point
1 2 START @ To get P1 and P2
DUP 'p' STO @ Current point to search furthest
lp  ABS @ Distance of all points from p
0. 'd' STO @ Init the ditance to 0.
1. « IF DUP d > THEN 'd' STO NSUB 'p' STO ELSE DROP END » DOSUBS @ Get the point of the list furthest to p
'lp' p GET
DUP
NEXT
DROP @ here we have p1 and p2 on the stack
+ 2. / lp SWAP  'lp' STO @ Change the origin of the graph to be at the center of the circle
"!" lp ABS d > lp IFT @ Select all the points outside the circle
UNTIL
IF DUP "!" SAME THEN DROP 1. ELSE 'lp' STO DROP 0. END @ If no point we have the max ! END
END @ else repeat again with new list of point
d
»
»
The input must be like :
{ (1 6) (2 6) (1 1) (7 1) (9 3) (6 5) (9 1) (7 1) }
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)
2/ search the furthest point > P1
3/ search the furthest point of P1 > P2
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.
It is very easy to calculate in 3 commands and could avoid some special configuration of points.
It will work like we do intuitively :
1/ Where is the 'center' of the figure
2/ Search the furthest > P1
3/ Search the furthest of P1 > P2
Edited: 3 Oct 2012, 2:30 a.m.
Posts: 468
Threads: 17
Joined: May 2011
And what do you think of this very simple algorithm :
1/ Take the first point of the list ( a random point will work)
2/ Search the furthest point of this initial point > P1
3/ Search the furthest point of P1 > P2
Distance from P1 to P2 seems to be the result...
If you have a counter example, i'm interested
«
0. 0. > p d @ point, distance
«
DUP HEAD @ Get the first point of the list point
1 2 START @ To get P1 and P2
DUP 'p' STO @ Current point to search furthest
OVER  ABS @ Distance of all points from p
0. 'd' STO @ Init the ditance to 0.
1. « IF DUP d > THEN 'd' STO NSUB 'p' STO ELSE DROP END » DOSUBS @ Get the point of the list furthest to p
DUP p GET
SWAP OVER
NEXT
DROP2  ABS
»
»
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.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
Quote: If you have a counter example, i'm interested
(0, 0)
(1, 1)
(0, 1.1)
(1.1, 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
▼
Posts: 468
Threads: 17
Joined: May 2011
I understand now the David Hayden idea and algortithm !
Posts: 528
Threads: 40
Joined: Dec 2008
Quote:
I believe a guaranteed correct result requires an O(n^{2}) worst case algorithm.
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
