The Museum of HP Calculators

HP Forum Archive 20

[ Return to Index | Top of Index ]

HP Forum HHC Programming contest idea / possible rules
Message #1 Posted by gene wright on 20 Sept 2011, 9:52 a.m.

Hi all.

I think I have the final RPN programming problem figured out in my head at least and thought about trying to have a contest here at the forum this weekend for those who cannot attend the HHC in San Diego.

Here's what I was thinking:

1) Post the problem here early Saturday morning San Diego time.

2) Post the rules here as well, one of which will be for anyone in the forum who is working on the problem NOT to post their solutions, etc. here in the forum until after the end time of the contest. That would not be cool. :-)

3) Solutions should be emailed to my email address by the end time of the contest (which would be Sunday afternoon San Diego time).

4) I determine the winner of the forum submissions.

5) After the deadline... post away here at the forum with your solutions. :-)

This would require discipline not to search the internet for help, not to post solutions here early, etc.

The winner of the forum contest would receive world-wide fame and fortune and some sort of prize from me. :-)

What do all of you think?

      
Re: HP Forum HHC Programming contest idea / possible rules
Message #2 Posted by Thomas Radtke on 20 Sept 2011, 11:37 a.m.,
in response to message #1 by gene wright

I's a good idea to compete in the dark, so to say. I'll be there on Saturday with my 32SII between my teeth.

            
Re: HP Forum HHC Programming contest idea / possible rules
Message #3 Posted by gene wright on 20 Sept 2011, 11:42 a.m.,
in response to message #2 by Thomas Radtke

Well, the HHC attendees will be competing against each other, but those who cannot attend often want to compete too.

As long as people respect the goal of the contest which is to figure out your best effort on your own and not to publicize anything until after the contest is over!

      
Re: HP Forum HHC Programming contest idea / possible rules
Message #4 Posted by Pal G. on 20 Sept 2011, 12:02 p.m.,
in response to message #1 by gene wright

I think this would be fun for those of us who cannot attend. Thanks for thinking of us non-attendees.

      
Re: HP Forum HHC Programming contest idea / possible rules
Message #5 Posted by David Ramsey on 20 Sept 2011, 5:51 p.m.,
in response to message #1 by gene wright

When would we have time to work on the problem? The Saturday conference goes until 10PM!

            
Re: HP Forum HHC Programming contest idea / possible rules
Message #6 Posted by gene wright on 20 Sept 2011, 6:19 p.m.,
in response to message #5 by David Ramsey

But we don't start again until Sunday at 9am or so.

?

                  
Re: HP Forum HHC Programming contest idea / possible rules
Message #7 Posted by Marcus von Cube, Germany on 20 Sept 2011, 7:29 p.m.,
in response to message #6 by gene wright

Hey, I've brought my wife and she will not be on the conference! No chance to win the contest. :-( .
.
.
.
.
.
.
.
.
.
.

;-)

                        
Re: HP Forum HHC Programming contest idea / possible rules
Message #8 Posted by Eric Smith on 21 Sept 2011, 1:41 p.m.,
in response to message #7 by Marcus von Cube, Germany

Have her write contest entry for you. (Or would that violate the rules?)

                        
Re: HP Forum HHC Programming contest idea / possible rules
Message #9 Posted by C.Ret on 22 Sept 2011, 4:05 a.m.,
in response to message #7 by Marcus von Cube, Germany

Quote:
[...]No chance to win the contest. :-( [...]

Not sure, there is a lot of distractions in San Diego:
Shopping, ZOO, The Bay, The GasLamp Quarter, The Beach, The Surfers, The Navy, Sun Sea & S...

Not sure your wife will be concentrate enought on the contest to make you win [;-)]


Having the opportunity to participate at real-time and world-while to the contest will a be truly great !
I already set my wall-clock to California Est Time. I will not miss start time or deliver any result too late ...

P.S.: I mess up with the winter/summer hours shift. Is 10:00 am at Paris (France), 01:00 am at San Diego ?

