The Museum of HP Calculators

HP Forum Archive 21

[ Return to Index | Top of Index ]

HHC 2012 Programming Contests: annotations, comments ...?
Message #1 Posted by Peter Murphy (Livermore) on 24 Sept 2012, 2:35 p.m.

As a relative newbie to RPL -- and to anything more than simple keystroke RPN -- I would find it very useful to have annotated solutions to the HHC 2012 Programming Contest problems. Equally useful would be discussions of nice insights into the problems and of nice bits of code.

All that's easy for me to ask, of course; I'd be most appreciative of any efforts in those directions. And thanks in advance for such.

Peter

      
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #2 Posted by David Hayden on 25 Sept 2012, 12:28 a.m.,
in response to message #1 by Peter Murphy (Livermore)

My solution is commented in this post.

Note that Bill Butler has written analyses of several past programming problems in Datafile. I wrote an analysis in Datafile one year too.

Dave

            
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #3 Posted by Peter Murphy (Livermore) on 25 Sept 2012, 2:06 a.m.,
in response to message #2 by David Hayden

David, I just read your message as I was headed for bed. I'll follow those links in the morning.

Thanks a lot for your reply. The generosity on view in this Forum is wonderful.

      
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #4 Posted by Thomas Klemm on 25 Sept 2012, 7:13 a.m.,
in response to message #1 by Peter Murphy (Livermore)

Using the definitions below I ended up with the same formula as David Hayden: n = (s+1)*ds/2+dy

  • si = xi + yi, where i = 1, 2
  • s = s1 + s2
  • ds = s2 - s1
  • dy = y2 - y1

Instead of listing my own solution I'm commenting Werner's program as it is an improvement: 

                        X                   Y                   Z                   T
00 { 19-Byte Prgm }     y2                  x2                  y1                  x1
01 STO+ ST Y            y2                  s2                  y1                  x1
02 RDN                  s2                  y1                  x1                  y2
03 RDN                  y1                  x1                  y2                  s2
04 STO- ST Z            y1                  x1                  dy                  s2
05 +                    s1                  dy                  s2                  s2
06 X<>Y                 dy                  s1                  s2                  s2
07 RDN                  s1                  s2                  s2                  dy
08 STO+ ST Z            s1                  s2                  s                   dy
09 -                    ds                  s                   dy                  dy
10 STO* ST Y            ds                  s*ds                dy                  dy
11 +                    (s+1)*ds            dy                  dy                  dy
12 2                    2                   (s+1)*ds            dy                  dy
13 /                    (s+1)*ds/2          dy                  dy                  dy
14 +                    (s+1)*ds/2+dy       dy                  dy                  dy
15 .END.
Kind regards
Thomas

Edited: 25 Sept 2012, 7:17 a.m.

      
Re: HHC 2012 RPL Programming Contests: annotations, comments ...?
Message #5 Posted by Gilles Carpentier on 25 Sept 2012, 4:51 p.m.,
in response to message #1 by Peter Murphy (Livermore)

@==============================================================
@ HHC 2012 RPL challenge. 
@ Size  : 140 Byte
@ Speed : 0.265 sec. for the example in the challenge on real HP50G
@--------------------------------------------------------------

{ 3 6 5 2 3 1 8 2 6 5 4 4 7 4 } 

«                                         @ SEE -1- Input list  
 LIST-> 2. / 1. +  -> s                   @ SEE -2- 'explode' the list on the stack and size/2+1 in 's'                 
  «
   DUP2                                   @ SEE -3- Trick for one point only input 
   1. s FOR n R->C s 2. * n -  ROLLD NEXT @ SEE -4- Transform in complex number on the stack
                                          @         and put each result in top of the stack
                                          @ SEE -5- : result for the last R->C before the ROLLD wich will put the complex number in level 8 and roll down 2-8 entries to 1-7
   0.                                     @ Init the max distance
   s 2. + 4. FOR n                        @ For each number
    4. n FOR m                            @   with each other 
     OVER m PICK                          @   SEE -6-
     -                                    @   SEE -7-
     ABS                                  @   SEE -8-
     MAX                                  @   SEE -9-
    NEXT 
                                          @ The idea is to compare each element to each other
    NIP                                   @ NIP is shortcut for SWAP DROP (delete item 2 on the stack)
   -1. STEP
   NIP
  »
»                                         @ SEE -10-

Edited: 25 Sept 2012, 5:34 p.m.

      
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #6 Posted by Gerson W. Barbosa on 25 Sept 2012, 8:47 p.m.,
in response to message #1 by Peter Murphy (Livermore)

Let's consider the example in the drawing above. The source point is (x1, y1) = (2, 3) and the destination point is (x2, y2) = (3, 5). C1 and C2 in the y-axis are the linear coefficients of the straight lines y = -x + C1 and y = -x + C2, which contain these points. From the drawing, 

  C1 = x1 + y1; C1 = 2 + 3; C1 = 5

  C2 = x2 + y2; C2 = 4 + 5; C2 = 9
