Re: HHC 2008 Programming Contest  anyone want to try an RPN solution? Message #26 Posted by Jeff O. on 11 Oct 2008, 11:18 p.m., in response to message #14 by Gene Wright
Below is my solution to the HHC 2008 programming contest. It is an RPN program, implemented on the 35S. It correctly solves the seven trial cases (as well as all others I have tried.) Total time to solve the seven trial cases, based on an average of three runs per case, came to 12.6 seconds.
In order to avoid "poisoning" my thought process with better ideas, I have not reviewed any of the other solutions posted here. I'll check them after I post this to see how much better I could have done:)
It took me a while to figure out how to attack the problem. I kicked around a variety of ideas and finally settled on a method in which I used the row numbers of the values (e.g., 1 is in the 1st row, 12 is in the 5th row, etc.) and the difference in corresponding values in different rows (e.g. the difference between the 1st value in row 7 (22) and the 1st value in row 3 (4) is 18) to check the validity of the set of points. Basically, check the first two points, predict the third based on the the first two and some calculations and see if it matches the entered value, if so and three points were entered it's a triangle, or proceeding to the 4th value for possible parallelograms and the 5th and 6th values for possible hexagons.
The equations I used are as follows:
Row Number of N = RN_{N} = Sqrt(2N + 0.25)  0.5
(if the formula does not yield an exact integer, then RN_{N} is the next largest integer.)
Corresponding Value Difference between RN_{x} and RN_{y} = CV_{xy}
where RN_{y} is greater than RN_{x}
let D = RN_{y}  RN_{x}
CV_{xy} = D(2RN_{x}+D1)/2
Jump
Line# Command Start Target Comments
A001 LBL A Label A
A002 RCL F recall 6th possible value
A003 x>0? is it greater than 0 (i.e., not equal to 0 or 1)?
A004 GTO A090 1 if yes, assume 6 points entered, branch to hexagon checking routine
A005 RCL E recall 5th possible value entered
A006 1 enter 1
A007 x=y? check if equal to 1
A008 GTO A050 2 if yes, assume 4 points entered, branch to parallelogram checking routine
A009 RCL D if no, recall 4th possible value entered
A010 x=y? check if equal to 1
A011 GTO A014 3 if yes, assume 3 points entered, branch to triangle checking routine
A012 CLSTK 8 if not 3, 4, or 6, set of points is invalid, clear stack to display zero.
A013 STOP stop, display zero for invalid set of points.
A014 RCL B 3 Begin triangle check routine, first sort values. Recall 2nd entered value
A015 RCL C recall third value entered
A016 x<y? third value less than second value?
A017 x<>y if yes, swap values
A018 STO C store X reg value in third value register
A019 x<>y swap
A020 RCL A recall first value entered
A021 x>y? first value greater than second value?
A022 x<>y if yes, swap values
A023 STO A store smallest value in first value register
A024 x<>y swap to get second value
A025 RCL C recall third value
A026 x<y? third value less than second value?
A027 x<>y if yes, swap values
A028 STO C store largest value in third value register
A029 x<>y swap
A030 STO B store 2nd largest value in second value register, values now sorted
A031 XEQ V001 4 execute subroutine to determine row number of second value (RN2)
A032 STO M store row number of 2nd value in M
A033 RCL A recall smallest value
A034 XEQ V001 4 execute subroutine to determine row number of smallest value (RN1)
A035 STO L store row number of smallest value in L
A036  subtract
A037 x<>0? is difference not zero?
A038 GTO A044 6 if not 0, values not in same row, possible uppointing triangle, branch to predict 3rd value
A039 RCL B if yes, values are in same row, possible downpointing triangle, recall B…
A040 RCL A recall A...
A041  subtract A from B and…
A042 STO N store difference in N and…
A043 XEQ W001 7 execute subroutine to determine difference between corresponding values (CV) in RN1 and RN2
A044 RCL+ B 6 for possible up pointing triangle, add row value difference to 2nd value to predict 3rd value.
for possible downpointing triangle add CV difference to 2nd value to predict 3rd value
A045 RCL C recall largest value, subtract from predicted
A046 x<>0? is difference not equal to 0?
A047 GTO A012 8 if entered and predicted 3rd values are not equal, not a triangle, branch to invalid data set stop
A048 1 if entered and predicted 3rd values are equal, is triangle, enter 1 for triangle
A049 STOP Stop, display 1 for triangle
A050 XEQ S001 9 2 Parallelogram checking routine. Begin by executing sort subroutine
A051 RCL D recall 2nd smallest value entered
A052 STO N Store in register that will hold side length
A053 XEQ V001 4 execute subroutine to determine row number of 2nd value (RN2)
A054 STO M store row number of 2nd value in M
A055 RCL C recall smallest value entered
A056 STO N subtract from 2nd value to determine side length (if not diamond), store in N
A057 XEQ V001 4 execute subroutine to determine row number of smallest value (RN1)
A058 STO L store row number of smallest value in L
A059  subtract RN1 from RN2
A060 x=0? is difference zero?
A061 GTO A071 12 if difference is zero, not diamond parallelogram, branch to check left & right
A062 STO N if difference not zero, is diamond possibility, store row difference in N
A063 RCL+ D add to 2nd value to predict 3rd
A064 RCL E Subtract entered 3rd value from predicted
A065 x<>0? is difference not 0?
A066 GTO A012 8 if difference is not zero, cannot be a parallelogram, branch to invalid data set stop
A067 RCL M recall row number of 2nd value
A068 STO L Store in register holding row number of 1st value
A069 XEQ W001 7 execute subroutine to determine difference between corresponding values (CV) in RN2 and RN4
A070 GTO A084 15 branch to predict 4th value
A071 XEQ W001 7 12 execute subroutine to determine difference between corresponding values (CV) in RN2 and RN3
A072 STO O Store CV difference for later use
A073 RCL C Recall 1st value
A074 + Add CV difference to 1st value to calculate predicted 3rd value for rightpointing case
A075 RCL E subtract entered 3rd value from predicted
A076 x=0? is difference 0?
A077 GTO A083 17 if yes, possible rightpointing parallelogram, branch to predict 4th point
A078 RCL O if no, may still be leftpointing, recall CV difference
A079 RCL+ D Add difference to 2nd value to calculate predicted 3rd value for leftpointing case
A080 RCL E subtract entered 3rd value from predicted
A081 x<>0? is difference not 0?
A082 GTO A012 8 if difference is not zero, cannot be a parallelogram, branch to invalid data set stop
A083 RCL N 17 recall side length
A084 RCL+ E 15 add to 3rd value to predict 4th point
A085 RCL F Subtract entered 4th value from predicted
A086 x<>0? is difference not 0?
A087 GTO A012 8 if difference is not zero, cannot be a parallelogram, branch to invalid data set stop
A088 2 if difference is 0, is a parallelogram. Enter 2 for parallelogram
A089 STOP Stop, display 2 for parallelogram
A090 XEQ S001 9 1 Hexagon checking routine. Begin by executing sort subroutine
A091 RCL B recall 2nd smallest value value entered
A092 STO N Store 2nd smallest value in register that will hold side length
A093 XEQ V001 4 execute subroutine to determine row number of second value
A094 STO M store row number of 2nd value in M
A095 RCL A recall smallest value
A096 STO N subtract from 2nd value to determine side length, store in N
A097 XEQ V001 4 execute subroutine to determine row number of smallest value
A098 STO L store row number of smallest value in L
A099  subtract
A100 x<>0? is difference not zero?
A101 GTO A012 8 if difference is not zero,cannot be a parallelogram, branch to invalid data set stop
A102 XEQ W001 7 execute subroutine to determine difference between corresponding values in RN2 and RN3
A103 STO O Store CV difference for later use
A104 RCL A Recall 1st value
A105 + Add CV difference to 1st value to calculate predicted 3rd value
A106 RCL C subtract entered 3rd value from predicted
A107 x<>0? is difference not 0?
A108 GTO A012 8 if difference is not zero, cannot be a hexagon, branch to invalid data set stop
A109 RCL C Recall 3rd value to predict 4th value
A110 RCL+ N Add side length
A111 RCL+ N Add side length again to predict 4th point
A112 RCL D Subtract entered 4th value from predicted
A113 x<>0? is difference not 0?
A114 GTO A012 8 if difference is not zero, cannot be a hexagon, branch to invalid data set stop
A115 RCL N recall side length
A116 STO+ L add to RN1, becomes RN3/4
A117 XEQ W001 7 execute subroutine to determine difference between corresponding values in RN3/4 and RN5/6
A118 RCL+C Add CV difference to 3rd value
A119 RCL+ N Add side length to calculate predicted 5rd value
A120 RCL E Subtract entered 5th value from predicted
A121 x<>0? is difference not 0?
A122 GTO A012 8 if difference is not 0 cannot be a hexagon, branch to invalid data set stop
A123 RCL E recall 5th value
A124 RCL+ N Add side length to calculate predicted 6th value
A125 RCL F Subtract entered 6th value from predicted
A126 x<>0? is difference not 0?
A127 GTO A012 8 if difference is not 0, cannot be a hexagon, branch to invalid data set stop
A128 3 if difference is 0, is a hexagon, enter 3 for hexagon
A129 STOP Stop, display 3 for hexagon
S001 LBL S 9 Sort routine
S002 5 input 5 for index (need to loop 5 times to sort 6 values)
S003 STO I store in index register
S004 RCL A 30 recall 1st value
S005 RCL B recall 2nd value
S006 x>y? 2nd bigger than 1st?
S007 x<>y if yes, swap, then…
S008 STO A store x register in 1st register
S009 x<>y swap to get current 2nd value
S010 RCL C recall 3rd value
S011 x>y? 3rd bigger than 2nd?
S012 x<>y if yes, swap, then…
S013 STO B store x register in 2nd register
S014 x<>y swap to get current 3rd value
S015 RCL D recall 4th value
S016 x>y? 4th bigger than 3rd?
S017 x<>y if yes, swap, then…
S018 STO C store x register in 3nd register
S019 x<>y swap to get current 4th value
S020 RCL E recall 5th value
S021 x>y? 5th bigger than 4th?
S022 x<>y if yes, swap, then…
S023 STO D store x register in 4th register
S024 x<>y swap to get current 5th value
S025 RCL F recall 6th value
S026 x>y? 6th bigger than 5th?
S027 x<>y if yes, swap, then…
S028 STO E store x register in 5th register
S029 x<>y swap to get current 6th value
S030 STO F store in register 6th register
S031 DSE I decrement index
S032 GTO S004 30 if looped less than 5 times, loop back to repeat
S033 RTN values sorted
V001 LBL V 4 RPN version of routine to determine row number of given value
V002 2
V003 x
V004 0.25
V005 +
V006 SQRT
V007 0.5
V008 
V009 +/
V010 INTG
V011 +/
V012 RTN
W001 LBL W 7 RPN version of routine to determine the absolute difference beteen corresponding
values (1st1st, 2nd2nd, etc.) in different rows given the row numbers
W002 2
W003 RCLx L
W004 RCL+ N
W005 1
W006 
W007 RCLx N
W008 2
W009 /
W010 RTN
...
