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
HHC 2012 RPN Programming Contest


« Next Oldest  Next Newest »

▼
09222012, 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 ▼
09222012, 11:54 AM
Hi, Gene: Hehe, just for starters your PDF document says (the highlighting is mine)
and then your proceed to list four values (and later enter four values in the examples). Details, details ... ! XD
Best regards from V. ▼
09222012, 01:57 PM
Yes, FOUR. :) Oops! ▼
09222012, 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 ▼
09222012, 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 ? ▼
09222012, 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. ? ▼
09222012, 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 :) ▼
09222012, 05:27 PM
My code are already stroke into my HP41C. I manage to reduce length to 19 merged instruction step for HP41C using only stack registers. I am currently testing a version for HP15C or HP25 (simulator) that also only need 19 steps but one extra register (R0).
▼
09222012, 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. ▼
09222012, 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 ▼
09222012, 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... ▼
09232012, 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.
▼
09232012, 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 :(
09232012, 04:29 PM
Quote:
00 { 21Byte Prgm } If the final .END. is counted as a step then there are 15. Now I'm keen on seeing your 12step solution.
Kind regards ▼
09232012, 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.
▼
09232012, 06:10 PM
So if I understand the magic [<>] operation correctly I could write the following program for the WP34S?
01 STO+ Y 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 ▼
09232012, 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 :)
▼
09232012, 07:40 PM
Now you probably make me RTFM, as Walter always suggests. Out of curiosity: which of the 12step 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:Do you mean something along the lines of: x^{2}  y^{2} = Re[(x + yi)^{2}]?
Cheers ▼
09232012, 08:10 PM
Quote: 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: 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.
09232012, 07:32 PM
Quote: It isn't like tight RPN programs are easy to follow at the best of times.
09242012, 04:58 AM
With some small changes it's two bytes shorter and fit for a 41, too:
00 { 19Byte Prgm }
Edited: 24 Sept 2012, 5:01 a.m.
09272012, 07:42 PM
On the HP42S, this 13step solution (not counting final END) is possible: 00 { 25Byte Prgm}25 bytes plus register 00 though. Gerson. _{Edited to fix a typo}
Edited: 27 Sept 2012, 7:58 p.m.
09232012, 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 ! ▼
09232012, 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.
09232012, 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 :)
11111 ENTER
▼
09232012, 03:33 AM
This matches my result for those numbers.
▼
09232012, 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 10digit display of the HP15C). 19 steps on the WP34S (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 My simple equivalent RPL program on the HP 50g is 160.5byte long (0.08 seconds). Gerson ▼
09232012, 12:41 PM
Hi, I am in trouble verifying this entry on my HP41C. 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: Can someone draw a graph to verify the coun ? ▼
09232012, 01:27 PM
On the HP15C, I get 7.407397038e11.
Quote:According to this website it is about 30 minutes past noon now in Nashville, so no problem posting solutions. Quote: I would, but I fear this window is too small to fit it :) Cheers, Gerson.
09222012, 08:52 PM
Quote: 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:
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:
In my opinion, this is blatantly unfair and thus slower machines such as the HP15C, HP65, HP67, are completely and unfairly handicapped as compared to faster, more advanced models. No one writing a program for an HP65 or HP67 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 Just saying ...
Best regards from V.
▼
09222012, 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) HP12C, the HP15C LE, the HP41CL, the WP34S or the DM16C. Nothing else has a chance speed wise. Maybe I should have included the HP33S 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 nowin situation. I'm still glad there is a challenge.
▼
09222012, 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).
09222012, 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 noncrystalequipped 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.
09222012, 02:41 PM
"Noon CDT Sunday September 22, 2012". Hmm, in my TZ, September 22 is Saturday.
09222012, 07:20 PM
Nice problem. 3am submission time. I guess I'll be a few hours late.
09222012, 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 email. Drop me a line at dbatiz(AT)hotmail(DOT)com Very respectfully, David ▼
09242012, 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 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
09232012, 01:14 PM
Interesting problem! Just for the sake of participating, here are two simple solutions: [WP 34S, SSIZE8:I have used the formula (3) below, which is a simplification of the formula (1),which can be derived from your drawing. On the HP15C, I've used the formula (1) or (2), which appear to be more adequate to the 4level RPN stack. The formulas are not difficult to derive, but optimizing the program for size is quite challenging. C_{1} = x_{1} + y_{1} Gerson. _{Edited to fix formatting}
Edited: 23 Sept 2012, 1:37 p.m. ▼
09232012, 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 inperson winners are announced. ▼
09232012, 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 Edited: 23 Sept 2012, 3:05 p.m.
09232012, 04:38 PM
Hi Gerson, In RPL you can simplify :
<< > a b c d or shorter and faster :
« 4. DUPN + SQ UNROT + SQ  5. ROLLD ROT  3. * + SWAP  + 2. / »60 Bytes ▼
09232012, 05:07 PM
Hi Gilles,
Quote:In RPL you can simplify : 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.
09242012, 04:23 PM
Hello Gilles,
55 bytes using n = ((x_{2} + y_{2})^{2} + (x_{2} + y_{2})  ((x_{1} + y_{1})^{2} + (x_{1} + y_{1})))/2 + y2  y1Any idea to make it even smaller? « ROT DUP2  5 ROLLDGerson.
09232012, 02:09 PM
19 steps HP 15c LE 01 STO 0 Edited: 23 Sept 2012, 2:10 p.m. ▼
09232012, 02:45 PM
Quote:It's more like 17 steps: line 10 and 11 can be replaced by a simple RCL+ 0, and the ENTER in line 15 can be omitted. ;) Dieter ▼
09232012, 03:52 PM
on a 34S, of course... more later. ▼
09232012, 06:07 PM
Edited to correct line 001. Sorry!
001 STOS 00 Edited: 24 Sept 2012, 8:52 a.m. after one or more responses were posted ▼
09232012, 08:19 PM
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. ▼
09232012, 08:51 PM
Yes it should be STOS 00. A two instruction sequence that does what you want is:
[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.
09232012, 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 Xaxis, 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: My first attempt used this formula and was 16 instructions. But rearranging things, this is the arithmetic series from s1+1 to s2, plus y2y1. Factoring this in, the expression to evaluate is: (s1+s2+1)(s2s1)/2 + y2  y1. So here's how the code evaluates the expression:
STOS 00 Stores the stack in R00R03Dave ▼
09242012, 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 = ((x_{2} + y_{2})^{2} + (x_{2} + y_{2})  ((x_{1} + y_{1})^{2} + (x_{1} + y_{1})))/2 + y2  y1
It's still a bit complicated, but at least it's now easier to program: 001 RCL Z Or, one step shorter (but not short enough), using STOS:
001 STOS 00 Gerson. ▼
09262012, 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 HP15C ? The shortest I get through is a code that need to enter x1,y1 and x2,y2 point coordinate differently :
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!
▼
09262012, 04:42 PM
Sticking to the rules, I cannot get anything better than 17 steps on the HP15C: 001 STO 0
With the same formula a 14step (and perhaps less) is possible on the WP 34S, using only the stack: 001 + Gerson.
▼
09262012, 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
10012012, 12:59 AM
Well, low memory usage is not a requirement. So the following could have been done :) 001 42 34 f CLEAR REG Gerson.
09232012, 04:03 PM
thank you. you are right.
09232012, 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) 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...
09232012, 05:16 PM
Interesting problem. Speed and step count. The WP34S 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) 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 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 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 Thirteen steps, zero execution time.
As a complete aside and mostly for the record, a version using the combinations form is possible:
01 [<>] YXTZ Again, on the older device, one step can be spared:
01 [<>] YXTZ 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 ▼
09232012, 05:58 PM
My entry was very similar to one of yours:
01 XEQ 00 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.
09242012, 02:41 AM
Hi, I use the same algorithm, but my implementation on HP41C and HP15c may have to be optimise :
01 LBL "HHC2012 Subroutine 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)
An adaptation for HP15C follow the same organisation, but use register R0 in subroutine calculation.
001 *Lbl A Edited: 24 Sept 2012, 6:24 a.m.
09242012, 06:16 AM
Quote:Yes, I admit I was it, and I adhere to that :) But please read p. 180 before complaining ;)
09242012, 12:16 AM
How about an eleven step solution that only uses the stack:
01: [<>] TYZX Execution time is essentially zero.
▼
09242012, 01:10 AM
Well deserved rice pudding :) I'm at 14 steps and one register, but that's my final attempt. Gerson.
09252012, 12:30 AM
Quote: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. ▼
09252012, 04:31 AM
Quote: If anyone posted early, we'd not get another crack at the challenges. I doubt anyone would want that.
 Pauli
09282012, 12:43 PM
I wonder nobody mentioned it is actually Cantor's enumeration function. 