HHC 2012 RPN Programming Contest - Printable Version +- HP Forums (https://archived.hpcalc.org/museumforum) +-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html) +--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html) +--- Thread: HHC 2012 RPN Programming Contest (/thread-231645.html) HHC 2012 RPN Programming Contest - Gene Wright - 09-22-2012 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 Re: HHC 2012 RPN Programming Contest - Valentin Albillo - 09-22-2012 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. ``` ``` Re: HHC 2012 RPN Programming Contest - Gene Wright - 09-22-2012 Yes, FOUR. :-) Oops! Update: Max input number allowed - Gene Wright - 09-22-2012 For the RPN contest, the maximum value input will be 99,999. This is a change from what the directions say. Gene Re: Update: Max input number allowed - Olivier De Smet - 09-22-2012 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 ? Re: Update: Max input number allowed - Gene Wright - 09-22-2012 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. ? Re: HHC 2012 RPN Programming Contest - x34 - 09-22-2012 "Noon CDT Sunday September 22, 2012". Hmm, in my TZ, September 22 is Saturday. Re: Update: Max input number allowed - Olivier De Smet - 09-22-2012 Ok, I understood the meaning of positive and negative by finding the solution of the problem, now it's time for coding :) Re: Update: Max input number allowed - C.Ret - 09-22-2012 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). Re: HHC 2012 RPN Programming Contest - Paul Dale - 09-22-2012 Nice problem. 3am submission time. I guess I'll be a few hours late. - Pauli Re: HHC 2012 RPN Programming Contest - Valentin Albillo - 09-22-2012 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. ``` ``` Re: HHC 2012 RPN Programming Contest - Paul Dale - 09-22-2012 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 Re: Update: Max input number allowed - Jim Horn - 09-22-2012 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. Re: HHC 2012 RPN Programming Contest - Gene Wright - 09-22-2012 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). Re: HHC 2012 RPN Programming Contest - Jim Horn - 09-22-2012 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. Re: HHC 2012 RPN Programming Contest - Paul Dale - 09-22-2012 The 34S timing should be based on the internal TICKS command which doesn't depend on the presence of a crystal or not. - Pauli Re: HHC 2012 RPN Programming Contest - dbatiz - 09-22-2012 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 Re: Update: Max input number allowed - Paul Dale - 09-22-2012 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 Re: Update: Max input number allowed - Jim Horn - 09-22-2012 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... Re: Update: Max input number allowed - Paul Dale - 09-23-2012 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 Version in 19 step and one register - C.Ret - 09-23-2012 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 ! Re: Version in 19 step and one register - Paul Dale - 09-23-2012 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 Re: Update: Max input number allowed - Paul Dale - 09-23-2012 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 Re: Version in 19 step and one register - Gerson W. Barbosa - 09-23-2012 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) ``` Re: Version in 19 step and one register - Paul Dale - 09-23-2012 This matches my result for those numbers. - Pauli Re: Version in 19 step and one register - Gerson W. Barbosa - 09-23-2012 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 Re: Version in 19 step and one register - C.Ret - 09-23-2012 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 ? Re: HHC 2012 RPN Programming Contest - Gerson W. Barbosa - 09-23-2012 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. Re: Version in 19 step and one register - Gerson W. Barbosa - 09-23-2012 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. Re: HHC 2012 RPN Programming Contest - nina scholz - 09-23-2012 19 steps HP 15c LE ```01 STO 0 02 + 03 R down 04 STO- 0 05 + 06 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. Re: HHC 2012 RPN Programming Contest - Jim Horn - 09-23-2012 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... Re: HHC 2012 RPN Programming Contest --- best in Nashville is 12 steps long - Gene Wright - 09-23-2012 on a 34S, of course... more later. Re: HHC 2012 RPN Programming Contest - nina scholz - 09-23-2012 thank you. you are right. Re: Update: Max input number allowed - Thomas Klemm - 09-23-2012 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 Re: HHC 2012 RPN Programming Contest - Gilles Carpentier - 09-23-2012 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 Re: HHC 2012 RPN Programming Contest - Gerson W. Barbosa - 09-23-2012 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. Re: HHC 2012 RPN Programming Contest - Paul Dale - 09-23-2012 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 Re: Update: Max input number allowed - Paul Dale - 09-23-2012 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 Re: HHC 2012 RPN Programming Contest - Eric Smith - 09-23-2012 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. 12 step Nashville 34S solution - Gene Wright - 09-23-2012 Edited to correct line 001. Sorry! ```001 STOS 00 002 + 003 Roll Down 004 + 005 STO-Z 006 RCL+ T 007 INC X 008 RCLx Z 009 2 010 / 011 RCL+ 00 012 RCL- 02 ``` Edited: 24 Sept 2012, 8:52 a.m. after one or more responses were posted Re: Update: Max input number allowed - Thomas Klemm - 09-23-2012 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 Re: Update: Max input number allowed - Paul Dale - 09-23-2012 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 Re: Update: Max input number allowed - Paul Dale - 09-23-2012 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 Re: Update: Max input number allowed - Thomas Klemm - 09-23-2012 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 Re: Update: Max input number allowed - Thomas Klemm - 09-23-2012 True! But then it's all a matter of habit, I guess. I'm just not used to shuffle the stack in these ways. Re: Update: Max input number allowed - Paul Dale - 09-23-2012 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 Re: 12 step Nashville 34S solution - Gerson W. Barbosa - 09-23-2012 I think line 001 should be STOS 00 (unless this has been changed). I used this instruction once, and ran into it again this morning, when looking up in the manual for an instruction that copies the registers X,Y,Z and T into A,B,C and D when using SSIZE8. Such an instruction would be useful, but wouldn't have helped much: my solution using STOS is 16 steps long. Re: 12 step Nashville 34S solution - Paul Dale - 09-23-2012 Yes it should be STOS 00. A two instruction sequence that does what you want is: ```[cmplx]RCL Z [cmplx]RCL Z ``` There is no single instruction that does this in SSIZE8. Also remember the [cmplx]z<> instruction which is good for saving the top two levels of the four level stack. - Pauli Re: 12 step Nashville 34S solution - David Hayden - 09-23-2012 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 Re: HHC 2012 RPN Programming Contest - Paul Dale - 09-24-2012 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 Re: 12 step Nashville 34S solution - Gerson W. Barbosa - 09-24-2012 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. Re: HHC 2012 RPN Programming Contest - Gerson W. Barbosa - 09-24-2012 Well deserved rice pudding :-) I'm at 14 steps and one register, but that's my final attempt. Gerson. Re: HHC 2012 RPN - HP-41C version - C.Ret - 09-24-2012 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. Re: Update: Max input number allowed - Werner - 09-24-2012 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. Re: HHC 2012 RPN Programming Contest - Walter B - 09-24-2012 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 ;-) Re: HHC 2012 RPN Programming Contest - Paul Dale - 09-24-2012 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 Re: HHC 2012 RPN Programming Contest - Gerson W. Barbosa - 09-24-2012 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. Re: HHC 2012 RPN Programming Contest - Gilles Carpentier - 09-24-2012 I tried tu use the LAST command but i don't find less ! Edited: 24 Sept 2012, 5:26 p.m. Re: HHC 2012 RPN Programming Contest - dbatiz - 09-24-2012 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 Re: HHC 2012 RPN Programming Contest - David Hayden - 09-25-2012 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. Re: HHC 2012 RPN Programming Contest - Paul Dale - 09-25-2012 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 Re: Update: Max input number allowed - Thomas Klemm - 09-25-2012 Nice improvement! Re: 12 step Nashville 34S solution - C.Ret - 09-26-2012 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! Re: 12 step Nashville 34S solution - Gerson W. Barbosa - 09-26-2012 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. Re: 12 step Nashville 34S solution - Paul Dale - 09-26-2012 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 Re: 12 step Nashville 34S solution - Gerson W. Barbosa - 09-26-2012 It does work! Gerson. Re: 12 step Nashville 34S solution - C.Ret - 09-27-2012 The WP 34S is really the greatest RPN tool ! Re: Update: Max input number allowed - Gerson W. Barbosa - 09-27-2012 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. Re: HHC 2012 RPN Programming Contest - x34 - 09-28-2012 I wonder nobody mentioned it is actually Cantor's enumeration function. Re: Update: Max input number allowed - Gerson W. Barbosa - 09-30-2012 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 ``` Re: 12 step Nashville 34S solution - Gerson W. Barbosa - 10-01-2012 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.