Posts: 875
Threads: 37
Joined: Jul 2005
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
Posts: 3,229
Threads: 42
Joined: Jul 2006
There is an eleven step solution :-)
- Pauli
Posts: 591
Threads: 16
Joined: Feb 2012
Hi.
I for one am always ready to learn: opt. 1
Luiz (Brazil)
Posts: 875
Threads: 37
Joined: Jul 2005
Aarghh! You are a cruel, cruel man :-)
Posts: 3,229
Threads: 42
Joined: Jul 2006
Not really, cruel would have been saying ten.
- Pauli
Posts: 2,761
Threads: 100
Joined: Jul 2005
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
Posts: 260
Threads: 0
Joined: Oct 2008
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.
Posts: 528
Threads: 40
Joined: Dec 2008
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
Posts: 875
Threads: 37
Joined: Jul 2005
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.
.
Posts: 2,761
Threads: 100
Joined: Jul 2005
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!
Posts: 875
Threads: 37
Joined: Jul 2005
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.)
Posts: 2,761
Threads: 100
Joined: Jul 2005
11 steps & 2 registers, the best I can.
Posts: 528
Threads: 40
Joined: Dec 2008
Can you post your answer? It would be interesting to see how it compares to Pauli's 11 step program.
Dave
Posts: 875
Threads: 37
Joined: Jul 2005
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.
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
Posts: 875
Threads: 37
Joined: Jul 2005
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.
|