home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1998 / MacHack 1998.toast / Programming Contest / Secret Solutions Folder / Problem 01 - Mode Sort / Solution.p < prev   
Encoding:
Text File  |  1998-06-11  |  3.0 KB  |  111 lines  |  [TEXT/CWIE]
  1. (*
  2. Problem 01 - Mode Sort
  3.  
  4. This problem is to sort an input string of N characters, N<1000000, based on the number of times a character occurs in the input.  The most frequently occurring character should be sorted to the front of the string, followed by the next most frequently occurring character, etc.  For characters occurring the same number of times, the character that occurs first in the input should be sorted to the front.
  5.  
  6. Header specification
  7.  
  8. pascal OSErr ModeSort( const FSSpec* infile, const FSSpec* outfile );
  9.  
  10. Input specification
  11.  
  12. The infile input file contains the characters.  Input characters other than those printable low ascii characters c, 0x20<c<0x7f, must be ignored.
  13.  
  14. Output specification
  15.  
  16. The outfile must be created and then filled with the sorted characters.  It's final length should be exactly the same as the count of characters in the allowed range (0x20<c<0x7f) (which may be shorter than the infile file length).
  17.  
  18. Sample input
  19.  
  20. abcdefghabbcccdddeee
  21. or
  22. 012345678911234567892123456789312345678941234567895123456789612345678971234567891
  23.  
  24. Sample output
  25.  
  26. ccccddddeeeebbbaafgh
  27. or
  28. 111111111122222222233333333344444444455555555566666666677777777788888888999999990
  29. *)
  30.  
  31. unit Solution;
  32.  
  33. interface
  34.  
  35. // Do not modify the interface
  36.  
  37.     uses
  38.         Types, Files;
  39.         
  40.     function ModeSort( const infile, outfile: FSSpec ): OSErr;
  41.  
  42. implementation
  43.  
  44. // Fill in your solution and then submit this folder
  45.  
  46. // Team Name: Example Solution
  47. // 9 minutes
  48.  
  49.     function ProblemFileRead( const infile: FSSpec; var data: Handle ): OSErr; external;
  50.     function ProblemFileWrite( const outfile: FSSpec; data: Handle ): OSErr; external;
  51.  
  52.     function ModeSort( const infile, outfile: FSSpec ): OSErr;
  53.         var
  54.             err: OSErr;
  55.             data: Handle;
  56.             counts: array[0..255] of longint;
  57.             firstpos: array[0..255] of longint;
  58.             i, len: longint;
  59.             what, best: integer;
  60.     begin
  61.         err := ProblemFileRead( infile, data );
  62.         if err = noErr then begin
  63.             for i := 0 to 255 do begin
  64.                 counts[i] := 0;
  65.                 firstpos[i] := 0;
  66.             end;
  67.             for i := 0 to GetHandleSize( data ) - 1 do begin
  68.                 what := band(Ptr(longint(data^)+i)^, $00FF);
  69.                 if (32 < what) & (what < 127) then begin
  70.                     if counts[what] = 0 then begin
  71.                         firstpos[what] := i;
  72.                     end;
  73.                     Inc(counts[what]);
  74.                 end;
  75.             end;
  76.             len := 0;
  77.             while true do begin
  78.                 best := -1;
  79.                 for what := 0 to 255 do begin
  80.                     if counts[what] > 0 then begin
  81.                         if best = -1 then begin
  82.                             best := what;
  83.                         end else begin
  84.                             if counts[what] > counts[best] then begin
  85.                                 best := what;
  86.                             end else if (counts[what] = counts[best]) & (firstpos[what] < firstpos[best]) then begin
  87.                                 best := what;
  88.                             end;
  89.                         end;
  90.                     end;
  91.                 end;
  92.                 if best = -1 then begin
  93.                     leave;
  94.                 end;
  95.                 i := counts[best];
  96.                 counts[best] := 0;
  97.                 while i > 0 do begin
  98.                     Ptr(longint(data^)+len)^ := best;
  99.                     Inc(len);
  100.                     Dec(i);
  101.                 end;
  102.             end;
  103.             SetHandleSize( data, len );
  104.             err := ProblemFileWrite( outfile, data );
  105.             DisposeHandle( data );
  106.         end;
  107.         ModeSort := err;
  108.     end;
  109.     
  110. end.
  111.