HHC 2012 RPN Programming Contest



#75

Here you go!

RPN Contest

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


#76

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.


#77

Yes, FOUR. :-)

Oops!


#78

For the RPN contest, the maximum value input will be 99,999. This is a change from what the directions say.

Gene


#79

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 ?


#80

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.

?


#81

Ok, I understood the meaning of positive and negative by finding the solution of the problem, now it's time for coding :)


#82

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


#83

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.


#84

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


#85

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


#86

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


#87

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

#88

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


#89

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


#90

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


#91

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


#92

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


#93

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

#94

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


#95

True! But then it's all a matter of habit, I guess. I'm just not used to shuffle the stack in these ways.

#96

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.


#97

Nice improvement!

#98

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.


#99

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

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 !


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

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)


This matches my result for those numbers.


- Pauli


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


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 ?


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.

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.


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


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

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.


The 34S timing should be based on the internal TICKS command which doesn't depend on the presence of a crystal or not.


- Pauli

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

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


- Pauli

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


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

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.


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.


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.

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

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.

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.


I tried tu use the LAST command but i don't find less !

Edited: 24 Sept 2012, 5:26 p.m.

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.


Quote:
19 steps HP 15c LE

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


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


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


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.


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

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

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.


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!


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.


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


It does work!

Gerson.


The WP 34S is really the greatest RPN tool !

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.

thank you. you are right.

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

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


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.

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.

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

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

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


Well deserved rice pudding :-)

I'm at 14 steps and one register, but that's my final attempt.

Gerson.

Quote:
Here you go!

RPN Contest

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.

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

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


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

Forum Jump: