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

 ▼ Gene Wright Unregistered Posts: 1,545 Threads: 168 Joined: Jul 2005 09-22-2012, 08:58 AM Here you go! Please do not post any solutions here until after Noon CDT Sunday September 23, 2012. Enjoy! Edited: 22 Sept 2012, 2:53 p.m. after one or more responses were posted ▼ Valentin Albillo Unregistered Posts: 1,755 Threads: 112 Joined: Jan 2005 09-22-2012, 11:54 AM Hi, Gene: Hehe, just for starters your PDF document says (the highlighting is mine) "Input: Each test case consists of three integers" and then your proceed to list four values (and later enter four values in the examples). Details, details ... ! XD Best regards from V. ``` ``` ▼ Gene Wright Unregistered Posts: 1,545 Threads: 168 Joined: Jul 2005 09-22-2012, 01:57 PM Yes, FOUR. :-) Oops! ▼ Gene Wright Unregistered Posts: 1,545 Threads: 168 Joined: Jul 2005 09-22-2012, 02:08 PM For the RPN contest, the maximum value input will be 99,999. This is a change from what the directions say. Gene ▼ Olivier De Smet Unregistered Posts: 275 Threads: 41 Joined: Mar 2010 09-22-2012, 02:14 PM It is not clear what is a forward or backward step when a solution mixes them, what should we give: sign of the first or of the last step ? ▼ Gene Wright Unregistered Posts: 1,545 Threads: 168 Joined: Jul 2005 09-22-2012, 02:26 PM Under what circumstances would you mix forward and backward steps in order to minimize them? The two examples shown indicate a positive number of steps and a negative number of steps. Given the arrows shown on the diagram in the contest, I'm not sure what a mix would entail. ? ▼ Olivier De Smet Unregistered Posts: 275 Threads: 41 Joined: Mar 2010 09-22-2012, 03:01 PM Ok, I understood the meaning of positive and negative by finding the solution of the problem, now it's time for coding :) ▼ C.Ret Unregistered Posts: 260 Threads: 0 Joined: Oct 2008 09-22-2012, 05:27 PM My code are already stroke into my HP-41C. I manage to reduce length to 19 merged instruction step for HP-41C using only stack registers. I am currently testing a version for HP-15C or HP-25 (simulator) that also only need 19 steps but one extra register (R0). ▼ Jim Horn Unregistered Posts: 151 Threads: 8 Joined: Oct 2009 09-22-2012, 09:19 PM Oooh, you wascally progwammer, you! (Elmer Fudd voice). I'm still at 19 steps *with* using a storage register. Gotta trim it down! Great to see the fantastic expertise of the masters here. I look forward to some great code tomorrow. ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-22-2012, 10:11 PM 19 is a tease. It can be done in fewer steps :-) My solution is ready and written up. If by some chance I'm awake at 3am here, I'll post it then. More likely six to eight hours later. - Pauli ▼ Jim Horn Unregistered Posts: 151 Threads: 8 Joined: Oct 2009 09-22-2012, 11:12 PM Thank you, Paul - for the fine machine that allows it to run in 14 steps on the stack (four level), unless I'm mistaken (a very real possibility). My '34S is at work so I can't try it out. Will have to download the emulator and see what I get... ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-23-2012, 12:07 AM A fourteen step solution is certainly possible -- I've found two such both of which use the same basic algorithm. I've a twelve step almost solution -- it fails for a small number of inputs. It is noticeably slower too. - Pauli ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-23-2012, 03:14 AM Once I fix the firmware and make my twelve step solution perfect, I'll be unbeatable. I will rule the universe. Unlimited rice pudding for all. Okay, not going to happen. The firmware is good as it stands and fixing it to support that solution is really introducing a bug. No rice pudding for me tonight :-( - Pauli Thomas Klemm Unregistered Posts: 735 Threads: 34 Joined: May 2007 09-23-2012, 04:29 PM Quote: A fourteen step solution is certainly possible ```00 { 21-Byte Prgm } 01 RDN 02 RCL+ ST T 03 RDN 04 STO- ST Z 05 + 06 X<>Y 07 RDN 08 STO+ ST Z 09 - 10 * 11 RCL+ ST L 12 2 13 / 14 + 15 .END. ``` If the final .END. is counted as a step then there are 15. Now I'm keen on seeing your 12-step solution. Kind regards Thomas ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-23-2012, 05:19 PM Nicely done. The 12 step solution is below. It uses the combinations function to calculate the distance from a point to the origin: dist(x, y) = Comb(x+y+1, 2) + y. Unfortunately it fails for x = y = 0 and I can't see how to add a check cheaply. - Pauli ▼ Thomas Klemm Unregistered Posts: 735 Threads: 34 Joined: May 2007 09-23-2012, 06:10 PM So if I understand the magic [<->] operation correctly I could write the following program for the WP-34S? ```01 STO+ Y 02 [<->] ZTXY 03 STO- Z 04 + 05 [<->] XZTY 06 STO+ Z 07 - 08 * 09 RCL+ L 10 # 1/2 11 [times] 12 + ``` Or is it [times] instead of * in line 08 as well? Pretty cool feature, this magic [<->] operator! But doesn't make the program easier to follow, I guess. Kind regards Thomas ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-23-2012, 06:21 PM It would be [times], although I expect everyone here will understand *. The [<->] shuffle operator is nice. It isn't limited to each stack level appearing once. e.g. [<->] XXYZ is like ENTER but keeps stack lift. Your step 2 could also be done with [cmplx]Rv, [cmplx]R^, [cmplx]x<> Z or [cmplx]z<> X :-) It feels like complex arithmetic operations could be leveraged here but I don't see how. - Pauli ▼ Thomas Klemm Unregistered Posts: 735 Threads: 34 Joined: May 2007 09-23-2012, 07:40 PM Now you probably make me RTFM, as Walter always suggests. Out of curiosity: which of the 12-step solutions is the fastest? I could imagine that using subroutines and additional registers makes a program slower. But then I could be completely wrong. Quote: It feels like complex arithmetic operations could be leveraged here but I don't see how. Do you mean something along the lines of: x2 - y2 = Re[(x + yi)2]? Cheers Thomas ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-23-2012, 08:10 PM Quote:Now you probably make me RTFM, as Walter always suggests. Out of curiosity: which of the 12-step solutions is the fastest? I could imagine that using subroutines and additional registers makes a program slower. But then I could be completely wrong. I've no idea which of the 12 step solutions is fastest, we've never profiled the code base -- space has always been more important that performance except when performance was truly dismal. Subroutine calls are very fast on the 34S. The arithmetic operators are slow in comparison. If I had to guess: your solution does least arithmetic. My COMB solution will be the slowest by far -- many logarithms are involved in this computation. Quote:Do you mean something along the lines of: x2 - y2 = Re[(x + yi)2]? Basically. The other thought I had was to try to leverage the orthogonal polynomial support but I doubt they will be any space savings realised by this. - Pauli Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-23-2012, 07:32 PM Quote:Pretty cool feature, this magic [<->] operator! But doesn't make the program easier to follow, I guess. It isn't like tight RPN programs are easy to follow at the best of times. - Pauli ▼ Thomas Klemm Unregistered Posts: 735 Threads: 34 Joined: May 2007 09-23-2012, 07:58 PM True! But then it's all a matter of habit, I guess. I'm just not used to shuffle the stack in these ways. Werner Unregistered Posts: 163 Threads: 7 Joined: Jul 2007 09-24-2012, 04:58 AM With some small changes it's two bytes shorter and fit for a 41, too: ```00 { 19-Byte Prgm } 01 STO+ ST Y 02 RDN 03 RDN 04 STO- ST Z 05 + 06 X<>Y 07 RDN 08 STO+ ST Z 09 - 10 STO* ST Y 11 + 12 2 13 / 14 + 15 .END. ``` Edited: 24 Sept 2012, 5:01 a.m. ▼ Thomas Klemm Unregistered Posts: 735 Threads: 34 Joined: May 2007 09-25-2012, 07:16 AM Nice improvement! Gerson W. Barbosa Unregistered Posts: 2,761 Threads: 100 Joined: Jul 2005 09-27-2012, 07:42 PM On the HP-42S, this 13-step solution (not counting final END) is possible: ```00 { 25-Byte Prgm} 01 STO 00 02 + 03 NOT 04 RCL* ST L 05 Rv 06 STO- 00 07 + 08 NOT 09 RCL* ST L 10 RCL- ST Z 11 2 12 / 13 RCL+ 00 14 .END. ``` 25 bytes plus register 00 though. Gerson. Edited to fix a typo Edited: 27 Sept 2012, 7:58 p.m. ▼ Gerson W. Barbosa Unregistered Posts: 2,761 Threads: 100 Joined: Jul 2005 09-30-2012, 10:00 PM FWIW, another 13-step 25-byte HP-42S solution: ```00 { 25-Byte Prgm } 01 CLSigma 02 Sigma+ 03 Rv 04 Rv 05 Sigma- 06 3 07 RCL* 11 08 RCL+ 12 09 RCL+ 13 10 RCL+ 14 11 2 12 / 13 RCL+ 15 14.END. 999999 ENTER 888888 ENTER 777777 ENTER 666666 R/S --> -740 379 703 704 ``` C.Ret Unregistered Posts: 260 Threads: 0 Joined: Oct 2008 09-23-2012, 02:48 AM Hi, Before you call me Master, please check what my code is doing! Having a short listing is one thing, having an efficient and correct solution is another... I am impatient to reach the date line and share with every participant my code for correction and improvements’. I expected that from dialoging and exchanging idea, a much better code will arise ! ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-23-2012, 03:08 AM Sharing ideas and group intelligence will almost certainly improve the solution. It did last year and I see no reason why this year should be any different. - Pauli Gerson W. Barbosa Unregistered Posts: 2,761 Threads: 100 Joined: Jul 2005 09-23-2012, 03:24 AM I'm a bit late to the party. I wasn't going to participate on this one, but after drinking a cappuccino past midnight I could sleep no more, so I decided to give this a try :-) My first attempt on the HP-15C LE uses only the stack and is 27 steps long. The running time doesn't depend on the coordinates (but I think that's what you all have been doing). ```11111 ENTER 22222 ENTER 33333 ENTER 44444 f A --> 2 469 130 864 (instantly, I just hope this is correct) ``` ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-23-2012, 03:33 AM This matches my result for those numbers. - Pauli ▼ Gerson W. Barbosa Unregistered Posts: 2,761 Threads: 100 Joined: Jul 2005 09-23-2012, 11:24 AM Thanks! I didn't notice Gene Wright had lowered the maximum input to 99,9999 (I had tried input values like 999,999 and 888,888 but the result would not fit in the 10-digit display of the HP-15C). 19 steps on the WP-34S (one less in integer mode if I knew how do display negative numbers properly). I think I should finally read the manual and learn how to use the stack shuffle instructions. Perhaps next time :-) ```999999 ENTER 888888 ENTER 777777 ENTER 666666 A --> -740 739 703 704 ``` My simple equivalent RPL program on the HP 50g is 160.5-byte long (0.08 seconds). Gerson ▼ C.Ret Unregistered Posts: 260 Threads: 0 Joined: Oct 2008 09-23-2012, 12:41 PM Hi, I am in trouble verifying this entry on my HP-41C. At least I can estimate that it is close to this. I have also made an RPL version, I will only give now of few bytes of it right now: ```« -> x1 y1 x2 y2 « ... ``` With this I can agree with your computation: From 999999 888888 to 777777 666666 path length is -740 739 703 710 Can someone draw a graph to verify the coun ? ▼ Gerson W. Barbosa Unregistered Posts: 2,761 Threads: 100 Joined: Jul 2005 09-23-2012, 01:27 PM On the HP-15C, I get -7.407397038e11. Quote: I have also made an RPL version, I will only give now of few bytes of it right now: ```« -> x1 y1 x2 y2 « ... ``` I've use local variables a, b, c and d instead, to save a few bytes. According to this website it is about 30 minutes past noon now in Nashville, so no problem posting solutions. Quote: Can someone draw a graph to verify the coun ? I would, but I fear this window is too small to fit it :-) Cheers, Gerson. Valentin Albillo Unregistered Posts: 1,755 Threads: 112 Joined: Jan 2005 09-22-2012, 08:52 PM Quote: Yes, FOUR. :-) Oops! Also, Rule 15 is a duplicate of Rule 2 ... :) ... On a more serious note (not that the above aren't serious), I think that the criterium to select a winner is utterly biased in favor of the fastest, more capable RPN machines. The criterium is stated as: "... (b) has the shortest number of steps x speed in seconds ..." so this clearly favors faster RPN machines regardless of the quality or merit of the code written for slower machines. Just for instance, consider this hypothetical scenario: only two people submit programs which give the correct answers, one written for an HP-15C, the other for an HP42S the HP-15C program is a marvel of optimization and efficiency for that machine, nothing short of miraculous, it has 10 steps and runs in 1 second. the HP42S program is an inefficient, horrible 40-step concoction which hurts the eyes but thanks to the 42S speed manages to run in 0.2 seconds. We do the arithmetic and get 10x1 = 10 for the HP-15C program and 40x0.2 = 8 for the HP32S program, so the inefficient and slow (for the 42S) program wins against the marvelous, efficient and fast (for the HP-15C) program. In my opinion, this is blatantly unfair and thus slower machines such as the HP-15C, HP-65, HP-67, are completely and unfairly handicapped as compared to faster, more advanced models. No one writing a program for an HP-65 or HP-67 would have any rational expectations of winning no matter how incredibly clever their program is, so writing anything for those machines is completely discouraged. Matter of fact, this means this is more of a hardware+programming contest than a programming contest as stated in its name, with heavy emphasis on the hardware part which can trump any programming finesse. One way to avoid this unfair scenario would be to use this criterium: shortest number of steps x speed in seconds x hardware factor where the hardware factor is a correction factor which depends on the machine the program was written for. For instance, classic slow machine XX would have a factor of 0.1, ultra-fast modern machine YY would have a factor of 1.5. A short list of suitable factors could be created and applied, which would restore fairness to this programming contest. Just saying ... Best regards from V. ``` ``` ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-22-2012, 09:08 PM I have to agree that there is a bias against the older devices. The only realistic candidates for the winner of this challenge are the (latest) HP-12C, the HP-15C LE, the HP-41CL, the WP-34S or the DM-16C. Nothing else has a chance speed wise. Maybe I should have included the HP-33S as well. Given the nature of this challenge, the judging criteria are going to have to be defined and I suspect will be biased against something. The suggested hardware factor will be difficult to define well -- e.g. the 34S has a very slow LN function but is fast for basic arithmetic. Using minimum number of steps is also biased against the less feature rich devices. The 42S generally has more compact code than e.g. a 15C. Guess the challenge setters are in a no-win situation. I'm still glad there is a challenge. BTW: I'm in a lost cause position for the RPL challenge -- my only functioning RPL calculator is a 28S which lacks many features later models have. Still I've had fun solving that challenge even though I've zero chance of winning it. - Pauli ▼ Gene Wright Unregistered Posts: 1,545 Threads: 168 Joined: Jul 2005 09-22-2012, 09:22 PM Valentin is quite correct. No argument there at all. Problem is what those factors should be AND how to accumulate them. I did the programming contest a couple of hours before the conference (which is why there were some typos in the rules). If only I had more time. :-) Still, if someone can come up with reasonable adjustments to make on leveling the speed advantages, I'll be glad to do it for NEXT year. :-) And, I fully expect that most people here will be using the 34S. What else is there? (ha). Jim Horn Unregistered Posts: 151 Threads: 8 Joined: Oct 2009 09-22-2012, 09:24 PM For this problem, the solutions should all be nearly instantaneous even on a older machine (the '67 should be able to solve it in the order of a second or two). That said, my WP34S solution to last year's challenge was beat by the order of the difference in speed of my non-crystal-equipped machine vs. the one that one and was so set equipped. Yesterday I soldered the crystal into mine. Hmmm - it would clobber clock accuracy but I wonder what would happen if I put in a crystal for a somewhat higher frequency than 2^15 Hz? Racing does tend to bring out the beast. ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-22-2012, 09:31 PM The 34S timing should be based on the internal TICKS command which doesn't depend on the presence of a crystal or not. - Pauli x34 Unregistered Posts: 114 Threads: 18 Joined: Jan 2011 09-22-2012, 02:41 PM "Noon CDT Sunday September 22, 2012". Hmm, in my TZ, September 22 is Saturday. Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-22-2012, 07:20 PM Nice problem. 3am submission time. I guess I'll be a few hours late. - Pauli dbatiz Unregistered Posts: 64 Threads: 8 Joined: Oct 2006 09-22-2012, 09:39 PM Thank you to the HHC 2012 team for putting together this contest! I don't know how you come up with these things, but they are always great fun. I don't have any of my RPN machines at home this weekend, so if I wanted to work on it, I had to use my 50g emulator. Not within the contest rules, but still great fun. Using variables for the ordered pairs (X1, Y1) and (X2, Y2) I created one equation with no conditionals that returns the correct answers to the sample problems. I'll gladly send my technique to anybody who'd care to see it via e-mail. Drop me a line at dbatiz(AT)hotmail(DOT)com Very respectfully, David ▼ dbatiz Unregistered Posts: 64 Threads: 8 Joined: Oct 2006 09-24-2012, 09:28 PM I couldn't get the image to post correctly, so I'm attempting to post using text. The solutions presented are much more elegant than what I came up with, but I hope that this may lead to some interesting modifications. I couldn't find an ordered pair where this would fail: ```X2+Y2+1 X2 X1+Y1+1 X1 E n + E n - ( E n + E n ) n=X2+2 n=0 n=X1+2 n=0 ``` Of course, it looks much better on the equation writer on the 50g. The creativity and resourcefulness demonstrated on this forum never ceases to amaze me. Thanks for the challenge and for all the thoughtful posts, Very respectfully, David Gerson W. Barbosa Unregistered Posts: 2,761 Threads: 100 Joined: Jul 2005 09-23-2012, 01:14 PM Interesting problem! Just for the sake of participating, here are two simple solutions: ```[WP 34S, SSIZE8: 001 LBL A 002 RCL+ Y 003 RCL L 004 RCL- T 005 3 006 * 007 x<> Z 008 RCL- A 009 x<> Y 010 x^2 011 RCL T 012 RCL+ B 013 x^2 014 - 015 + 016 + 017 2 018 / 019 END HP 50g, exact mode: << -> a b c d << c d + SQ a b + SQ - d b - 3 * + c + 2 - 2 / ->NUM >> >> ``` I have used the formula (3) below, which is a simplification of the formula (1),which can be derived from your drawing. On the HP-15C, I've used the formula (1) or (2), which appear to be more adequate to the 4-level RPN stack. The formulas are not difficult to derive, but optimizing the program for size is quite challenging. ```C1 = x1 + y1 C2 = x2 + y2 n = C2 - C1 + ((C1 + C2)*((C2 - C1 - 1 ))/2 + C1 - y1 + y2 ( 1 ) n = C2 - C1 + ((C1 + C2)*((C2 - C1 - 1 ))/2 + x1 + y2 ( 2 ) or n = ((x2 + y2)2 - (x1 + y1)2 + 3*(y2 - y1) + x2 - x1))/2 ( 3 ) ``` Gerson. Edited to fix formatting Edited: 23 Sept 2012, 1:37 p.m. ▼ Eric Smith Unregistered Posts: 2,309 Threads: 116 Joined: Jun 2005 09-23-2012, 02:25 PM If you use SSIZE8, the program has to set it, and set back to SSIZE4 before halting (rule 13). That adds two steps. My submission for the 34s is 16 steps including the END, and does not use SSIZE8. Earlier I tried using SSIZE8, but the shortest program I was able to come up with was actually longer than my program using SSIZE4. I'll post my program after the in-person winners are announced. ▼ Gerson W. Barbosa Unregistered Posts: 2,761 Threads: 100 Joined: Jul 2005 09-23-2012, 02:54 PM Thank you! Looks like I haven't read the rules thoroughly. I'm looking forward to your and other people's solutions. 21 steps! Definitely not a good idea: ```001 LBL A 002 SSIZE8 003 RCL+ Y 004 RCL L 005 RCL- T 006 3 007 * 008 x<> Z 009 RCL- A 010 x<> Y 011 x^2 012 RCL T 013 RCL+ B 014 x^2 015 - 016 + 017 + 018 2 019 / 020 SSIZE4 021 END ``` Edited: 23 Sept 2012, 3:05 p.m. Gilles Carpentier Unregistered Posts: 468 Threads: 17 Joined: May 2011 09-23-2012, 04:38 PM Hi Gerson, In RPL you can simplify : ```<< -> a b c d << c d + SQ a b + SQ - d b - 3. * + c + a - 2. / >> >> ``` or shorter and faster : ```« 4. DUPN + SQ UNROT + SQ - 5. ROLLD ROT - 3. * + SWAP - + 2. / » ``` 60 Bytes ▼ Gerson W. Barbosa Unregistered Posts: 2,761 Threads: 100 Joined: Jul 2005 09-23-2012, 05:07 PM Hi Gilles, Quote:```In RPL you can simplify : << -> a b c d << c d + SQ a b + SQ - d b - 3. * + c + a - 2. / >> >>``` Actually, that was a typo. It's correct in my calculator: ... 3 * + c + a - 2 / ... Quote:```« 4. DUPN + SQ UNROT + SQ - 5. ROLLD ROT - 3. * + SWAP - + 2. / » ``` I didn't try to use the stack only, but I surely wouldn't get something as short as this one. I would prefer exact mode: ```« 4 DUPN + SQ UNROT + SQ - 5 ROLLD ROT - 3 * + SWAP - + 2 / » ``` otherwise my example returns a slightly different result, -740739703705, instead of -740739703704. It takes now 0.055 seconds for this example! Cheers, Gerson. Edited: 23 Sept 2012, 5:19 p.m. Gerson W. Barbosa Unregistered Posts: 2,761 Threads: 100 Joined: Jul 2005 09-24-2012, 04:23 PM Hello Gilles, 55 bytes using ```n = ((x2 + y2)2 + (x2 + y2) - ((x1 + y1)2 + (x1 + y1)))/2 + y2 - y1 ``` Any idea to make it even smaller? ```« ROT DUP2 - 5 ROLLD 1 2 START UNROT + DUP SQ + NEXT - 2 / + » ``` Gerson. ▼ Gilles Carpentier Unregistered Posts: 468 Threads: 17 Joined: May 2011 09-24-2012, 05:18 PM I tried tu use the LAST command but i don't find less ! Edited: 24 Sept 2012, 5:26 p.m. nina scholz Unregistered Posts: 20 Threads: 3 Joined: Mar 2012 09-23-2012, 02:09 PM 19 steps HP 15c LE ```01 STO 0 02 + 03 R down 04 STO- 0 05 + 06 x> instruction which is good for saving the top two levels of the four level stack. - Pauli David Hayden Unregistered Posts: 528 Threads: 40 Joined: Dec 2008 09-23-2012, 10:52 PM Here's an explanation of my program. It wouldn't have been possible without the great support in the 34s for things like register artithmetic on ALL registers, including the stack. To get from (0,0) to (x,0) on the X-axis, it's an arithmetic series. Now to get to a point (x,y), you first have to get to (x+y,0), and then you move diagonally up and left y points to (x,y). Let s=x+y. So to get to (x,y), the distance is s(s+1)/2+y. To get from point (x1,y1) to (x2,y2), it's just the difference: s2(s2+1)/2+y2 - s1(s1+1)/2+y1. My first attempt used this formula and was 16 instructions. But rearranging things, this is the arithmetic series from s1+1 to s2, plus y2-y1. Factoring this in, the expression to evaluate is: (s1+s2+1)(s2-s1)/2 + y2 - y1. So here's how the code evaluates the expression: ```STOS 00 Stores the stack in R00-R03 + Stack: x1 x1 y1 s2 Rdown s2 x1 x1 y1 + s2 s2 x1 s1 STO- Z s2 (s2-s1) x1 s1 RCL+T s2 (s2-s1) x1 (s1+s2) INC X s2 (s2-s1) x1 (s1+s2+1) RCL* Z s2 (s2-s1) x1 (s1+s2+1)(s2-s1) 2 / (s2-s1)(s20s1) x1 (s1+s2+1)(s2-s1)/2 RCL+ 00 X = (s1+s2+s1)(s2-s1)/2 + y2 RCL- 02 X = (s1+s2+s1)(s2-s1)/2 + y2 - y1 ``` Dave ▼ Gerson W. Barbosa Unregistered Posts: 2,761 Threads: 100 Joined: Jul 2005 09-24-2012, 12:59 AM Very nice! My formula includes the sum of an arithmetic progression, but you've come up with a more simple one. I've rewritten mine as ```n = ((x2 + y2)2 + (x2 + y2) - ((x1 + y1)2 + (x1 + y1)))/2 + y2 - y1 ``` It's still a bit complicated, but at least it's now easier to program: ```001 RCL- Z 002 STO 00 003 x<> L 004 + 005 x^2 006 RCL+ L 007 x<> Z 008 + 009 x^2 010 RCL+ L 011 - 012 2 013 / 014 RCL+ 00 ``` Or, one step shorter (but not short enough), using STOS: ```001 STOS 00 002 + 003 x^2 004 RCL+ L 005 x<> Z 006 + 007 x^2 008 RCL+ L 009 - 010 2 011 / 012 RCL+ 00 013 RCL- 02 ``` Gerson. ▼ C.Ret Unregistered Posts: 260 Threads: 0 Joined: Oct 2008 09-26-2012, 10:37 AM Hi, The use of the STOS is a great advantage. But what's up on an HP without stack manipulation and storage functions? For example on an HP-15C ? The shortest I get through is a code that need to enter x1,y1 and x2,y2 point coordinate differently : ``` # -------------------------------------------- t: z: y: x: 000 { } u(x',y') ~ x y 001 { 40 } + u(x',y') u(x',y') ~ x+y 002 { 43 33 } g Rup u(x',y') ~ x+y u(x',y') 003 { 34 } x<->y u(x',y') x+y 004 { 43 36 } g LSTx u(x',y') x+y y 005 { 34 } x<->y u(x',y') y x+y 006 { 43 11 } g x^2 u(x',y') y (x+y)² 007 { 43 36 } g LSTx u(x',y') y (x+y)2 x+y 008 { 40 } + u(x',y') y (x+y)(1+x+y) 009 { 2 } 2 u(x',y') y (x+y)(1+ 2 010 { 10 } ÷ u(x',y') y (x+y)(1+x+y)/2 011 { 40 } + u(x',y') u(x,y) 012 { 30 } - -d 013 { 43 36 } g LSTx -d u(x,y) 014 { 34 } x<->y u(x,y) -d 015 { 16 } CHS u(x,y) d # -------------------------------------------- Use : Keystroke: Display: x1 ENTER^ y1 R/S ignore display x2 ENTER^ y2 R/S d = d( 1 --> 2 ) x3 ENTER^ y3 R/S d = d( 2 --> 3 ) ... Where : x ,y coordinates of current entry point x',y' coordinates of last entry point d signed distance between point x,y and x',y' u(x',y') recorded (keep in stack) potential value at last position x',y' ``` The program has to be run through two times to compute a distance. But of course it is not acceptable since it's not following the contest requirements! ▼ Gerson W. Barbosa Unregistered Posts: 2,761 Threads: 100 Joined: Jul 2005 09-26-2012, 04:42 PM Sticking to the rules, I cannot get anything better than 17 steps on the HP-15C: ```001- STO 0 002- + 003- g x^2 004- g LASTx 005- + 006- ENTER 007- g R^ 008- g R^ 009- STO- 0 010- + 011- g x^2 012- g LASTx 013- + 014- - 015- 2 016- / 017- RCL- 0 ``` With the same formula a 14-step (and perhaps less) is possible on the WP 34S, using only the stack: ```001 + 002 RCL L 003 RCL- Z 004 Rv 005 x^2 006 RCL+ L 007 x<> Y 008 RCL+ Z 009 x^2 010 RCL+ L 011 - 012 2 013 / 014 RCL+ T ``` Gerson. ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-26-2012, 05:52 PM I've not tried this out to see if it is actually correct or not but it is twelve steps: ``` start y2 x2 y1 x1 01: <-> YTXZ x2 x1 y2 y1 02: [cmplx]+ s2 s1 y2 y1 where si = xi+yi 03: x^2 04: RCL+ L s2^2+s2 s1 y2 y1 05: x<> Y 06: x^2 07: RCL+ L s1^2+s1 s2^2+s2 y2 y1 08: - s2^2+s2-(s1^2+s1) y2 y1 09: 2 10: / 11: + 12: RCL- Y ``` - Pauli ▼ Gerson W. Barbosa Unregistered Posts: 2,761 Threads: 100 Joined: Jul 2005 09-26-2012, 11:00 PM It does work! Gerson. ▼ C.Ret Unregistered Posts: 260 Threads: 0 Joined: Oct 2008 09-27-2012, 08:43 AM The WP 34S is really the greatest RPN tool ! Gerson W. Barbosa Unregistered Posts: 2,761 Threads: 100 Joined: Jul 2005 10-01-2012, 12:59 AM Well, low memory usage is not a requirement. So the following could have been done :-) ```001- 42 34 f CLEAR REG 002- 49 SIGMA+ 003- 33 Rv 004- 33 Rv 005- 43 49 g SIGMA- 006- 3 3 007- 45 20 3 RCL* 3 008- 45 40 4 RCL+ 4 009- 45 40 5 RCL+ 5 010- 45 40 6 RCL+ 6 011- 2 2 012- 10 / 013- 45 40 7 RCL+ 7 11111 ENTER 22222 ENTER 33333 ENTER 44444 R/S --> 2 469 130 864 (less than 3 seconds on the HP-15C) ``` Gerson. nina scholz Unregistered Posts: 20 Threads: 3 Joined: Mar 2012 09-23-2012, 04:03 PM thank you. you are right. Jim Horn Unregistered Posts: 151 Threads: 8 Joined: Oct 2009 09-23-2012, 03:51 PM I really hesitate to post a program as I don't havd my WP 34S to try (and debug) it on. While attempting to fix my tractor yesterday, I realized that we can define a position function F(x,y) such that we only need to find F(x2,y2)-F(x1,y1). Also, F(x,y)=F(x+y,0)+y {just count down to the right on the plot until reaching the X axis}. And F(x,0) is our old friend, the sum of the first N numbers: F(x,0)=(x*(x+1))/2. So, for each pair of values find (x+y)*(x+y+1), find the difference and divide that by two (to reduce the divisions in half). That leads to something like: GSB 0 // Find F(X2, Y2) Rdown // Save it to T GSB 0 // Find F(X1, Y1) RCL - T // Find difference -2 / // Change sign and scale. RTN LBL 0 STO + Y // X*Y STO + X // 2*Y X <> Y ISG X // XY + 1 RCL * L // XY(XY+1) + // XY(XY+1) + 2Y RTN // =2F(X,Y) Probably that's full of holes - I don't know if ISG saves X in LastX or if there's really an ISG that won't skip a step for general increment. The final RTN can be dropped a the END there should do the job if my '41 memories are correct. But it shows where I was headed. I do have to admire those who are adept at getting the most out of register arithmetic, swapping and such. Time for this old dog to master such tricks. Now if only I could get the tractor to work... Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-23-2012, 05:16 PM Interesting problem. Speed and step count. The WP-34S will be hard to beat here unless there are some long constants involved in the solution. The only faster RPN device is the 15c LE and no other has such a rich suite of programmer friendly instructions. My first thought is to calculate the distance from the points to an axis, figure the distance between the axis points out and sum these. Can we do better? Unsurprisingly, yes. Instead calculate the distance to the origin and subtract. Each diagonal consists of a set of points (x, y) where x+y is constant. We want f(x,y) the distance from the origin of the point (x, y). Moving the (x, y) point down the diagonal back to the x axis takes y steps. Thus: ``` f(x, y) = f(x+y, 0) + y. ``` Now to work out f(n, 0). It is fairly easy to show that this is the nth triangular number. The first few values strongly indicate this: ``` n f(n, 0) 0 0 1 1 2 3 3 6 4 10 5 15 ``` The formula for f(n, 0) is: ``` f(n, 0) = n (n+1) / 2 = (n^2 + n) / 2 = Combinations(n+1, 2) ``` This explains the maximum limit on the coordinates that was given. The limit squared doesn't overflow. Nice, we're likely on the right track. The direct formula for f(x, y) is ``` f(x, y) = (x+y) (x+y+1) / 2 + y = ((x+y)^2 + (x+y) + 2y) / 2 = Combinations(x+y+1, 2) ``` We need to produce: ``` f(T, Z) - f(Y, X) ``` A subroutine that calculates the value of f(x, y) without disturbing the stack is required. I don't see how to use the final Combinations(n+1, 2) without stack destruction, plus this function is very slow on the 34S and a solution using this doesn't execute instantly -- still fast though. Instead we'll use the (n^2 + n) / 2 form. The first quick program: ``` 01 LBL A y2 x2 y1 x1 02 XEQ 00 f(x2 y2) 03 [<->] YZXT y1 x1 f(x2 y2) 04 XEQ 00 f(x1 y1) f(x2 y2) 05 - our answer 06 RTN 07 LBL 00 x y z t 08 x[<->] Y x y z t 09 RCL+ Y x+y y z t 10 x[^2] (x+y)^2 y z t 11 RCL+ L (x+y)^2+(x+y) y z t 12 RCL+ Y (x+y)^2+(x+y)+y y z t 13 + (x+y)^2+(x+y)+2y z t t 14 # 002 2 sum z t 15 / ((x+y)^2+(x+y)+2y)/2 z t t ``` Can we do shorter and faster? Of course. Well faster is difficult, the program executes essentially instantly even in SLOW mode (which isn't the default). Factor out the "2 /" so they are only executed once only and change the divide to a multiply will save some milliseconds but that is about it without profiling individual instructions. Remove the label A since the given example requires R/S to start execution. This means a GTO . 000 is required before execution but that's liveable. The 41 series might have problems getting repeatability here with its weird RTN behaviour. Replace the x[<->] Y in the subroutine with a [<->] YXTZ at the start of the program -- this doesn't save any instructions but executes one less. This will definitely not be noticeable. ``` 01 [<->] YXTZ 02 XEQ 00 03 [<->] YZXT 04 XEQ 00 05 - 06 # 1/2 07 [times] 08 RTN 09 LBL 00 10 RCL+ Y 11 x[^2] 12 RCL+ L 13 RCL+ Y 14 + ``` Timing this using TICKS generally gives zero as the result. I.e. a tenth of a second or less. Step count becomes important since it is the final decision criteria. How to reduce steps further? Pity Walter insisted the BSRF instruction was removed from the 34S or we could have saved another step. Hang on, the instruction is there so the assembler can be tricked into producing it for us, probably against the rules or at least the spirit of them. I've got a 34S running older firmware somewhere, I knew I kept it for a reason :-) Yes, found it. Drat, it doesn't have the 1/2 constant. Oh well, speed really isn't important here. A version that works on that calculator saving one more step: ``` 01 [<->] YXTZ 02 BSRF 006 03 [<->] YZXT 04 BSRF 004 05 - 06 # 002 07 / 08 RTN 09 RCL+ Y 10 x[^2] 11 RCL+ L 12 RCL+ Y 13 + ``` Thirteen steps, zero execution time. As a complete aside and mostly for the record, a version using the combinations form is possible: ``` 01 [<->] YXTZ 02 [cmplx]z[<->] J 03 XEQ 00 04 [cmplx]RCL J 05 XEQ 00 06 - 07 RTN 08 LBL 00 09 RCL+ Y 10 INC X 11 # 002 12 COMB 13 + ``` Again, on the older device, one step can be spared: ``` 01 [<->] YXTZ 02 [cmplx]z[<->] J 03 BSRF 004 04 [cmplx]RCL J 05 BSRF 002 06 - 07 RTN 08 RCL+ Y 09 INC X 10 # 002 11 COMB 12 + ``` Unfortunately, these programs take 8 - 10 TICKS to execute (i.e. about a second). To my mind, this doesn't qualify as nearly identical but if it does, one fewer step is possible. They also don't deal with the origin as one of the points, so these two aren't worthy of further consideration. Finally, add one step to all of these if the mandatory END is included -- this isn't really an instruction, the firmware fakes it and it doesn't occupy a step of RAM if it is the final END in RAM. - Pauli Edited: 23 Sept 2012, 6:08 p.m. after one or more responses were posted ▼ Eric Smith Unregistered Posts: 2,309 Threads: 116 Joined: Jun 2005 09-23-2012, 05:58 PM My entry was very similar to one of yours: ```01 XEQ 00 02 STO T 03 RDN 04 XEQ 00 05 - 06 RTN 07 LBL 00 08 STO+Y 09 STO+X 10 x<>y 11 x^2 12 RCL+L 13 + 14 2 15 / ``` I didn't include a label at the beginning because the rules indicated that the program would be started at step 001. The winning entry by David Hayden used the STOS instruction and was only 12 steps. Edited: 23 Sept 2012, 5:59 p.m. C.Ret Unregistered Posts: 260 Threads: 0 Joined: Oct 2008 09-24-2012, 02:41 AM Hi, I use the same algorithm, but my implementation on HP-41C and HP-15c may have to be optimise : ```01 LBL "HHC2012 XEQ 00 XEQ 00 RCL Z - 06 RTN 07 LBL 00 + LASTX RDN X^2 ST+ L CLX 2 ST/ L x<> L ST+ T RDN 19 RTN ``` Sub-routine 00 compute f(x,y) by only using two stack register (and Lastx L register) and place result on Z: stack position. ```f(x,y) y (0,5) 20 (0,4) 14 19 (0,3) 9 13 18 (0,2) 5 8 12 17 (0,1) 2 4 7 11 16 (0,0) 0 1 3 6 10 15 ... (0,0)(1,0)(2,0)(3,0)(4,0)(5,0) x ``` An adaptation for HP-15C follow the same organisation, but use register R0 in sub-routine calculation. :-( ```001 *Lbl A 002 GSB 0 003 GSB 0 004 RCL 0 005 - 006 RTN 007 *Lbl 0 008 STO 0 009 + 010 x² 011 Lastx 012 + 013 2 014 / 015 ST0+0 016 RCL 0 017 Rdn 018 Rdn 019 RTN ``` Edited: 24 Sept 2012, 6:24 a.m. Walter B Unregistered Posts: 4,587 Threads: 105 Joined: Jul 2005 09-24-2012, 06:16 AM Quote: Pity Walter insisted the BSRF instruction was removed from the 34S or we could have saved another step. Hang on, the instruction is there so the assembler can be tricked into producing it for us, probably against the rules or at least the spirit of them. Yes, I admit I was it, and I adhere to that :-) But please read p. 180 before complaining ;-) ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-24-2012, 06:20 AM I'm surprised you suffered through this thread long enough to find that little gem ;-) I'll add that I don't disagree with the omission of these commands. - Pauli Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-24-2012, 12:16 AM How about an eleven step solution that only uses the stack: ``` 01: [<->] TYZX 02: [cmplx]+ 03: RCL+ Y 04: x[<->] Y 05: RCL- L 06: INC Y 07: * 08: # 1/2 09: * 10: RCL+ T 11: RCL- Y ``` Execution time is essentially zero. - Pauli ▼ Gerson W. Barbosa Unregistered Posts: 2,761 Threads: 100 Joined: Jul 2005 09-24-2012, 01:10 AM Well deserved rice pudding :-) I'm at 14 steps and one register, but that's my final attempt. Gerson. David Hayden Unregistered Posts: 528 Threads: 40 Joined: Dec 2008 09-25-2012, 12:30 AM Quote: Here you go! Please do not post any solutions here until after Noon CDT Sunday September 23, 2012. Enjoy! It appears that posting the contents on the forum was a big success. I think we've worried in the past that some people might post solutions before the official contest ended, but it seems that when asked to refrain, we comply. ▼ Paul Dale Unregistered Posts: 3,229 Threads: 42 Joined: Jul 2006 09-25-2012, 04:31 AM Quote:I think we've worried in the past that some people might post solutions before the official contest ended, but it seems that when asked to refrain, we comply. If anyone posted early, we'd not get another crack at the challenges. I doubt anyone would want that. - Pauli x34 Unregistered Posts: 114 Threads: 18 Joined: Jan 2011 09-28-2012, 12:43 PM I wonder nobody mentioned it is actually Cantor's enumeration function.

 Possibly Related Threads… Thread Author Replies Views Last Post [PRIME] RPN: another attempt at returning more than one value to the RPN stack Marcus von Cube, Germany 5 2,450 11-05-2013, 02:44 AM Last Post: Marcus von Cube, Germany 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,636 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,606 09-26-2013, 02:51 AM Last Post: Geoff Quickfall HHC 2013 Day 2 Highlights Eddie W. Shore 6 2,563 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,562 09-22-2013, 09:39 AM Last Post: Miguel Toro HHC 2013 room numbers David Hayden 2 1,297 09-20-2013, 05:34 PM Last Post: sjthomas FYI: HHC 2013 Programming contests are coming Gene Wright 0 910 09-17-2013, 03:12 PM Last Post: gene wright

Forum Jump: