 |
|
|
|
|
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.
PQRSTUVZABCDEFGHWXYIJKLMNO
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:
PQRSTUVZABCDEFGHWXYIJKLMNO
In a recent survey, 90% of programmers
rated themselves in the top 10% in ability.
The standard output file should be:
IJKLMNOPTUVWXYZABCDEFGQRSH
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
etc.
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:
{"REVIVER", "ROTATOR"}
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.
|
|
| |
|
|