Edited: 22 Sept 2011, 4:23 a.m.

                              
Re: HP Forum HHC Programming contest idea / possible rules
Message #10 Posted by Howard Owen on 22 Sept 2011, 4:50 a.m.,
in response to message #9 by C.Ret

Quote:
P.S.: I mess up with the winter/summer hours shift. Is 10:00 am at Paris (France), 01:00 am at San Diego ?

Yes, you are 9 hours ahead when we are both on summer or both on winter time. We are still on summer (daylight savings) time here. I think you are as well?

                                    
Re: HP Forum HHC Programming contest idea / possible rules
Message #11 Posted by Marcus von Cube, Germany on 23 Sept 2011, 10:54 a.m.,
in response to message #10 by Howard Owen

The 9 hours is correct. I'm still fighting the jet lag.

                              
Re: HP Forum HHC Programming contest idea / possible rules
Message #12 Posted by Dave Shaffer (Arizona) on 22 Sept 2011, 6:44 p.m.,
in response to message #9 by C.Ret

Quote:
P.S.: I mess up with the winter/summer hours shift. Is 10:00 am at Paris (France), 01:00 am at San Diego ?

Alternatively (since I don't know what time Paris is on), when on Daylight Savings Time compared to GMT, San Diego is 7 hours different (I can't decide whether this should be called "later" or "earlier"!). i.e. at GMT midnight (beginning of the new day), it is 5 PM (the previous day) in San Diego. During regular time, the offset is 8 hours.

                                    
Re: HP Forum HHC Programming contest idea / possible rules
Message #13 Posted by Walter B on 22 Sept 2011, 6:53 p.m.,
in response to message #12 by Dave Shaffer (Arizona)

Quote:
I don't know what time Paris is on
Like most of the EU, also Paris claims to see the sun 1h earlier than Greenwich. Portugal's the only country on the continent joining British time.
                                          
Re: HP Forum HHC Programming contest idea / possible rules
Message #14 Posted by Dave Shaffer (Arizona) on 22 Sept 2011, 9:24 p.m.,
in response to message #13 by Walter B

I am under the impression that not even Britain is on GMT (?) but an hour (or two in the summer) different.

                                    
Re: HP Forum HHC Programming contest idea / possible rules
Message #15 Posted by C.Ret on 23 Sept 2011, 6:40 a.m.,
in response to message #12 by Dave Shaffer (Arizona)

Thank you, all this is of great help.

I am now sure not to miss start and end of the contest :-)

      
I will post the RPN HHC Programming problem here Saturday A.M. San Diego time...
Message #16 Posted by gene wright on 22 Sept 2011, 7:42 a.m.,
in response to message #1 by gene wright

I have (inefficiently) programmed the problem on a 15c LE and on the 34S so I know it can be done. lol.

Speed is of course important, but I hope people will try the problem on other, not-quite-as-fast machines.

I also hope you will enjoy thinking through the problem.

But remember --- please respect the rules by NOT searching the internet for hints on how to solve it AND by not posting solutions here to the forum until AFTER 5p.m. Sunday San Diego time.

Everyone agree? :-)

            
Re: I will post the RPN HHC Programming problem here Saturday A.M. San Diego time...
Message #17 Posted by Werner on 25 Sept 2011, 2:12 p.m.,
in response to message #16 by gene wright

Agree. No solution, no hint.

41C 58 bytes, r=100, (x,y)=(1,1) in 21.38 secs

Let's see how I fared.. Werner

                  
Re: I will post the RPN HHC Programming problem here Saturday A.M. San Diego time...
Message #18 Posted by Thomas Radtke on 25 Sept 2011, 2:31 p.m.,
in response to message #17 by Werner

32SII, r=100: 45 byte, 10s. Not really optimized, I fear.

This was very much fun, and brought back a lot of the old fascination in this particular calculator. Thanks for it, Gene! :-)

                        
Re: I will post the RPN HHC Programming problem here Saturday A.M. San Diego time...
Message #19 Posted by Werner on 25 Sept 2011, 4:29 p.m.,
in response to message #18 by Thomas Radtke

41C, 39 bytes, r=100 in 14.75s

I can only hope the 32SII is much faster than the 41C ;-)

Werner

                              
Re: I will post the RPN HHC Programming problem here Saturday A.M. San Diego time...
Message #20 Posted by Paul Dale on 25 Sept 2011, 5:03 p.m.,
in response to message #19 by Werner

34S 21 steps, r=100 sub 1 second :-)

My fastest version is twice the size and about seven times faster but sadly incorrect.

- Pauli

                                    
Re: I will post the RPN HHC Programming problem here Saturday A.M. San Diego time...
Message #21 Posted by Dave Shaffer (Arizona) on 25 Sept 2011, 5:12 p.m.,
in response to message #20 by Paul Dale

Quote:
My fastest version is twice the size and about seven times faster but sadly incorrect.

A bit like the joke at NASA about spacecraft missions a while ago:

"Better, Faster, Cheaper - pick two out of three!"

                                          
Re: I will post the RPN HHC Programming problem here Saturday A.M. San Diego time...
Message #22 Posted by Paul Dale on 25 Sept 2011, 5:50 p.m.,
in response to message #21 by Dave Shaffer (Arizona)

:-)

In this case I'm sure the program can be fixed to give the expected results without any time penalty. I spent way too long fiddling around with the problem already and have real life things to get done. So yes, that quote applies.

- Pauli

                                    
Re: I will post the RPN HHC Programming problem here Saturday A.M. San Diego time...
Message #23 Posted by Dieter on 25 Sept 2011, 5:25 p.m.,
in response to message #20 by Paul Dale

35s: just 19 steps including LBL and RTN.
But r=100 takes ...a tiny bit longer: 13 seconds ;-)

Dieter

                              
Re: I will post the RPN HHC Programming problem here Saturday A.M. San Diego time...
Message #24 Posted by Gerson W. Barbosa on 25 Sept 2011, 5:39 p.m.,
in response to message #19 by Werner

HP-12C: 48 steps, r=100 -> 97 seconds (equivalent to about 43 seconds on the 41C).

                                    
Re: I will post the RPN HHC Programming problem here Saturday A.M. San Diego time...
Message #25 Posted by Werner on 26 Sept 2011, 2:19 a.m.,
in response to message #24 by Gerson W. Barbosa

By my reckoning it's 11PM San Diego time, so I can post a solution:


41C 37-byte prgm (excluding label and end)
timing 100:    13.00s    31'796
       540: 1m 09.12s   918'168
      1000: 2m 07.44s 3'145'520

pixels in a circle
------------------

 observations:
 - input parameters x and y are superfluous. We will assume a circle with centre (0,0)
 - solution is symmetric in every quadrant. We'll count the pixels in quadrant 1 and multiply by four
 - a pixel(x,y) is lit when (x-1)^2 + (y-1)^2 < r^2

 Let's start by assuming all pixels of the quadrant are lit, and then determine which ones are dark,
 as follows (take r=10 as an example):

 1. determine the first dark pixel in the top row:

    (m-1)^2 + (10-1)^2 >= 10^2
  or
     m = CEIL(sqrt(10^2 - 9^2) + 1) = 6

  so p(x,10) are lit, x=1..5
     p(x,10) are dark, x=6..10

  then, because of symmetry, we know these 9 pixels are dark:

   x x x x x . . . . .
   x x x x x x x x x .
   x x x x x x x x x .
   x x x x x x x x x .
   x x x x x x x x x .
   x x x x x x x x x x
   x x x x x x x x x x
   x x x x x x x x x x
   x x x x x x x x x x
   x x x x x x x x x x

 2. determine the first dark pixel in the second row:

    (m-1)^2 + (9-1)^2 >= 10^2
  or
     m = CEIL(sqrt(10^2 - 8^2) + 1) = 7

  so p(x,9) are lit, x=1..6
     p(x,9) are dark, x=7..10 - but 10 we knew already

  and we can darken the following 7 pixels, too:

   x x x x x . . . . .
   x x x x x x . . . .
   x x x x x x x x . .
   x x x x x x x x . .
   x x x x x x x x x .
   x x x x x x x x x x
   x x x x x x x x x x
   x x x x x x x x x x
   x x x x x x x x x x
   x x x x x x x x x x

 3. determine first dark pixel on row three

    (m-1)^2 + (8-1)^2 >= 10^2
  or
     m = CEIL(sqrt(10^2 - 7^2) + 1) = 9

 this means (x,8) is dark for x=9..10, and we are done

 in pseudocode this reads:

 p := r^2;
 y := r;
 do
   y := y - 1;
   m := CEIL(sqrt(r^2 - y^2) + 1);
   t := (m-y)*2 - 3;
   if t<0 then p := p + t;
 until t>=0;

