HHC 2012 RPN Programming Challenge Conundrum



#5

I enjoy the HHC programming challenges, usually tackling after the fact. For personal satisfaction, I try to develop my best solution before looking at the Museum Forum discussion. I cogitated a little over the weekend of 22-23 September regarding this year's problem, but did not really start trying to write anything until Tuesday the 25th, and relatively quickly had a working routine (all routines on a wp34s.) Of course I kept up my normal Forum review, not reading any posts that had "HHC Programming Challenge" in the subject line. But I could see the subject lines, and saw that one mentioned something about a "12 Step Nashville Solution." 12 steps!!? Crap, my first attempt was 38 steps. OK, the first attempt was just to get a working program, I was sure it could be optimized, but 26 steps worth of optimization seemed unlikely. Long story short, I finally got down to 14 steps before writing this message. In the past, I would probably have been satisfied with going from 38 steps down to 14, but since I know there is a 12 step solution, it is difficult to stop. I'm doubtful I can shave it down to 12 using the solution approach I have chosen. I suspect there is some fundamental simplification to the solution that I am not going to see. So, if you have read this far, here is the conundrum. Should I:

1. Give up, read all of the Forum posts and be ready to slap my forehead when I see the obvious simplification I've been missing.

2. Give up, don't read the discussion and just try to be satisfied with my 14 step using-registers and 16 step all-stack programs.

3. Don't read the posts and keep on plugging away.

update - I followed option 3 and got down to 12 steps. Then followed option 1. With some insights gained, was able to write a 10 step program to solve the challenge.





Edited: 16 Oct 2012, 10:43 a.m. after one or more responses were posted


#6

There is an eleven step solution :-)


- Pauli


#7

Aarghh! You are a cruel, cruel man :-)


#8

Not really, cruel would have been saying ten.


- Pauli

#9

Hi.

I for one am always ready to learn: opt. 1

Luiz (Brazil)

#10

Quote:
3. Don't read the posts and keep on plugging away.

I would suggest this option --if you're still having fun-- at least until you find a 14-step stack-only solution. This shouldn't be difficult even on the HP-42S using the formula you appear to have now.
I guess you'll be surprised to know an unusual 13-step solution is possible on the HP-15C, but not using only the stack, of course :-)

Gerson


#11

I will suggest you another option:

   4. Read the posts and keep on programming your own solutions

Clearly, the best solution is not only the shortest. Length of code greatly depends on calculator faculties. For this WP-34S overlords other great RPN majors (HP-42S, HP-41C, HP-15c) and other or older calculators have not the tricky stack or integrated instruction to hit length records.
Try to table programs length versus calculator model

A longer personal code don't indicate you miss same important mathematical or logical fact. It's certainly more probable you don't notice any tricky detail in a specific function of your calculator.
This doesn’t mean you are a bad programmer; length of code optimization is only a play.

Day to day usage of your calculator implies a more clever integration of multiple code, an easy user-interface as well as specific capabilities for you specific daily applications.

I remember the old days when I use my Pocket Computer every day at work. Having the shortest or fastest code was not the key point. What save my day was that all the programs where well integrated, allowing rapid use of the pocket efficient and confident, unambiguous results display. I was using my advanced calculator mainly to check result from other sources of computation.

This cost a few extra steps, but help to spare a lot of time programming, using or verifying results!


Edited: 4 Oct 2012, 5:36 a.m.


#12

I agree with C.Ret. There is probably some mathematical trick or programming instruction that you haven't thought of. Read the posts and learn.

I took a similar approach with the RPL contest. After returning from Nashville I coded up an answer that I liked and then read the forum. There were several tricks there that I never would have thought of. To me, it's a learning process.

Dave


#13

Thanks Dave and to all who commented. I think I'll probably stew a little more on my own, then read the Forums. I had a new idea last night that I thought might help, but still landed at 14 steps* when I tried using it.

* - Just to clarify, by steps I am using and counting the mandatory END at the end of a program in wp34s. Also, I am not using a label at the beginning. So my programs look something like this:

001 STOS
.
.
.
.
013 /
014 END

I sure hope the 11 and 12 step programs do not have a Label at the beginning and a RTN at the end counted among those steps, else I am even further away from success.

.


#14

The final END shouldn't be counted, as mentioned elsewhere. On the HP-42S, for instance, it is appended automatically and adds nothing to the byte count. So you are now at 13 steps. Congrats!


#15

Great! In that case I am now at 12 steps, having successfully exorcized a step from my former 13 step (was 14 steps counting END) version using storage registers. Only one more step to go to get to 11. (Unfortunately, I fear it will take an infinite amount of mental energy to do so, like going from 99.999% of the speed of light, which is pretty darn fast, up to the actual speed of light.)


#16

11 steps & 2 registers, the best I can.


#17

Can you post your answer? It would be interesting to see how it compares to Pauli's 11 step program.

Dave


#18

For what it is worth, I was planning to post my best results today. The first thing I did was develop the following as the algorithm I would use to attack the problem:

steps between two points = (D2+D1) * (D2-D1+1)/2 + (D2-D1) - y1 - x2

where D2 = x2+y2 and D1= x1 + y1

(I now realize that the above was not the most enlightened approach, but that’s what I came up with, so I stuck with it.)

I boiled the above into two different equations:

equation 1: steps between points = ((x2+y2)^2-(x1+y1)^2+3*(y2-y1)+x2-x1)/2

The shortest program I could come up with was based on the above, uses registers:

