Computer programming is an exercise in problem solving. As a programmer, you are presented with the challenge of creating a computerized solution. Using your logic and experience, you craft the solution, and when you're finished, there's a good degree of satisfaction exchanged for your effort. The programming process may even include a clever flash of insight, which is also rewarded with a feeling of accomplishment.

Within the programmer community, there exists an association of folks who take programming and problem-solving to a global level of organization. This is the world of contest programming.

Contest Programming

Contest programming is designed to sharpen programmers' problem-solving and coding skills in a competitive structure. Programmers can compete with others from all over the world to see how well they stack up to one another.

Contest problems can also be taken out of the competitive setting and used as a set of little coding puzzles, available to one and all. These little problems can be a great source of practice for learning a new coding language or for acquiring additional problem-solving skills.

In either case, contest programming consists of problems that are to be solved with a computer, the solution source code that will produce the solution, and a judge that decides whether the solution is correct. A solution is considered to be correct if it produces the correct output. Beyond some loose performance restrictions (your program must run in less than one minute, for instance,) there is no consideration for coding practices. That is, there are no style points in contest programming.

Problem Solving

To the iSeries professional operating within a business environment, "problem solving" usually takes the form of, for example, a call from Debbie in AP: "Hi. How's the family? (No pause.) I've just printed 300 checks on check stock for an account that was closed four months ago. Can you help me? (Now, a pause.) Roll something back, maybe, like last time? Lemme know by 3:00? Soccer night. Thanks."

Well, problem solving can also mean the act of creating a computer solution to a sort of contrived programming challenge. The value in such an enterprise is an increase in logic and coding abilities, plus an exposure to new data structures and programming techniques.

Take, for example, the famous "traveling salesman" problem. That is, what is the shortest route a traveling salesman can take to visit each city in his territory once and then return home? Well, as you would expect, the answer to this problem has been worked out. The solution is also famous and is known as Dijkstra's Shortest Path Algorithm. But still the challenge remains of turning something like Dijkstra's Algorithm into actual working code.

Note that it is not uncommon for some employers (Microsoft among them) to focus on an employment candidate's problem-solving skills when being considered for hire. Many organizations use the contest problems as a test of these skills. Such a test shows how well and how fast you can code.

University Programming Contests

Contest programming has been used within colleges and universities for a long time to teach and recognize good problem-solving skills. The contests range from small internal events where students within a given school compete with each other to large state, regional, and national trials.

Here's how a typical programming contest works within the computer science departments of many universities. Teams of two to four programmers are given five hours to solve as many short, yet challenging, programming problems as they can. Teams are given a list of programming problems as the clock is started. Each problem may be solved with a short C, C++, or Java program, but the solution requires some degree of coding dexterity. Once a solution has been created, the code is submitted to a judge. The judge runs the program against a robust set of test data to expose any flaw in the solution. If the solution is correct, the team scores a point, and the number of minutes since the beginning of the contest is noted and accumulated. At the end of the five hours, the team that has solved the most problems wins. If more than one team has the same number of solved problems, the total minutes taken determines the winner. The fewer minutes taken to solve the problems, the better.

Contestants may bring printed reference materials to the contest, but electronic media and Internet access are not allowed. (Note that the current trend may change to disallow printed reference material as well.)

What a Contest Problem Looks Like

A typical contest problem resembles this popular example, called the "Crypt Kicker II". (The term "crypt" refers to encryption.) This example by Miguel Revilla is from the Universidad de Valladolid contest Web site.

Crypt Kicker II

A common but insecure method of encrypting text is to permute the letters of the alphabet. That is, in the text, each letter of the alphabet is consistently replaced by some other letter. So as to ensure that the encryption is reversible, no two letters are replaced by the same letter.

A common method of cryptanalysis is the known plaintext attack. In a known plaintext attack, the cryptanalist manages to have a known phrase or sentence encrypted by the enemy, and by observing the encrypted text then deduces the method of encoding.
 

Your task is to decrypt several encrypted lines of text, assuming that each line uses the same set of replacements, and that one of the lines of input is the encrypted form of the plain text

