Here you go!
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.
HHC 2012 RPL Programming Contest

09222012, 08:57 AM
Here you go!
Please do not post any solutions here until after Noon CDT Sunday September 22, 2012. Edited: 22 Sept 2012, 10:03 a.m.
09222012, 11:04 AM
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 5and 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.
09222012, 05:39 PM
There doesn't appear to be a winning criteria here....
09222012, 05:44 PM
"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."
09222012, 06:04 PM
I've my solution... What is noon Sunday in GMT times ?
09222012, 09:55 PM
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.
09232012, 05:40 AM
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 ?
09232012, 07:05 AM
My assumption is that yes, a single point is legal and that the distance in this case is zero.
09232012, 12:28 PM
Hi, Gilles.
Yes, that correct the rule clearly indicate that { 2 3 } is a correct entry; 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.
09232012, 03:29 PM
Hi all ! I'm back to home and saw the RPN contribution, so I suppose it's time to publish ;)
«
145 Bytes
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.
09232012, 05:23 PM
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(n^{2}) brute force approach. Pull out my only working RPL device, a veteran HP 28S with replacement battery cover and code it:
<< 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(n^{2}) obvious algorithm especially when N_{max} 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, 1eps), (0, eps1), (1eps, 0), (eps1, 0) define a circle about the origin with diameter 22*eps < 2. The two points (2*eps1, 2*eps1) and (12*eps, 12*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:
<< 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.
<< Performance has improved and the size is reduced but this isn't as fast as the original list only approach.
09232012, 05:35 PM
Here is another way to do with the 50G.
«
My 2 versions use the same algorithm to compare each point with each others and avoid to compare twice the sames points.
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 ;) 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.
09232012, 06:01 PM
Improve version (140 Bytes) and some comments :
«
Edited: 23 Sept 2012, 6:12 p.m.
09232012, 07:40 PM
This is my version with the 50G: \<< 0 1 PICK3 SIZE 1  Bytes: 125 Edwin
09242012, 02:26 AM
Hi, Gilles
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 HP28S which use the same algorithm, but look much shorter :
« LIST> 2 / > n // desmount original list and get number of points
09242012, 06:20 AM
Hi Pauli,
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.
09242012, 06:48 AM
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.
09242012, 07:06 AM
the same code enhanced (50G) « 0. 1. PICK3 SIZE 1. Bytes: 120.5 Edwin
09242012, 07:56 AM
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 And 10 is on the stack. My not heavily optimised program for this is:
01: LBL A 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.
09242012, 08:49 AM
Isn't the drawing somewhat misleading? Finding the smallest enclosing circle of a set of points is a different problem.
09242012, 12:51 PM
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
09262012, 08:24 AM
If the entry list was a list of complex points, it would be easy: \<<Success, Werner Edited: 27 Sept 2012, 1:56 a.m. after one or more responses were posted
09262012, 09:26 AM
Hi, Gilles
I only realise now that my code is not speed optimize !
A speed improuve algorithm may be : « LIST> 2 / > n // desmount original list and get number of points This will reduce the running time by a factor 2 (nearly) !
09262012, 09:32 AM
Quote: 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
« LIST> 2 / > n 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.
09262012, 02:38 PM
"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.) }
«
Edited: 26 Sept 2012, 5:10 p.m. after one or more responses were posted
09262012, 10:39 PM
It's a very minor point, but you can save 2.5 bytes by replacing DUP DUP with DUPDUP. Dave
09262012, 11:02 PM
Quote:Here's a slight size improvement. If there's a way to put a builtin command directly on the stack, that would save another 5 bytes:
1. « NSUB 2. MOD NOT { R>C } IFT » DOSUBS
09272012, 01:57 AM
C'mon. That Mission Impossible quote was a joke, you know ;)
09272012, 02:05 AM
2. \<< R\>C 1. NSUB ^ DROPN \>> DOSUBSCheers, Werner
09272012, 05:32 AM
Now we have a 108 Bytes program ;)
«
But both have problem with single point entry list (SigmaList 'bug') Edited: 27 Sept 2012, 6:09 a.m.
09272012, 12:01 PM
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 ! :)
09272012, 12:04 PM
Yes, that right. Unfortunetely, DUPDUP don't exist on my HP28S. For an HP48/50g vrsion, perhaps have instruction LIST> to be exchange with OBJ> as well.
09272012, 12:08 PM
Hi C.ret
This works fine but takes a lot of bytes ! << 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.
09272012, 06:11 PM
A 98 bytes version. Handle one point case.
« AXL convert list<>matrix 
« Next Oldest  Next Newest »
