The string can contain, in any order, any of the characters in the set of ten digits and twenty-six upper case letters:

{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z}

Your program will generate every possible anagram of the input string, printing them to the file "output.txt" in the default directory, grouping the output by length from 1 up to the positive integer specified, and sorting each group in reverse alphabetical order (Z to A then 9 to 0). Anagrams need not be words, though some of them will be. As you can see below, most of the anagrams found in the example are not words.

Use commas to separate the anagrams in each group. Each group should appear on its own "line."

The standard "end of line" character that your operating system uses should come after every "line". If you have a choice, or if you are manually coding the end of line character, we prefer that you use Carriage Return, with or without the Line Feed. See "rule 9" for more discussion about this paragraph. If you use your compiler's standard commands for output, we should be able to read your output file.

For example, if the two inputs were:

DAD1
3

Your "output.txt" file should look like this:

D,A,1
DD,DA,D1,AD,A1,1D,1A
DDA,DD1,DAD,DA1,D1D,D1A,ADD,AD1,A1D,1DD,1DA,1AD

and your screen should display the number 22 (in an optional sentence of your choice):

22

Your program's logic should be able to handle any valid input, any string up to 40 characters in length, and any integer from 1 up to 40. However, we will not test any combination of string and number that will create an output file longer than two megabytes. You may, if you wish, write your program to handle any characters, but we will only test with strings as defined above.

We will run selected programs on a final set of input values, values which should result in an output file of less than two megabytes. When rating programs on that final test, entries will be disqualified:

1. if the output file is over two megabytes in size,
2. if the program takes longer than one hour (60 minutes) to execute, or
3. if each "line" or "group" of output file is not in reverse alphabetical order (Z-A then 9-0)

What are anagrams?

Webster's Dictionary defines "anagram" as:

• an*a*gram [1] (noun)
• [probably from Middle French anagramme, from New Latin anagrammat-, anagramma, modification of Greek anagrammatismos, from anagrammatizein to transpose letters, from ana- + grammat-, gramma letter -- more at GRAM]
• First appeared 1589
• 1 : a word or phrase made by transposing the letters of another word or phrase
• 2 plural but singular in construction : a game in which words are formed by rearranging the letters of other words or by arranging letters taken (as from a stock of cards or blocks) at random

More information about the April challenge is below, but we'll take a break here to look at the April results.

Our official test was performed on this input:

     ABCDDEEEFFFGGGHHHHIIIIJJJJKKKKLLLLMMMM
     5

