Home What Is Euphoria? Documentation News EUforum Download Euphoria Donate
Recent User Contributions The Archive Other Euphoria Web Sites RDS Development Related Books & Software
Programming Contest

$100 In Prize Money!
March 1, 2002: Rapid Deployment Software announces the first ever Official Euphoria Programming Contest. Thanks to an anonymous donor, prizes totalling $100 U.S. in Euphoria Micro-Economy money will be awarded to the winners. To ensure that programmers at all levels of experience have a chance to win something, there are actually three separate contests, each with a different prize. The easy contest has a prize of $20. The medium-level contest has a prize of $30, and the hard contest has a prize of $50. In addition, the winner of each contest will get a $5 bonus if his/her program runs correctly on all platforms (WIN32, DOS32, Linux) without requiring any changes. Contestants may only enter one of the three contests below. Note: The contest ended April 1, 2002.

Contest #1 (Easy $20)
Write a program in Euphoria that reads from standard input (file number 0) a "cipher" line containing the 26 letters of the alphabet, rearranged somehow, e.g.

This tells your program to convert all 'A's to 'P', all 'B's to 'Q', all C's to 'R' etc., as well as all 'a's to 'p' etc.

Write out the inverse mapping cipher line to standard output (file number 1). Then read the following lines of English text from standard input, convert the letters according to the cipher, and write them to standard output.

As a test, you should be able to read your output and get back the original file with the original cipher-line at the top.

Note: You must preserve upper/lower case in the English text.

For example, if the standard input file is:

In a recent survey, 90% of programmers
rated themselves in the top 10% in ability.

The standard output file should be:

Af p xtrtfi yjxktn, 90% gu hxgvxpeetxy
xpits izteytdkty af izt igh 10% af pqadain.

Note: you can assume that a proper cipher line, consisting of 26 upper-case letters, without duplicates, will be present as the first line of input. Subsequent lines will contain plain English text, with no strange characters and no lines longer than 1000 characters.

Also, count the number of occurrences of each letter in the input file. Write to a file called "letters.txt" a list of the 26 letters and their counts, sorted with the most frequent letter listed first, e.g.
E 63
T 52

The count for (say) E should be the sum of the number of E's and the number of e's.

It should be possible to run your program with a command-line like:

ex yourprog.ex < clear.txt > coded.txt

With letters.txt being produced as well. Instead of ex (DOS), you could also use exu (Linux). (On some versions of Windows, this type of command-line will also work with exw. On other versions, it won't - so just use ex.)

By processing some large files of English text, you can get letter-frequency statistics that might be of some help in deciphering English text (hard problem below). For example, in English, the most common letter is typically 'E'.

Correctness, then speed decides the winner.

Contest #2 (Medium $30)
Read in a list of 51,795 English words and organize it somehow in memory. You must use words.txt contained in Junko's spell checker in the Archive. In Junko's dictionary, the words are in alphabetical order, one per line, and are all in upper case.

Write a library routine that will return all words in the dictionary that match a given pattern. For example, given {1,2,3,4,3,2,1} as the argument to your function, you'd return a sequence of all 7-letter words with that pattern, i.e. first and last characters are the same, second and second last are the same etc. In this case the answer is:

The user can also specify certain specific letters, e.g. {'T', 1, 2, 1, 3, 'G'} would get all 6-letter words beginning with 'T' and ending with 'G', where the 2nd and 4th letters are the same, but otherwise the letters are all different from each other. {"TIEING", "TILING", "TIMING", "TIRING"} Note in this case that 1, 2 and 3 represent three distinct and different characters, none of which is 'T' or 'G', and none of which is the same as one of the others.

Assume that the numbers 0 to 32 are used to indicate the pattern, while the numbers above 32 are the ASCII codes of literal characters to be matched (including apostrophe and hyphen). You may assume that literal characters will be in upper-case. Do not assume that the pattern numbers will start at 0 or 1, or that they will be consecutive.

Your routine will be a global function in an include file. Somewhere in the include file you must read the list of words. You could do this using top level code that's executed when the file is included, or perhaps your library routine can read in the list of words the first time it is called.

Correctness, and then speed decides the winner. Your program's total time will include the time to read Junko's file, plus the time to process 1000 different calls to your pattern-matching subroutine. The test set will be created using random numbers, but everyone will be given the same set.

Contest #3 (Hard $50)
Write a program that tries to decipher a text file that has been encoded using a simple one to one cipher where each letter of the alphabet A-Z and a-z has been replaced by a different letter, but blanks, tabs and punctuation characters have been left alone.

For example, your program would try to convert:

Af p xtrtfi yjxktn, 90% gu hxgvxpeetxy xpits izteytdkty af izt igh 10% af pqadain.

back to the original:

In a recent survey, 90% of programmers rated themselves in the top 10% in ability.

It's desirable, but not required, to preserve upper/lower case.

Programs will be tested using English text inputs ranging from 1 to 5 sentences. A small percentage of words might contain hyphens or apostrophes, and a small percentage might not be in Junko's dictionary. For this problem, you can modify or replace Junko's dictionary with something else if you wish (but it probably won't help much).

Use statistically-known frequencies of letters and words in English. Check letter-patterns against an English dictionary, or any other algorithm you can think of, to decipher the input text. Your program might measure its progress by the number of deciphered words that can be found in the dictionary.

Your goal is to get as many words correct as possible, on the sample English files that RDS will test with. Your score will be the sum of the percentage of words correct on each test, divided by the number of tests. Thus each test carries equal weight, regardless of its word count. There's a 5 minute maximum on execution time for one test (on a Pentium 350 Mhz).

In one test, all of the words will be in Junko's dictionary. In another test, one or more words will not be in Junko's dictionary. The remaining tests are yet to be decided, but at least 90% of the words will be in her dictionary.

There are several heuristic (ad-hoc) methods that might help. e.g. looking for the one-letter words, 'I' or 'a', common words like "the" etc. You can probably win this contest armed with Junko's dictionary, plus a very basic knowledge of English.

Some Rules:
  • Submitted programs will be tested using the Euphoria 2.3 interpreter, on a 350 MHz Pentium machine with 64 Mb RAM. This is enough RAM to store Junko's entire dictionary in memory, unless you do something that's extremely space-inefficient.
  • The use of machine code routines, or external programs coded in some language other than Euphoria, is not permitted.
  • By submitting a program, you agree that we (RDS) may post that program on our Web site. Anyone will be allowed to use your program for any purpose, as long as they acknowledge you as being the author.
  • You may discuss the contest rules, and the algorithms that might be useful, on the Euphoria mailing list, but do not post code to solve any of the problems. Send your program to rds@RapidEuphoria.com, preferably as a zipped file, to avoid line-wrap and tab problems.
  • The contest closes on April 1, 2002 at 12:00 noon Eastern time. Submissions after that time will not be considered.
  • Additional rules and clarifications may be added at any time up until the closing date.
  • The decision of RDS is final. Attempts to break the letter or spirit of the rules, could result in disqualification or cancellation of any MicroEconomy money awarded.

This site is maintained by Robert Craig and Junko C. Miura of Rapid Deployment Software