▼
Posts: 1,545
Threads: 168
Joined: Jul 2005
Here you go!
RPL Contest
Please do not post any solutions here until after Noon CDT Sunday September 22, 2012.
Questions here and I will be checking periodically. Enjoy!
Edited: 22 Sept 2012, 10:03 a.m.
▼
Posts: 260
Threads: 0
Joined: Oct 2008
Hi,
Thanks, it looks to be a great challenge...
If, I correctly interpret the problem,
diameter of { 0 3 0 0 4 0 3 4 4 3 } is 5
and
diameter of { 3 6 5 2 3 1 8 2 6 5 4 4 7 4 } is 6.4031
Edited: 22 Sept 2012, 12:58 p.m.
▼
Posts: 163
Threads: 7
Joined: Jul 2007
Isn't the drawing somewhat misleading? Finding the smallest enclosing circle of a set of points is a different problem.
▼
Posts: 260
Threads: 0
Joined: Oct 2008
Hi,
Yes, that's right, finding the smallest enclosing circle is another problem.
To make the drawing less confusing, I may have illustrate another list of points:
{ 1 0 0 0 1 1 2 3 3 4 4 0 } returns 5
Posts: 3,229
Threads: 42
Joined: Jul 2006
There doesn't appear to be a winning criteria here....
- Pauli
▼
Posts: 1,545
Threads: 168
Joined: Jul 2005
"The winning program will be the one for which size*speed (bytes*sec) is least, where the speed of execution will be determined for one or more test cases chosen by the judge."
▼
Posts: 468
Threads: 17
Joined: May 2011
I've my solution...
What is noon Sunday in GMT times ?
Posts: 151
Threads: 8
Joined: Oct 2009
With the completely new programming language of the 39gII, perhaps we'll see similar challenges for it in the future. Meanwhile, thank you, Gene and company for the nifty challenges and terrific Conferences! And thank you, Forum goers, for your insight, skills, and delightful exchanges.
Posts: 468
Threads: 17
Joined: May 2011
Hi Gene,
I have a doubt :
It is write for the input list : "The list will contain at least one pair of numbers..."
Does that mean that { 2 3 } is a correct input which seems a non sense ? Does the output must be zero if this input is allowed ?
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
My assumption is that yes, a single point is legal and that the distance in this case is zero.
- Pauli
Posts: 260
Threads: 0
Joined: Oct 2008
Hi, Gilles.
Yes, that correct the rule clearly indicate that { 2 3 } is a correct entry;
And yes, in this case, the diameter of the circle have to be zero, since that is the only size for a circle passing the two farest distant instance of the only point !
In the same idea,{ 2 3 2 3 } or { 2 3 2 3 } or { 2 3 2 3 ... 2 3 }are also instances returnng zero sized circle diameter.
At least, all this is my interpretation and assumption for the excercice.
Posts: 468
Threads: 17
Joined: May 2011
Hi all !
I'm back to home and saw the RPN contribution, so I suppose it's time to publish ;)
«
DUP SIZE 2. / 1. + -> s
«
EVAL DUP2
1. s FOR n R->C s 2. * n - ROLLD NEXT
0.
s 2. + 4. FOR n
4. n FOR m OVER m PICK - ABS MAX NEXT
NIP
-1. STEP
NIP
»
»
145 Bytes
Run time = 0.2772 s with the example of the contest on my real HP50G
I suppose there could be a trick with the "up to 10 pairs of numbers" limit, but i dont see ... The limitation of this program is the just memory....
Edited: 23 Sept 2012, 3:33 p.m.
▼
Posts: 468
Threads: 17
Joined: May 2011
Improve version (140 Bytes) and some comments :
«
LIST-> 2. / 1. + -> s @ 'explode' the list on the stack and size/2+1 in 's'
«
DUP2 @ Trick for one point only input
1. s FOR n R->C s 2. * n - ROLLD NEXT @ Transform all datas in complex numbers (points) on the stack
0. @ Init the max distance
s 2. + 4. FOR n
4. n FOR m OVER m PICK - ABS MAX NEXT @ get the max distance all on the stack
NIP
-1. STEP
NIP
»
»
Edited: 23 Sept 2012, 6:12 p.m.
Posts: 3,229
Threads: 42
Joined: Jul 2006
Another interesting problem. Looks to be the diameter of a graph unless I'm mistaken. I'm not aware of any algorithm better than the O(n2) brute force approach. Pull out my only working RPL device, a veteran HP 28S with replacement battery cover and code it:
<<
DUP SIZE 2 / 0 DUP -> L N D A # List, N, diameter, first point
<<
IF N 1 > # Special case single point list
THEN
1 N 1 -
FOR I
L I 2 * GET
L I 2 * 1 - GET # Get Ith point
R->C 'A' STO # as a complex number
I 1 + N
FOR J
L J 2 * GET
L J 2 * 1 - GET # Get Jth point
R->C A - ABS # distance apart
D MAX 'D' STO # keep the maximum distance
NEXT
NEXT
END
>>
D
>>
Don't bother typing this in and running it. It isn't optimised for speed or size. The later RPL machines add lots of nice list processing features that the 28S doesn't have so a 28S program is unlikely to be competitive.
There is a pseudo diameter algorithm for a graph which is faster but not guaranteed to get the maximal result. This is essentially pick a point and find the farthest from it. Repeat to get the diameter. Perhaps repeat a couple of times but we're getting back towards the O(n2) obvious algorithm especially when Nmax is 10.
Can we determine the minimum and maximum coordinates and use that instead? No, it is possible to construct a set where the maximal distance doesn't include the points with minimum or maximum coordinates. (0, 1-eps), (0, eps-1), (1-eps, 0), (eps-1, 0) define a circle about the origin with diameter 2-2*eps < 2. The two points (2*eps-1, 2*eps-1) and (1-2*eps, 1-2*eps) line strictly inside these bounds but are almost 2*sqrt(2) > 2.8 apart.
There are plenty of optimisations possible. The code to extract the values from the list isn't ideal and should be in a subroutine. An array of complex values would be better again and the code to convert should pay for itself given the number of times it is executed. Unfortunately, the 28S can't have a local variable with an array in it and it requires a list based index. This means the overhead for using an array of complex numbers is more than the benefits:
<<
LIST-> 2 / DUP 1 ->LIST (0,0) CON 0 DUP -> N A D E
<<
1 N FOR I
R->C A I 1 ->LIST ROT PUT 'A' STO
NEXT
IF N 1 >
THEN
1 N OVER - FOR I
A I 1 ->LIST GET 'E' STO
I 1 + N FOR J
A J 1 ->LIST GET E - ABS D MAX 'D' STO
NEXT
NEXT
END
D
>>
>>
This version is slower than the list based approach for small lists and about the same for the maximum sized list.
One further optimisation is possible here. Instead of two loops, one to pack the complex values and one to find the diameter, they could be combined.
<<
LIST-> 2 / DUP 1 ->LIST (0,0) CON 0 DUP -> N A D E
<<
1 N FOR I
R->C DUP 'E' STO A I 1 ->LIST ROT PUT 'A'
IF I 1 >
THEN
1 I OVER - FOR J
A J 1 ->LIST GET E - ABS D MAX 'D' STO
NEXT
END
NEXT D
>>
>>
Performance has improved and the size is reduced but this isn't as fast as the original list only approach.
Sorry no sizes or execution times. I don't remember how to find the size of a program on a 28S and I suspect its timings won't be good enough.
- Pauli
▼
Posts: 468
Threads: 17
Joined: May 2011
Here is another way to do with the 50G.
It uses lot list processing. It is a little shorter that my full stack version below (140 Bytes vs 145), but 2 or more times slower :
«
2. « NSUB 2. MOD {R->C} {DROP2} IFTE » DOSUBS @ Transform the list in complex number (point) list
{} SWAP 2. OVER SIZE START
DUP HEAD SWAP TAIL DUP ROT - ABS ROT + SWAP
NEXT
DROP 0. + « MAX » STREAM
»
My 2 versions use the same algorithm to compare each point with each others and avoid to compare twice the sames points.
Both use a trick to work with 1 point only to return zero.
EDIT : I think my "full stack" version could work on a 28 with just changing NIP with SWAP DROP... I m fairly sure that the full stack approach is the best for time execution in this case but ... who kwnows ;)
The problem with my list processing version is that I augment the size of the list in each loop and this is very slow in RPL
Note that << MAX >> STREAM is a very easy way to find the max of a list on the 50. Perhaps a way on the 50 is to use the STREAM command to calculate the distance and get the MAX in the same time ... could be an interesting approach
Edited: 23 Sept 2012, 6:33 p.m.
▼
Posts: 260
Threads: 0
Joined: Oct 2008
Hi, Gilles
As you, I use the MAX function to stream maximal diameter out of the computation.
As you, I also convert the initial list to a row array format containing complex number since with complex, distance is easely compute through the ABS function.
But, in my code, the ABS distance computation is hide into the RNRM instruction that operate norm operation (ABS equivalent) for each element in a row and only returns the maximal.
This is my code for HP-28S which use the same algorithm, but look much shorter :
« LIST-> 2 / -> n // desmount original list and get number of points
« { n 2 } ->ARRY [1,(0,1)] * -> D // convert into complex row vector
« 0 // Initiate max diameter value
1 n FOR i // for each point in the row vector
D DUP DUP i GET CON - RNRM MAX // compute distance with other points and keep maximum
NEXT
»
»
»
▼
Posts: 468
Threads: 17
Joined: May 2011
Hi C.ret...
Beautifull ! shorter but slower ....
1.2 sec vs 0.27 with 'full stack' and ~ 0.6s with list processing on the 50G. It goes faster on the real HP50G than with the "authentic calculator speed" of EMU48 wich is not very accurate
Edited: 24 Sept 2012, 7:13 a.m.
▼
Posts: 260
Threads: 0
Joined: Oct 2008
Hi, Gilles
I only realise now that my code is not speed optimize !
The FOR i loop compare each point two times !
The distance is symetric, ABS((2,3)-(1,1)) is equivalent to ABS((1,1)-(2,3))
A speed improuve algorithm may be :
« LIST-> 2 / -> n // desmount original list and get number of points
« { n 2 } ->ARRY [1,(0,1)] * -> D // convert into complex row vector
« 0 // Initiate max diameter value
1 n 2 / FOR i // for half of the points in the row vector
D DUP DUP i GET CON - RNRM MAX // compute distance with other points and keep maximum
NEXT
»
»
»
This will reduce the running time by a factor 2 (nearly) !
▼
Posts: 528
Threads: 40
Joined: Dec 2008
It's a very minor point, but you can save 2.5 bytes by replacing DUP DUP with DUPDUP.
Dave
▼
Posts: 260
Threads: 0
Joined: Oct 2008
Yes, that right. Unfortunetely, DUPDUP don't exist on my HP-28S.
For an HP-48/50g vrsion, perhaps have instruction LIST-> to be exchange with OBJ-> as well.
Posts: 260
Threads: 0
Joined: Oct 2008
Hi Pauli,
I made the same analysis as you. Consequently I also use exactly the same algorithm.
I just have spare much more operation by converting the original list into a row vector of complex (array of points 's coordinate).
This result in a shorter code (see post below)
From this row vector of complex coordinate, a substration and ABS norm make easy to compute distance. And MAX is used to keep the largest distance into the stack.
Posts: 9
Threads: 0
Joined: Sep 2012
This is my version with the 50G:
\<< 0 1 PICK3 SIZE 1 -
FOR I OVER I DUP 1 + SUB 1 I 2 -
FOR J PICK3 J DUP 1 + SUB OVER - DUP * EVAL + ROT MAX SWAP 2
STEP DROP 2
STEP NIP \v/
\>>
Bytes: 125
-Edwin
▼
Posts: 9
Threads: 0
Joined: Sep 2012
the same code enhanced (50G)
« 0. 1. PICK3 SIZE 1. -
FOR I OVER I DUP 1. + SUB 1. I 2. -
FOR J PICK3 J DUP 1. + SUB OVER - AXL ABS ROT MAX SWAP 2.
STEP DROP 2.
STEP NIP
»
Bytes: 120.5
-Edwin
Posts: 3,229
Threads: 42
Joined: Jul 2006
I figured I'd try this problem on the 34S. Since there are no lists, I've changed things so that the values are in registers 00 .. n and n+1 is on the stack. So the problem example is set up:
00: 1 05: 3
01: 1 06: 3
02: 0 07: 4
03: 0 08: 1
04: 2 09: 0
And 10 is on the stack.
My not heavily optimised program for this is:
01: LBL A
02: # 002
03: -
04: x[<=]0?
05: CLx
06: x=0?
07: RTN
08: # 002
09: SDR 005
10: +
11: STO J
12: # 000
13: LBL 00
14: RCL J
15: STO K
16: DROP
17: LBL 01
18: [cmplx]RCL[->]J
19: [cmplx]RCL-[->]K
20: [cmplx]ABS
21: [<->] XZTT
22: MAX
23: DSL K
24: GTO 01
25: DSE J
26: GTO 00
27: END
Of these, the END and the three LBLs can be removed for a total of 23 steps. This is 46 bytes. The five point example executes instantly, ten points in well under a second.
- Pauli
Edited: 24 Sept 2012, 5:20 p.m.
Posts: 163
Threads: 7
Joined: Jul 2007
If the entry list was a list of complex points, it would be easy:
\<<
0
SWAP
2
\<< - ABS MAX \>>
DOCOMB
\>>
That is, if only we had the command DOCOMB ;-)
DOCOMB would work much like DOLIST and DOSUBS.
Its arguments are:
3: list
2: n = number of list elements to be taken in every iteration
1: object
DOCOMB will evaluate <object> for every combination of n elements taken from list L.
eg.
3: { 1 2 3 4 }
2: 3
1: \<< 3 \->LIST \>>
DOCOMB
will result in
{ 1 2 3 }
{ 1 2 4 }
{ 1 3 4 }
{ 2 3 4 }
versions of DOCOMB for n=2 or n=3 are easy:
@ DOCOMB for n=2
\<<
3 PICK SIZE
\-> L n ob s
\<<
1 s 1 -
FOR i
i 1 + s
FOR j
L i GET L j GET ob EVAL
NEXT
NEXT
\>>
\>>
@ DOCOMB for n=3
\<<
3 PICK SIZE
\-> L n ob s
\<<
1 s 2 -
FOR i
i 1 + s 1 -
FOR j
j 1 + s
FOR k
L i GET L j GET L k GET ob EVAL
NEXT
NEXT
NEXT
\>>
\>>
Your mission, if you choose to accept it, is to write DOCOMB so
that it will accept any n, n=1..size of list. Any single
combination must have the objects in the same order as they appear
in the list. Successive combinations may be generated in any order.
Success, Werner
Edited: 27 Sept 2012, 1:56 a.m. after one or more responses were posted
▼
Posts: 260
Threads: 0
Joined: Oct 2008
Quote:
If the entry list was a list of complex points, it would be easy:
I agree with that !
But, we have to recognised that we are not far from it, a couple of instructions will do it!
Please consider the following trace :
PROGRAM STEPS STACK AND DISPLAY
-------------------- ---------------------------------------
« 1: { 1 1 0 0 2 3 3 4 1 0 }
LIST-> 11: 1
10: 1
9: 0
8: 0
7: 2
6: 3
5: 3
4: 4
3: 1
2: 0
1: 10.
2. / 11: 1
10: 1
9: 0
8: 0
7: 2
6: 3
5: 3
4: 4
3: 1
2: 0
1: 5.
-> n « 10: 1
9: 1
8: 0
7: 0
6: 2
5: 3
4: 3
3: 4
2: 1
1: 0
{ n 2 } ->ARRY 1: [[ 1 1 ]
[ 0 0 ]
[ 2 3 ]
[ 3 4 ]
[ 1 0 ]]
[ (1,0) (0,1) ] 2: [[ 1 1 ][ 0 0 ][ 2 3 ][ 3 4 ][ 1 0]]
1: [ (1,0) (0,1) ]
* 1: [(1,1) (0,0) (2,3) (3,4) (1,0)]
-> D « 0 1: 0
1 n FOR i 1: 0
D 2: 0
1: [(1,1) (0,0) (2,3) (3,4) (1,0)]
DUP DUP 4: 0
3: [(1,1) (0,0) (2,3) (3,4) (1,0)]
2: [(1,1) (0,0) (2,3) (3,4) (1,0)]
1: [(1,1) (0,0) (2,3) (3,4) (1,0)]
i GET CON 3: 0
2: [(1,1) (0,0) (2,3) (3,4) (1,0)]
1: [(1,1) (1,1) (1,1) (1,1) (1,1)]
- 2: 0
1: [(0,0) (-1,-1) (1,2) (2,3) (0,-1)]
RNRM 2: 0
1: 3.60555127546
MAX 1: 3.60555127546
NEXT 1: 3.60555127546
D 2: 3.60555127546
1: [(1,1) (0,0) (2,3) (3,4) (1,0)]
DUP DUP 4: 3.60555127546
3: [(1,1) (0,0) (2,3) (3,4) (1,0)]
2: [(1,1) (0,0) (2,3) (3,4) (1,0)]
1: [(1,1) (0,0) (2,3) (3,4) (1,0)]
i GET CON 3: 3.60555127546
2: [(1,1) (0,0) (2,3) (3,4) (1,0)]
1: [(0,0) (0,0) (0,0) (0,0) (0,0)]
- 2: 3.60555127546
1: [(1,1) (0,0) (2,3) (3,4) (1,0)]
RNRM 2: 3.60555127546
1: 5.
MAX 1: 5.
NEXT 1: 5.
.........
RNRM 2: 5.
1: 4.472135955
MAX 1: 5.
NEXT 1: 5.
» » » 1: 5.
-------------------- ---------------------------------------
« LIST-> 2 / -> n
« { n 2 } ->ARRY [ 1 (0,1) ] * -> D
« 0
1 n FOR i
D DUP DUP i GET CON - RNRM MAX NEXT
»
»
»
The initial list is easely converted into a row array contening the coordinate of the points as complex coordinates by the two first line of the code.
Edited: 26 Sept 2012, 9:39 a.m.
Posts: 468
Threads: 17
Joined: May 2011
"If the entry list was a list of complex points, it would be easy: "
Here is another easy way to do :
2. « IF NSUB 2. MOD THEN R->C ELSE DROP2 END » DOSUBS
{ 3 6 5 2 3 1 8 2 6 5 4 4 7 4 }
->
{ (3.,6.) (5.,2.) (3.,1.) (8.,2.) (6.,5.) (4.,4.) (7.,4.) }
118 Bytes solution
«
2. « IF NSUB 2. MOD THEN R->C ELSE DROP2 END » DOSUBS
DUP SIZE NDUPN ->LIST DUP TRAN
\GSLIST SWAP \GSLIST - ABS
0 + «MAX» STREAM
»
Edited: 26 Sept 2012, 5:10 p.m. after one or more responses were posted
▼
Posts: 528
Threads: 40
Joined: Dec 2008
Quote:
2. « IF NSUB 2. MOD THEN R->C ELSE DROP2 END » DOSUBS
{ 3 6 5 2 3 1 8 2 6 5 4 4 7 4 }
->
{ (3.,6.) (5.,2.) (3.,1.) (8.,2.) (6.,5.) (4.,4.) (7.,4.) }
Here's a slight size improvement. If there's a way to put a built-in command directly on the stack, that would save another 5 bytes:
1. « NSUB 2. MOD NOT { R->C } IFT » DOSUBS
▼
Posts: 163
Threads: 7
Joined: Jul 2007
2. \<< R\->C -1. NSUB ^ DROPN \>> DOSUBS
Cheers, Werner
▼
Posts: 468
Threads: 17
Joined: May 2011
Now we have a 108 Bytes program ;)
This one in 99 Bytes:
«
2. « R->C -1. NSUB ^ DROPN » DOSUBS
DUP SIZE NDUPN ->LIST DUP TRAN
\GSLIST SWAP \GSLIST - ABS
SORT REVLIST HEAD
»
But both have problem with single point entry list (SigmaList 'bug')
Edited: 27 Sept 2012, 6:09 a.m.
▼
Posts: 260
Threads: 0
Joined: Oct 2008
Yes, where LIST-> -> n « {n 2} ->ARRY [1 (0,1)] * » or shortly LIST-> 2 / { 2 } + ->ARRY [1 (0,1)] * have no problem with inital single point list ! :-)
▼
Posts: 468
Threads: 17
Joined: May 2011
Hi C.ret
This works fine but takes a lot of bytes !
I would try to be less than 100 Bytes whatever speed (I think it is imposssible to be quicker than a full stack approach ) ;)
<< LIST-> 2 / { 2 } + ->ARRY [1 (0,1)] * >>
takes 58.5 Bytes
<< LIST-> 2 / { 2 } + ->ARRY [1 'i'] * >>
only 47.5 but in this case, we must be in complex mode, so we have to set and restore flags...
« 2. « R->C -1. NSUB ^ DROPN » DOSUBS »
is 46 Bytes
Edited: 27 Sept 2012, 12:15 p.m.
Posts: 468
Threads: 17
Joined: May 2011
A 98 bytes version. Handle one point case.
«
1. « IFERR R->C THEN END » DOSUBS
DUP HEAD + DUP SIZE NDUPN ->LIST
DUP TRAN \GSLIST SWAP \GSLIST -
AXL RNRM
»
AXL convert list<->matrix
Posts: 163
Threads: 7
Joined: Jul 2007
C'mon. That Mission Impossible quote was a joke, you know ;-)
|