Re: HHC 2011 Programming Puzzle SPOILERS, nothing but stack! Message #52 Posted by Jeff O. on 5 Oct 2011, 1:16 p.m., in response to message #51 by Gerson W. Barbosa
I have been fooling around with the challenge since Sept. 25. I think I have reached the point of diminishing returns, or at least should stop spending time on it. So I'll present some results, maybe that will stop the obsessive tweaking.
Using the inscribed square reduction depicted here (which I did develop on my own on Sept. 26 before looking at any of the solutions), the following listing is about the best I can come up with for wp34s. It returns 78,528,204 for a radius of 4999 in about 8.20 seconds.
001 LBL B
002 RCL Z Recall stack Z, since radius is there per rules
003 ENTER Get another copy of the radius on the stack
004 STO 08 Store radius for future use
005 STO + 08 double the stored value of the radius for future use
006 x^2 square the radius
007 2 enter 2 to compute area of square inscribed in a quarter circle
008 / divide 2 into radius squared to determine area of square inscribed in quarter circle
009 SQRT take square root to determine side length of square inscribed in quarter circle
010 CEIL go up to next whole pixel
011 STO 06 store side length in register that will accumulate area
012 STO x 06 multiply side length by stored side length to compute area of inscribed square in whole pixels
013 - subtract size of square from radius to determine how many remaining columns must be summed
014 STO I store in register I for looping to compute height of remaining columns
015 RCL 8 Recall twice the radius
016 RCL - I Recall index and subtract from twice the radius
017 RCL x I Recall I, multiply times above to form 2xRadiusxIndex-Index^2
018 SQRT square root to compute square root of 2xRadiusxIndex-Index^2
019 CEIL compute height of row in full pixels if any part is touched by a circle of the given radius
020 STO + 06 add to summation of area
021 STO + 06 add again for area of upper wedge
022 DSE I decrement index, skip when less than zero
023 BACK 8 loop back if more columns
024 4 enter 4
025 RCL x 06 multiply times 4 to compute the area of the full circle in whole
pixels if any part of a pixel is within the circle of the given radius
026 STOP done
Summing the area in the stack appears to be a popular option, so I created the listing below. It is one step longer, and also seems to run ever-so-slightly slower, returning the result for 4999 in about 8.35 seconds.
001 LBL B
002 RCL Z Recall stack Z, since radius is there per rules
003 ENTER Get another copy of the radius on the stack
004 STO 08 Store radius for future use
005 STO + 08 double the stored value of the radius for future use
006 x^2 square the radius
007 2 enter 2 to compute area of inscribed square
008 / divide 2 into radius squared to determine area of square inscribed in quarter circle
009 SQRT take square root to determine side length of square inscribed in quarter circle
010 CEIL go up to next whole pixel
011 x^2 square side length to compute area of inscribed square in whole pixels
012 x<>y swap to get radius
013 RCL - L subtract size of square from radius to determine how many remaining columns must be summed
014 STO I store in register I for looping to compute height of remaining columns
015 x<>y swap to get area of square to stack X for area sum start
016 RCL 8 Recall twice the radius
017 RCL - I Recall index and subtract from twice the radius, forms 2xRadius-Index
018 RCL x I Recall I, multiply times above to form 2xRadiusxIndex-Index^2
019 SQRT square root to compute square root of 2xRadiusxIndex-Index^2
020 CEIL compute height of row in full pixels if any part is touched by a circle of the given radius
021 + add to summation of column heights
022 RCL + L add again for area of upper wedge
023 DSE I decrement index, skip when less than zero
024 BACK 08 loop back if more columns
025 4 enter 4
026 x multiply times 4 to compute the area of the full circle in whole
pixels if any part of a pixel is within the circle of the given radius
027 STOP done
Observations - I don't claim the above to be the best possible, just likely the best I can do with reasonable effort.
I have of course also worked on versions for the 15c LE, the latest of which returns the answer for 4999 in about 19 seconds. I may have to keep working on that one...
...
Edited: 6 Oct 2011, 8:42 a.m. after one or more responses were posted
|