×
INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Log In

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!
  • Students Click Here

*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Students Click Here

A puzzling code

A puzzling code

A puzzling code

(OP)
 
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.

 

mmerlinn

http://mmerlinn.com

"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

 

RE: A puzzling code

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

Hidden:

binary insertion sort
  

RE: A puzzling code

Just guessing, as I don't quite understand that code, although I see some signs it could be...

Hidden:

quick sort

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+ winky smile

Bye, Olaf.

RE: A puzzling code

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)

RE: A puzzling code

Well, it's been a week. Are you going to enlighten us, mmerlinn?

RE: A puzzling code

Ah well, I guess we'll never know for sure ...

RE: A puzzling code

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.

Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Tek-Tips Forums free from inappropriate posts.
The Tek-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members! Already a Member? Login

Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close