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*

You're currently viewing a stripped down version of our content. View the full version with proper formatting.

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*

09-22-2012, 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.

09-22-2012, 01:57 PM

Yes, FOUR. :-)

Oops!

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

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 ?

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.

?

09-22-2012, 02:41 PM

"Noon CDT Sunday September 22, 2012". Hmm, in my TZ, September 22 is Saturday.

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 :)

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).

09-22-2012, 07:20 PM

Nice problem. 3am submission time. I guess I'll be a few hours late.

- Pauli

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:

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.

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

Just saying ...

Best regards from V.

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

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.

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).

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.

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

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

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

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...

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

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 !

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

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

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)

09-23-2012, 03:33 AM

This matches my result for those numbers.

- Pauli

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

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 ?

09-23-2012, 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 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.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 ENDHP 50g, exact mode:

<< -> a b c d

<< c d + SQ a b + SQ -

d b - 3 * + c + 2 -

2 / ->NUM

>>

>>

C_{1}= x_{1}+ y_{1}

C_{2}= x_{2}+ y_{2}n = C

_{2}- C_{1}+ ((C_{1}+ C_{2})*((C_{2}- C_{1}- 1 ))/_{2}+ C_{1}- y_{1}+ y_{2}( 1 )n = C

_{2}- C_{1}+ ((C_{1}+ C_{2})*((C_{2}- C_{1}- 1 ))/_{2}+ x_{1}+ y_{2}( 2 )or

n = ((x

_{2}+ y_{2})^{2}- (x_{1}+ y_{1})^{2}+ 3*(y_{2}- y_{1}) + x_{2}- x_{1}))/2 ( 3 )

Gerson.

_{Edited to fix formatting}

*Edited: 23 Sept 2012, 1:37 p.m. *

09-23-2012, 01:27 PM

On the HP-15C, I get -7.407397038e11.

Quote:According to this website it is about 30 minutes past noon now in Nashville, so no problem posting solutions.

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.

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.

09-23-2012, 02:09 PM

19 steps HP 15c LE

01 STO 0

02 +

03 R down

04 STO- 0

05 +

06 x><y

07 GSB B

08 STO- 0

09 GSB B

10 STO+ 0

11 RCL 0

12 R/S

13 LBL B

14 R down

15 ENTER

16 1

17 +

18 2

19 Cy,x

*Edited: 23 Sept 2012, 2:10 p.m. *

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.

09-23-2012, 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. ;-)

19 steps HP 15c LE

Dieter

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. *

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...

09-23-2012, 03:52 PM

on a 34S, of course... more later.

09-23-2012, 04:03 PM

thank you. you are right.

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

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

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. *

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*

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

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. *

09-23-2012, 06:07 PM

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*

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

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

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

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:Do you mean something along the lines of:

It feels like complex arithmetic operations could be leveraged here but I don't see how.

Cheers

Thomas

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.

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:x?^{2}- y^{2}= 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

09-23-2012, 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.

09-23-2012, 08:51 PM

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

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-R03Dave

+ 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

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

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 = ((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

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.

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.

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. *

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. *

09-24-2012, 06:16 AM

Quote:Yes, I admit I was it, and I adhere to that :-) But please read p. 180 before complaining ;-)

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.

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

09-24-2012, 04:23 PM

Hello Gilles,

55 bytes using

n = ((xAny idea to make it even smaller?_{2}+ y_{2})^{2}+ (x_{2}+ y_{2}) - ((x_{1}+ y_{1})^{2}+ (x_{1}+ y_{1})))/2 + y2 - y1

« ROT DUP2 - 5 ROLLDGerson.

1 2

START

UNROT + DUP SQ +

NEXT

- 2 / +

»

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. *

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

09-25-2012, 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.

Here you go!Please do not post any solutions here until after Noon CDT Sunday September 23, 2012.

Enjoy!

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

09-25-2012, 07:16 AM

Nice improvement!

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!

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.

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

09-26-2012, 11:00 PM

It does work!

Gerson.

09-27-2012, 08:43 AM

The WP 34S is really the greatest RPN tool !

09-27-2012, 07:42 PM

On the HP-42S, this 13-step solution (not counting final END) is possible:

00 { 25-Byte Prgm}25 bytes plus register 00 though.

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.

Gerson.

_{Edited to fix a typo}

*Edited: 27 Sept 2012, 7:58 p.m. *

09-28-2012, 12:43 PM

I wonder nobody mentioned it is actually Cantor's enumeration function.

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

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.

Powered By MyBB, © 2002-2023 MyBB Group