Aug 00 Challenge
Volume Number: 16
Issue Number: 8
Column Tag: Programmer's Challenge
Programmer's Challenge
By Bob Boonstra, Westford, MA
Longest Word Sort
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, [TOKEN:12074] the text to be sorted */
long numChars, /* the length of the
text in bytes */
Boolean descending, [TOKEN:12074] 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 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 length, and then in order of occurrence.
As an example, the following two lines have the same length pattern, with each
containing two 5-letter words and one 3-letter word:
the quick foxes
early birds win
Sorted in ascending order, the second line is smaller, based on a comparison of "early
and "quick".
The text may include non-alphanumeric characters, which should ge 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.
Three Months Ago Winner
The May BigNum Math Challenge required contestants to write a collection of
numerical routines for very large integers, numbers with hundreds of digits or more,
well beyond what might fit in the memory normally allocated for an integer. The
problem required design of an internal representation for these big numbers, and
creation of routines to add, subtract, multiply, and divide them. It also required code to
raise one such number to the power of another, and code to calculate the square root of
such numbers. And it required routines to convert the internal representation back
and forth from a decimal representation. Congratulations to Ernst Munter (Kanata,
Ontario) for taking first place in the BigNum Math Challenge.
Ernst chose to represent his BigNums as a sequence of unsigned 16-bit terms, to
ensure that intermediate results fit into a 32-bit long word. The multiplication
algorithm is inspired by an algorithm from Knuth, optimized to maximize the use of
registers. The exponentiation tests were the most computationally intensive; Ernst's
solution scans the bits of the exponent, squaring the intermediate result with each
step, and optionally multiplying by the base. For conversion back to decimal, Ernst
saves some time by converting to an intermediate representation in base 10000. These
and other functions are well commented in the published code.
The second place solution by Mark Day was actually faster than the winning solution in
many of the test cases. However, Mark's solution was significantly slower in the
exponentiation test case, putting it in second place overall.
The table below lists, for each of the solutions submitted, and the cumulative execution
time in milliseconds. It also provides the code size, data size, and programming
language used for each entry. As usual, the number in parentheses after the entrant's
name is the total number of Challenge points earned in all Challenges prior to this one.
Name Time (secs) Code Size Data Size Lang
Ernst Munter (607) 1.95 49012 452 C++
Mark Day (20) 4.22 23800 162 C
Tom Saxton (158) 65.1 11700 196 C++
Willeke Rieken (88) 98.63 13044 280 C++
Steve Lobosso 749.06 41608 2813 C++
Jonny Taylor * 16216 3868 C
Top Contestants
Listed here are the Top Contestants for the Programmer's Challenge, including
everyone who has accumulated 10 or more points during the past two years. The
numbers below include points awarded over the 24 most recent contests, including
points earned by this month's entrants.
Rank Name Points
1. Munter, Ernst 245
2. Saxton, Tom 146
3. Maurer, Sebastian 78
4. Boring, Randy 52
5. Shearer, Rob 47
6. Rieken, Willeke 45
7. Heathcock, JG 23
8. Taylor, Jonathan 26
9. Brown, Pat 20
10. Downs, Andrew 12
11. Jones, Dennis 12
12. Day, Mark 10
13. Duga, Brady 10
14. Fazekas, Miklos 10
15. Hewett, Kevin 10
16. Murphy, ACC 10
17. Selengut, Jared 10
18. Strout, Joe 10
There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2)
being the first person to find a bug in a published winning solution or, (3) being the
first person to suggest a Challenge that I use. The points you can win are:
1st place ›20 points
2nd place ›10 points
3rd place ›7 points
4th place ›4 points
5th place ›2 points
finding bug ›2 points
suggesting Challenge ›2 points
Here is Ernst's winning BigNum Math solution:
Bignum.cp
Copyright © 2000
Ernst Munter
/*
"BigNum Math
Version 3.1
--
Implement a set of arithmetic function for multi-digit numbers.
The design of the big number data structure is unspecified.