Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

  • Congratulations Mike Lewis on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

A puzzling code

Status
Not open for further replies.

mmerlinn

Programmer
May 20, 2005
745
US
[ ]
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.

[tt]

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

[/tt]

Note that this code ALWAYS exits thru the [tt]RETURN[/tt] in line 1010. It never exits the [tt]Z3[/tt] 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 [tt]Z0[/tt] and [tt]Z3[/tt] loops).

Variables that need to be set before calling this are:

[tt]

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$()

[/tt]

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.



mmerlinn


"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
 
A pedant (i.e. me) notes that it isn't actually a five line program; it's ... erm, allowing for the vagueries of Apple Basic ... about 30.

And it looks to me to be a
[hide]binary insertion sort[/hide]
 
Just guessing, as I don't quite understand that code, although I see some signs it could be...
[hide]quick sort[/hide]

I remember we used Apple IIe in school, although privately I already moved from VIC-20 over C-64 to Atari ST. But I could use my 6502 Assembler knowledge at school and did a game like Snakes/Munch (called it 'Mampf') for Apple IIe. The kid of my teacher liked it and I got an A+ ;-)

Bye, Olaf.
 
Thats pretty funny. I have no idea how Apple Code works (I'm only 24), but I looked at that code, and laughed. Then I tried reading the code out loud to my coworker and had an epiphany (I didn't get to the end of the first line) and My guess was what strongm said (I don't know how to do hidden)
 
Well, it's been a week. Are you going to enlighten us, mmerlinn?
 
mmerlin, can you enlighten us with some basic knowlegde of how this basic language works.

I assume
1. : as seperating commands
2. IF will execute everything after THEN until the line ends, if the condition is fulfilled.
3. the quirks with the loops are: a) They are executed even in a case like going from 1 TO 1. In conjunction with STEP -1 this leads to an endless loop (a replacement for While True...Endwhile), unless you exit in some way. b) Apple basic does not care for nesting, NEXT Variable will simply step back to FOR Variable. And this may be one of the ways out of an endless loop.

Am I correct with these assumptions?

Bye, Olaf.
 
Status
Not open for further replies.

Part and Inventory Search

Sponsor

Back
Top