The number of steps marked in orange is 
  n1 = C2 - C1; n1 = 9 - 5; n1 = 4
The number of steps marked in blue, from (x1, y1) to C1, is 
  n2 = x1; n2 = 2
The number of steps marked in green, from the x-axis to (x2, y2), is 
  n3 = y2; n3 = 5
The number of the remaining steps, marked in red, is 
        C2-1
        ----
  n4 =  \     k  ; n4 = (C22 - C2 - C12 - C1)/2; n4 = (92 - 9 - 52 - 5)/2; n4 = 21
        /      
        ---- 
       k=C1+1
Finally, the total number of steps is 
  n = n1 + n2 + n3 + n4; n = 4 + 2 + 5 + 21; n= 32
or, generically, 
  n = C2 - C1 + x1 + y2 + (C22 - C2 - C12 - C1)/2
which can be simplified to 
  n = ((x2 + y2)2 + (x2 + y2) - ((x1 + y1)2 + (x1 + y1)))/2 + y2 - y1

The symetry of the latter allows for this HP 50g 55-byte program: 

PGM1:

« ROT DUP2 - 5 ROLLD
  1 2 
  START 
    UNROT + DUP SQ +
  NEXT
  - 2 / +
»

Example: 

2 ENTER 3 ENTER 4 ENTER 5 PGM1   -->   32

This doesn't mean, however, smaller RPL programs are not possible.

Gerson.

Edited: 25 Sept 2012, 9:17 p.m.

            
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #7 Posted by Gilles Carpentier on 26 Sept 2012, 12:44 p.m.,
in response to message #6 by Gerson W. Barbosa

« ROT DUP2 - 5 ROLLD
  1 2 
  START 
    UNROT + DUP SQ +
  NEXT
  - 2 / +
»

Well done !

But with the Score= Time * Size,perhaps this could have a best score :

« ROT DUP2 - 5 ROLLD
  UNROT + DUP SQ +
  UNROT + DUP SQ +
  - 2 / +
»
                  
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #8 Posted by Gerson W. Barbosa on 26 Sept 2012, 1:36 p.m.,
in response to message #7 by Gilles Carpentier

Quote:
Well done !

Merci. Venu du maître du RPL, c'est vraiment un compliment ! :-)

Quote:
But with the Score= Time * Size,perhaps this could have a best score

Your're right. I had tried that first, 57.5 bytes I think, running time below 50 milliseconds. START NEXT saved 2.5 bytes, but has introduced a small delay.

That problem was meant for RPN calculators only, hence the scarce number of RPL solutions. A quest for even smaller code using various formulas and tricks might be interesting however.

Cheers,

Gerson.

                        
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #9 Posted by Neil Hamilton (Ottawa) on 26 Sept 2012, 2:48 p.m.,
in response to message #8 by Gerson W. Barbosa

Probably a silly question but how are you deriving the runtime? Do you encapsulate and call your program with TICKS or something? Possibly something like this:

<< TICKS -> t
  << YOURPRG TICKS t - B->R 8192 / >>
>>

Just curious.

Thanks...

                              
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #10 Posted by gene wright on 26 Sept 2012, 3:01 p.m.,
in response to message #9 by Neil Hamilton (Ottawa)

Put the inputs on the stack, followed by the program name in quotes, then TEVAL and press ENTER.

                                    
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #11 Posted by Gerson W. Barbosa on 26 Sept 2012, 4:09 p.m.,
in response to message #10 by gene wright

Yes. From the catalog HELP, HP49G,49G+ & 50 g: 