Table One: Final Rankings by total points
Final Standings							ranked by total points
Rank	Minutes	Points1	Source	Points2	ExeTim	Points3	Tpoints	E-mail
1	149	3.31	642	1.32	0.064	1.00	5.629	grg22(at)ai.mit.edu
2	107	2.38	1068	2.19	0.212	3.31	7.883	im14u2c(at)primenet.com
3	301	6.69	662	1.36	0.146	2.28	10.329	s9805027(at)student.up.ac.za
4	111	2.47	717	1.47	0.868	13.56	17.501	Zdravko.Nezic(at)ieee.org
5	207	4.60	524	1.08	0.817	12.77	18.442	fluff(at)geocities.com
6	87	1.93	663	1.36	0.986	15.41	18.701	rudisin(at)srobarka.sk
7	434	9.64	973	2.00	0.549	8.58	20.221	adams(at)kp.km.ua
8	45	1.00	1429	2.93	1.083	16.92	20.856	chiniforooshan(at)yahoo.com
9	77	1.71	1388	2.85	1.044	16.31	20.874	marioziv(at)public.srce.hr
10	114	2.53	1072	2.20	1.040	16.25	20.985	wsx(at)svsbb.sk
11	66	1.47	1192	2.45	1.370	21.41	25.321	vitap(at)lux.lt
12	136	3.02	1230	2.53	1.320	20.63	26.173	konsept48(at)hotmail.com
13	66	1.47	698	1.43	1.536	24.00	26.900	slovenac(at)ptt.yu
14	166	3.69	1033	2.12	1.374	21.47	27.279	achiko(at)gemaco.kheta.ge
15	158	3.51	2633	5.41	1.203	18.80	27.715	virag(at)para.chem.elte.hu
16	165	3.67	885	1.82	1.426	22.28	27.765	marian(at)step.sk
17	372	8.27	735	1.51	1.705	26.64	36.417	jvandyk(at)worldmail.nl
18	964	21.42	1089	2.24	1.227	19.17	42.830	martins(at)cclu.lv
19	1472	32.71	781	1.60	1.045	16.33	50.643	heribo(at)ghost.matcom.uh.cu
20	1173	26.07	611	1.25	1.765	27.58	54.899	w.van.der.vegt(at)windesheim.nl
21	553	12.29	1393	2.86	2.577	40.27	55.415	msmammel(at)starpower.net
22	66	1.47	1158	2.38	3.624	56.63	60.469	nixm(at)cent.co.yu
23	1350	30.00	1392	2.86	1.921	30.02	62.874	kcwong(at)school.net.hk
24	2000	44.44	1313	2.70	1.050	16.41	63.547	spymorg(at)hotmail.com
25	2380	52.89	487	1.00	0.825	12.89	66.780	dminn(at)cc.gatech.edu
26	1735	38.56	1595	3.28	2.481	38.77	80.596	alfaunits(at)ptt.yu
27	2368	52.62	2486	5.10	1.811	28.30	86.024	rogertcp(at)singnet.com.sg
28	3968	88.18	629	1.29	0.870	13.59	103.063	vbresan(at)jagor.srce.hr
29	3373	74.96	1116	2.29	2.193	34.27	111.513	mark.engelberg(at)bigfoot.com
30	2272	50.49	1003	2.06	5.044	78.81	131.361	unam(at)club-internet.fr
31	5157	114.60	1333	2.74	0.958	14.97	132.306	bfennema(at)ix.netcom.com
32	218	4.84	1220	2.51	8.478	132.47	139.818	pdbaylie(at)eos.ncsu.edu
33	5908	131.29	1667	3.42	0.932	14.56	149.274	pnic(at)alfaunits.co.yu
34	6153	136.73	1211	2.49	1.283	20.05	159.267	hyatt(at)cs.utk.edu
35	1557	34.60	1158	2.38	14.171	221.42	258.400	kurtvdb(at)village.uunet.be
36	5711	126.91	1434	2.94	47.021	734.70	864.559	malaschitz(at)seznam.cz

Now, you know the standings, let's look at some of the details.

Table Two - Fastest Executables (third-stage only)
Rank	Exec Time	Entrant
1	0.064	grg22(at)ai.mit.edu
2	0.146	s9805027(at)student.up.ac.za
3	0.212	im14u2c(at)primenet.com
4	0.549	adams(at)kp.km.ua
5	0.817	fluff(at)geocities.com
6	0.825	dminn(at)cc.gatech.edu
7	0.868	Zdravko.Nezic(at)ieee.org
8	0.870	vbresan(at)jagor.srce.hr
9	0.932	pnic(at)alfaunits.co.yu
10	0.958	bfennema(at)ix.netcom.com
11	0.986	rudisin(at)srobarka.sk
12	1.040	wsx(at)svsbb.sk
13	1.044	marioziv(at)public.srce.hr
14	1.045	heribo(at)ghost.matcom.uh.cu
15	1.050	spymorg(at)hotmail.com
16	1.083	chiniforooshan(at)yahoo.com
17	1.203	virag(at)para.chem.elte.hu
18	1.227	martins(at)cclu.lv
19	1.283	hyatt(at)cs.utk.edu
20	1.320	konsept48(at)hotmail.com

Table Three: The twenty shortest programs
Rank	Bytes	Entrant
1	487	dminn(at)cc.gatech.edu
2	524	fluff(at)geocities.com
3	611	w.van.der.vegt(at)windesheim.nl
4	629	vbresan(at)jagor.srce.hr
5	642	grg22(at)ai.mit.edu
6	643	siulung(at)163.net
7	662	s9805027(at)student.up.ac.za
8	663	rudisin(at)srobarka.sk
9	664	j-waldby(at)home.com
10	687	larrybar(at)eng.auburn.edu
11	698	slovenac(at)ptt.yu
12	717	Zdravko.Nezic(at)ieee.org
13	719	ibakos(at)vivcomp.hu
14	735	jvandyk(at)worldmail.nl
15	781	heribo(at)ghost.matcom.uh.cu
16	809	eljakim(at)acm.org
17	814	jfrench(at)chumbo.com
18	885	marian(at)step.sk
19	912	siamakt(at)hotmail.com
20	973	adams(at)kp.km.ua