41C 37-byte prgm (excluding label and end)
timing 100:    13.00s    31'796   
       540: 1m 09.12s   918'168
      1000: 2m 07.44s 3'145'520

01*LBL"PX"
02 RDN
03 RDN
04 STO 03		-- y
05 X^2
06 STO 01		-- r^2
07 STO 02		-- p
08*LBL 02
09 RCL 01
10 RCL 03
11 1
12 - 
13 STO 03
14 X^2
15 -
16 SQRT
17 INT
18 LASTX
19 FRC
20 X#0?
21 SIGN
22 +			-- m
23 RCL 03
24 -
25 ST+ X
26 1
27 -
28 X<0?
29 ST+ 02
30 X<0?
31 GTO 02
32 RCL 02
33 4
34 *
35 END

Cheers, Werner

                                          
Re: I will post the RPN HHC Programming problem here Saturday A.M. San Diego time...
Message #26 Posted by Paul Dale on 26 Sept 2011, 2:30 a.m.,
in response to message #25 by Werner

Nice idea counting dark pixels. Will terminate sooner than counting lit ones.

- Pauli

                                                
Re: I will post the RPN HHC Programming problem here Saturday A.M. San Diego time...
Message #27 Posted by Paul Dale on 26 Sept 2011, 6:43 a.m.,
in response to message #26 by Paul Dale

Thinking about this some more, it won't terminate much sooner for large radii. e.g. At a radius of 250, it stops 10% sooner. Still a neat way to approach the problem.

Working with octants instead of quadrants should save more.

- Pauli

                                                      
Re: I will post the RPN HHC Programming problem here Saturday A.M. San Diego time...
Message #28 Posted by Werner on 26 Sept 2011, 7:25 a.m.,
in response to message #27 by Paul Dale

But I work with octants already..
I determine the size of a 'corner' every time, and move in diagonally.
For r=100, I only go through the loop 29 times to determine all 31796 pixels..

Cheers, Werner

                                                            
Re: I will post the RPN HHC Programming problem here Saturday A.M. San Diego time...
Message #29 Posted by Gerson W. Barbosa on 26 Sept 2011, 8:15 a.m.,
in response to message #28 by Werner

Quote:
For r=100, I only go through the loop 29 times to determine all 31796 pixels.

On the other hand, mine loops 71 times, exactly the complement. At least, it returns the same result :-)

Cheers,

Gerson.

                                                            
Re: I will post the RPN HHC Programming problem here Saturday A.M. San Diego time...
Message #30 Posted by Paul Dale on 26 Sept 2011, 4:55 p.m.,
in response to message #28 by Werner

Quote:
But I work with octants already..

Oops, sorry I missed that :-(

The best of both options then.

- Pauli

                                          
Re: I will post the RPN HHC Programming problem here Saturday A.M. San Diego time...
Message #31 Posted by Gerson W. Barbosa on 26 Sept 2011, 8:07 a.m.,
in response to message #25 by Werner

Very well explained!

Here's my approach, with much less detailed explanations: 

   x   x   x   x   x   .   .   . | .   .
                                 |
   x   x   x   x   x   x   .   . | .   .
                                 +------
   x   x   x   x   x   x   x   x   .   .
                             /
   x   x   x   x   x   x   x   x   .   .
                         /
   x   x   x   x   x   x   x   x   x   .
                     /
   x   x   x   x   x   x   x   x   x   x
                 /
   x   x   x   x   x   x   x   x   x   x
             /
   x   x   x   x   x   x   x   x   x   x
         /
   x   x   x   x   x   x   x   x   x   x
     /
   x   x   x   x   x   x   x   x   x   x

Starting from the first column up to the 8th column (int[10*sqrt(2) + 1]), we check the number of dark pixels in each one. Using simmetry, the number of dark pixels in the quadrant is 

d = 2*5 + 2^2 = 14

The total number of lit pixels is 

n = 4*(r^2 - d^2) = 4*(100 - 14) = 344

That's the same number returned by your program.

The HP-12C program is almost a direct translation of the following BASIC program, hence its inefficiency: 

 5 CLS
10 INPUT R
15 R2 = R * R
20 L = INT(R / SQR(2)): D = R - L - 1
30 I = 0: S = 0
35 IF I >= L THEN 70
40   I = I + 1
50   S = S + INT(R - SQR(R2 - I * I))
60 GOTO 35
70 PRINT 4 * (R * R - 2 * S - D * D)
80 GOTO 10

HP-12C program 

Keystrokes      |Display       | 
[f][P/R]        |              | 
[f]CLEAR[PRGM]  |00-           | 
[ENTER]         |01-        36 | 
[STO]0          |02-    44   0 | 
[x]             |03-        20 | 
[STO]1          |04-    44   1 | 
[CLx]           |05-        35 | 
[STO]2          |06-    44   2 | 
[STO]3          |07-    44   3 | 
[RCL]0          |08-    45   0 | 
2               |09-         2 | 
[g][SQRT]       |10-    43  21 | 
[/]             |11-        10 | 
[g][INTG]       |12-    43  25 | 
[STO]4          |13-    44   4 | 
[g][x<=y]       |14-    43  34 | 
[g][GTO]31      |15- 43,33  31 | 
1               |16-         1 | 
[STO][+]3       |17- 44 40   3 | 
[RCL]0          |18-    45   0 | 
[RCL]1          |19-    45   1 | 
[RCL]3          |20-    45   3 | 
[ENTER]         |21-        36 | 
[x]             |22-        20 | 
[-]             |23-        30 | 
[g][SQRT]       |24-    43  21 | 
[-]             |25-        30 | 
[g][INTG]       |26-    43  25 | 
[STO][-]2       |27- 44 30   2 | 
[RCL]3          |28-    45   3 | 
[RCL]4          |29-    45   4 | 
[g][GTO]14      |30- 43,33  14 | 
[RCL]2          |31-    45   2 | 
[ENTER]         |32-        36 | 
[+]             |33-        40 | 
[RCL]1          |34-    45   1 | 
[+]             |35-        40 | 
[RCL]0          |36-    45   0 | 
[RCL]4          |37-    45   4 | 
[-]             |38-        30 | 
1               |39-         1 | 
[-]             |40-        30 | 
[ENTER]         |41-        36 | 
[x]             |42-        20 | 
[-]             |43-        30 | 
4               |44-         4 | 
[x]             |45-        20 | 
[g][GTO]00      |46- 43,33  00 | 
[f][P/R]        |              | 


The center coordinates shouldn't be entered.


     1 R/S ->           4       (   -  ,    2.2 s)
     5 R/S ->          88       (   -  ,    5.6 s)   
   540 R/S ->     918,168       ( 6.8 s,  407.0 s)
  5000 R/S ->  78,559,640       (60.3 s,    -    )

(timings on the 12C+ and 12C, respectively)

It should run faster on the 12C+ with the latest firmware.

Regards,

Gerson.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall