My entry for the HP35S Programming Contest in HHC 2007 (long) Message #1 Posted by Andrés C. Rodríguez on 17 Nov 2007, 9:03 p.m.
I would like to share this program, which got the second place in the HHC 2007 Programming Contest.
The challenge was to create a program to order the digits of an integer in the range between 1 and 9 999 999 999, zero was not permitted as a digit. So, for instance,
1234512345 will result in 1122334455,
827516 will result in 125678,
9876 will result in 6789,
and so on. The program which does it faster will win.
I had no prior experience with the HP35S, but had quite experience with HP41C and 42S, and some with HP32Sii and HP33S.
The first idea was not to resort (no pun intended) to a sort algorythm, but to count how many appeareances of each digit there were, and create the output accordingly.
Another idea was to reuse values stored in variables, instead of reentering a number, because recalling was faster than input.
A third idea was to use inline code in place of some loops, since the 35S was plenty of free memory. While this is inefficient from a memory usage point of view, and more difficult to edit and debug, it is faster at execution.
There are two parts in the program: LBL A analyzes the input, LBL D builds the output from the data gathered in the analysis part.
ISG instructions were used to increment the registers which count the number of times a digit appears. The "skip" part of ISG was of no interest, in fact, the next instruction was always skipped. I used DEG as a rather innocuous instruction, a NOP would properly fit. See that the DEG will never be executed, so calculator settings were not changed.
Integer division and reminder operations were used to decompose the original value, storage arithmetic (addition and times-10 multiplication) were used to build the output.
Since the challenge stated that the calculator should be returned to the original state, care was taken as to free all memory used by the program, some steps at the end of the program took care of that. As the output-building loops were decrementing, the counters end in zero with no effort. Other variables were specifically zeroed at recall time by means of a "STO -" instruction; finally a variable was zeroed by means of a "x<>" instruction. No flags or modes were changed, although the program looks nicer if run in FIX 0 mode.
Now, the code...
Brackets were used on the right side of instructions as graphical aids to identify loops and loop nesting. Also brackets on the left side of instructions were used to show the destinations of GTO instructions.
- PRGM TOP -
A001 LBL A
A002 1.009
A003 STO B Keep 1.009 for future use as loop counter
A004 STO I Initialize loop counter
A005 CLx
A006 STO D Set output variable to zero
A007 [] STO (I) [] Loop here to clear counters (Regs 1 to 9)
A008 ISG I []
A009 GTO A007[]
A010 R v Roll down to recover the number to be “sorted”
A011 ENTER Start analysis
A012 ENTER Keep a copy of number in y
A013 10
A014 STO C Keep 10 for future use from a register, it is faster
A015 RMDR Get rightmost digit by the reminder operation
A016 x=0? If zero…
A017 GTO D001 … break!
A018 STO I Use digit as index and…
A019 ISG (I) … increment respective counter
A020 DEG Just a placekeeper, will never be executed
A021 CLx And now… (number is still in y)
A022 LAST x … recover 10 and …
A023 INT / … get the remaining leftside digits by integer division
A024 ENTER Repeat analysis for next digit…
A025 ENTER (this could have been done by a loop,
A026 LAST x but was coded inline for speed, the
A027 RMDR HP 35S has plenty of RAM for this)
A028 x=0?
A029 GTO D001
A030 STO I
A031 ISG (I)
A032 DEG
A033 CLx
A034 LAST x
A035 INT /
A036 ENTER Repeat analysis for next digit…
A037 ENTER
A038 LAST x
A039 RMDR
A040 x=0?
A041 GTO D001
A042 STO I
A043 ISG (I)
A044 DEG
A045 CLx
A046 LAST x
A047 INT /
A048 ENTER Repeat analysis for next digit…
A049 ENTER
A050 LAST x
A051 RMDR
A052 x=0?
A053 GTO D001
A054 STO I
A055 ISG (I)
A056 DEG
A057 CLx
A058 LAST x
A059 INT /
A060 ENTER Repeat analysis for next digit…
A061 ENTER
A062 LAST x
A063 RMDR
A064 x=0?
A065 GTO D001
A066 STO I
A067 ISG (I)
A068 DEG
A069 CLx
A070 LAST x
A071 INT /
A072 ENTER Repeat analysis for next digit…
A073 ENTER
A074 LAST x
A075 RMDR
A076 x=0?
A077 GTO D001
A078 STO I
A079 ISG (I)
A080 DEG
A081 CLx
A082 LAST x
A083 INT /
A084 ENTER Repeat analysis for next digit…
A085 ENTER
A086 LAST x
A087 RMDR
A088 x=0?
A089 GTO D001
A090 STO I
A091 ISG (I)
A092 DEG
A093 CLx
A094 LAST x
A095 INT /
A096 ENTER Repeat analysis for next digit…
A097 ENTER
A098 LAST x
A099 RMDR
A100 x=0?
A101 GTO D001
A102 STO I
A103 ISG (I)
A104 DEG
A105 CLx
A106 LAST x
A107 INT /
A108 ENTER Repeat analysis for next digit…
A109 ENTER
A110 LAST x
A111 RMDR
A112 x=0?
A113 GTO D001
A114 STO I
A115 ISG (I)
A116 DEG
A117 CLx
A118 LAST x
A119 INT /
A120 x=0? For the leftmost digit analysis…
A121 GTO D001 … things are simpler
A122 STO I
A123 ISG (I) End of analysis!
D001 [] LBL D Start building the output in variable D
D002 RCL B Recover 1.009 to initialize loop counter…
D003 STO - B … and release B, we don’t need it anymore
D004 STO I For 1 to 9…
D005 [] RCL (I) [] … recall the number of times each digit had appeared
D006 x=0? [] If zero…
D007 GTO D015 [] … break!
D008 [] RCL C [] [] Recall 10…
D009 STO x D [] [] … use to shift left the contents of D
D010 RCL I [] [] Recall the working digit from counter…
D011 IP [] []
D012 STO + D [] [] … and add it to D
D013 DSE (I) [] [] Repeat for same digit (also cleans the counters)
D014 GTO D008[] []
D015 [] ISG I [] Next digit
D016 GTO D005 []
D017 CL STK Prepare to finish, Regs 1-9 have been zeroed, B is clean
D018 STO C … so clear the stack and clear C…
D019 STO I … clear I…
D020 x <> D … and get the result, clearing D at the same time!!
I enjoyed a lot with this challenge, which made me stay awaken for a couple of hours that night. I found the HP35S manual good enough to clarify things (as the usage of numbered registers and the specifics of indirect addressing in the particular model). While it is not as good reading as the manuals of the golden years (1975-1990), is rather good, and certainly better than most modern examples.
Edited: 18 Nov 2007, 8:28 a.m.
|