A puzzling code
A puzzling code
Most of the puzzles in this thread ask for the code to produce a predetermined set of results. The puzzle here is the reverse - It is the code for producing the results. It is your job to figure out what the code does and the results that it produces.
For those of you with a background in BASIC, especially AppleSoft BASIC, this puzzle should be very easy for you to solve.
I want to know two things. First, what does the following code do? And, second, what is the common name for this routine? A star for the first one who solves this riddle by posting answers to BOTH questions above. Note that I want the SPECIFIC name for it, not the general name which would encompass many other similar ways of gettting the same results.
1010 FOR Z = ZI TO ZE: Z%(Z) = Z: NEXT Z: ZP%(1) = ZE: Z2 = ZI: FOR Z0 = 1 TO 1 STEP -1: FOR Z3 = Z0 TO ZE: Z = ZP%(Z0): IF Z <= Z2 THEN Z2 = ZP%(Z0) + 2: NEXT Z0: RETURN
1020 Z1 = Z2: Z% = (Z1 + Z) / 2: FOR Y = Z1 TO Z: IF S$(SR%(Z%(Y))) > S$(SR%(Z%(Z%))) THEN FOR X = 0 TO 1: X = S$(SR%(Z%(Z))) < S$(SR%(Z%(Z%))) OR Z = Y: Z = Z - 1: NEXT X: IF Z => Y THEN W = Z%(Y): Z%(Y) = Z%(Z + 1): Z%(Z + 1) = W
1030 IF Y => Z THEN Z1 = Z + (Y < Z%): Y = ZE
1040 NEXT Y: IF Z1 <> Z% THEN W = Z%(Z1): Z%(Z1) = Z%(Z%): Z%(Z%) = W
1050 Z0 = Z0 + 1: ZP%(Z0) = Z1 - 1: NEXT Z3
Note that this code ALWAYS exits thru the RETURN in line 1010. It never exits the Z3 loop anywhere else.
Also note that Apple BASIC allowed loops to be nested "incorrectly" which turns out to be one of the key reasons this code is so short (Note the Z0 and Z3 loops).
Variables that need to be set before calling this are:
S$(1) ... S$(N) String array one column wide
SR%(0) Row count of S$()
SR%(1) ... SR%(N) 1 thru N
ZI First row to use in S$()
ZE Last row to use in S$()
Now for some history about the above.
I originally found this routine about 1982 or so in Kilobaud or some other such Apple magazine. But after I typed all 250 lines of the code in, I discovered several things. First, it was SLOW. Second, it was a memory hog. And, third, it was not easy to use at all. Even with those drawbacks it was hours faster than what I had used up to that time.
So, I tinkered with it until I managed to get the original 250 lines down to a mere 3 lines. After much testing, I finally settled on the 5-line code above as the fastest way to do this job on a 1mhz Apple with 16k RAM. It was used daily for over 14 years. Occasionally I still fire up the old Apple II+ to access the old database.
This code works on a magnitude of 60 times faster than the original 250 lines I typed in. The 5-line version above works 20% faster than the 3-line version. The above code could do in one minute what the original version would do in one hour.
I still have a letter around here somewhere from Beagle Bros Software saying it is impossible for BASIC to do this job as fast as this code works. According to them, only assembly language could do this job at the speed that the 5-liner above can do it.
"We've found by experience that people who are careless and sloppy writers are usually also careless and sloppy at thinking and coding. Answering questions for careless and sloppy thinkers is not rewarding." - Eric Steven Raymond