▼
Posts: 1,545
Threads: 168
Joined: Jul 2005
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?
▼
Posts: 1,089
Threads: 32
Joined: Dec 2005
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.
▼
Posts: 1,545
Threads: 168
Joined: Jul 2005
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!
Posts: 260
Threads: 21
Joined: Nov 2006
I think this would be fun for those of us who cannot attend. Thanks for thinking of us non-attendees.
Posts: 521
Threads: 72
Joined: Jul 2007
When would we have time to work on the problem? The Saturday conference goes until 10PM!
▼
Posts: 1,545
Threads: 168
Joined: Jul 2005
But we don't start again until Sunday at 9am or so.
?
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
Hey, I've brought my wife and she will not be on the conference! No chance to win the contest. :-(
.
.
.
.
.
.
.
.
.
.
.
;-)
▼
Posts: 2,309
Threads: 116
Joined: Jun 2005
Have her write contest entry for you. (Or would that violate the rules?)
Posts: 260
Threads: 0
Joined: Oct 2008
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.
▼
Posts: 1,830
Threads: 113
Joined: Aug 2005
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?
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
The 9 hours is correct. I'm still fighting the jet lag.
Posts: 776
Threads: 25
Joined: Jun 2007
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.
▼
Posts: 4,587
Threads: 105
Joined: Jul 2005
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.
▼
Posts: 776
Threads: 25
Joined: Jun 2007
I am under the impression that not even Britain is on GMT (?) but an hour (or two in the summer) different.
Posts: 260
Threads: 0
Joined: Oct 2008
Thank you, all this is of great help.
I am now sure not to miss start and end of the contest :-)
Posts: 1,545
Threads: 168
Joined: Jul 2005
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? :-)
▼
Posts: 163
Threads: 7
Joined: Jul 2007
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
▼
Posts: 1,089
Threads: 32
Joined: Dec 2005
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! :-)
▼
Posts: 163
Threads: 7
Joined: Jul 2007
41C, 39 bytes, r=100 in 14.75s
I can only hope the 32SII is much faster than the 41C ;-)
Werner
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
34S 21 steps, r=100 sub 1 second :-)
My fastest version is twice the size and about seven times faster but sadly incorrect.
- Pauli
▼
Posts: 776
Threads: 25
Joined: Jun 2007
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!"
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
:-)
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
Posts: 653
Threads: 26
Joined: Aug 2010
35s: just 19 steps including LBL and RTN.
But r=100 takes ...a tiny bit longer: 13 seconds ;-)
Dieter
Posts: 2,761
Threads: 100
Joined: Jul 2005
HP-12C: 48 steps, r=100 -> 97 seconds (equivalent to about 43 seconds on the 41C).
▼
Posts: 163
Threads: 7
Joined: Jul 2007
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
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
Nice idea counting dark pixels. Will terminate sooner than counting lit ones.
- Pauli
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
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
▼
Posts: 163
Threads: 7
Joined: Jul 2007
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
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
Posts: 3,229
Threads: 42
Joined: Jul 2006
Quote: But I work with octants already..
Oops, sorry I missed that :-(
The best of both options then.
- Pauli
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
|