Evaluates object and 
returns time for eval.
TEVAL(TCOLLECT(SIN(X)+
COS(X)))
{sqrt2*COS(X-pi/4) s:.052...

It appears TEVAL is available only from the catalog.

                                          
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #12 Posted by gene wright on 26 Sept 2012, 4:29 p.m.,
in response to message #11 by Gerson W. Barbosa

When I was judging the contest, I just held down the alpha key and pressed TEVAL then let the alpha key go and pressed eval.

Wasn't too tough. If I were doing it for a lot of situations, I would assign it to a key.

                                    
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #13 Posted by Neil Hamilton (Ottawa) on 26 Sept 2012, 4:31 p.m.,
in response to message #10 by gene wright

Great! Thanks.

It appears that TEVAL is not in my 48SX I have at work. I will try it on my 48G and 50 at home tonight.

                                          
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #14 Posted by Neil hamilton (ottawa) on 26 Sept 2012, 6:26 p.m.,
in response to message #13 by Neil Hamilton (Ottawa)

According to the "Command Menu-Path Table" from 50 AUR(?) [Appendix I], TEVAL did not arrive until ROM rev 1.05 -- which is presumably the 49G and onwards. So no luck on my 48G either.

Oh well. I'll try in my 49G+ (2.15).

...time passes...

Tried it on my 49G+ and it seems to return a variable amount: +/- 0.002 s. Not too surprising.

It looks like my little UserRPL knockoff does essentially the same as TEVAL (slightly improved from previous stab -- formatted to look similar to TEVAL) so I should be about to do this on 48g/s as well:

<< TICKS -> t
  << EVAL t - B->R 8192 /  "s" ->TAG >>
>>
      
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #15 Posted by Gerson W. Barbosa on 1 Oct 2012, 10:21 p.m.,
in response to message #1 by Peter Murphy (Livermore)

The expression 

  n = ((x2 + y2)2 + (x2 + y2) - ((x1 + y1)2 + (x1 + y1)))/2 + y2 - y1

above can be simplified on the HP-28S (if one is not willing to do it manually) using the EXCO program (page 256 of the Owner's Manual) as follows: 

'((x2+y2)^2+(x2+y2)-
((x1+y1)^2+(x1+y1)))
/2+(y2-y1)'

EXCO

'-(x1*y1)-.5*x1^2+x2
*y2+.5*x2^2-.5*y1^2+
.5*y2^2-.5*x1+.5*x2-
1.5*y1+1.5*y2'
which can be further simplified as 
'((x2 - x1) + 3*(y2 - y1) + (x2^2 - x1^2) + (y2^2 - y1^2))/2 + (x2*y2 - x1*y1)'
This allows for the following 13-step HP-15C program:

001-    42 34  f CLEAR REG
002-       49    SIGMA+              ; Notice xi and yi are in reversed order on the stack
003-       33    Rv
004-       33    Rv
005-    43 49  g SIGMA-
006-        3    3
007- 45 20  3    RCL* 3              ; R3: SIGMAx
008- 45 40  4    RCL+ 4              ; R4: SIGMAx2
009- 45 40  5    RCL+ 5              ; R5: SIGMAy
010- 45 40  6    RCL+ 6              ; R6: SIGMAy2
011-        2    2
012-       10    /
013- 45 40  7    RCL+ 7              ; R7: SIGMAxy

11111 ENTER
22222 ENTER
33333 ENTER 
44444 R/S     -->  2 469 130 864  (less than 3 seconds on the HP-15C, about 25 milliseconds on the HP-15C LE)

Gerson.

            
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #16 Posted by Katie Wasserman on 2 Oct 2012, 12:27 a.m.,
in response to message #15 by Gerson W. Barbosa

I love recall register arithmetic and non-standard use of Sigma+, I've done that too in several programs to shorten (and obfuscate) code. But I don't recall ever using Sigma- for that purpose, nice one!

                  
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #17 Posted by Gerson W. Barbosa on 2 Oct 2012, 5:12 p.m.,
in response to message #16 by Katie Wasserman

It's only a pity that CLEAR SIGMA clears also the HP-15C stack. On the HP-34C and HP-41 it does not, but then they lack recall arithmetic. More recent RPN calculators, the WP 34s included, have dedicated statistical registers (with neither storage nor recall arithmetic, of course). So it appears this solution will fit the HP-15C and HP-42S only, better on the latter on which CLSIGMA can be used instead of CLEAR REG, thus preserving all registers but the statistical ones.

                        
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #18 Posted by Paul Dale on 2 Oct 2012, 5:23 p.m.,
in response to message #17 by Gerson W. Barbosa

Version 2 firmware for the 34S doesn't have separate statistical registers. They occupy the high numbered registers instead.

The 34S only got separate (& more accurate) statistical registers once memory partitioning was implemented in version 3.

- Pauli

                              
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #19 Posted by Gerson W. Barbosa on 2 Oct 2012, 6:54 p.m.,
in response to message #18 by Paul Dale

I think I'll stick to Version 3. That would save only one step anyway.

Gerson.

            
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #20 Posted by Jeff O. on 17 Oct 2012, 1:19 p.m.,
in response to message #15 by Gerson W. Barbosa

Gerson,
After pretty much beating wp34s solutions to the RPN contest into the ground, and taking a short break, I of course turned my attention to the 15C. I came up with three 17-step solutions, all of which fail when the sum of either x,y pair exceeds 99,999. This is due me using the same algorithms used in my wp34s solutions, which call for the squaring of this sum, which exceeds the 10 digit capability of the 15C. Rather than spend a lot of time trying to optimize and fix, I just searched through the posts in this thread. I thought I recalled seeing a relatively short solution, and found yours. I want to compliment you on the above 13 step solution that works for the prescribed argument range. Very nice indeed!
Best regards
Jeff

.

                  
Re: HHC 2012 Programming Contests: annotations, comments ...?
Message #21 Posted by Gerson W. Barbosa on 17 Oct 2012, 4:47 p.m.,
in response to message #20 by Jeff O.

Hello Jeff,

Thanks for the compliment! Clearing all registers is a disadvantage, though. It's a pity Clear Stack and Clear Statistics are merged into one single instruction on the Voyagers.
My previous HP-15C attempt was 17-step long too (message #57 in the incomplete original Google-cached thread here).

Best regards,

Gerson.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall