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?

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.

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!

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

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

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

?

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

.

.

.

.

.

.

.

.

.

.

;-)

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

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.

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?

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

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.

Quote:

---

I don't know what time Paris is on

---

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

Thank you, all this is of great help.

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

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

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

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

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

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

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

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!"

35s: just 19 steps including LBL and RTN.

But r=100 takes ...a tiny bit longer: 13 seconds ;-)

Dieter

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

:-)

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

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

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

- Pauli

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

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

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.

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.

Quote:

---

But I work with octants already..

---

Oops, sorry I missed that :-(

The best of both options then.

- Pauli