"Table Four: Quickest Programmers
Rank	Minutes	Entrant
1	45	chiniforooshan(at)yahoo.com
2	64	omilani(at)hotmail.com
3	66	vitap(at)lux.lt
3	66	slovenac(at)ptt.yu
3	66	nixm(at)cent.co.yu
6	77	marioziv(at)public.srce.hr
7	84	marsavic(at)eunet.yu
8	87	rudisin(at)srobarka.sk
9	105	siulung(at)163.net
10	107	im14u2c(at)primenet.com
11	111	Zdravko.Nezic(at)ieee.org
12	114	wsx(at)svsbb.sk
13	115	siamakt(at)hotmail.com
14	125	stephenk(at)cc.gatech.edu
15	136	konsept48(at)hotmail.com
16	145	atai(at)glink.net.hk
17	149	grg22(at)ai.mit.edu
18	158	virag(at)para.chem.elte.hu
19	165	marian(at)step.sk
19	165	vasilich(at)kp.km.ua

Some entries did not make it to the second or third stages of judging for various reasons:

Eliminated during second stage (no particular order):

• siulung: Program execution exceeded 15 minutes
• siamakt: Program execution exceeded 15 minutes
• pat7787: Program execution exceeded 15 minutes
• jfrench: PERL program not evaluated by agreement with entrant
  (if I had allowed the above four programs to finish execution, they would have been in the 37th to 40th places, order unknown)
• vasilich: required file "RTM.EXE" not found"
• liurujia: required file "RTM.EXE" not found"
• larrybar: final output file 819200 bytes
• j-waldby: final output file zero bytes
• manabu: file creation error during execution
• filliatr: uncaught exception failure "int_of_string"

• omilani: entry form listed number of answers as "many"
• ibakos: entry form listed number of answers as "1"
• marsavic: submitted output file was not sorted
• atai: submitted data file had errors
• photonx: submitted output file not in specified format
• stephenk: submitted output file in lower case
• eljakim: submitted output file in lower case
• brenton: submitted output file in lower case
• aguzlo: submitted output file in lower case

And, here is the entire set of results, for those of you who want to calculate various numbers or do various comparisons. (Only programs which survived the third stage have executable times listed. Everyone else is welcome to estimate their times).

How to estimate your program's execution time:

• Test your program on this input data:
  
          ABCDDEEEFFFGGGHHHHIIIIJJJJKKKKLLLLMMMM
          5
   
• Time how long it takes to generate your answers, including all execution time.
• Your output file should be approximately 2,023,849 bytes in length, depending on your operating system.
• We timed everything done by all programs, including program load and unload time, with approximately this sequence of instructions:
  
          start > timing.txt
          EntrantProgram
          stop >> timing.txt
   
• Multiply your execution time by the speed of your processor, then divide by 450 (because we ran all official tests on a 450 mhz system).
  
  For example, if your program runs in 30 seconds on your 150 mhz system, you would calculate
      30 * 150 / 450 = 10
  which would let you guess that it would have run in 10 seconds on my system.
   
• This month, we ran each entrant program five times, and used the smallest of the five timings as the official timing. This detail varies from month to month.