001	STOS 11
002 CPX RCL-Z
003 CPX x<>11
004 Y<>Z
005 CPX+
006 CPX X^2
007 RCL+12
008 3
009 RCLx11
010 +
011 2
012 /
equation 2: steps between points = (D2*(D2+3)-D1*(D1+1))/2 - y1 - x2

The shortest stack-only program I could come up with was based on the above:

001	RCL+Y
002 <>ZTYX
003 STO+Z
004 +
005 ENTER
006 x^2
007 +
008 3
009 RCL+T
010 RCLxT
011 RCL-Y
012 2
013 /
014 RCL-T
Of course the above could be shortened to 13 steps by eliminating the ENTER in step 5 and replacing step 7 with RCL+L. But since that would still be 13 steps, and the previous program is only 12, there was no real point. So I leave the above as my shortest stack-only version. I played around trying to create stack-only programs from the first equation or shorter register-using versions from the second equation, but did not seem to be able to improve upon the above. So I finally gave up and read the Forum posts over the weekend. While I did not approach the problem quite as efficiently as Dave's described method, I was not as far off as I feared. But, I don’t think either of my programs breaks any new ground compared to the other solutions presented.

Jeff

edit - added new solution, then decided to post as new message


Edited: 9 Oct 2012, 10:50 a.m.


#19

Because this continues to be fun, I applied one of Dave's ideas to my original approach and came up with this equation:

steps between two points = (D2+D1) * (D2-D1+1)/2 - (y1 - y2) - D1
where D2 = x2+y2 and D1= x1 + y1

this led to the following 12 step all-stack solution:

				                                  X               Y               Z               T
beginning values in stack -> y2 x2 y1 x1
001 y<>Z swap Y with Z for next step, enables
complex add to create D1 and D2
simultaneously y2 y1 x2 x1
002 CPX STO+Z Complex store add to create D2 in Z,
D1 in T, y2 and y1 still in X and Y y2 y1 D2 D1
003 - subtract y2 from y1 to create y1-y2,
and drop stack to create second copy
of D1 in T y1-y2 D2 D1 D1
004 x<>Y swap X with Y for next step D2 y1-y2 D1 D1
005 STO+T add D2 to D1 in T to create D2+D1 D2 y1-y2 D1 D2+D1
006 RCL-Z Subtract D1 from D2 to create D2-D1 in X D2-D1 y1-y2 D1 D2+D1
007 INC X increment X to create D2-D1+1 D2-D1+1 y1-y2 D1 D2+D1
008 RCLxT mutiply D2-D1+1 by D2+D1 (D2-D1+1)*(D2+D1) y1-y2 D1 D2+D1
009 2 enter 2 2 (D2+D1+1)*(D2-D1) y1-y2 D1
010 / divide 2 into (D2-D1+1)*(D2+D1) (D2-D1+1)*(D2+D1)/2 y1-y2 D1 D1
011 RCL-Y subtract y1-y2 (D2-D1+1)*(D2+D1)/2-(y1-y2) y1-y2 D1 D1
012 RCL-Z subtract D1, final answer (D2-D1+1)*(D2+D1)/2-(y1-y2)-D1

As it is all-stack and is the same length as my previous shortest, I'm pretty sure it is the best I can do. Since my equation has an extra term as compared to Paul's 11 step solution which uses Dave's equation (I think), I don't believe it is possible to get down to 11 steps. (I'd be happy to see an 11 step version using this equation if anyone can do so.) So hopefully I will stop now.

edited to add comments and stack diagram


Edited: 9 Oct 2012, 4:20 p.m.

#20

Quote:
Can you post your answer? It would be interesting to see how it compares to Pauli's 11 step program.

Sure, Dave. I've used Pauli's magic C+ which does two sums at a time. There's no gain (quite the contrary, as two registers are needed), but this exploration of complex instructions might be useful for other applications:

001 y<> Z
002 CSTO 00
003 C+
004 Cx2
005 CRCL L
006 -
007 -
008 2
009 /
010 RCL+ 00
011 RCL- 01

Gerson.


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,547 11-05-2013, 02:44 AM
Last Post: Marcus von Cube, Germany
  HHC 2013 RPN Programming Challenge - Final Thought Jeff O. 7 2,483 10-17-2013, 11:02 AM
Last Post: Jeff O.
  HHC 2013 programming contest winners Brian Walsh 52 13,088 09-26-2013, 11:39 PM
Last Post: David Hayden
  Box left at HHC Tim Wessman 1 1,648 09-26-2013, 11:05 PM
Last Post: Wlodek Mier-Jedrzejowicz
  HHC 2013 speakers' files Joe Horn 2 1,673 09-26-2013, 02:51 AM
Last Post: Geoff Quickfall
  HHC 2013 Day 2 Highlights Eddie W. Shore 6 2,663 09-23-2013, 04:03 PM
Last Post: Kimberly Thompson
  HHC 2013: Day 1 Highlights Eddie W. Shore 28 8,160 09-23-2013, 03:22 PM
Last Post: Brad Barton
  HHC / HP Museum Programming Contest for RPN and RPL machines Gene Wright 18 5,796 09-22-2013, 09:39 AM
Last Post: Miguel Toro
  HHC 2013 room numbers David Hayden 2 1,343 09-20-2013, 05:34 PM
Last Post: sjthomas
  FYI: HHC 2013 Programming contests are coming Gene Wright 0 933 09-17-2013, 03:12 PM
Last Post: gene wright

Forum Jump: