|
August 2000 Programmer's Challenge
Longest Word Sort
Mail solutions to:
progchallenge@mactech.com
Due Date: 11:59pm ET, Tuesday, 1 August 2000
This month’s problem puts a twist on a well-known computing problem, the common text sort. Your Challenge is to sort a block of text into ascending or descending order. Yawn.... Except that the comparison function used to do the sort is a little unusual….
The prototype for the code you should write is:
void LongestWordSort(
char *textToSort, /* the text to be sorted */
long numChars, /* the length of the text in bytes */
Boolean descending, /* sort in descending order if true */
Boolean caseSensitive /* sort is case sensitive if true */
);
The textToSort provided to your LongestWordSort routine consists of a sequence of lines of text, each terminated by a return character (0x0D). You are to sort the lines of text in place into either ascending or descending order, based on the value of the descending flag, considering the text as either case sensitive or not case sensitive, based on the caseSensitive flag. The twist is that the primary sort criterion is the length of the words in the line, regardless of the position of the word in the line.
Words are a sequence of alphanumeric characters, separated by anything else (spaces, punctuation, etc.). A line with a longest word of N characters is considered to be "greater" than any line with a longest word of fewer characters. Among lines with longest words of the same length, the line with the larger number of words of that length is considered "greater". If two lines have the same number of longest words of the same length, the sort order is based on the length of the next-longest word, and so on. Finally, among lines with words of exactly the same length, the sort order is based on text order of the individual words, compared in order of decreasing length, and then in order of occurrence. Whether the sort is done in ascending or descending order, the determination of which line is "greater" is always based on the longest word first, then the next longest, etc.
As an example, examine the following lines:
the earliest birds
quick early birds
early over quick
the quick foxes
early birds win
These lines are correctly sorted in descending order. The first line has the longest word. The remaining lines all have a longest word of 5 letters, but the second line has more of them. The last 3 lines all have 2 words of 5 letters, but the 3rd line has a second-longest word of 4 letters. Finally, the last line is smaller than the one before it, based on a comparison of "early" and "quick".
The text may include non-alphanumeric characters, which should be ignored for purposes of comparison.
This will be a native PowerPC Challenge, using the CodeWarrior Pro 5 environment. Solutions may be coded in C, C++, or Pascal. This month, we’ll also allow solutions that are completely or partially coded in assembly language. The winner will be the solution that correctly sorts a number of blocks of text in the least amount of execution time.
This problem was suggested by Ernst Munter, who earns two Challenge points for the suggestion.
Test code for this Challenge is now available.
You can get a head start on the Challenge by reading the
Programmer's Challenge mailing list. It will be posted to the list on
or before the 12th of the preceding month. To join, send an email to
listserv@listmail.xplain.com
with the subject "subscribe challenge-A". You can also join the
discussion list by sending a message with the subject "subscribe
challenge-D".
|
Slashdot
Digg
del.icio.us
reddit
newsvine
Y! MyWeb