45	487	0.064
quickest	shortest	fastest
Minutes	Source	ExeTim	E-mail
166	1033	1.374	achiko
434	973	0.549	adams
5306	1935		aguzlo
1735	1595	2.481	alfaunits
145	1923		atai
5157	1333	0.958	bfennema
1220	1646		brenton
45	1429	1.083	chiniforooshan
2380	487	0.825	dminn
377	809		eljakim
1517	1259		filliatr
207	524	0.817	fluff
149	642	0.064	grg22
1472	781	1.045	heribo
6153	1211	1.283	hyatt
5655	719		ibakos
107	1068	0.212	im14u2c
5951	814		jfrench
372	735	1.705	jvandyk
308	664		j-waldby
1350	1392	1.921	kcwong
136	1230	1.320	konsept48
1557	1158	14.171	kurtvdb
203	687		larrybar
180	2181		liurujia
5711	1434	47.021	malaschitz
891	2376		manabu
165	885	1.426	marian
77	1388	1.044	marioziv
3373	1116	2.193	mark.engelberg
84	1072		marsavic
964	1089	1.227	martins
553	1393	2.577	msmammel
66	1158	3.624	nixm
64	1192		omilani
5748	1131		pat7787
218	1220	8.478	pdbaylie
5429	4015		photonx
5908	1667	0.932	pnic
2368	2486	1.811	rogertcp
87	663	0.986	rudisin
301	662	0.146	s9805027
115	912		siamakt
105	643		siulung
66	698	1.536	slovenac
2000	1313	1.050	spymorg
125	2744		stephenk
2272	1003	5.044	unam
165	1284		vasilich
3968	629	0.870	vbresan
158	2633	1.203	virag
66	1192	1.370	vitap
1173	611	1.765	w.van.der.vegt
114	1072	1.040	wsx
111	717	0.868	Zdravko.Nezic

Here's what Greg had to say when he sent in his prettified source code:

Sorry for the delay. The more presentable version of the source is below; but that's actally very close to what I coded up in the contest. I added 3 or 4 block comments explaining what's going on and commented about a half dozen extra lines of code. I tend to code with plenty of comments; the rest of them were already there (though I did make them more readable by changing 4-word explanations to 8-word explanations).

Since part of the scoring is code length, I then took this source and stripped it down to bare essentials and crammed it into as unreadable a form as I could manage before submitting.

--grg

---------------------------------------------------------------------------

//
// Contest entry for April 2000 Mind Sports Olympiad Programming Contest
// see http://msoworld.com/programming/contest4.html
// by Greg Galperin
//
// Generate all unique permutations of a provided multiset of characters.
// 
// For efficiency:
// * buffer our own output: saves I/O overhead
// * compute a "histogram" (frequency count) of each character: allows us to
//   generate each unique permutation exactly once, eliminating duplicated
//   effort
// * pack the histogram -- remove all entries with zero count: saves
//   overhead of scanning through a list of lots of zeros
// * reverse sort the characters, so we generate items in the correct
//   (reverse alphabetic) order: eliminates need for post-processing
// * modify data structures in place: eliminate overhead of copying structs.
//

#include 
#include 
#include 
#include 

///////////////////////////////////////////////////////////////////////////
//				     Utils
///////////////////////////////////////////////////////////////////////////

// While we input and output characters, we convert these to simple indices for
// use in the processing.  The indices are in the range [0..35], with 0..9
// representing '0'..'9' and 10..35 representing 'A'..'Z'

int c2i(char c)			// char to index
{
    if (c <= '9')
	return c - '0';
    return c - ('A' - 10);
}

int i2c(int i)			// index to char
{
    if (i <= 9) 
	return i + '0';
    return i + ('A' - 10);
}


///////////////////////////////////////////////////////////////////////////
//				     Data
///////////////////////////////////////////////////////////////////////////

int curLen;			// current length we're generating

// "sparse" histogram: histogram[i] tells how many of character i2c(i) we have
// to work with.  (Note this is initialized to 0 by the compiler.)
int histogram[36];		// histogram; 0-9 then A-Z

// packed histogram: elements [0..hn-1] of the arrays contain the actual
// characters and their counts for only those characters with nonzero counts.
char hchar[36];			// packed histogram chars
int hcount[36];			// packed histogram counts
int hn;				// number of entries in packed histogram

// expose the "stack" of the recursion which contains the current "word"
char stack[40];			// chars in current recursion stack

// output buffer and accounting
char out[2000010];		// output string
int nout;			// length of output string
int tot;			// total # of solns found


///////////////////////////////////////////////////////////////////////////

// Build a "word" recursively by trying to append at each step every unique
// character we have remaining.

void dive(int currDepth)	// currDepth=0 means one letter left.
{
    // base case for recursion: we have a complete "word," so output it.
    if (currDepth<0) {
	// append this "word" to the end of the output buffer
	// (the "word" is built of the characters on the stack)
	for (int i=curLen-1; i>=0; --i)
	    out[nout++] = stack[i];
	out[nout++] = ',';	// always add a comma; remove last one later.
	assert(nout<2000000);
	++tot;
	return;
    }

    // try every possible character in this next position (here's the meat:)
    for (int i=0; i=1 && size<=40);
    result = fclose(fyl);
    assert(!result);


    ////
    //// CREATE PACKED HISTOGRAM
    ////

    // count characters to make "sparse" histogram
    int l=strlen(s);
    for (int i=0; i=0; --i) {
	if (histogram[i]) {
	    hcount[hn] = histogram[i];
	    hchar[hn++] = i2c(i);
	}
    }


    ////
    //// SET UP OUTPUT
    ////
    fyl=fopen("output.txt","w");
    assert(fyl);


    ////
    //// COMPUTE PERMUTATIONS AND OUTPUT
    ////
    for (curLen=1; curLen<=size; ++curLen) {
	// init and start the recursive enumeration
	nout=0;
	dive(curLen-1);

	// strip off trailing comma and write our buffer to the file
	out[--nout]=0;
	fprintf(fyl,"%s\n",out); // would have been faster if I'd used fwrite()
    }

    // display on the screen the total number of permutations found.
    printf("%d\n",tot);
}

Program Input:

1. During execution, you will type two lines of input as described above (or you will use "redirection" to type that input for you. During testing, we will redirect input to retrieve two lines of input from an input file, so you may, of course, do the same thing during testing. If you wish to do so, here is the approximate method that we will use to redirect input during testing:
        name@isp.exe < input.txt > name@isp.exe.scr
   (we will use a similar method under Linux)
2. We will not throw "invalid input" at your program this month.
3. Your program should handle any combination of input that results in an output file of up to two megabytes.

Program Output:

1. Your output file should be stored in the default directory, the same directory that contains your executable program

2. Your output file should be named "output.txt"

3. Your output file should contain every possible unique anagram, in reverse alphabetical order, grouped as described above.

4. Answer groups should be comma-delimited
         ONE,TWO,THREE,FOUR,FIVE,etc.
   and new groups should start new lines

5. Your program should output the number of anagrams found to the video screen.

INPUT:

Test your program on these two lines of keyboard input:

MSOWORLD4
4

In other words, your program should create every possible 1, 2, 3 and 4 length anagram out of the string "MSOWORLD4" (those are both letter O's).

OUTPUT:

Every solution you find should be printed, in the specified order, to the "output.txt" file. Delimiters (commas and carriage returns (or CR/LF) should be used as described above.

The screen's display should be limited to one line of output, including the number of solutions you printed to the output file, and, if you wish, your time estimate for how long your program took to run. You may use any method of your choice to estimate program execution time. We ask that your time estimate be as accurate as you can estimate. To the nearest second should be fine. We will use a "start" and "stop" utility to time program execution more precisely.

Do not clear the screen during program execution. If we run your program three times, we want to see all three execution results on the screen at once.

Be very careful that your output matches the style established in these samples, because a computer program will be used to read and score your input files. You can study our sample output file if you are not sure how reverse alphabetical order works between numbers and letters.

RATINGS:

Entrant programs will be disqualified if:

• Program execution time exceeds sixty minutes (most programs should require much less)

• Output file is not grouped by length, shortest to longest, or if output of one length is not sorted in the stipulated order. (Try running the sample input and make sure you get the right output).

• If the output file exceeds two megabytes in size, or if it exceeds the size of most entrant's output files by 25% or more.

• The reason for these disqualifications is not really to disqualify those entries, but because these errors would typically put them at the bottom of the rankings and would not be displayed anyway.

A computer program of our design will count how many unique and valid answers are in the "output.txt" field on your entry form. It will deduct duplicate answers and invalid answers, if any, from that count, to arrive at the First Stage Ranking.

If your count does not agree with our count, we will declare this an error and deduct one answer from your First Stage Ranking. The most common reason for this error is to forget to use a variable with enough precision to handle the count.

This set of initial counts will be used to group all entrants into groups according to those First Stage Rankings.

Within those groups, entries will be differentiated by running the official final data through those programs, and counting their output as described above. Any remaining ties (entries with identical results in both first and second stage ratings) will be differentiated using the formula shown here:

Rating
= (Your programming time / fastest programming time)
+ (Your execution time / fastest execution time)
+ (Your program size / smallest program size)

NOTE: This month, we are calculating "program size" to be the size of your SOURCE CODE. You may, if you wish, submit two copies of your source code, one without comments, the other with comments. If you choose to submit two, the commented source may be pasted into the "Comments" box.

Additional note: Please make sure that your program releases all memory and resources back to the operating system when your program is done running.

[ Back to Top ]

Summary of Rules:
(The expanded "wordy" rules are posted on an extra page. Click here to read the full rules.)

Some rules are stipulated because it will allow the judging to proceed more smoothly.

Our intent is not to become sticklers. When possible, we will help you understand our requirements, or occasionally bend rules, if doing so would be more fair to everyone.

We reserve the right to change the rules up to the moment that each contest starts. No rule changes will be posted during the actual contest, but if an error in the rules becomes evident, we will change application of that rule in a way that is fair to all entrants.

1. A specific challenge will be described fully and posted here at the designated time, along with all information about how to enter the contest. More Information.
2. You must, from scratch, create a brand new program to solve the challenge using test data supplied by MSO. Preprogramming is not allowed. More Information.
3. Your program will be expected to run any valid data, subject to limits we designate. We will supply any required files, which should be stored on your computer in the same directory as the program to be run at execution time. More Information.
4. Your executable program name should be created from your e-mail address, as described on the entry form. More Information.
5. One entry per person. Entries must be received by the contest deadline as posted. Late entries will not be accepted. You may only submit entries under your own name. More Information.
6. Directions for submitting your executable program will be posted in the middle of the contest entry form. More Information.
7. If you make a minor mistake during entry, notify us immediately the contest address. Output errors will not be corrected. More Information.
8. Test your program on the test data, note the elapsed time for your program run, and enter all required information on the official entry form. Except as noted, your program should send all output to a file called "output.txt." More Information.
9. Each "line" of output should be followed by the standard "end of line" character sequence used by your operating system. If you have a choice, we prefer that you use the carriage return (decimal 013 = octal /015 = hex 0D) or click here for more discussion. If you use standard output commands, we should be able to handle it. More Information.
10. Your program must allow CTRL+BREAK or ALT+F4 (or similar method) to escape execution on demand. More Information.
11. Execution Time Limit = One hour, unless specified otherwise on contest page. More Information.
12. You must supply source and executable at time of entry. You agree that we may post your name, e-address, and source code to pages of our choice relating to this contest. More Information.
13. Programs should be written so that we can run your program at the DOS prompt or Linux Terminal prompt by typing the program name and redirection information as part of a "batch file" that runs three programs in a row. Do not clear the screen as part of your execution. More Information.
14. We recommend that you do not submit GUI (Visual) programs. More Information.
15. All executable programs must be able to run, as compiled and entered, on the official testing computer, which is a Pentium 450 mhz system that runs MS-Dos, Windows 98, and Red Hot Linux 6.1. More Information.
16. If the judges require it, you must be willing to run sample test data through the program on your machine.
17. We will make our best reasonable efforts to try to verify the program is as described and performs correctly. More Information.
18. We reserve the right to judge only those entries which calculate the right (or best) answer. More Information.
19. Entries which need to be differentiated, after counting answers on the final test, will be compared with the formula below, or with some similar formula which will be stated with the contest description. More Information.
20. The "rating" terms and numbers are explained here: More Information.
21. You can only win the cash prize once every six months, but we encourage past winners to enter every month. More Information.
22. We encourage entrants to share source code, ideas, and improvements with each other and with us, through the programming contest discussion mailing list. More Information.
23. Judge's interpretations of rules is final. If you wish to ask questions about the rules, please join the discussion mailing list and ask your question there. More Information.

Rating
= (Your programming time / fastest programming time)
+ (Your execution time / fastest execution time)
+ (Your program size / smallest program size)

(note: some months "program size" will be the size of the executable file, other months, it will be the size of the "source code". Each entry form and challenge description will make this clear.

[ Back to Top ]