the quick brown fox jumps over the lazy dog

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The input consists of several lines of input. Each line is encrypted as described above. The encrypted lines contain only lower case letters and spaces and do not exceed 80 characters in length. There are at most 100 input lines.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

Decrypt each line and print it to standard output. If there is more than one possible decryption (several lines can be decoded to the key sentence), use the first line found for decoding.

If decryption is impossible, output a single line:
No solution.

Sample Input

1

vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq

Sample Output

now is the time for all good men to come to the aid of the party
the quick brown fox jumps over the lazy dog
programming contests are fun arent they

This example problem is a text-handling puzzle. Other problems focus on other coding challenges like array handling, algorithmic manipulations, or programming concepts such as recursion. In any type of problem, the exact output as described in the problem must be provided by your solution program.

The Solution

The solution to the above problem will take the form of a small Java, C++, or C program (or sometimes Pascal) consisting of a single source file. The program will accept the input from standard in and send the output to standard out. Nothing more and nothing less. Absolutely nothing.

If you're coding in Java, you may use all the tools found in the Java SDK. For example, you may use the Java language function Math.sqrt to get the square root of a number. If you're coding in C/C++, you may use all the functions in the standard libraries.

Universidad de Valladolid

At Spain's Universidad de Valladolid (or UVa) beats the heart of the contest programming scene. As Rochester is to the iSeries, Valladolid is to contest programming (Figure 1).

Figure 1: The Universidad de Valladolid Web site is the center of the contest programming world. (Click image to enlarge.)

In this well-supported Web site is a collection of established problems and an online judging process. The UVa maintains a database of contest problem participants, the problems attempted, and the results. Anyone can join and participate in this free service sponsored by the Association of Computing Machinery (ACM). If you're a programming puzzle enthusiast or if you're trying to hone your instruction-following and problem-solving skills, this is for you.

Part of the UVa Web site for contest programming is the online judge. The online judge is really a program, not a person. Once you've attempted to solve a problem, you submit your program source code to the online judge. The judge first tries to compile your code. If your code compiles, the judge launches your program and feeds it the test data (note that the judge's test data is much more exhaustive than the example input shown in the problem instructions).

Once the judging is complete, the results are made available to you. If your program was found to be unacceptable (and believe me, this can happen even when you're absolutely sure it's correct), you are given a hint as to the nature of the flaw. For example, the return value from the online judge could be CE for compiler error, WA for wrong answer, or TL for time limit exceeded. You then fix the problem and submit it again. Typically, multiple submissions will be required before you've thought of everything and finally pass. See the UVa Web site for more information.

The Programming Challenges Book and Web Site

If you're interested in participating, you may do well to look into the book Programming Challenges by Steven S. Skiena and Miguel A. Revilla. This book is dedicated to contest programming participants and contains very valuable instructions and tips, together with over 100 of the best programming problems from UVa. Also included are discussions of the various programming techniques typically used to solve these types of problems (graph traversal, backtracking, number theory, recursion, etc.). Please see the Programming Challenges Web site.

TopCoder Web Site

Another resource for contest problems deserves mention: the TopCoder Web site. TopCoder is a contest problem Web site where the best programmers from around the world are tracked and ranked. These sponsored competitions are handled in a variety of ways. Some are directed at collegiate level programmers, some are sponsored by organizations (like Sun Microsystems), and then there are the ones by special invitation only for the coding elite. This site is for true red-meat programmers only.

Some of the sharpest programmers in the world participate in contest programming, and you might be surprised at how they stack up. Take a look at the world rankings sometime. You have to go quite a way down the list before finding the first entry from the United States. As of this writing, a young man from Poland with the handle "Tomek" is the world's best contest programmer. Tomek has earned over $50,000 in coding competitions.

Chris Peters has 26 years of experience in the IBM midrange and PC platforms. Chris is president of Evergreen Interactive Systems, a software development firm and creators of the iSeries Report Downloader. Chris is the author of The OS/400 and Microsoft Office 2000 Integration Handbook, The AS/400 TCP/IP Handbook, AS/400 Client/Server Programming with Visual Basic, and Peer Networking on the AS/400 (MC Press). He is also a nationally recognized seminar instructor. Chris can be reached at This email address is being protected from spambots. You need JavaScript enabled to view it..