MC: Alphabetize a String
The Challenge
From: joehorn@jps.net
Newsgroups: comp.sys.hp48
Subject: MC: Alphabetize a word
Another Mini-Challenge for the brilliant but bored:
Sneak preview of tonight's HP48 Programming Class assignment:
Sort the characters in a string ("A" to "Z" only) into ASCII order.
Example: "BAZAAR" --> "AAABRZ"
Winner: smallest bytes * seconds * clockspeed, as tested on a
huge string (500 to 1000 bytes) with many repeated characters.
All the usual Mini-Challenge rules apply. Happy Programming!
-Joe-
The Entries
Scroll down a few lines if you really want to see the entries
From: <patrickd@cmdnet.lu> (DOSTERT Patrick)
Subject: Re: MC: Alphabetize a word
Date: Sun, 08 Mar 1998 09:50:22 GMT
\<<
"A" +
[ 0 ] { 26 } RDM OBJ\-> DROP 27 ROLL
1 OVER SIZE 1 -
START
DUP HEAD NUM 63 - ROLL LASTARG SWAP 1 + SWAP ROLLD TAIL
NEXT
DROP
""
"A" NUM "Z" NUM
FOR I
SWAP
IF DUP
THEN
1 SWAP
I CHR 4 ROLLD
START
OVER +
NEXT
SWAP
END
DROP
NEXT
\>>
222.5 bytes, under one minute with 1024 chrs string (on gx)
From: <painvtqm@worldnet.att.net> (Robert Bellman) Subject: Re: Alphabetize a word Date: 8 Mar 1998 19:44:37 GMT Not that I expect to really compete, but here's mine: << "" DUP DUP2 4 DUPN 8 DUPN 10 DUPN 27 ROLL 1 OVER SIZE 1 SWAP START DUP2 DUP SUB DUP NUM DUP 60 - ROLL 3 ROLL + SWAP 62 - ROLLD 1 + NEXT DROP2 1 25 START SWAP + NEXT >> 160 BYTES. It takes about 42 seconds on my GX to do a 1024 character string. String may only contain A-Z, no spaces or anything else - although these could be handled with slight modifications. Now, I have to get back to my REAL homework and studying for my finance test next Thursday! :-) Yours, Robert Bellman, Jr.
From: dkw@wolferts.sub.de (Klaus Wolferts) Subject: Re: MC: Alphabetize a word Date: Sat, 07 Mar 98 23:46:15 -1 Nice challenge, here my solution: \<< 1 OVER SIZE FOR i DUP i DUP SUB SWAP NEXT SIZE \->LIST SORT OBJ\-> 2 SWAP START + NEXT \>> Checksum #71DEh, 67 bytes Not really fast ( <3 s for a 50 char string), but rather short ;-) Needs 6 bytes/char space for the growing stack, so dont try really huge strings with only little ram space left ;-) Klaus -- dkw@wolferts.sub.de | Dr.-Ing. Klaus Wolferts Tel: +49 721 706016 | Ingenieurbuero fuer EDV + Elektronik Fax: +49 721 706017_|_Mitteltorstr. 45, D-76149 Karlsruhe (Nrt)
From: <postbus@jarno.demon.nl> (Jarno Peschier)
Subject: Re: MC: Alphabetize a word
Date: Tue, 10 Mar 1998 10:10:51 GMT
[regarding the above entry]
You can simply replace the OBJ-> 2 SWAP START + NEXT with one
SigmaLIST command. This gives you # 9BB8h, 52 bytes.
Of course it depends on how exactly to interpret the challenge if this
is solution to the MC or not. If the "("A" to "Z" only)" part was
meant as "the input string only contains A to Z" or "the program
should only take the characters A to Z from the input string and sort
those". (I'm really not sure yet, though I suspect the former which
means your short solution is a valid solution.)
Jarno Peschier, who has recently changed his email address!
mailto:postbus@jarno.demon.nl http://jarno.home.ml.org/
From: <wndalouise@aol.com> (WndaLouise)
Subject: Re: Alphabetize a word
Date: 8 Mar 1998 22:10:06 GMT
slightly shorter, much much slower...
<< { } 1 3 PICK SIZE
FOR $ OVER $ $
SUB +
NEXT SORT OBJ-> 2
START + -1
STEP SWAP DROP
>>
it took nearly 40 minutes !!! for a 1000 character string...
From: <dlr@mediaone.net> (Douglas L. Rohm)
Subject: Re: Alphabetize a word
Date: Sun, 8 Mar 1998 22:25:26 -0500
Here goes nothing. I know this isn't the fastest, but it was my first go at
it.
<<
DUP SIZE 2 SWAP FOR i DUP HEAD SWAP TAIL
NEXT DEPTH ->LIST SORT ZLIST
>>
* ZLIST = List Sum Command. MTH LIST menu. Page 3-170 in Advanced Users
Reference Manual and page G-24 in the Users Manual.
68.0 bytes. Checksum is #DA50h. Program took 1261569.41 ticks and
154.00_secs for a 1024 character string on a GX. Two and a half minutes
ain't too bad. I used TIM from the Hack Library to time this. This is my
first time doing the Mini-Challenge, hope I did ok.
Douglas L. Rohm
dlr@mediaone.net
From: <postbus@jarno.demon.nl> (Jarno Peschier) Subject: Re: Alphabetize a word Date: Tue, 10 Mar 1998 12:57:07 GMT [regarding the above entry] You don't seem to use the loop variable i anywhere, so why not replace the "FOR i" with "START" and save the space and time of that explicit loop variable? Jarno Peschier, who has recently changed his email address! mailto:postbus@jarno.demon.nl http://jarno.home.ml.org/
From: <wndalouise@aol.com> (WndaLouise)
Subject: Re: Alphabetize a word
Date: 9 Mar 1998 06:29:18 GMT
Asort
Alaphabetical Sorter
Sorts a list of 1000 target characters in about 72 seconds.
265 * 72 * 3.754976 = 71644.94208
Asort deviates from the pure assignment in that it checks for both capital and
lowercase target letters, and satanic non-target characters as well, which it
sticks on the end of the returned string.
input:
1: "string of characters"
output:
1: "semi-alphabetized string of characters"
1: "BpmacJA.2aNx-gH"
Asort
1: "aAaBcgHJmNpx.2-"
Asort
# F146h
265 bytes
%%HP: T(3)A(D)F(.);
\<< 1 27
START ""
NEXT
"AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz"
29 ROLL 1 OVER SIZE
START DUP2 HEAD
SWAP OVER POS 2 /
DUP
\<< 4 + DUP ROLL
ROT + SWAP 2 -
ROLLD
\>>
\<< DROP 30 ROLL
SWAP + 29 ROLLD
\>> IFTE TAIL
NEXT DROP2 1 26
START SWAP +
NEXT
\>>
From: <danli97@ite.mh.se> (Daniel Lidstrom) Subject: Re: MC: Alphabetize a word Date: Tue, 10 Mar 1998 03:25:14 -0600 Here is my best attempt: << "" DUP 1 12 START DUP2 NEXT 27 ROLL 1 OVER SIZE START DUP HEAD DUP NUM 61 - DUP ROLL ROT + SWAP 2 - ROLLD TAIL NEXT DROP 26 ->LIST << SWAP + >> STREAM >> Size: 153.5 checksum: # 4676h Time:52.7 (3.92) => bytes*time*speed = 31727 The string was created by this sequence: 1000 "" 1 ROT START RAND 26 * CEIL 64 + 0 RND CHR + NEXT Daniel Lidstrom, danli97@ite.mh.se http://www.ite.mh.se/~danli97/
From: <jhmeyers@miu.edu> (John H Meyers)
Subject: Re: MC: Alphabetize a word
Date: 11 Mar 1998 06:31:49 GMT
Here is a method along lines suggested before, but using an
array of reals to keep character counts, rather than actually
keeping the characters themselves; by using 256 reals,
we can in fact sort the characters of an arbitrary string,
which is what I have actually done and timed here.
In "real life," one is often interested in character frequencies,
but I haven't yet seen a practical application for
keeping the string of re-arranged characters :)
As to comparing timings, everyone may have different amounts
of free memory, different card slots filled, and perhaps even
differently skewed "random" character strings, so the basis
for comparisons is not very exact, even if CPU speed is
already factored in (I didn't bother here).
Stack contents for first part (counting characters):
"string" [ counters ]
Stack contents for second part (building result string):
[ counters ] "result string" (outer FOR loop)
[ counters ] "current character" "result string" (inner START loop)
%%HP: T(3);
\<< 2 8 ^ 1 \->LIST 0 CON OVER SIZE 1 SWAP FOR n
OVER n DUP SUB NUM 1 + DUP2 GET 1 + PUT NEXT
@ Character-counting is done above; building output string below:
"" 1 2 8 ^ FOR n OVER n GET DUP
{ n 1 - CHR ROT ROT 1 SWAP START OVER + NEXT SWAP DROP }
{ DROP } IFTE NEXT ROT ROT DROP2 \>>
@ 180 bytes
@ 1000 random characters (from 256-char set)
@ 85K free memory at execution time, 85 seconds on GX with 2 cards.
This is a bit wasteful for sorting the letters of a short word of
capital letters only, since it goes through all 256 possible output
characters (taking 4.8 seconds on a word of one character only),
but it does of course get more efficient on longer random strings.
There is probably room for optimizing this a bit more,
but I've already used up my recreation time for the day :)
-----------------------------------------------------------
With best wishes from: John H Meyers <jhmeyers@mum.edu>
Final Thoughts
From: joehorn@jps.net
Subject: Re: Alphabetize a word
This mini-challenge turned out to be lots of fun!
But only two differing methodologies have been posted so far:
(a) Convert the string into a list of characters (or ASCII values),
then SORT the list, then convert the list back into a single string.
(b) Use one level of the stack to accumulate all the A's, another
level to accumulate the B's, and so on, until the string is all
used up, then concatenate the 26 stack levels into a single
string. This is the faster method, because it avoids the SORT
command which is very slow on large lists.
Here's a third method that is kind of crazy but it's faster than
method (a)!
(c) Convert the string into an *array* of ASCII codes, then store it
into SigmaDAT, and let the BINS command tally the frequency of each
letter! Unfortunately, BINS is no speed demon either.
For those of you who can read RPL, here's a working incarnation:
<< DUP SIZE -> s
<< 1 s
START DUP NUM SWAP TAIL
NEXT DROP s 1 2 ->LIST ->ARRY STOSigma
>> 65 1 26 BINS DROP "" 1 26
FOR j
IF OVER j GET
THEN 1 3 PICK j GET
START j 64 + CHR +
NEXT
END
NEXT SWAP DROP CLSigma 'SigmaPAR' PURGE
>>
BYTES: #2FC0h 214.0
Runtime on random 1000-char string: about 1.5 minutes.
Some other methodologies come to mind:
(d) Build the final output one character at a time, inserting
each new character into place using a binary search.
(e) Make 26 passes through the string, counting how many A's there
are, then how many B's, and so on.
(f) Sort the string "in place" by swapping characters. Any sorting
method could be used.
(g) Screw RPL and do it in assembly language, like God intended.
-Joe-
joehorn@jps.net
The Winner
From: joehorn@jps.net Subject: Re: Alphabetize a word Date: 10 Mar 1998 10:57:29 GMT Robert Bellman's program is the current winner for size * speed. The best program that came out of the HP48 Programming Class was similar to Robert's, but it was slowed down by using HEAD and TAIL (instead of SUB, which is faster). Way to go, Robert! -Joe- joehorn@jps.net