Mind Sports Olympiad

Information

'99 Schedule

'99 Details

'99 Entry form

Accommodation

Book

MSO History

Games' rules

Home

Mindzine
Play Games Online
Message Boards
IQ Tests
Puzzles
Creative Thinking
Links
Chat

Search Site

To whet your appetite, here is the challenge that faced our February entrants:

February's Challenge and February's Rules

Our second programming challenge ran for seven days starting at 5pm GMT on Sunday 13th February and is outlined below:

The Challenge:

Your program will take a list of letters, and find all possible anagrams of letters found in a supplied dictionary. You can get the dictionary, composed of 26 files (one for each letter) here.

Your program must be able to accept up to 50 letters. For example, if the letters "ABN" are supplied as input, your program could find "A", "AB", "BAN" and "NAB" but not "BANANA" since only one "A" and one "N" is available. That would require that "AAABNN" be in the input letters.

Test your program on this sequence of letters: AFSGKRMEO.

This "rule" was altered during the contest:

• Old rule: If you suggest a word which does not appear in words.zip then you lose one valid word from your overall total.
• Revised rule: If you suggest a word which does not appear in words.zip, or if you fail to find a valid anagram that does appear in words.zip, your entry will be disqualified from consideration.
• Reason for change: Several entrants (and this editor) pointed out that the rules and the formula, as originally stated, would have allowed a person who found ZERO valid words to win the contest. We felt that this revised rule better reflected the original intent of the people who created this challenge. (more information at footnote one.)

Winning entries must allow us to publish the source code.

You have to write new code for the contest and can't enter any solution for the problem that you may have produced in the past, even if you were the author.

More rules, and reasons entries were disqualified, can be found at the bottom of the page. .

It took us longer than we expected, but we finally compiled all of the results. All programs which were submitted to the evaluation team were evaluated for speed and accuracy on the same system. Here are four tables outlining our results.

T S Lung, the quickest programmer, submitted his entry after only 25 minutes (see Table One for the twenty quickest programmers) T S Dimitrov submitted the shortest executable program, a mere 202 bytes (see Table Two for the twenty shortest programs) G Economou had the fastest program, which ran in just 460 milliseconds (see Table Three for the twenty fastest programs, and Editor's comment about Murphy's Law as it relates to fast programs on slow computers) Milan Stanojevic ended up with the best rating, 21.0 (see Table Four for the top thirty ratings, biography to read more about Milan, or source code to see his program, which I'm sure is very similar to some of our other entrants' programs)

----- Milan's source code -----
{
   Program is fairly simple and I belive that others came up with very
   similar solutions.
   I've first observed that there are less than 100,000 words in dictionary.
   It ment that I could just browse through dictionary. (100,000 cycles is
   not very much for today's computers). I just speed it up a bit by skipping
   dictionary files with words that start with unavailable letters.
   I read given letters from first line of 'input.txt' and write found
   valid words to 'output.txt'.
}

var
{ these arrays hold how many of each letter we have available }
   brpoj, trbrpoj: array['A'..'Z'] of integer;
   inputlen: integer; {number of available letters (not necessary different)}
   rec: string;       {current word in checking}
   fout: text;

procedure getinput;
var
   fin: text;
   st: string;
   i: integer;
begin
   assign(fin, 'input.txt');
   reset(fin);
   readln(fin, st);
   close(fin);

   inputlen := length(st);
   fillchar(brpoj, sizeof(brpoj), 0);

   for i:=1 to length(st) do          {compute number of each}
      inc(brpoj[ upcase(st[i]) ]);    {letter's occurences   }
end;

{ procedure checks if REC holds a word that can be made of given letters }
procedure probaj;
var
   i, len: integer;
   ch: char;
begin
   move(brpoj, trbrpoj, sizeof(brpoj)); {store available letters in
                                         temporary variable }
   len := length(rec);

   if len > inputlen then exit;         {not enough letters}

{ go trough the word and use one by one letter. if we don't run out of
  letters then it is a valid word }
   for i:=1 to len do
   begin
      ch := rec[i];
      dec(trbrpoj[ch]);                 {use letter}
      if trbrpoj[ch] < 0 then exit;     {ran out of letters. not a valid word}
   end;

   writeln(fout, rec);                  {found a valid word}
end;

procedure nadjireci;
var
   ch: char;
   fin: text;
begin
   assign(fout, 'output.txt');
   rewrite(fout);

{ check dictionary files exept those that contain words that start with
  anavailable letters }
   for ch:='A' to 'Z' do
      if brpoj[ch] > 0 then
      begin
         assign(fin, ch + '.WRD');
         reset(fin);
         while not eof(fin) do
         begin
            readln(fin, rec);           {read word into REC}
            probaj;                     {check REC}
         end;
         close(fin);
      end;

   close(fout);
end;

begin
   getinput;
   nadjireci;
end.

Do you think you could do better? March's contest will be bigger and better and has another $500 prize. A new set of rules for March's contest will be released in advance of the contest, which will start at 5pm GMT (noon Eastern, 9am Pacific) on Sunday, March 12.

January's contest results here.

An Outline of the February Programming Contest Rules:

The contest will set out a specific computing task. Programmers will create a program to perform this function using test data supplied by MSO. Once you have completed your program, you must run it on the test data, note the elapsed time for the program run, and enter this information on a form above. If your program appears to be a winner, you may be required to verify this on other sample data we supply.

To prevent cheating and possible later program modifications or enhancements, all entries must run the final executable version of their program though an industry standard checksum program. MSO will supply this program in both "C" language and compiled form for MS-DOS computers HERE.

Entries must be received by the time noted in the contest. Late entries will not be accepted.

After receiving all entries, judges will decide on a possible winner, then require the possible winning entries to send in the source and compiled code so that it can be verified against an internal set of inputs. Full instructions must be supplied at this point if data entry is not immediately obvious. Judges will use their best means to verify the program is as described and performs correctly. If the judges require it, the programmer must be willing to run sample test data through the program on his or her machine. Any winning entry must supply the full source code and allow MSO Worldwide to display the source code on the web site. All source code must be original, new and written by the submitting author(s).

Winners will be based on the entries which get the best score (lowest number) using this formula:

Your programming time / fastest programming time
+ Your execution time / fastest execution time
+ Your program size / smallest program size  *** 

Program size is of the object code (executable code). Only entries which calculate the right answers will be judged. Programming time is the time between when the contest is begun and the time you submit your entry.

Only one entry is allowed per programmer per contest. Each programmer can only win the cash prize once every six months, but feel free to enter and get credit anyway. Program checksum must match the submitted checksum, or your entry will be disqualified

Reasons entries were disqualified:

• Multiple entries (rules stated "Only one entry is allowed")
• Entrant did not submit 293 words with his entry
• Entrant did not e-mail executable program for verification by March 4
• Program did not find 12 words in "BANANA" when tested on official computer
• Program did not find 64,738 words during the "timing evaluation" "AABBDDEEFFGGHHIIJJKKLLMMNNOOPPRRSSTTUUVVWWXXYYZZ"
• Program would have required recompilation in order to change the input.
• Program did not run on computer used for official evaluation.
  • A few programmers used a shortcut to save execution time that is not valid on all computers, or imposed limits on their program that required recompiling to handle long output files.
  • Some programmers renamed the input files causing execution errors when their program could not find the originally named input files on our official system.
• We tried to make every effort to make sure that we were fair.
  • We did not use C in our final speed tests, because two entrants told us there was a mistake in C.WRD (there was no CR/LF after the last word in the file), and we did not want to hurt any entrants whose program might not find CZARS
  • We accepted one entry that missed DA, because he concatenated the dictionary files, causing CZARSDA to become a word. (This won't happen in future contests because we will require using the input files as supplied).
  • We tried to anticipate every method of INPUT that might be used by a programmer. We even tried to hex-edit programs that appeared to be hard-coded.
  • We did our best to run all submitted programs on our evaluation system, under Windows, under DOS, and under Linux.
  • We tried to contact entrants whose programs did not work on our computer, especially if there appeared to be a chance a program might have won in its category. Note that we do NOT plan to contact programmers during future contests.
• Changes that will be made to future rules based on problems during this contest
  • Standard INPUT methods will be required
    • command line entry
    • input during execution
    • a designated input file
  • All files to be in the same directory as the executable.
  • All programs must work with supplied files as given
    • no content changes
    • no renaming of files
    • no file concatenation
  • all programs must include all input and output time in calculation of execution times.
  • Programmers may not use aliases to bypass the one entry per programmer limit (it can cause loss of prize when names don't match, especially if you later get invited to compete in person).

(footnote one *** By the way, astute observers will notice a change in our formula from that which was posted on February 13. Due to an error in that formula, an error which several entrants pointed out to us during the Programming Chat Session, a program which found ZERO answers could have won. The judges chose to ONLY consider programs which found all 293 possible words for the next stage of the judging, and to only rank entrant programs which found 12 words in BANANA and 64,738 words in the final string. This was the original intent of the revision in the rules. The formula above is the one that was posted, and used, for the January contest.)

Editor's comment about program execution on old computers (Table Three):

When I realized that G Economou's program, written on an 11 mhz computer (possibly the slowest computer used in this competition), outperformed programs written on faster computers, I immediately thought about Murphy's Law and some of its corralaries, especially "Any program will expand to fill available memory." I mention that here because it is certainly possible that the old compilers from SMALL computers may have created more efficient programs because they didn't have all the bells and whistles of today's computers. The earliest programmers had to do everything in less memory!! Just my idea why a programmer on a very slow computer could end up in first position according to speed. I remember when I was programming in 16K of memory that I developed MANY shortcuts and tricks to fill a program with options that others said wouldn't fit. Anyone who remembers a 16K Star Trek written for the TRS-80 Model One might have seen some of those tricks ... comment added by John Knoderer.

[ Back to Top ]