HHC 2012 RPL Programming Contest « Next Oldest | Next Newest »

 ▼ Gene Wright Unregistered Posts: 1,545 Threads: 168 Joined: Jul 2005 09-22-2012, 08:57 AM 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. ▼ C.Ret Unregistered Posts: 260 Threads: 0 Joined: Oct 2008 09-22-2012, 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 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. ▼ Werner Unregistered Posts: 163 Threads: 7 Joined: Jul 2007 09-24-2012, 08:49 AM Isn't the drawing somewhat misleading? Finding the smallest enclosing circle of a set of points is a different problem. ▼ C.Ret Unregistered Posts: 260 Threads: 0 Joined: Oct 2008 09-24-2012, 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 ``` Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-22-2012, 05:39 PM There doesn't appear to be a winning criteria here.... - Pauli ▼ Gene Wright Unregistered Posts: 1,545 Threads: 168 Joined: Jul 2005 09-22-2012, 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." ▼ Gilles Carpentier Unregistered Posts: 468 Threads: 17 Joined: May 2011 09-22-2012, 06:04 PM I've my solution... What is noon Sunday in GMT times ? Jim Horn Unregistered Posts: 151 Threads: 8 Joined: Oct 2009 09-22-2012, 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. Gilles Carpentier Unregistered Posts: 468 Threads: 17 Joined: May 2011 09-23-2012, 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 ? ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-23-2012, 07:05 AM My assumption is that yes, a single point is legal and that the distance in this case is zero. - Pauli C.Ret Unregistered Posts: 260 Threads: 0 Joined: Oct 2008 09-23-2012, 12:28 PM 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. Gilles Carpentier Unregistered Posts: 468 Threads: 17 Joined: May 2011 09-23-2012, 03:29 PM 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. ▼ Gilles Carpentier Unregistered Posts: 468 Threads: 17 Joined: May 2011 09-23-2012, 06:01 PM 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. Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-23-2012, 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(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 ▼ Gilles Carpentier Unregistered Posts: 468 Threads: 17 Joined: May 2011 09-23-2012, 05:35 PM 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. ▼ C.Ret Unregistered Posts: 260 Threads: 0 Joined: Oct 2008 09-24-2012, 02:26 AM 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 » » » ``` ▼ Gilles Carpentier Unregistered Posts: 468 Threads: 17 Joined: May 2011 09-24-2012, 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. ▼ C.Ret Unregistered Posts: 260 Threads: 0 Joined: Oct 2008 09-26-2012, 09:26 AM 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) ! ▼ David Hayden Unregistered Posts: 528 Threads: 40 Joined: Dec 2008 09-26-2012, 10:39 PM It's a very minor point, but you can save 2.5 bytes by replacing DUP DUP with DUPDUP. Dave ▼ C.Ret Unregistered Posts: 260 Threads: 0 Joined: Oct 2008 09-27-2012, 12:04 PM 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. C.Ret Unregistered Posts: 260 Threads: 0 Joined: Oct 2008 09-24-2012, 06:20 AM 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. Edwin Unregistered Posts: 9 Threads: 0 Joined: Sep 2012 09-23-2012, 07:40 PM 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 ▼ Edwin Unregistered Posts: 9 Threads: 0 Joined: Sep 2012 09-24-2012, 07:06 AM 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 Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-24-2012, 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 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. Werner Unregistered Posts: 163 Threads: 7 Joined: Jul 2007 09-26-2012, 08:24 AM 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

 Possibly Related Threads… Thread Author Replies Views Last Post Writing RPL programs on OS X Sean Freeman 18 5,152 11-30-2013, 03:59 PM Last Post: Sean Freeman 48G vs 49G+ User RPL Speed Comparison John Colvin 7 2,585 11-16-2013, 10:07 PM Last Post: Han RPL 32 David Hayden 4 2,068 11-11-2013, 11:34 AM Last Post: David Hayden HHC 2013 RPN Programming Challenge - Final Thought Jeff O. 7 2,361 10-17-2013, 11:02 AM Last Post: Jeff O. HHC 2013 programming contest winners Brian Walsh 52 12,641 09-26-2013, 11:39 PM Last Post: David Hayden Box left at HHC Tim Wessman 1 1,594 09-26-2013, 11:05 PM Last Post: Wlodek Mier-Jedrzejowicz HHC 2013 speakers' files Joe Horn 2 1,608 09-26-2013, 02:51 AM Last Post: Geoff Quickfall HHC 2013 Day 2 Highlights Eddie W. Shore 6 2,565 09-23-2013, 04:03 PM Last Post: Kimberly Thompson HHC 2013: Day 1 Highlights Eddie W. Shore 28 7,869 09-23-2013, 03:22 PM Last Post: Brad Barton HHC / HP Museum Programming Contest for RPN and RPL machines Gene Wright 18 5,573 09-22-2013, 09:39 AM Last Post: Miguel Toro

Forum Jump: